刷题，启动！！！-CSDN博客

原创秋叶收藏集

对于状态1来说即dp[i][0](0代表状态1，后续以此类推）,dp[i][0] = dp[i-1][0] + isyellow;同理，dp[i][2] = min(dp[i-1][1], dp[i-1][2]) + isyellow。最后，由于状态的数量不能大于叶子的数量，所以dp[0][1] = dp[0][2] = dp[1][2] = INT_MAX;边界条件为：第0个叶子必须为红色。

2024-03-06 17:02:19 413 1

这时候想到了在开辟一个maxjump[k]数组，代表了跳跃k步能到达的最远距离（k是单调递增的），这时候f[i]的更新就需要两个因素了：f[i] = min(f[i], k + 1,f[j]+jump[j])~~(j是i前序通过一步正好到达i的节点）。最后就是k的更新，k是用来索引maxjump【k】的，maxjump[k]是单调递增的，当i > maxjump[k] 时，也就是当前跳跃步数k 无法到达当前位置或其右侧的时候，就无法 k + 1 部来更新f[i] l了，所以此时需要将++k。

2024-03-01 12:21:52 300 1

原创剧情触发时间

首先想到暴力解法，每次从0递增C、R和H，每次遍历时将满足条件的剧情触发时间修改即可。然后遍历剧情，在循环内部二分查找满足剧情的最低天数即可，这样时间复杂度就变成了O（mlogn）。根据所给信息，请计算每个剧情的触发时间，并以一个数组返回。如果某个剧情不会被触发，则该剧情对应的触发时间为 -1。在战略游戏中，玩家往往需要发展自己的势力来触发各种新的剧情。这个二维数组的每个元素是一个长度为 3 的一维数组，对于某个剧情的触发条件。来表示每天的增加情况。在游戏开始时（第 0 天），三种属性的值均为 0。

2024-02-28 16:05:47 330 1

原创子集问题！

我们可以看到如【1,2】的子集有【】、【1】、【2】、【1,2】。而【1,2,3】的子集比【1,2】的子集多出了【3】、【1,3】、【2,3】、【1,2,3】。所以对于子集问题，可以当做是其前序子集的扩展。只需要层层添加扩展即可，而扩展又依赖于前序。，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

2024-02-21 16:41:16 369

原创二叉树中的最大路径和

例如我们看值为20的这颗子树，它首先能贡献在这颗子树中最大路径为15->20->7，和为42。同时它能向自己的父亲节点贡献20->15 = 20 + 15 = 35 的经过根节点的最大路径和。所以，想到了递归遍历，首先计算这颗子树自己的贡献1（需要利用这颗子树的左右子树的贡献2），然后向上层调用者返回这颗子树自己贡献2。可以看到此题不同于一般的最大路径问题，因为可以从任意节点出发到任意节点结束并且只需要无重复节点和相邻节点存在直连边。被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。

2024-02-18 19:15:33 398

原创合并K个升序链表

对于两个升序链表的情况，我们很容易想到只需要利用两个指针将较小的元素放入新链表再后移相应指针，直到连个链表遍历完毕。对于n个链表，自然还可以想到利用n个指针，通过比较n个指针指向的链表元素大小，将最小的指针指向的元素填入新链表并后移当前指针即可。由此我们新建vector容器存储n个指针，只要容器不为空我们就寻找最小元素的指针并后移，当相应指针为空时代表链表遍历完毕，就把这个链表从容器内移除，当容器为空时，所有链表的元素都以排好序。请你将所有链表合并到一个升序链表中，返回合并后的链表。

2024-02-17 18:00:03 338

原创不同路径问题

任意一点只能从这个点的左侧点或是上侧点到达，即到达当前点的路径条数=达到左侧点的路径条数+到达上侧面的路径条数，这就满足了无后效性问题。同时满足子问题重叠与最优子结构特点。由此想到了动态规划方法。网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

2024-02-12 16:56:00 373

weixin_45523677的博客