【每日编程-443期】Leetcode.997.有序数组的平方
样例一：
输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]
样例二：
输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。
解决方法：
（1）算法的基本思想：
暴力解法：将原来数组的每个数先平方，然后调用sort函数即可。
但是题目给了有序数组，如果将这个条件用上。
按照快排的思想，双向指针的思想解：
定义与A数组等长的空数组B，遍历A数组，因为是非递减数组，left指向前端，right指向尾端，如果left指向的元素的绝对值大于right指向的元素，则将该元素的平方加在B数组的尾部，否则将right指向的元素的平方加在B数组的尾部，直到A遍历结束。
（2）代码实现：
//不太厚道的解法
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
for(int i = 0;i<A.size();i++){
A[i] = A[i]*A[i];
}
sort(A.begin(),A.end());
return A;
}
};
//快排_双向指针思想
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int left = 0;
int right = A.size()-1;
vector<int> B(A.size());
for(int i = A.size() - 1; i >=0; i--) {
if(abs(A[left]) > abs(A[right])) {
B[i] = A[left] * A[left];
left++;
} else {
B[i] = A[right] * A[right];
right--;
}
}
return B;
}
};
给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。
返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：
如果 S[i] == "I"，那么 A[i] < A[i+1]
如果 S[i] == "D"，那么 A[i] > A[i+1]
样例一：
输入："IDID"
输出：[0,4,1,3,2]
样例二：
输入："III"
输出：[0,1,2,3]
样例三：
输入："DDI"
输出：[3,2,2,3]
class Solution {
public:
vector<int> diStringMatch(string S) {
}
};