【算法题解】

文章目录

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]);
    }