leetcode-2

[88] 合并两个有序数组

利用已经排序的特性，取出两组数组中的最小值，然后进行排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int len=m+n;
    int res[len];
    int p1=0,p2=0;
    int cur;
    while(p1<m||p2<n){
        if(p1==m){
            cur=nums2[p2++];
        } else if(p2==n){
            cur=nums1[p1++];
        }else if(nums1[p1]<nums2[p2]){
            cur=nums1[p1++];
        }else{
            cur=nums2[p2++];
        }
        res[p1+p2-1]=cur;
        
    }
    for(int i=0;i<len;i++){
        nums1[i]=res[i];
    }
}

最优：题目中有一个条件：数组1的长度等于数组1和数组2的非零整数和，运用逆向双指针，数组后部分为0的特性。总共会用到三个指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int p1 = m - 1, p2 = n - 1;
    int tail = m + n - 1;
    int cur;
    while (p1 >= 0 || p2 >= 0) {
        if (p1 == -1) {
            cur = nums2[p2--];
        } else if (p2 == -1) {
            cur = nums1[p1--];
        } else if (nums1[p1] > nums2[p2]) {
            cur = nums1[p1--];
        } else {
            cur = nums2[p2--];
        }
        nums1[tail--] = cur;
    }
}

[27] 移除元素

两个指针，一个指针去找数组的值是否等于指定值，另一个指针指向该数组最后输出的数组顺序位

1
2
3
4
5
6
7
8
9
10
11
12

int removeElement(vector<int>& nums, int val) {
    int n =nums.size();
    int left=0;
    for(int right=0;right<n;right++){
        if(nums[right]!=val){
            nums[left]=nums[right];
            left++;
        }
    }
    return left;
}

最优：两个指针一个指向开头，另一个指向结尾.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int removeElement(vector<int>& nums, int val) {
    int right =nums.size();
    int left=0;
    while(left<right){
        if(nums[left]==val){
            nums[left]=nums[right-1];
            right--;
        }else{
            left++;
        }
    }
    return left;
}

[26]删除有序数组中的重复项

两个指针，一个指针去找数组中的值是否与之前的值重复，另一个指针指向该数组最后输出的数组，按顺序找，即可保证顺序一致

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int removeDuplicates(vector<int>& nums) {
    int slow =1;
    int fast =1;
    int n=nums.size();
    if(n==0){
        return 0;
    }

    while(fast<n){
        if(nums[fast]!=nums[fast-1]){
            nums[slow]=nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

[125] 验证回文串

先转换成小写字母，头尾指针两个方向判断，当指针相遇，则返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

bool isPalindrome(string s) {
    string sgood;
    for(auto i:s){
        if(isalnum(i)){
            sgood+=tolower(i);
        }
    }
    int left =0;
    int right=sgood.size()-1;
    while(left<right){
        if(sgood[left]!=sgood[right])
        {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

[209] 长度最小的子数组

两个循环求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int minSubArrayLen(int target, vector<int>& nums) {
    int n=nums.size();
    if(n==0){
        return 0;
    }
    int ans=INT_MAX;
    for(int i =0;i<n;i++){
        int sum=0;
        for(int j =i;j<n;j++){
            sum+=nums[j];
            if(sum>=target){
                ans=min(ans,j-i+1);
                break;
            }
        }
        
    }
    return ans==INT_MAX?0:ans;
}

最优: 滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int minSubArrayLen(int target, vector<int>& nums) {
    int n=nums.size();
    if(n==0){
        return 0;
    }
    int ans=INT_MAX;
    int start =0,end=0;
    int sum=0;
    while(end<n){
        sum +=nums[end];
        while(sum>=target){
            ans=min(ans,end-start+1);
            sum-=nums[start];
            start++;
        }
        end++;
    }
    return ans ==INT_MAX?0:ans;
}

注意，子数组是位置不改变的数组，而不是直接从数组中挑选几个满足条件的数