leetcode解题思路分析（三十六）299 - 305题

约定不等于承诺〃 2022-11-24 14:10 134阅读 0赞

1.  猜数字游戏  
    **需要遍历两次，优化在于第二次和第一次有关联：哈希表中存储的会包括第一次的**

class Solution { 
    public:
        string getHint(string secret, string guess) { 
            int x = 0, y = 0;
            string ret;
            unordered_map<char, int> map;
            for (int i = 0; i < guess.size(); i++)
            { 
                 if (secret[i] == guess[i])
                { 
                    x++;
                } 
                else
                { 
                    if (map[secret[i]] > 0) 
                        map[secret[i]]++;
                    else 
                        map[secret[i]] = 1;       
                }                    
            }
    
            for (int i = 0; i < guess.size(); i++)
            { 
                if (map[guess[i]] > 0 && secret[i] != guess[i])
                { 
                    map[guess[i]]--;
                    y++;
                }
            }
    
            ret += to_string(x);
            ret += 'A';
            ret += to_string(y);
            ret += 'B';
    
            return ret;
        }
    };

1.  最长上升子序列  
    给定一个无序的整数数组，找到其中最长上升子序列的长度。

**用动态规划易解，比较前面的dp取最大值+1既可。但是动态规划需要每次重复遍历之前每个位置找寻最大值，更优的做法是采用贪心算法求解。核心思想可以概括为：尽可能维持一个最小的尾数，这样可以尽可能多的再叠加新的数组成更长的子序列。因此每次可以不需要遍历前面所有的位置，而是遍历该子序列记录数组本身，替换大于新元素的旧元素。由于子序列已排序，因此可以用二分法求解，从而优化了时间复杂度。**

class Solution { 
    public:
        int lengthOfLIS(vector<int>& nums) { 
            int size = nums.size();
            if (size == 0) return 0;
            vector<int> dp(size, 0);
            int max = 1, dpMax;
            dp[0] = 1;
            for (int i = 1; i < size; i++)
            { 
                dpMax = 1;
                for (int j = 0; j < i; j++)
                { 
                    if (nums[i] > nums[j])
                    { 
                        if (dp[j] + 1 > dpMax)
                        { 
                            dpMax = dp[j] + 1;
                        }
                    }
                }
                dp[i] = dpMax;
                if (dpMax > max)
                    max = dpMax;
            }
            return max;
        }
    };

class Solution { 
    public:
        int lengthOfLIS(vector<int> &nums) { 
            int len = nums.size();
            if (len < 2) { 
                return len;
            }
    
            vector<int> tail;
            tail.push_back(nums[0]);
            // tail 结尾的那个索引
            int end = 0;
    
            for (int i = 1; i < len; ++i) 
            { 
                if (nums[i] > tail[end]) 
                { 
                    tail.push_back(nums[i]);
                    end++;
                } 
                else 
                { 
                    int left = 0;
                    int right = end;
                    while (left < right) 
                    { 
                        int mid = (left + right) >> 1;
                        if (tail[mid] < nums[i]) 
                        { 
                            left = mid + 1;
                        } 
                        else 
                        { 
                            right = mid;
                        }
                    }
                    tail[left] = nums[i];
                }
            }
            return end + 1;
        }
    };

1.  删除无效的括号  
    删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。

**经典的回溯法解题。将判断字符串有效的过程放到深度遍历过程中，一旦当前得到的结果字符串无效，提前终止。具体实现是，记录当前结果字符串中错误的 ‘(’ 和 ‘)’ 的数量 cntl 和 cntr，如果遍历过程中出现 cntr > cntl，则当前结果字符串无效，提前终止**

class Solution { 
    public:
        unordered_set<string> sets;
    
        /* * @param s: 源字符串 * @param index: 当前源字符串索引 * @param str: 记录结果 * @param el: 当前可以删除的'('的数量 * @param er: 当前可以删除的')'的数量 * @param cntl: 记录当前str中错误的'('的数量 * @param cntr: 记录当前str中错误的')'的数量 */
        void dfs(string &s, int index, string &str, int el, int er, int cntl, int cntr){ 
            // 剪枝
            if(cntr > cntl || el < 0 || er < 0) return;
            // 结束条件
            if(index == s.length()){ 
                if(cntl == 0 && cntr == 0){ 
                    sets.insert(str);
                }
                return;
            }
    
            // 当前字符不是括号，直接跳过
            if(s[index] != '(' && s[index] != ')'){ 
                str += s[index];
                dfs(s, index+1, str, el, er, cntl, cntr);
                str.erase(str.length()-1, 1);
            }else{ 
                // 不删除当前括号，需要记录当前str中错误的左右括号的数量
                str += s[index];
                int cl = cntl, cr = cntr;
                if(s[index] == '(') cl++;
                else{ 
                    if(cl == 0) cr++;
                    else cl--;
                }
                dfs(s, index+1, str, el, er, cl, cr);
                str.erase(str.length()-1, 1);
    
                // 删除当前括号，修改可删除的左右括号数量
                if(s[index] == '(') --el;
                else --er;
                dfs(s, index+1, str, el, er, cntl, cntr);
            }
        }
    
        vector<string> removeInvalidParentheses(string s) { 
            vector<string> res;
    
            // 统计源字符串中无效括号数目
            int el = 0, er = 0;
            for(int i = 0; i < s.length(); ++i){ 
                if(s[i] == '(') el++;
                else if(s[i] == ')'){ 
                    if(el == 0) er++;
                    else el--;
                }
            }
    
            string str = "";
            dfs(s, 0, str, el, er, 0, 0);
    
            for(auto it = sets.begin(); it != sets.end(); ++it){ 
                res.push_back(*it);
            }
    
            return res;
        }
    };

1.  区域和检索  
    给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

**很简单的一道题，提前存储好累加变量，然后相减即可**

class NumArray { 
    public:
        NumArray(vector<int>& nums) { 
    
            int sum = 0;
            for (int i = 0; i < nums.size(); ++i)
            { 
                sum += nums.at(i);
                m_map[i] = sum;
            }
        }
    
        int sumRange(int i, int j) { 
    
            return m_map[j] - m_map[i - 1]; // i == 0 key为-1不存在，会自动插入pair(-1, 0)
        }
    
    
    private:
        unordered_map<int, int> m_map; //<索引，0到索引的元素和>
    
    };

1.  二维区域和检索  
    给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2)。

**本题本质上和上题是一样的：缓存四个定点到0,0的面积，然后相减即可**

class NumMatrix { 
    public:
        NumMatrix(vector<vector<int>>& matrix) { 
            rw = matrix.size();
            cl = rw ?  matrix[0].size() : 0;
            sumMatrix = vector<vector<int>>(rw + 1, vector<int> (cl + 1, 0));
            for (int i = 1; i < rw + 1; ++i){ 
                for (int j = 1; j < cl + 1; ++j){ 
                    sumMatrix[i][j] = matrix[i - 1][j - 1] + 
                    sumMatrix[i - 1][j] + sumMatrix[i][j - 1] - sumMatrix[i - 1][j - 1];
                }
            }
        }
        
        int sumRegion(int row1, int col1, int row2, int col2) {         
            return sumMatrix[row2 + 1][col2 + 1] - sumMatrix[row1][col2 + 1] - sumMatrix[row2 + 1][col1] + sumMatrix[row1][col1];
        }
    private:
        int rw, cl;
        vector<vector<int>> sumMatrix;
    };
    
    /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix* obj = new NumMatrix(matrix); * int param_1 = obj->sumRegion(row1,col1,row2,col2); */

1.  累加数  
    累加数是一个字符串，组成它的数字可以形成累加序列。  
    一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。  
    给定一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。

\*\*本题是典型的回溯思想，遍历长度只需要一半：再长的话组成的第一个数就无法得到和第二个数的和了，不够长。 \*\*

class Solution { 
    public:
        bool isAdditiveNumber(string num) { 
            int len = num.size();
            for(int i = 1; i <= len/2; i++){ 
                // 为了排除“0235813”
                if(i>1 && num[0]=='0')
                    break;
                for(int j = 1; j + i < len;j++){ 
                    // 这里需要排除第二个数以0开头的情况，dfs里面不需要判断，因为加完的数开始肯定没有0，如果字符串里面有那么找到的位置也不是index3 + len3
                    if(!(j>1 && num[i]=='0') && dfs(num,0,i,stol(num.substr(0,i)),i,j,stol(num.substr(i,j)),len))
                        return true;
                }
            }
            return false;
        }
    // 当前要加的两个数的索引和长度
        bool dfs(string& num, int index2,int len2,long num2,int index3,int len3,long num3, int &len){ 
            // 如果第二个数的索引加上他的长度就等于num的长度，就说明到末尾了，返回true
            if(index3 + len3 == len)
                return true;
            long sum = num2 + num3;
            string sSum = to_string(sum);
            // 将两个数加起来，在剩下的字符串中去寻找这个和，如果在开始的位置就找到，就说明可以继续下去
            if(num.find(sSum,index3+len3)!=index3+len3)
                return false;
            return dfs(num,index3,len3,num3,index3+len3,sSum.size(),sum,len);
        }
    
    };