1--全排列（46）

主要思路1：

经典全排列，每次枚举每一位时，重头开始枚举，用一个访问数组记录当前已经被访问过的数字；

这道题不包含重复数字，所以不需要进行树层上的剪枝；

#include <iostream>
#include <vector>class Solution {
public:std::vector<std::vector<int>> permute(std::vector<int>& nums) {if(nums.size() == 0) return res;std::vector<bool> vis(nums.size(), false);std::vector<int> tmp;dfs(nums, vis, tmp);return res;}void dfs(std::vector<int>& nums, std::vector<bool>& vis, std::vector<int> &tmp){if(tmp.size() == nums.size()){res.push_back(tmp);return;}for(int i = 0; i < nums.size(); i++){if(vis[i] == true) continue;tmp.push_back(nums[i]);vis[i] = true;dfs(nums, vis, tmp);// 回溯tmp.pop_back();vis[i] = false;}}
private:std::vector<std::vector<int>> res;
};int main(int argc, char *argv[]){std::vector<int> test = {1,2,3};Solution S1;std::vector<std::vector<int>> res = S1.permute(test);for(auto v : res){for(auto i : v) std::cout << i << " ";std::cout << std::endl;}
}

主要思路2：

可以利用下一个排列的思想来枚举全排列，首先需要将数组进行从小到大排序，然后不断求解下一个排列，一个下一个排列就是一个新的排列，直到最大的排列为止；

#include <iostream>
#include <vector>
#include <algorithm>class Solution {
public:std::vector<std::vector<int>> permute(std::vector<int>& nums) {if(nums.size() == 0) return res;std::sort(nums.begin(), nums.end()); // 从小到大排列res.push_back(nums); // 记录最小的排列while(nextp(nums)){res.push_back(nums);}return res;}bool nextp(std::vector<int>& nums){int n = nums.size();// 找到第一个顺序对int i;for(i = n - 2; i >= 0; i--){if(nums[i] < nums[i+1]) break;}if(i == -1) return false; //已经是最大排列了// 找到一个nums[j] > 上面的nums[i]int j;for(j = n - 1; j > i; j--){if(nums[j] > nums[i]) break;}// 交换nums[i] 和 nums[j]std::swap(nums[i], nums[j]);// 反转num[i+1] ~ nums.end()std::reverse(nums.begin() + i + 1, nums.end());return true;}private:std::vector<std::vector<int>> res;
};int main(int argc, char *argv[]){std::vector<int> test = {1,2,3};Solution S1;std::vector<std::vector<int>> res = S1.permute(test);for(auto v : res){for(auto i : v) std::cout << i << " ";std::cout << std::endl;}
}

2--旋转图像（48）

主要思路：

按层（圈）来旋转，对于坐标为(r, c)的值，其旋转后的坐标为(c, n - 1 - r)，且每四个（上，右，下，左）为一个循环节，循环交换循环节中四个元素即可，视频讲解参考：旋转图像

#include <iostream>
#include <vector>
#include <algorithm>class Solution {
public:void rotate(std::vector<std::vector<int>>& matrix) {int n = matrix.size();// 按层（圈）处理for(int L = n; L > 0; L -= 2){// 左上角起始元素int row = (n - L) / 2;int col = row;// 当前这一行，顶行的前 L-1 个元素for(int k = 0; k < L - 1; k++){// 当前元素int r = row, c = col + k;int tmp = matrix[r][c];// 从(r, c)开始寻找循环节，循环节的长度一定是4for(int i = 0; i < 4; i++){// 旋转后的坐标int rr = c;int cc = n - 1 - r;// 旋转std::swap(tmp, matrix[rr][cc]);r = rr;c = cc;}}}}
};
int main(int argc, char *argv[]){std::vector<std::vector<int>> test = {{1,2,3}, {4,5,6}, {7,8,9}};Solution S1;S1.rotate(test);for(auto v : test){for(auto i : v) std::cout << i << " ";std::cout << std::endl;}
}

3--字母异位词分组（49）

主要思路：

字母异位词排序后肯定相同，因此将每个字符串按字符进行排序，将排序后的结果作为key，原字符串的集合作为value，通过哈希的方式将字母异位词存储在一次，最后遍历哈希表返回结果即可；

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>class Solution {
public:std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs) {std::unordered_map<std::string, std::vector<std::string>> hash;for(const auto &str : strs){std::string key = str;std::sort(key.begin(), key.end()); // 字母异位词的排序顺序肯定相同hash[key].push_back(str);}std::vector<std::vector<std::string>> res;for(auto item : hash){ // 遍历哈希表res.push_back(item.second);}return res;}
};
int main(int argc, char *argv[]){std::vector<std::string> test = {"eat", "tea", "tan", "ate", "nat", "bat"};Solution S1;std::vector<std::vector<std::string>> res = S1.groupAnagrams(test);for(auto item : res){for(std::string str : item) std::cout << str << " ";std::cout << std::endl;}
}

4--最大子数组和（53）

主要思路：

有点类似于一个滑动窗口（一般需要维护左右边界指针，但本题可以只维护右边界的指针），当滑动窗口内的和为正数时，右边界贪心地去纳入下一个数；

当纳入下一个数时导致滑动窗口内的和为负数时，舍弃该滑动窗口并将当前的和置为0，接着从下一个数重新开始纳入新的值；

#include <iostream>
#include <vector>class Solution {
public:int maxSubArray(std::vector<int>& nums) {if(nums.size() == 1) return nums[0];// 初始化int max_sum = nums[0];int sum = 0;for(int i = 0; i < nums.size(); i++){// 尝试贪心地纳入新的一个值int cur_sum = sum + nums[i];// 当前滑动窗口内的和为正数，更新滑动窗口的和if(cur_sum > 0) sum = cur_sum;// 当前滑动窗口内的和为负数，抛弃前缀和为负数的结果else sum = 0; // 更新最大值if(cur_sum > max_sum) max_sum = cur_sum;}return max_sum;}
};int main(int argc, char *argv[]){std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};Solution S1;int res = S1.maxSubArray(nums);std::cout << res << std::endl;
}

5--跳跃游戏（55）

主要思路：

维护一个滑动窗口，遍历数组的每一个元素，判断当前滑动窗口能到达的最大范围，当滑动窗口能够覆盖最后一个下标时，返回 true，否则返回 false；

#include <iostream>
#include <vector>class Solution {
public:bool canJump(std::vector<int>& nums) {int n = nums.size();int l = 0, r = 0;while(l < n - 1){int bound = l + nums[l];r = std::max(r, bound);if(l == r) break;l++;}return r >= n-1;}
};int main(int argc, char *argv[]){std::vector<int> nums = {2, 3, 1, 1, 4};Solution S1;bool res = S1.canJump(nums);if(res) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;return 0;
}

6--合并区间（56）

主要思路：

对数组进行排序，然后遍历数组，比较两者是否能合并，不能合并则存储上一区间，并从下一组重新开始判断，否则合并两个区间，继续判断下一组元素；

#include <iostream>
#include <vector>
#include <algorithm>class Solution {
public:std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {std::sort(intervals.begin(), intervals.end());int n = intervals.size();std::vector<std::vector<int>> res;int l = intervals[0][0], r = intervals[0][1];for(int i = 1; i < n; i++){if(intervals[i][0] > r){res.push_back({l, r});l = intervals[i][0];r = intervals[i][1];}else{r = std::max(r, intervals[i][1]);}}res.push_back({l, r}); // 存储最后一组return res;}
};int main(int argc, char *argv[]){// intervals = [[1,3],[2,6],[8,10],[15,18]]std::vector<std::vector<int>> test = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};Solution S1;std::vector<std::vector<int>> res = S1.merge(test);for(auto v : res){for(int item : v){std::cout << item << " ";}std::cout << std::endl;}return 0;
}

7--不同路径（62）

主要思路：

比较直观的思路是使用递归的方法，向下和向右深度搜索能否到达右下角，但在本题中这种解法会超时；

#include <iostream>
#include <vector>// 递归
class Solution {
public:int uniquePaths(int m, int n) {dfs(0, 0, m, n);return res;}void dfs(int start_i, int start_j, int m, int n){if(start_i >= m || start_j >= n){return;}if(start_i == m - 1 && start_j == n - 1){res += 1;return;}dfs(start_i + 1, start_j, m, n);dfs(start_i, start_j + 1, m, n);}private:int res = 0;
};int main(int argc, char *argv[]){// m = 3, n = 7int m = 3, n = 2;Solution S1;int res = S1.uniquePaths(m, n);std::cout << res << std::endl;return 0;
}

主要思路：

基于动态规划，定义状态 dp[i][j] 表示到达 (i,j) 坐标时的路径总数；

状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j-1]；

初始状态：上边界dp[0][j] = 1，左边界dp[i][0] = 1；

#include <iostream>
#include <vector>// 动态规划
class Solution {
public:int uniquePaths(int m, int n) {std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));for(int i = 0; i < m; i++){dp[i][0] = 1;}for(int j = 0; j < n; j++){dp[0][j] = 1; }for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m-1][n-1];}
};int main(int argc, char *argv[]){// m = 3, n = 7int m = 3, n = 2;Solution S1;int res = S1.uniquePaths(m, n);std::cout << res << std::endl;return 0;
}

8--最小路径和（64）

主要思路：

类似于上题，可以使用动态规划的方式进行求解，状态 dp[i][j] 表示经过到达坐标点 (i, j) 路径的最小和；

状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]；

初始状态：dp[0][0] = grid[0][0]，上边界dp[0][j] = dp[0][j-1] + grid[0][j]，左边界dp[i][0] = dp[i-1][0] + grid[i][0]；

#include <iostream>
#include <vector>// 动态规划
class Solution {
public:int minPathSum(std::vector<std::vector<int>>& grid) {int m = grid.size(), n = grid[0].size();std::vector<std::vector<int>> dp(grid.size(), std::vector<int>(grid[0].size(), 0));// 初始状态dp[0][0] = grid[0][0];for(int i = 1; i < m; i++){dp[i][0] = grid[i][0] + dp[i-1][0];}for(int j = 1; j < n; j++){dp[0][j] = grid[0][j] + dp[0][j-1]; }// 状态转移for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){dp[i][j] = std::min(dp[i-1][j],  dp[i][j-1]) + grid[i][j];}}return dp[m-1][n-1];}
};int main(int argc, char *argv[]){// grid = [[1,3,1],[1,5,1],[4,2,1]]std::vector<std::vector<int>> test = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};Solution S1;int res = S1.minPathSum(test);std::cout << res << std::endl;return 0;
}

可以进一步将空间复杂度优化到O(1)，直接在原数组中进行修改；

#include <iostream>
#include <vector>// 动态规划
class Solution {
public:int minPathSum(std::vector<std::vector<int>>& grid) {int m = grid.size(), n = grid[0].size();// 初始状态for(int i = 1; i < m; i++){grid[i][0] = grid[i][0] + grid[i-1][0];}for(int j = 1; j < n; j++){grid[0][j] = grid[0][j] + grid[0][j-1]; }// 状态转移for(int i = 1; i < m; i++){for(int j = 1; j < n; j++){grid[i][j] = std::min(grid[i-1][j],  grid[i][j-1]) + grid[i][j];}}return grid[m-1][n-1];}
};int main(int argc, char *argv[]){// grid = [[1,3,1],[1,5,1],[4,2,1]]std::vector<std::vector<int>> test = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};Solution S1;int res = S1.minPathSum(test);std::cout << res << std::endl;return 0;
}

9--爬楼梯（70）

主要思路：

经典动态规划easy题，定义状态 dp[i] 表示到达 i 阶楼梯时的方法数；

状态转移方程：dp[i] = dp[i-1] + dp[i-2]；

初始状态：dp[0] = 1，dp[1] = 2；

#include "iostream"
#include <vector>class Solution {
public:int climbStairs(int n) {if(n == 1) return 1;std::vector<int> dp(n, 0);dp[0] = 1;dp[1] = 2;for(int i = 2; i < n; i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n-1];}
};int main(int arc, char *argv[]){int n = 3;Solution S1;int res = S1.climbStairs(n);std::cout << res << std::endl;
}

10--编辑距离（72）

主要思路：

基于动态规划，定义状态 dp[i][j] 表示 word1 前 i 个字符与 word2 前 j 个字符相等时的最少操作数；

状态转移方程：当 word1[i] == word2[j] 时，dp[i][j] = dp[i-1][j-1]；当 word1[i] != word2[j] 时，dp[i][j] = min(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1)；

初始状态：dp[0][0] = 0 表示两者都是空串，dp[i][0] = i 和 dp[0][j] = j 表示其中一个字符串为空；

#include "iostream"
#include <vector>
#include <string>
#include <algorithm>class Solution {
public:int minDistance(std::string word1, std::string word2){int n = word1.size(), m = word2.size();std::vector<std::vector<int>> dp(n+1, std::vector<int>(m+1, 0));// 初始化dp[0][0] = 0; // 两者都是空串for(int i = 1; i <= n; i++) dp[i][0] = i; // 其中一个为空串for(int j = 1; j <= m; j++) dp[0][j] = j;// 状态转移for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(word1[i-1] == word2[j-1]){dp[i][j] = dp[i-1][j-1];} else{dp[i][j] = std::min(dp[i-1][j-1] + 1,std::min(dp[i][j-1]+1, dp[i-1][j]+1));}}}return dp[n][m];}
};int main(int arc, char *argv[]){// word1 = "horse", word2 = "ros"std::string word1 = "horse";std::string word2 = "ros";Solution S1;int res = S1.minDistance(word1, word2);std::cout << res << std::endl;return 0;
}