ParKS

刷题

3C(1) ARPG系列(42) C+基础(4) Shader(13) Unity程序框架(17) 地编-饥荒(13) 实用工具(9) 序言(1) 战斗系统(6) 未归档(3) 计算机图形学(6) 计算机网络(2)

/ 注册

全部文章 / 刷题（共57篇）

[代码随想录一刷] day42 动态规划来自专栏

01背包问题，你该了解这些！ dp[i][j]：从0到i号物品，容量上限为j的最大收益。 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]),取或者不取当前第i个物品。 dp[i][0] = 0，容量为0收益为0,dp...

2023-05-31

0 248

[代码随想录一刷] day41 动态规划来自专栏

343. 整数拆分 dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)); 要么拆两个直接乘，要么拆两个及以上。初始化：dp[2] = 1,注意拆0和1没意义。遍历顺序，从前往...

2023-05-31

0 242

[代码随想录一刷] day39 动态规划来自专栏

62.不同路径 dp[i][j]是从（0, 0）出发走到(i, j)的不同路径数. 限定了只能向右或者向下走，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，初始化边界的路径数都为1，遍历顺序从左上到右下每层遍历。注意小trick，结果是dp[m - 1]...

2023-05-31

0 270

[代码随想录一刷] day38 动态规划来自专栏

理论基础动态规划五步骤：确定dp数组（dp table）以及下标的含义确定递推公式 dp数组如何初始化确定遍历顺序举例推导dp数组验证 509. 斐波那契数按五步走，dp数组为第i个数的斐波那契数值是dp[i]，地推公式和初始化已给，顺序遍历。 //C++ class Solutio...

2023-05-31

0 227

[代码随想录一刷] day37 贪心算法来自专栏

738.单调递增的数字想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了。注意实际上是之后的都要为9 想到了贪心，还要考...

2023-05-31

0 236

[代码随想录一刷] day36 贪心算法来自专栏

435. 无重叠区间和打气球类似，根据左边界排序，找重叠就跳结果+1，更新最小右边界。需要注意的是，左边界排序再对右边界排序不能取代更新最小右边界，因为存在左边界更大，右边界也更小也是要更新的。 class Solution { public: static bool cmp(vecto...

2023-05-30

0 276

[代码随想录一刷] day35 贪心算法来自专栏

860.柠檬水找零分三种情况，5就收，10找一张5,20优先找1张10一张5（贪心），再考虑三张5. class Solution { public: bool lemonadeChange(vector<int>& bills) { int five ...

2023-05-30

0 232

[代码随想录一刷] day34 贪心算法来自专栏

1005.K次取反后最大化的数组和用两次贪心，第一次先把负数都转过来，第二次如果k还有剩的为奇数再把最小的正数转过来。注意负数转过来后可能会产生更小的正数，所以一开始排序要不然按绝对值排序，要不然转过来之后再排序一次。注意一点，选当前点前面的起始点相当于多了油量，二刷借此想法看看第一种全局的...

2023-05-29

1 288

[代码随想录一刷] day32 贪心算法来自专栏

122.买卖股票的最佳时机II 将整体利润拆分为每天的利润（两天为一个单位），然后只收集正利润。注意不是最长递增序列，可以跳着卖，只要在正利润区间卖出即可。 class Solution { public: int maxProfit(vector<int>& price...

2023-05-29

0 221

[代码随想录一刷] day31 贪心算法来自专栏

将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解这个四步其实过于理论化了，我们平时在做贪心类的题目很难去按照这四步去思考，真是有点“鸡肋”。做题的时候，只要想清楚局部最优是什么，如果推导出全局最优，其实就够了。 455.分发饼干大胃口先...

2023-05-08

0 361