leetcode day19 844+977

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都大于等于0
        if(i>=0&&j>=0){
            if(s[i]!=t[j])return false;
        }else{
            //i,j只有一个大于等于0
           if(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;
}