0511刷题

0511刷题

贪心算法：

class Solution {
public:
    bool increasingTriplet(vector& nums) {
        int a = INT_MAX, b = INT_MAX;
        for(int x: nums)
            if(x <= a) a = x;
            else if(x <= b) b = x;
            else return true;
        return false;
    }
};

赋初始值的时候，已经满足second > first了，现在找第三个数third

(1) 如果third比second大，那就是找到了，直接返回true

(2) 如果third比second小，但是比first大，那就把second的值设为third，然后继续遍历找third

(3) 如果third比first还小，那就把first的值设为third，然后继续遍历找third（这样的话first会跑到second的后边，但是不要紧，因为在second的前边，老first还是满足的）

官方解答：

class Solution {
public:
    bool increasingTriplet(vector& nums) {
        int n = nums.size();
        if (n < 3) {
            return false;
        }
        int first = nums[0], second = INT_MAX;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (num > second) {
                return true;
            } else if (num > first) {
                second = num;
            } else {
                first = num;
            }
        }
        return false;
    }
};

1.双指针法：

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> result;

        sort(nums.begin(),nums.end());
        for(int i=0;i0&&nums[i]==nums[i-1]) continue;

            int left=i+1;
            int right=nums.size()-1;

            while(left0)
                {
                    right--;
                    while(left{nums[i],nums[left],nums[right]});
                    while(left 
2.哈希：
 
class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> result;
        sort(nums.begin(),nums.end());//-4 -1 -1 0 1 2
        for(int i=0;i
            if(nums[i]>0) break;
            if(i>0&&nums[i]==nums[i-1]) continue;//三元组元素a去重
            
            unordered_set set;
            for(int j=i+1;j
                if(j>i+2&&nums[j]==nums[j-1]&&nums[j-1]==nums[j-2]) continue;// 三元组元素b去重

                int tmp=0-(nums[i]+nums[j]);
                if(set.find(tmp)!=set.end())
                {
                    result.push_back({nums[i],nums[j],tmp});
                    set.erase(tmp);// 三元组元素c去重
                }
                else
                {
                    set.insert(nums[j]);
                }
            }
        }
        return result;
    }
};
 
注意
 
if(j>i+2&&nums[j]==nums[j-1]&&nums[j-1]==nums[j-2]) continue;// 三元组元素b去重
 
这个不是很明白。
 
LeetCode 541. 反转字符串 II 
LeetCode 541. 反转字符串 II 
class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) 
        {
            // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= s.size()) 
            {
                reverse(s.begin() + i, s.begin() + i + k );
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
            reverse(s.begin() + i, s.end());
        }
        return s;
    }
};
 
debug解法，还未debug：
 
class Solution {
public:
    string reverseStr(string s, int k) {
        int count=1;
        string result="";
        string str="";
        for(int i=0;i
            if(count<=2*k) 
            {
                count++;
                str+=s[i];
                if(i==s.size()-1)
                {
                    if(str.size()
                        //如果剩余字符少于 k 个，则将剩余字符全部反转。
                        string newString1=str;
                        int left=0;
                        int right=newString1.size()-1;
                        while(left
                            char tmp=newString1[left];
                            newString1[left]=newString1[right];
                            newString1[right]=tmp;
                            left++;
                            right--;
                        }
                        result+=newString1;
                    }
                    else 
                    {
                        //如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
                        string newString2="";
                        for(int i=0;i
                            newString2+=str[i];
                        }
                        int left=0;
                        int right=k-1;
                        while(left
                            char tmp=newString2[left];
                            newString2[left]=newString2[right];
                            newString2[right]=tmp;
                            left++;
                            right--;
                        }
                        for(int i=k;i
                            newString2+=str[i];
                        }
                        result+=newString2;
                    }
                }
            }
            else if(count>2*k)
            {
                //反转这 2k 字符中的前 k 个字符。
                string newString3="";
                for(int i=0;i
                    newString3+=str[i];
                }
                int left=0;
                int right=k-1;
                while(left
                    char tmp=newString3[left];
                    newString3[left]=newString3[right];
                    newString3[right]=tmp;
                    left++;
                    right--;
                }
                for(int i=k;i
                    newString3+=str[i];
                }
                result+=newString3;
                count=1;
                str="";
                newString3="";
            } 
        }
        return result;
    }
    
};