笔试——Day10

第一题

题目

最长回文子串

思路

中心拓展算法：
将每一个位置都作为中心点，向两边拓展，找到最大的长度；

• 遍历所有中心点：对于字符串中的每一个字符，分别作为奇数长度和偶数长度的回文中心进行扩展。例如，对于字符A[i]，奇数长度回文以A[i]为中心，偶数长度回文以A[i]和A[i+1]为中心。
• 更新最大长度：每次扩展后，比较当前回文长度与已知的最大长度，更新最大长度。

代码

第二题

题目：

买卖股票的最好时机(一)

思路

模拟：

• 栈用于存储当前遇到的最小值；
• 遍历数组：对于每个元素，检查栈是否为空或栈顶元素是否小于当前元素。
  • 如果是，则计算当前元素与栈顶元素的差值，并更新最大差值；
  • 否则，将当前元素压入栈中；
• 更新最大值

代码

第三题

题目：

过河卒

思路

动态规划：
标记⾛马脚位置的⽅法数为0

代码