前言
由于比赛临近，老师给我们布置了一些LeetCode算法题目，但是我在学完Hello算法的数据结构部分之后，就跑去学习算法第四版了。被一些安全比赛耽误，算法的学习进度比较慢，通过这篇文章就可以体现出我的技术还是比较菜的，还望谅解，哈哈。
一、反转链表
LeetCode题目#206 反转链表
这是老师布置的第一道题，我发现独立完成这题的提升比之前所有的提升还大，学习还得是实战。
根据题目描述和一些提示，可以使用循环或递归遍历链表，一开始我不甘示弱只使用递归，想递到链尾创建节点再归，做不出来，换了一种思路。
我选择使用链表实现的栈来解决这道题，根据栈的先进后出性质，当链表的所有节点的值进入栈中时，栈顶值也就是反转前的链尾值，然后直接返回栈顶节点即可。
下面是入栈核心代码，当栈顶为空时创建一个栈顶节点，oldfirst保存旧栈顶节点，新建一个栈顶节点，next指向旧栈顶。
public void add(int v)
{
if (first == null)
{
first = new ListNode(v);
}else {
ListNode oldfirst = first;
first = new ListNode();
first.val = v;
first.next = oldfirst;
}
}
下面是主要逻辑，循环遍历链表的值，添加到栈中，返回栈顶。
Stack q = new Stack();
public ListNode reverseList(ListNode head) {
if (head == null) return null;
while (head != null)
{
q.add(head.val);
head = head.next;
}
return q.get();
}
下面是全部代码：
class Solution {
public class Stack
{
ListNode first;
public void add(int v)
{
if (first == null)
{
first = new ListNode(v);
}else {
ListNode oldfirst = first;
first = new ListNode();
first.val = v;
first.next = oldfirst;
}
}
public ListNode get()
{
return first;
}
}
Stack q = new Stack();
public ListNode reverseList(ListNode head) {
if (head == null) return null;
while (head != null)
{
q.add(head.val);
head = head.next;
}
return q.get();
}
}
二、杨辉三角
LeetCode题目#118 杨辉三角
在做这题的时候，还没学过动态规划，所以使用的是队列解法。
我们将上一行的所有数入队，下一行的第一个数我们初始化为1，从第二个数开始等于上面两个数的和。
下面是全部代码，n是我们要返回的列表，queue是队列，外循环的i表示行列表索引，内循环的j表示第i行的数的索引，当i大于0也就是第二行的时候，将上一行入队，列表m每次循环都会new成新的列表，因为当时内循环出错，我将j等于1独立出来了，不知道这会不会有点多余。
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> n = new LinkedList<>();
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numRows; i++)
{
if(i > 0)
for(Integer num : n.get(i-1))
queue.offer(num);
List<Integer> m = new LinkedList<>();
m.add(1);
Integer tmp = null;
for (int j = 1; j < i+1; j++)
{
if (j == 1)
{
Integer x = queue.poll();
if( x == null) x = 0;
Integer y = queue.poll();
if( y == null ) y = 0;
m.add(x+y);
tmp = y;
}else {
Integer x = tmp;
Integer y = queue.poll();
if( y == null ) y = 0;
m.add(x+y);
tmp = y;
}
}
n.add(m);
}
return n;
}
}
三、爬楼梯
LeetCode题目#70 爬楼梯
这是改变命运的一题，一开始我使用暴力解法，发现最多只能计算到40阶，最后只能跑去hello算法学动态规划了，学成归来，发现这题挺简单的。
1111
211
121
112
发现一个2可以取代两个1，2可以在1号位、2号位、3号位，也就是数学题，从3个不同的球之中拿1个，有多少种组合。
来个循环，外面定义1的数量，2的数量，里面每次循环1数量-2，2数量+1，然后 ans=ans+C(1数量+2数量，2数量)，当然1数量小于2数量时，ans=ans+C(1数量+2数量，1数量)，但是阶乘到后面会非常非常大，也是失败了好吧。
我理解的动态规划：问题可以从前往后推，有初始状态。小的问题会决定大的问题，也就是状态转移。重点是在问题中找出规律，合理设计dp表和状态转移方程。
我是在Hello算法学动态规划才知道他的规律的，尴尬了，到n-1阶加上到n-2阶的方式就等于到n阶的方式，这就是状态转移。
下面是Hello算法中dp解法的代码，一开始看dp的理论还是有点懵的，看了代码之后思路就清晰了。
/* 爬楼梯：动态规划 */
int climbingStairsDP(int n) {
if (n == 1 || n == 2)
return n;
// 初始化 dp 表，用于存储子问题的解
int[] dp = new int[n + 1];
// 初始状态：预设最小子问题的解
dp[1] = 1;
dp[2] = 2;
// 状态转移：从较小子问题逐步求解较大子问题
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
四、杨辉三角 II
LeetCode题目#119 杨辉三角 II
好吧，别怪我太水，把第一代杨辉三角代码的循环条件和返回值改一下即可，因为第一代的参数是从1开始的，第二代的参数是从0开始的。
下面是第二代的代码
class Solution {
public List<Integer> getRow(int rowIndex) {
List<List<Integer>> n = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < rowIndex+1; i++)
{
if(i > 0)
for(Integer num : n.get(i-1))
queue.offer(num);
List<Integer> m = new ArrayList<>();
m.add(1);
Integer tmp = null;
for (int j = 1; j < i+1; j++)
{
if (j == 1)
{
Integer x = queue.poll();
if( x == null) x = 0;
Integer y = queue.poll();
if( y == null ) y = 0;
m.add(x+y);
tmp = y;
}else {
Integer x = tmp;
Integer y = queue.poll();
if( y == null ) y = 0;
m.add(x+y);
tmp = y;
}
}
n.add(m);
}
return n.get(rowIndex);
}
}
五、斐波那契数
LeetCode题目#509 斐波那契数
动态规划解法
初始状态：
dp[0] = 0;
dp[1] = 1;
状态转移：
dp[i] = dp[i-1] + dp[i-2];
下面是全部代码，当然也是可以优化一下空间的，为了方便理解就不整这个了：
class Solution {
public int fib(int n) {
if (n == 0 || n == 1) return n;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i < n+1; i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
六、最长相邻不相等子序列 I
LeetCode题目#2900 最长相邻不相等子序列 I
题目话太多了，估计是给第二代铺垫。
主打一个不相等，我们先在循环外面使用一个变量记录groups数组的第一个元素，循环里面的i表示索引，判断当groups数组中有和上一个记录的groups元素不一样时，把words的索引i元素add进列表，刷新记录为groups的索引i元素。
下面是全部代码：
class Solution {
public List<String> getLongestSubsequence(String[] words, int[] groups) {
List<String> seq = new ArrayList<>();
seq.add(words[0]);
if (words.length == 1) return seq;
int f = groups[0];
for (int i = 1; i < groups.length; i++)
{
if (groups[i] != f)
{
seq.add(words[i]);
f = groups[i];
}
}
return seq;
}
}
七、比特位计数
LeetCode题目#338 比特位计数
0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000
可以看到2、4、8、16二进制的1的数量是1个，而前面的最高位数刚好是他们的0的个数。
将他们的索引记录下来，ret = i，后面的就是ans[i]=ans[i-ret] + 1。
下面是全部代码：
class Solution {
public int[] countBits(int n) {
if (n == 0) return new int[]{0};
if (n == 1) return new int[]{0,1};
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
int ret = 0;
for (int i = 2; i <= n; i++)
{
if (i%2 == 0 && dp[i/2] == 1)
{
dp[i] = 1;
ret = i;
}else {
dp[i] = dp[i - ret] + 1;
}
}
return dp;
}
}
八、括号生成
LeetCode题目#22 括号生成
n = 4
( ( ( ( ) ) ) ) 前面4个(
( ( ( ) ( ) ) ) 前面3个(
( ( ( ) ) ( ) )
( ( ( ) ) ) ( )
( ( ) ( ( ) ) ) 前面2个(
( ( ) ( ) ( ) )
( ( ) ( ) ) ( )
( ( ) ) ( ( ) )
( ( ) ) ( ) ( )
( ) ( ( ( ) ) ) 前面1个(
( ) ( ( ) ( ) )
( ) ( ( ) ) ( )
( ) ( ) ( ( ) )
( ) ( ) ( ) ( )
n = 4
dp[]数组记录\(的位置
结束，最终的结果
[0,2,4,6]
开始
[0,1,2,3]
[0,1,2,4]
[0,1,2,5]
[0,1,2,6]
[0,1,3,4]
[0,1,3,5]
[0,1,3,6]
[0,1,4,5]
[0,1,4,6]
[0,2,3,4]
。。。
思路:初始状态前面n个\(,后面n个\),状态转移,x从1开始,dp[n-x]循环加1,倒数第x个数不能大于2n-2x,如果等于2n-2x时,x+1
下面是根据数组记录的位置生成括号组合的代码，i是遍历输出字符串，x是记录的索引：
String str = new String();
int x = 0;
for (int i = 0; i < n*2; i++)
{
if (x < n && i == dp[x])
{
str = str + "(";
x = x + 1;
}else {
str = str + ")";
}
}
raw.add(str);
下面是生成括号位置记录的代码，ret的作用：倒数第ret个记录，里面还有个for循环作用是将倒数第ret个记录后面的记录等于前面的加1。当ret等于n时结束，返回结果：
int ret = 1;
while (true)
{
if (dp[n - ret] != 2 * n - 2 * ret)
{
dp[n - ret] = dp[n - ret] + 1;
for (int j = ret-1; j > 0; j-- )
{
dp[n-j] = dp[n-j-1] + 1;
}
break;
}else if(ret == n)
{
return raw;
}
ret = ret + 1;
}
下面是全部代码，好吧，模块化编程的代码量的确是有点多，把自己尬住了：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> raw = new ArrayList<>();
if (n == 1)
{
raw.add("()");
return raw;
}
int[] dp = new int[n];
for (int i = 0; i < n; i++)
{
dp[i] = i;
}
while(true)
{
String str = new String();
int x = 0;
for (int i = 0; i < n*2; i++)
{
if (x < n && i == dp[x])
{
str = str + "(";
x = x + 1;
}else {
str = str + ")";
}
}
raw.add(str);
int ret = 1;
while (true)
{
if (dp[n - ret] != 2 * n - 2 * ret) {
dp[n - ret] = dp[n - ret] + 1;
for (int j = ret-1; j > 0; j-- )
{
dp[n-j] = dp[n-j-1] + 1;
}
break;
}else if(ret == n)
{
return raw;
}
ret = ret + 1;
}
}
}
}
九、最小路径和
LeetCode题目#64 最小路径和
我们记录每一个位置的最小总和
初始状态
int[][] dp = new int[row][col];
dp[0][0] = grid[0][0];
状态转移
if (i==0&&j==0) continue;
else if (i==0) dp[i][j] = dp[i][j-1] + grid[i][j];
else if (j==0) dp[i][j] = dp[i-1][j] + grid[i][j];
else dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
下面是全部代码：
import static java.lang.Math.min;
class Solution {
public int minPathSum(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
if (row == 1 && col == 1) return grid[0][0];
int[][] dp = new int[row][col];
dp[0][0] = grid[0][0];
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (i==0&&j==0) continue;
else if (i==0) dp[i][j] = dp[i][j-1] + grid[i][j];
else if (j==0) dp[i][j] = dp[i-1][j] + grid[i][j];
else dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
}
}
return dp[row-1][col-1];
}
}
十、不同的二叉搜索树 II
LeetCode题目#95 不同的二叉搜索树 II
发现节点值为n的节点只能放在上一个1->n-1 树的根节点的右上方和所有最右节点的右子节点,由于上一个树可以延伸出很多1->n 树,所以给每一个延伸情况复制一份上一个1->n-1 树,然后计算有多少个最右非空节点，再循环插入节点
递归复制二叉树
TreeNode newroot;
public TreeNode copy(TreeNode oldnode,TreeNode newnode)
{
if (oldnode == null)
{
newnode = null;
return null;
}
newnode.val = oldnode.val;
if (oldnode.left != null)
{
newnode.left = new TreeNode();
copy(oldnode.left,newnode.left);
}
if (oldnode.right != null)
{
newnode.right = new TreeNode();
copy(oldnode.right,newnode.right);
}
return newroot;
}
初始状态
List<TreeNode> dp = new ArrayList<>();
dp.add(new TreeNode(1));
第一次添加节点，放在右上方
TreeNode add = new TreeNode(i);
newroot = new TreeNode();
add.left = copy(oldroot,newroot);
tmp.add(add);
看看有多少个非空最右节点
newroot = new TreeNode();
int rightnum = 1;
TreeNode tmpnew = copy(oldroot,newroot);
while (tmpnew.right != null)
{
rightnum = rightnum + 1;
tmpnew = tmpnew.right;
}
循环添加节点，还要判断右节点是否为空，判断大小决定子树放在左边还是右边，不知道最后的if分支会不会有点多余
for (int j = 1; j <= rightnum; j++)
{
add = new TreeNode(i);
newroot = new TreeNode();
newroot = copy(oldroot,newroot);
TreeNode cur = newroot, pre = null;
for (int x = 1; x <= j; x++)
{
pre = cur;
cur = cur.right;
}
if (cur == null)
{
pre.right = add;
}else if (cur.val < i){
pre.right = add;
add.left = cur;
}else {
pre.right = add;
add.right = cur;
}
tmp.add(newroot);
}
下面是所有代码，尴尬了，做完这题之后，我决定去学习一下深度优先搜索
class Solution {
TreeNode newroot;
public TreeNode copy(TreeNode oldnode,TreeNode newnode)
{
if (oldnode == null)
{
newnode = null;
return null;
}
newnode.val = oldnode.val;
if (oldnode.left != null)
{
newnode.left = new TreeNode();
copy(oldnode.left,newnode.left);
}
if (oldnode.right != null)
{
newnode.right = new TreeNode();
copy(oldnode.right,newnode.right);
}
return newroot;
}
public List<TreeNode> generateTrees(int n) {
List<TreeNode> dp = new ArrayList<>();
dp.add(new TreeNode(1));
if (n==1)
{
return dp;
}
for (int i = 2; i <= n; i++)
{
List<TreeNode> tmp = new ArrayList<>();
for (TreeNode oldroot : dp)
{
TreeNode add = new TreeNode(i);
newroot = new TreeNode();
add.left = copy(oldroot,newroot);
tmp.add(add);
newroot = new TreeNode();
int rightnum = 1;
TreeNode tmpnew = copy(oldroot,newroot);
while (tmpnew.right != null)
{
rightnum = rightnum + 1;
tmpnew = tmpnew.right;
}
for (int j = 1; j <= rightnum; j++)
{
add = new TreeNode(i);
newroot = new TreeNode();
newroot = copy(oldroot,newroot);
TreeNode cur = newroot, pre = null;
for (int x = 1; x <= j; x++)
{
pre = cur;
cur = cur.right;
}
if (cur == null)
{
pre.right = add;
}else if (cur.val < i){
pre.right = add;
add.left = cur;
}else {
pre.right = add;
add.right = cur;
}
tmp.add(newroot);
}
}
dp = tmp;
}
return dp;
}
}
十一、所有可能的真二叉树
LeetCode题目#894 所有可能的真二叉树
做完上一题之后，我专门去看了同为1ms的标准答案，使用了深度优先搜索，代码量是真的少，通过之前的一些积累和上一题的标准答案代码逻辑，这题就借鉴一下上一题的标准答案吧。
我目前理解的深度优先搜索，一般使用递归实现，因为内存的栈中各同名方法和同名局部变量相互隔离，所以可以很好地分解问题，由深及近，先解决深部根本的问题，再解决浅部表面的问题，返回条件一般反映了问题的最深状态。
n=5
1 2 3 4 5
1 (2) 3 4 5 || 1 2 3 (4) 5
n>1真二叉树的根节点只能是第偶数个
问题被分解为(1)和(3 4 5)
(1)就是问题的最深状态,(3 4 5)继续分解
3 (4) 5
(3) (5)
以上就是根节点为2的问题分解情况
下面是全部代码，最外面的for循环遍历第偶数个根节点，第二层循环为分解的左子问题，第三层循环为分解的右子问题。当然这可能有一些重复操作，可以适当的剪枝，但是为了方便理解，就不整这个了。
class Solution {
public List<TreeNode> allPossibleFBT(int n) {
if (n % 2 == 0) return new ArrayList<>();
return dfs(n);
}
public List<TreeNode> dfs(int n)
{
List<TreeNode> ans = new ArrayList<>();
if (n == 1)
{
TreeNode dark = new TreeNode(0);
ans.add(dark);
}
for (int i = 2; i < n; i+=2)
{
for (TreeNode x : dfs(i-1))
{
for (TreeNode y : dfs(n-i))
{
TreeNode root = new TreeNode(0);
root.left = x;
root.right = y;
ans.add(root);
}
}
}
return ans;
}
}
十二、跳跃游戏
LeetCode题目#55 跳跃游戏
终于到了贪心题，在做完这道题之前我对贪心的概念还挺模糊的，依稀记得在抖音刷视频的时候看到一个博主分享的一个"找零钱"问题，先选择面值最大的，再从剩下的选择面值最大的，难道贪心真的选最大的就可以了吗，带着这个问题，我尝试去做这道题。
当没办法跳过可用步数为0的位置时就会出现无法跳到终点的情况。我不想一个个地遍历数组，所以我选择每到一个位置直接跳可用的最大步数即可，当跳到0的时候，回头寻找可以跳过这个0的位置，直到到达终点为止。
判断当前位置是否可以跳到终点，可以的话跳出循环，返回true
int n = nums[i];
if (i+n >= nums.length-1) break;
当跳到0时
for (int j = nums[i]-1; j>=i*(-1); j--) //j表示到原地的相对位置，向前为正，原地为0，向后为负
{ //从可用步数减一开始，i*(-1)数组的第一个元素
if (nums[i+j] > nums[i]-j) //nums[i]-j是递增的，表示必须大于它才能跳过0，找到了就说明可以跳过
{
i = i+j+nums[i+j];
break;
}else if (j == i*(-1)) return false; //直到回到第一个元素，返回false
}
下面是全部代码，这真是贪心吗，看看第二代
class Solution {
public boolean canJump(int[] nums) {
if (nums.length==1) return true;
if (nums[0] == 0) return false;
int i = 0;
while (i<nums.length)
{
int n = nums[i];
if (i+n >= nums.length-1) break;
if (nums[i+n] != 0 )
{
i = i+nums[i];
}else {
for (int j = nums[i]-1; j>=i*(-1); j--)
{
if (nums[i+j] > nums[i]-j)
{
i = i+j+nums[i+j];
break;
}else if (j == i*(-1)) return false;
}
}
}
return true;
}
}
十三、跳跃游戏 II
LeetCode题目#45 跳跃游戏 II
我们每次跳跃都回头寻找比当前跳跃的价值还大的位置，这样就能找到最小跳跃数了。
寻找能获得最多价值的位置
int MAXi = i+nums[i]; //记录比i的价值更大瓶.
for (int j = nums[i]-1, n = nums[i+nums[i]]+1,dev = 0; j>0; j--,n++)//j的作用和上一题相同，最小回到原地
{ //n等于原本跳跃获得的步数加1，每次往回寻找下一个，n要加1，去i+j的价值要大于n才值得
if (nums[i+j] > n && nums[i+j]-n > dev) //dev记录了目前能获得的最大价值
{
dev = nums[i+j]-n;
MAXi = i+j;
}
}
i = MAXi;
ans++;
下面是全部代码，所以贪心要的不是最大值，而是最大的价值吗，这要去Hello算法寻找一下答案
class Solution {
public int jump(int[] nums) {
int ans = 0;
if (nums.length == 1) return ans;
int i = 0;
while (i<nums.length)
{
if (i+nums[i] >= nums.length-1)
{
ans++;
break;
}
if (nums[i] == 1)
{
i++;
ans++;
continue;
}
int MAXi = i+nums[i];
for (int j = nums[i]-1, n = nums[i+nums[i]]+1,dev = 0; j>0; j--,n++)
{
if (nums[i+j] > n && nums[i+j]-n > dev)
{
dev = nums[i+j]-n;
MAXi = i+j;
}
}
i = MAXi;
ans++;
}
return ans;
}
}
总结
这几周的刷题让我收获良多，学习了动态规划、深度优先搜索、贪心等算法，也提高了代码熟练度。
当然也引出了许多问题，是否需要花时间去把答案做到0ms，还有比赛和实习临近，我应该如何把控时间，虽然我是网络安全专业的，但是我更爱算法。
虽然说兴趣是最好的老师，到底是不是这块料，通过实践，它会把你按在太阳底下暴晒。文章来源：https://www.toymoban.com/news/detail-851528.html
路漫漫其修远兮，吾将上下而求索。文章来源地址https://www.toymoban.com/news/detail-851528.html
到了这里，关于快来看看萌新小白学习动态规划、深度优先搜索、贪心的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
