844 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c" 输出：true 解释：s 和 t 都会变成 "ac"。
示例 2：
输入：s = "ab##", t = "c#d#" 输出：true 解释：s 和 t 都会变成 ""。
示例 3：
输入：s = "a#c", t = "b" 输出：false 解释：s 会变成 "c"，但 t 仍然是 "b"。
解题思路：双指针法，i和j分别为字符串进行匹配的位置，初始值为字符串末尾。
cnt1为#的数量，从后开始遍历是因为前面的字符不会影响后面的。分情况讨论
（1）如果s[i]=#,cnt1++，i--
（2）如果cnt1>0，说明该字符的后面有#，该字符要删掉，i--,cnt1--
（3）其他情况，break。i即为要进行匹配字符的位置
字符串t同理
到达i,j后进行字符匹配
（1）如果i,j都大于0，s[i]!=t[j],return false
（2）i,j不同时大于0
(i)i,j只有一个大于等于0，一个小于0，return false（说明一个字符串已经匹配到开头，另一个还没匹配到开头）
(ii)i,j都小于0，说明两个字符串都匹配完了，这个可以和最后的return true合并
bool backspaceCompare(char* s, char* t) {int cnt1=0,cnt2=0,i,j;//cnt1为#个数for(i=strlen(s)-1,j=strlen(t)-1;i>=0||j>=0;i--,j--){//找到s字符串第一个要匹配的字符while(i>=0){if(s[i]=='#'){cnt1++;i--;}else if(cnt1>0){cnt1--;i--;}else break;}while(j>=0){if(t[j]=='#'){cnt2++;j--;}else if(cnt2>0){cnt2--;j--;}else break;}//匹配情况 i,j都大于等于0if(i>=0&&j>=0){if(s[i]!=t[j])return false;}else{//i,j只有一个大于等于0if(i>=0||j>=0) return false;if(i<0&&j<0)return true;}}return true;
}977 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]
解题思路：
方法一：双指针，找出正负数的分界线split，正数平方按非递减顺序顺序，负数相反。
负数[0,split],负数[split+1,numsSize]，split初始值为-1,
双指针i，j。i为最后一个负数位置，j为第一个正数位置
归并排序，分配一个新的数组空间a
(1)全为正数，i=-1小于0，j=0,从j小的开始填, a[(*returnSize)++]=nums[j]*nums[j],j++
(2)全为负数，i=numsSize-1,j=numsSize,从i小的开始填中， a[(*returnSize)++]=nums[i]*nums[i],i--
比较nums[i]*nums[i]与nums[j]*nums[j]的大小
(3)nums[i]*nums[i]<nums[j]*nums[j]，填入较小的i,i--
(4)nums[i]*nums[i]>nums[j]*nums[j]，填入较小的j,j++
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* sortedSquares(int* nums, int numsSize, int* returnSize) {int split=-1;//正负数分界线,split为最后一个负数所在位置for(int i=0;i<numsSize;i++){if(nums[i]<0)split=i;else break;}//分配数组内存空间int *a=malloc(sizeof(int)*numsSize);*returnSize=0;int i=split,j=split+1;//i为最后一个负数位置，j为第一个正数位置while(i>=0||j<numsSize){//全是正数,j=0，升序if(i<0){a[(*returnSize)++]=nums[j]*nums[j];j++;}else if(i==numsSize-1){//全是负数,降序a[(*returnSize)++]=nums[i]*nums[i];i--;}else if(nums[i]*nums[i]<nums[j]*nums[j]){a[(*returnSize)++]=nums[i]*nums[i];i--;}else{a[(*returnSize)++]=nums[j]*nums[j];j++;}}return a;
}方法二：双指针法，如果正负数都包含，那么最大平方必定在两边，即0或n-1的位置
双指针i,j分别指向数组边界位置，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。证明逆序，loc初始值设为n-1即可，每次循环loc--
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* sortedSquares(int* nums, int numsSize, int* returnSize) {int *a=malloc(sizeof(int)*numsSize);*returnSize=numsSize;int loc=numsSize-1;//从大的开始填for(int i=0,j=numsSize-1;i<=j;loc--){if(nums[i]*nums[i]>nums[j]*nums[j]){a[loc]=nums[i]*nums[i];i++;}else{a[loc]=nums[j]*nums[j];j--;}}return a;
}
