LeetCode41-50

41、缺失的第一个正数

数组中元素互换，让元素大小与下标相对应。数值小于0或者大于数组长度的元素值，直接略过，之后遍历整个数组，第一次出现数值和下标不相等的位置就是ans，如果全部满足，返回数组长度即可。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        nums.push_back(-1);  // 添加一个无用元素，方便后续操作
        for(int i=0; i<nums.size(); i++){
            if( nums[i]<0 || nums[i]>=nums.size() || nums[nums[i]]==nums[i] )
                continue;
            swap(nums[nums[i]], nums[i]);
            i--;
        }
        for(int i=1; i<nums.size(); i++){ // i 从 1 开始，保证正整数
            if( nums[i]!=i )
                return i;
        }
        return nums.size();
    }
};

42、接雨水

先找到全局最高的那个柱子，然后从两边往最高柱靠近，靠近过程中不断更新当前最高柱，并根据当前最高柱的值来计算当前遍历点能够接雨水的量。

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()==0)
            return 0;
        int ans = 0;
        int max_index = 0;
        for(int i=1; i<height.size(); i++){
            if( height[max_index]<height[i] )
                max_index = i;
        }
        int cur_max = height[0];
        for(int i=1; i<max_index; i++){
            if( height[i]>=cur_max ){
                cur_max = height[i];
                continue;
            }
            ans += cur_max - height[i];
        }
        cur_max = height[height.size()-1];
        for(int i=height.size()-2; i>max_index; i--){
            if( height[i]>=cur_max ){
                cur_max = height[i];
                continue;
            }
            ans += cur_max - height[i];
        }
        return ans;
    }
};

43、字符串相乘

模拟题，使用字符串模拟乘法运算即可。

class Solution {
public:
    string multiply(string num1, string num2) {
        string ans, cur_multi;
        int multiplier, product_step;
        for(int i=num2.size()-1; i>=0; i--){
            cur_multi = num1;
            multiplier = num2[i] - '0';
            product_step = 0;
            for(int j=cur_multi.size()-1; j>=0; j--){
                product_step += (cur_multi[j]-'0')*multiplier;
                cur_multi[j] = product_step%10 + '0';
                product_step /= 10;
            }
            if(product_step)
                cur_multi.insert(cur_multi.begin(), product_step+'0');
            for(int j=0; j<num2.size()-1-i; j++)
                cur_multi += "0";
            // 计算 cur_multi + ans
            int m=0, n=0, sum=0;
            for(m=ans.size()-1, n=cur_multi.size()-1; m>=0&&n>=0; m--,n--){
                sum += (ans[m]-'0') + (cur_multi[n]-'0');
                ans[m] = sum%10 + '0';
                sum /= 10;
            }
            while(m>=0){
                sum += (ans[m]-'0');
                ans[m] = sum%10 + '0';
                sum /= 10;
                m--;
            }
            while(n>=0){
                sum += (cur_multi[n]-'0');
                ans.insert(ans.begin(), sum%10+'0');
                sum /= 10;
                n--;
            }
            if(sum)
                ans.insert(ans.begin(), sum+'0');
        }
        while(ans.size()>0 && ans[0]=='0')  //过滤前导 0 
            ans.erase(ans.begin());
        return ans.size()==0? "0" : ans;
    }
};

44、通配符匹配

dp 题，写出状态转移方程即可。根据 * 号考虑各种情况。

class Solution {
public:
    bool isMatch(string s, string p) {
        int lenS = s.length(), lenP = p.length();
        bool match[lenS+1][lenP+1] = {true};
        for(int i=1; i<=lenS; i++)
            match[i][0] = false;
        for(int i=1; i<=lenP; i++)
            match[0][i] = p[i-1]=='*' && match[0][i-1];
        for(int i=1; i<=lenS; i++){
            for(int j=1; j<=lenP; j++){
                if( p[j-1]=='*' )
                    match[i][j] = match[i][j-1] || match[i-1][j];   //匹配 0 个或多个
                else
                    match[i][j] = (s[i-1]==p[j-1] || p[j-1]=='?') && match[i-1][j-1];
            }
        }
        return match[lenS][lenP];
    }
};

45、跳跃游戏 II

贪心题，每次选择下次跳的最远的位置。

class Solution {
public:
    int jump(vector<int>& nums) {
        int pos = 0, ans = 0;
        while(pos < nums.size()-1){
            int max_step = -1, max_index = -1;
            for(int i=1; i<=nums[pos]; i++){
                if(pos+i==nums.size()-1)
                    return ans+1;
                if(max_step <= i+nums[pos+i]){
                    max_step = i + nums[pos+i];
                    max_index = i;
                }
            }
            ans++;
            pos = pos + max_index;
            //cout << max_index << " " << pos << endl;
        }
        return ans;
    }
};

46、全排列

直接上 next_permutation 库函数。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector< vector<int> > ans;
        sort(nums.begin(), nums.end());
        do{
            ans.push_back(nums);
        }while(next_permutation(nums.begin(), nums.end()));
        return ans;
    }
};

47、全排列 II

之所以出现重复是因为相同的元素的排列导致的，DFS 实现全排列并去重。

class Solution {
public:
    vector< vector<int> > ans;
    void DFS(vector<int>& nums, vector<bool>& book, vector<int>& temp_ans){
        if(nums.size() == temp_ans.size()){
            ans.push_back(temp_ans);
            return ;
        }
        for(int i=0; i<nums.size(); i++){
            if(book[i]==true) continue;
            if(i>0 && nums[i-1]==nums[i] && book[i-1]==false) continue;
            book[i] = true;
            temp_ans.push_back(nums[i]);
            DFS(nums, book, temp_ans);
            temp_ans.pop_back();
            book[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> book(nums.size(), false);
        vector<int> temp_ans;
        DFS(nums, book, temp_ans);
        return ans;
    }
};

48、旋转图像

模拟题，计算好对应的位置即可。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int len = matrix[0].size();
        for(int row=0; row<len/2; row++){
            for(int col=row; col<len-1-row; col++){
                int tmp_val = matrix[row][col];

                int row1 = row, col1 = col;
                matrix[row1][col1] = matrix[len-1-col1][row1];

                int row2 = len-1-col1, col2 = row1;
                matrix[row2][col2] = matrix[len-1-col2][row2];

                int row3 = len-1-col2, col3 = row2;
                matrix[row3][col3] = matrix[len-1-col3][row3];

                int row4 = len-1-col3, col4 = row3;
                matrix[row4][col4] = tmp_val;
            }
        }
    }
};

49、字母异位词分组

水题，直接用 map 或者 sort 后使用 vector都可以。

class Solution {
public:
    static bool compare(string s1, string s2){
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        return s1 < s2;
    }
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<string> tmp_ans;
        vector< vector<string> > ans;
        sort(strs.begin(), strs.end(), compare);
        for(auto str : strs){
            if(tmp_ans.size()==0){
                tmp_ans.push_back(str);
                continue;
            }
            string s1 = tmp_ans.back();
            string s2 = str;
            sort(s1.begin(), s1.end());
            sort(s2.begin(), s2.end());
            if( s1!=s2 ){
                ans.push_back(tmp_ans);
                tmp_ans.clear();
                tmp_ans.push_back(str);
            }
            else
                tmp_ans.push_back(str);
        }
        if(tmp_ans.size()>=1)
            ans.push_back(tmp_ans);
        return ans;
    }
};

50、Pow(x, n)

快速幂

class Solution {
public:
    double myPow(double x, int n) {
        int flag = n>=0? 1 : -1;
        long long N = (long long)(flag)*(long long)(n);
        double ans = 1;
        while(N){
            if(N%2)
                ans *= x;
            x *= x;
            N /= 2;
        }
        return flag==-1? 1.0/ans : ans;
    }
};