文章目录
- day4_26
- 最长回文子串
- 思路:
- 代码:
- **DP30** **买卖股票的最好时机(一)**
- 思路:贪心
- 代码:
- 过河卒
- 思路:动态规划---路径类
- 代码:
day4_26
https://www.nowcoder.com/questionTerminal/12e081cd10ee4794a2bd70c7d68f5507
最长回文子串
思路:
空间扩展算法
1.枚举中心位置的时候,要考虑回文串长度的奇偶性
- 奇数,枚举的数在中心,left,right在两边去扩展
- 偶数,left在i的位置上,right在i的右边,进行扩展
2.如何计算长度
right-left-1
代码:
public int getLongestPalindrome(String s) {
int n = s.length();
int ans = 0;
for (int i = 0; i < n; i++) {
int left = i - 1;
int right = i + 1;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
ans = Math.max(ans,right-left-1);
left = i;
right = i+1;
while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
ans = Math.max(ans,right-left-1);
}
return ans;
}
DP30 买卖股票的最好时机(一)
https://www.nowcoder.com/practice/351b87e53d0d44928f4de9b6217d36bb?tpId=230&tqId=39767&ru=/exam/oj
思路:贪心
1.用一个变量来表示,当前位置的前驱最小值
2.每输入一个数,更新当前的最小利润
3.跟新最小值
代码:
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int ret = 0;
int x = 0;
int prevMin = in.nextInt();
for (int i = 1; i < n; i++) {
x = in.nextInt();
ret = Math.max(ret,x-prevMin);
prevMin = Math.min(prevMin,x);
}
System.out.println(ret<0?0:ret);
}
过河卒
https://ac.nowcoder.com/acm/problem/16708
思路:动态规划—路径类
1.状态表示:dp[i] [j] 表示从00位置出发,到达ij位置,一共有多少种方法。
2.状态转移方程:dp[i] [j] = dp[i-1] [ j] +dp[i] [j-1]
3.如果是马所能到达的位置,就为0
4.初始化: dp表规模(n+2)*(m+2).dp[0] [1]==1 || dp[1] [0] ==1
5.填表:dp[n+1] [m+1];
代码:
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int x = in.nextInt();
int y = in.nextInt();
int[][] dp = new int[n + 2][m + 2];
dp[0][1] = 1;
x += 1;
y += 1;
for (int i = 1; i <= n + 1; i++) {
for (int j = 1; j <= m + 1; j++) {
if (i != x && j != y && Math.abs(i - x) + Math.abs(j - y) == 3 || (i == x && j == y)) {
dp[i][j] = 0;
}else {
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
}
System.out.println(dp[n+1][m+1]);
}
点击移步博客主页,欢迎光临~