❤ 作者主页：欢迎来到我的技术博客 ❀ 个人介绍：大家好，本人热衷于Java后端开发，欢迎来交流学习哦！(￣▽￣)~* 如果文章对您有帮助，记得关注、点赞、收藏、评论⭐️⭐️⭐️ 您的支持将是我创作的动力，让我们一起加油进步吧！！！
文章目录
一、全排列1. 题目描述2. 思路分析3. 代码实现
二、旋转图像1. 题目描述2. 思路分析3. 代码实现
三、字母异位词分组1.题目描述2. 思路分析3. 代码实现
四、最大子数组和1. 题目描述2. 思路分析3. 代码实现
五、跳跃游戏1. 题目描述2. 思路分析3. 代码实现
六、合并区间1. 题目描述2. 思路分析3. 代码实现
七、不同路径1. 题目描述2. 思路分析3. 代码实现
八、最小路径和1. 题目描述2. 思路分析3. 代码实现
九、爬楼梯1. 题目描述2. 思路分析3. 代码实现
十、编辑距离1. 题目描述2. 思路分析3. 代码实现
一、全排列
1. 题目描述
2. 思路分析
算法流程：
用
p
a
t
h
path
path 数组来保存排序，当排序长度为 n 时，是一个排序方案，输出该方案；用
s
t
a
t
e
state
state 数组表示数字是否使用过。当
s
t
a
t
e
[
i
]
state[i]
state[i] 为 1 时表示
i
i
i已经被使用过，
s
t
a
t
e
[
i
]
state[i]
state[i] 为 0 时表示
i
i
i没有被使用过；
d
f
s
(
i
)
dfs(i)
dfs(i) 表示的含义是：在
p
a
t
h
[
i
]
path[i]
path[i] 处填写数字，然后递归的在下一个位置填写数字;回溯：第 i 个位置填写某个数字的所有情况都遍历后， 第 i 个位置填写下一个数字。
3. 代码实现
class Solution {
public:
vector
vector
vector
vector
path = vector
st = vector
dfs(nums, 0);
return ans;
}
void dfs(vector
if (u == nums.size()) {
ans.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i ++) {
if (!st[i]) {
path[u] = nums[i];
st[i] = true;
dfs(nums, u + 1);
st[i] = false;
}
}
}
};
二、旋转图像
1. 题目描述
2. 思路分析
(操作分解） O(
n
2
n^2
n2) 直接操作旋转
9
0
o
90^o
90o比较困难，我们可以将它分解成两个操作：
先以左上-右下对角线为轴做翻转；再以中心的竖线为轴做翻转；
3. 代码实现
class Solution {
public:
void rotate(vector
int n = matrix.size();
for (int i = 0; i < n; i ++)
for (int j = i + 1; j < n; j ++)
swap(matrix[i][j], matrix[j][i]);
for (int i = 0; i < n; i ++)
for (int j = 0, k = n - 1; j < k; j ++, k --)
swap(matrix[i][j], matrix[i][k]);
}
};
三、字母异位词分组
1.题目描述
2. 思路分析
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
定义从 string 映射到vector
3. 代码实现
class Solution {
public:
vector
unordered_map
for (auto& str : strs) {
string nstr = str;
sort(nstr.begin(), nstr.end());
hash[nstr].push_back(str);
}
vector
for (auto& item : hash) res.push_back(item.second);
return res;
}
};
四、最大子数组和
1. 题目描述
2. 思路分析
动态规划
O
(
n
)
O(n)
O(n)
设 f(i)f(i) 表示以第
i
i
i 个数字为结尾的最大连续子序列的 总和 是多少。初始化: f(0)=nums[0]。转移方程 f(i)=max(f(i−1)+nums[i],nums[i])。可以理解为当前有两种决策，一种是将第
i
i
i 个数字和前边的数字拼接起来；另一种是第
i
i
i 个数字单独作为一个新的子序列的开始。最终答案为
a
n
s
=
m
a
x
(
f
(
k
)
)
,
0
≤
k
<
n
ans=max(f(k)),0≤k ans=max(f(k)),0≤k 3. 代码实现 class Solution { public: int maxSubArray(vector int n = nums.size(), res = nums[0]; vector f[0] = nums[0]; for (int i = 1; i < n; i ++) { f[i] = max(f[i - 1] + nums[i], nums[i]); res = max(res, f[i]); } return res; } }; 五、跳跃游戏 1. 题目描述 2. 思路分析 核心思想：尽可能跳到更远的位置。 若往后的位置能跳到，则前面的位置一定可以跳到， l a s t last last 表示的是从前 i − 1 i - 1 i−1 个位置中跳，能跳到最远的位置是 l a s t last last；若前 i − 1 i - 1 i−1 个位置中跳，跳到最远的位置是 l a s t last last 比 i i i 小，表示从前 i − 1 i - 1 i−1 个位置中跳，跳不到 i i i 的位置，因此一定不能跳到最后一个的位置；若前 i − 1 i - 1 i−1 个位置中跳，能跳到 i i i，则继续尝试从 i i i 位置跳，可能会跳得更远，更新 l a s t last last 的值。 3. 代码实现 class Solution { public: bool canJump(vector int last = 0; for (int i = 0; i if (last < i) return false; last = max(last, i + nums[i]); } return true; } }; 六、合并区间 1. 题目描述 2. 思路分析 贪心思想： 首先对各区间进行排序；定义当前区间的左右端点为第一个区间的左右端点；从前往后遍历每一个区间，如果当前区间与上一个区间有交集，则更新右端点；否则将上一个区间加入集合，然后更新当前区间。 3. 代码实现 class Solution { public: vector vector if (a.empty()) return res; sort(a.begin(), a.end()); int l = a[0][0], r = a[0][1]; for (int i = 1; i < a.size(); i ++) { if (a[i][0] > r) { res.push_back({l, r}); l = a[i][0], r = a[i][1]; } else r = max(r, a[i][1]); } res.push_back({l, r}); return res; } }; 七、不同路径 1. 题目描述 2. 思路分析 动态规划 状态表示： f[i][j] 表示从起点到 ( i , j ) (i,j) (i,j) 的路径总和；状态转移方程： f[i][j] = f[i - 1][j] + f[i][j - 1];初始化： 对于第一行f[0][j] 或者第一列 f[j][0]，由于都是在边界，所有只能为1。 3. 代码实现 class Solution { public: int uniquePaths(int m, int n) { vector for (int i = 0; i < m; i ++) for (int j = 0; j < n; j ++) { if (!i || !j) f[i][j] = 1; //f[i][0] 和 f[0][j]单独初始化为1 else f[i][j] = f[i - 1][j] + f[i][j - 1]; } return f[m - 1][n - 1]; } }; 八、最小路径和 1. 题目描述 2. 思路分析 状态表示: f[i][j] 表示从起点到 ( i , j ) (i,j) (i,j) 的最小路径和。 很显然，f[0][0] = grid[0][0]，对于 f f f 中的其余元素值，通过以下状态转移方程计算元素值： 当 i > 0 i > 0 i>0 且 j = 0 j = 0 j=0 时(即第一行)，f[i][0] = f[i - 1][0] + grid[i][0];当 i = 0 i = 0 i=0 且 j > 0 j > 0 j>0 时(即第一列)，f[0][j] = f[0][j - 1] + grid[0][j];当 i > 0 i > 0 i>0 且 j > 0 j > 0 j>0 时，f[i][j] = min(f[i - 1][j], f[i][j - 1] + grid[i][j]; 3. 代码实现 class Solution { public: int minPathSum(vector int n = grid.size(), m = grid[0].size(); vector f[0][0] = grid[0][0]; //起点 //第一行，只能从左边来 for (int i = 1; i < n; i ++) { f[i][0] = f[i - 1][0] + grid[i][0]; } //第一列，只能从上面来 for (int j = 1; j < m; j ++) { f[0][j] = f[0][j - 1] + grid[0][j]; } //其他的则可以从左边或者上面来 for (int i = 1; i < n; i ++) for (int j = 1; j < m; j ++) { f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]; } return f[n - 1][m - 1]; } }; 九、爬楼梯 1. 题目描述 2. 思路分析 定义数组 f [ i ] f[i] f[i] 表示上 i i i 级台阶的方案数，则枚举最后一步是上1级台阶，还是上2级台阶，所以有：f[i] = f[i − 1] + f[i − 2]。 3. 代码实现 class Solution { public: int climbStairs(int n) { vector f[0] = 1; f[1] = 1; for (int i = 2; i <= n; i ++) f[i] = f[i - 1] + f[i - 2]; return f[n]; } }; 十、编辑距离 1. 题目描述 2. 思路分析 动态规划 状态表示： f[i][j] 表示 w o r d 1 word1 word1 到 i i i 位置转化成 w o r d 2 word2 word2 到 j j j 位置需要的最小步数。 状态转移方程： 当 word1[i] == word2[j]，f[i][j] = f[i - 1][j - 1];当 word1[i] != word2[j]，[i][j] = min(f[i - 1][j - 1] + 1, min(f[i][j - 1] + 1, f[i - 1][j] + 1)); 其中，f[i - 1][j - 1] 表示替换操作， f[i - 1][j] 表示删除操作，f[i][j - 1] 表示插入操作。 注意：针对第一行和第一列到单独考虑，我们引入 '' 如下图所示： 3. 代码实现 class Solution { public: int minDistance(string a, string b) { int n = a.size(), m = b.size(); a = ' ' + a, b = ' ' + b; vector for (int i = 1; i <= n; i ++) f[i][0] = i; for (int j = 1; j <= m; j ++) f[0][j] = j; for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++) { if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1]; else f[i][j] = min(f[i - 1][j - 1] + 1, min(f[i][j - 1] + 1, f[i - 1][j] + 1)); } return f[n][m]; } }; 非常感谢您阅读到这里，如果这篇文章对您有帮助，希望能留下您的点赞 关注 分享 留言thanks！！！ 推荐链接
您阅读本篇文章共花了：
发表评论