leetcode刷题记录

野性酷女 2022-10-31 15:53 151阅读 0赞

\*\*

## leetcode刷题记录 ##

\*\*  
别人的刷题记录：[leetcode题解一览表][leetcode]  
1052. 爱生气的书店老板  
看到了位置可选的长度为X的一个区间，马上要想到sliding window。

5.最长回文子串 [方法以及代码解释][Link 1]  
动态规划的状态转移：（以空间换时间的动态规划策略）  
动态规划的总结：

动态规划的三要素:最优子结构,边界和状态转移函数,最优子结构是指每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到(子问题的最优解能够决定这个问题的最优解),边界指的是问题最小子集的解(初始范围),状态转移函数是指从一个阶段向另一个阶段过度的具体形式,描述的是两个相邻子问题之间的关系(递推式)

重叠子问题,对每个子问题只计算一次,然后将其计算的结果保存到一个表格中,每一次需要上一个子问题解时,进行调用,只要o(1)时间复杂度,准确的说,动态规划是利用空间去换取时间的算法.

判断是否可以利用动态规划求解,第一个是判断是否存在重叠子问题,  
　　  
动态规划的使用：  
53. 最大子序和  
边界：如果为空，返回零。如果为一个，就为最大的。  
递归方式：dp来保存最大的结果，如果当前数值大于当前数值与原dp之和，则dp增加一个当前数值，否则就加入当前数值与原数值之和。  
198. 打家劫舍  
边界：空，一个的时候，两个数的时候。  
递归方式：dp.append(max(dp\[i-1\],dp\[i-2\]+nums\[i\]))  
121. 买卖股票的最佳时机  
边界：引入变量记录最小价格。空的时候跟只有一个数的时候。  
递归方式：dp.append(max(dp\[i-1\],prices\[i\]-min\_prices))从后面考虑，看后面的东西跟前面有什么区别。

<table> 
 <thead> 
  <tr> 
   <th>746</th> 
   <th>使用最小花费爬楼梯</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>边界：</td> 
   <td>从楼顶分析，比如说10为楼顶，到达楼顶只有两种方式，一种从第八层走两步到达，一种是从第九层走一步到达，因为该10为楼顶其：</td> 
  </tr> 
  <tr> 
   <td>递归方式：</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <th>120</th> 
   <th>三角形最小路径和</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>边界：</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>递归方式：</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <th>338</th> 
   <th>比特位计数</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>边界：</td> 
   <td>整个数组用来存放计数，当i为2的K次方时，就为1 循环的时候到数字加1 是否 加1容易迷</td> 
  </tr> 
  <tr> 
   <td>递归方式</td> 
   <td>1+res[i-2**k]</td> 
  </tr> 
 </tbody> 
</table>

[leetcode]: https://blog.csdn.net/weixin_40449300/article/details/89470836
[Link 1]: https://www.jianshu.com/p/6f226c9180e2