C++ : 力扣_Top(62-84)

C++ : 力扣_Top(62-84)

---

62、不同路径（中等）

一个机器人位于一个 m x n 网格的左上角,机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角.问总共有多少条不同的路径？

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 向右 向下
2. 向右 向下 向右
3. 向下 向右 向右

输入: m = 7, n = 3
输出: 28

// 简单递归（超时，无价值）
class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m<=0||n<=0) return 0;
        return NumPaths(0,0,m,n);
    }
    int NumPaths(int i, int j, int m, int n){
        if(i==m-1&&j==n-1) return 1; // 如果到头了，则算为一种路径
        if(i==m-1) return NumPaths(i,j+1,m,n); // 到底了，往右走
        else if(j==n-1) return NumPaths(i+1,j,m,n); // 到最右了，往下走
        else return  NumPaths(i+1,j,m,n) + NumPaths(i,j+1,m,n); // 不然的话由向右向下两种方法
    }
};

// 简单动态规划
class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m==0||n==0) return 0;
        int bp[n]; // 结果暂存数组
        for(int i=0; i<n; ++i){ // 初始化第一层，都为1
            bp[i] = 1;
        }
        for(int i=1; i<m; ++i){ // 从第二层开始遍历
            for(int j=1; j<n; ++j){ // bp的第一个数永远是1，不用改变
                bp[j] = bp[j-1] + bp[j]; // f(i,j)=f(i-1,j)+f(i,j-1);
            }
        }
        return bp[n-1];
    }
};

思路：递归的方法好懂但复杂度特别高，故将递归转换为简单的动态规划，f(i,j)表示走到坐标（i,j)处的路径数，故f(i,j)=f(i-1,j)+f(i,j-1); 可以建立动态规划矩阵，但实际上我们只会利用矩阵左侧和上侧的信息，故只需要一行数组来保存上一行的结果即可；根据递推公式进行累计计算；

---

66、加一（简单）

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        if(digits.empty()) return {}; // 容器为空直接返回
        for(int i=digits.size()-1; i>=0; --i){ // 从后往前遍历
            if(digits[i]==9){ // 如果当前为9，则置为0
                digits[i] = 0;
                if(i==0){ // 如果该数已经是首位，说明digits元素全是9，则需要变成10000...
                    vector<int> re(digits.size()+1,0);
                    re.front() = 1; 
                    return re;
                }
            }
            else{ // 当前不是最高位,第一个不是9的数
                digits[i] += 1;
                break; // +1处理完毕，跳出循环
            }
        }
        vector<int> re(digits.begin(),digits.end());
        return re; 
    }
};

思路：比较简单，不用化为数学形式做，直接分为两种情况进位即可，从后往前遍历，首先如果当前位不是9，直接加1返回就行了；如果当前位是9，则把它变成0就好；如果是[9,9,9]的情况，则需要每位的9都变成0，然后在前面再添加一位1；

---

69、x的平方根（中等）

实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

// 二分查找法
class Solution {
public:
    int mySqrt(int x) {
        if(x<0) return -1;
        if(x==0) return 0;
        int left = 0, right = x/2 + 1; // (x的根方)小于(x/2+1)
        int mid;
        long int squa;
        while(left<right){ // 二分查找(稍微不同)
            mid = (left + right) / 2 + 1; // 多加了1，使mid值靠右
            squa = mid; squa *= squa; // 计算平方
            if(squa==x) return mid;
            if(squa<x) left = mid;
            if(squa>x) right = mid - 1; // 因为靠右侧，所以右侧要减一
        }
        return left;
    }
};

// 牛顿法
class Solution {
public:
    int mySqrt(int a) {
        if(a<0) return -1;
        if(a==0) return 0;
        double x = 1; // 当前迭代的值，取值随机，但不能为0（分母）
        double x0 = 0; // 迭代时上一个点的参考值，取值随机
        while(abs(x-x0)>1e-6){ // 循环到误差足够小
            x0 = x; // 将x的值赋给x0当做上一个参考点
            x = 0.5 * (x0 + a/x0); // 继续按照公式迭代x
        }
        return int(x);
    }
};

思路：两种方法：其一是二分查找法，对0-x中的值进行二分查找，其中二分的时候由于取整数部分的特殊操作，需要在二分的时候进行特殊处理，具体见代码注释；其次还有一个牛顿法，也可以用迭代的方法解方程组：x^{2-a=0，此处a是程序输入，x是最终结果；牛顿法简单推导：定义f(x)=x}2-a=0，即求解x的方程组，方程左侧泰勒展开f(x)=f(x0)+f’(x0)(x-x0)=0.令其为零，则x=x0-f(x0)/f’(x0)，不停的用新的x去代替x0直至x和x0的差距很小。

---

70、爬楼梯（简单）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

class Solution {
public:
    int climbStairs(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(n==2) return 2;
        int num0 = 1, num1 = 2;
        int result = 0;
        for(int i=3; i<=n; ++i){
            result = num0 + num1;
            (num0 < num1 ? num0 : num1) = result; 
        }
        return result;
    }
};

思路：与剑指offer的青蛙跳台阶相同，f(n)=f(n-1)+f(n-2)，斐波那契数列，用动态规划从小往大循环递增即可；

---

73、矩阵置零（中等）

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

输入:
[1,1,1],
[1,0,1],
[1,1,1]
输出:
[1,0,1],
[0,0,0],
[1,0,1]

输入:
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
输出:
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if(matrix.empty()) return;
        vector<int>::size_type m = matrix.size();
        vector<int>::size_type n = matrix[0].size();
        set<size_t> list_row, list_col; // 存在0的行和列的哈希表
        for(size_t i=0; i<m; ++i){
            for(size_t j=0; j<n; ++j){
                if(matrix[i][j]==0){
                    list_row.insert(i); // 记录存在0的行
                    list_col.insert(j); // 记录存在0的列
                }
            }
        } // 对每个记录的行置零
        for(auto iter=list_row.begin(); iter!=list_row.end(); ++iter){
            for(size_t i=0; i<n; ++i){
                matrix[*iter][i] = 0;
            }
        } // 对每个记录的列置零
        for(auto iter=list_col.begin(); iter!=list_col.end(); ++iter){
            for(size_t i=0; i<m; ++i){
                matrix[i][*iter] = 0;
            }
        }
    }
};

思路：常规题，没有特别好的办法，具体思路是利用两个set哈希表，编译一次数组，找到存在0的行号和列号，分别存入set，（set的好处是可以剔除重复的键值，置零的时候不用重复置零，比如坐标(1,2)和(1,3)都是0时，记录行号1和列号2，3;然后根据两个set的值进行置零即可；

---

75、颜色分类（中等）

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:不能使用代码库中的排序函数来解决这道题。

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

// 荷兰国旗，三指针法
class Solution {
public:
    void sortColors(vector<int>& nums) {
        if(nums.empty()) return;
        vector<int>::size_type size = nums.size();
        vector<int>::size_type left = 0, right = size - 1; // 0的右边界、2的左边界指针
        for(size_t i=0; i<=right&&right>0; ++i){ //遍历到2的边界处即可停止
            if(nums[i]==0){ // 当前节点为0
                swap(nums[left],nums[i]); // 注意此处的nums[left]只可能是1
                ++left; // 0的右边界向右移动一位
            }
            else if(nums[i]==2){ // 当前节点为2
                swap(nums[right],nums[i]);
                --right; // 2的左边界向左移动一位，注意此处可能会出现right为0-1的情况，应避免
                --i; // 重新判断交换回的这一位数
            }
        }
    }
};

思路：典型的荷兰国旗问题，三指针法可以一次遍历解决问题，并且不使用额外的内存空间；首先定义left和right表示排序后前面的0和后面的2的边界处，然后定义一个指针从头遍历数组，如果遇到0，则将其和现在的left处的值交换，把0换到前面去，然后left指针向右移动一位，注意此处换过来的数一定是1，所以不用再重新判断当前换过来的节点；如果遇到1，则忽视，继续遍历；如果遇到2，则将其和right处的值交换，把2换到右边，然后right指针向左移动一位，由于不知道原先right处的值是多少，故需要–i，重新判断当前缓过来的这个节点；另外还有一个需要注意的是如果定义了size_type或size_t，一定注意其不能为负，在自减操作时必须留意不能为0；

---

76、最小覆盖子串（困难）

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

// 哈希表和滑动窗口法
class Solution {
public:
    string minWindow(string s, string t) {
        int start = 0, minLen = INT_MAX; // 最终结果的起始下标和最短长度
        if(t.empty()||s.empty()||s.size()<t.size()) return "";
        unordered_map<char,int> letter_t; // map,存放t中所有字母和其出现的次数
        unordered_map<char,int> letter_w; // map,存放滑动窗口中的字母和出现的次数
        for(auto c : t){ // 统计t中的字母情况
            ++letter_t[c];
        }
        int left = 0, right = 0; // 滑动窗口左右指针
        int num_matched = 0; // 目前窗口中的总匹配数
        while(right<s.size()){ // 总循环，窗口移动
            char c = s[right]; // 当前字符
            if(letter_t.find(c)!=letter_t.end()){ // 这个字符在t中存在
                ++letter_w[c]; // 窗口中的该字符数目+1
                if(letter_t[c]==letter_w[c]){ // 如果该字符数目与t中的相等了，则该字符已匹配
                    ++num_matched; // 匹配数目+1
                }

            }
            while(num_matched==letter_t.size()){ // 如果当前匹配上的字符数与t中的相同了
                if(right-left+1<minLen){ // 当前匹配的字段长度更小，则更新最小长度和起始下标
                    minLen = right - left + 1;
                    start = left;
                }
                char c2 = s[left]; // 准备左指针右移，直到不能满足匹配关系，其中更新最终结果的范围
                if(letter_t.find(c2)!=letter_t.end()){ // 当前要排除的字符属于t
                    if(--letter_w[c2]<letter_t[c2]){ // 排除了字符导致匹配的字符数减少
                        --num_matched;
                    }
                }
                ++left; // 窗口左指针右移
            }
            ++right; // 指针右移，继续遍历下一个字符
        }
        return minLen<INT_MAX ? s.substr(start,minLen) : ""; // 如果minLen每更新过，则没匹配
    }
};

思路：稍微复杂的题目；可以利用滑动窗口，两个指针left,right交叉右移；两个哈希表，一个letter_t记录t中出现的字符和出现的次数，一个letter_w记录滑动窗口中出现的字符和出现次数；首先right右移，直到满足窗口中的字符满足匹配条件（哈希表letter_w中的字符的次数都大于等于letter_t中的字符的个数，该条件可用一个num_matched判断，其表示当前窗口中已经匹配上的字符的数量，如果等于了letter_t元素的数目，就是匹配上了），然后让left指针右移收缩，收缩同时更新满足条件的滑动窗口的最短长度和起始下标，直到不满足匹配条件时停止；然后继续right右移。。。。算法相当于先遍历一遍t，然后使左右指针从左到右遍历一遍s，复杂度为O(len_t+2len_s);

---

78、子集（中等）

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

输入: nums = [1,2,3]
输出:
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]

// 常规DFS递归
class Solution {
    vector<vector<int> > result;
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        if(nums.empty()) return result;
        vector<int> tmp;
        FindSubVec(nums, 0, nums.size(), tmp);
        return result;
    }
    void FindSubVec(vector<int>& nums, int left, int size, vector<int>& tmp){
        if(left==size){
            result.push_back(tmp);
            return;
        }
        tmp.push_back(nums[left]);
        FindSubVec(nums, left+1, size, tmp);
        tmp.pop_back();
        FindSubVec(nums, left+1, size, tmp);
    }
};

// 逐个字符扩充的循环法
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > result(1); // 初始化result, 赋予第一个元素{}，一个空vector
        for(int i=0; i<nums.size(); ++i){ // 每次加入nums的一个元素
            int size = result.size(); 
            for(int j=0; j<size; ++j){ // 从当前result中已有的size个元素中再扩充一个数，变成双倍size
                vector<int> tmp = result[j]; // 取出result中的一个vector
                tmp.push_back(nums[i]); // 给这个vector扩充一个数并放入result
                result.push_back(tmp);
            }
        }
        return result;
    }
};

思路：典型的求全组合问题，递归深度优先遍历求解是最常用的做法；第二种循环法的思想比较有趣，从空vector算起，每次给这些组合添加一个元素，添加后的组合数量应该为之前的两倍，具体思路见图：

---

79、单次搜索（中等）

给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

board =
[‘A’,‘B’,‘C’,‘E’],
[‘S’,‘F’,‘C’,‘S’],
[‘A’,‘D’,‘E’,‘E’]

给定 word = “ABCCED”, 返回 true
给定 word = “SEE”, 返回 true
给定 word = “ABCB”, 返回 false

提示：
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(word.empty()) return true; // 若word为空，则一定匹配
        if(board.empty()) return false; // 若board为空word不为空，则一定不匹配
        int row = board.size();
        int col = board[0].size();
        int list[row*col]; // 建立走过的路径标记矩阵，并赋初值为全0
        memset(list, 0, sizeof(list));
        bool result = false;
        for(int i=0; i<row; ++i){ // 遍历矩阵，如果遇到word的第一个字符，则开始回溯寻找
            for(int j=0; j<col; ++j){
                if(board[i][j]==word.front()){
                    result = result || FindPath(board, word, i, j, 0, row, col, list);
                }
            }
        }
        return result;
    }
    bool FindPath(vector<vector<char> >& board, string& word, int i, int j, int num, int row, int col, int* list){
        // 如果当前越界了、是走过的路线、值不相等，则直接返回false；
        if(i<0||j<0||i>=row||j>=col||list[i*col+j]!=0||board[i][j]!=word[num]) return false; 
        else if(num==word.size()-1) return true; // 如果当前值匹配，又是最后一个字符匹配，则返回true；
        else{ // 当前匹配但不是最后一个节点，继续往后寻找
            list[i*col+j] = 1; // 当前这个走过的节点置为1
            bool restmp =  FindPath(board, word, i-1, j, num+1, row, col, list) // 上下左右寻找路径，用或，只要有一条走的通即可
                || FindPath(board, word, i+1, j, num+1, row, col, list)
                || FindPath(board, word, i, j-1, num+1, row, col, list)
                || FindPath(board, word, i, j+1, num+1, row, col, list);
            list[i*col+j] = 0; // 返回之前，一定要记得将当前节点的标志置回0！！！！！很重要
            return restmp;
        }
    }
};

思路：典型的回溯法找路径问题，代码量稍微大一些，思路比较清楚，看代码注释即可；

---

84、柱状图中最大的矩形（困难）

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

输入: [2,1,5,6,2,3]
输出: 10

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.empty()) return 0;
        heights.push_back(0); // 在数组末尾添加一个0，用于遍历的时候最终将所有元素都出栈
        stack<int> stk; // 栈stk，用作单调递增栈，注意其存放的是单调递增的元素的下标
        int result = 0; // 结果变量
        for(int i=0; i<heights.size(); ++i){ // 遍历数组
            while(!stk.empty() && heights[i]<heights[stk.top()]){ // 如果单调栈不为空且当前元素小于栈顶元素
                int index = stk.top(); // 将大于当前元素的栈顶元素全部出栈，出栈同时计算覆盖出栈元素的最大矩阵面积
                stk.pop(); // 为了将当前元素入栈并保持单调栈特点，将栈顶出栈
                result = max(result, heights[index] * (stk.empty()?(i):(i-stk.top()-1)) ); // 更新面积
            }
            stk.push(i); // 当前元素入栈
        }
        return result;
    }
};

思路：一言难尽的一道题，跟接雨水那道题看似差不多，但完全不同，用到了单调递增栈来解决问题；代码思路很奇葩，遍历整个数组，元素入栈时如果栈顶元素更大，则一直出栈，直到新入栈的元素可以满足单调栈的规则；出栈的过程中计算每个出栈元素的覆盖到它的最大矩型的面积，其面积等于（当前遍历元素下标左侧）和（出栈元素的左侧第一个小于它的元素的右边界）之间的部分，还要考虑出栈元素左侧没有比他更小的数的情况（出栈后栈为空了）。但具体的求面积的思路很难讲，可以用测试用例带入然后实际感受一下；

---