冲刺大厂每日算法&面试题，动态规划21天——第十七天 导读

发表于

「这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战」

导读

在这里插入图片描述

肥友们为了更好的去帮助新同学适应算法和面试题，最近我们开始进行专项突击一步一步来。我们先来搞一下让大家最头疼的一类算法题，动态规划我们将进行为时21天的养成计划。还在等什么快来一起肥学进行动态规划21天挑战吧！！

21天动态规划入门

给你一个字符串 s，找到 s 中最长的回文子串。

1
2
3
4
5
java复制代码示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
1
2
3
4
java复制代码示例 2：

输入：s = "cbbd"
输出："bb"
1
2
3
4
java复制代码示例 3：

输入：s = "a"
输出："a"
1
2
3
4
java复制代码示例 4：

输入：s = "ac"
输出："a"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
java复制代码class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        //从串的第一个元素为中心扩散
        for (int i = 0; i < s.length(); i++) {
            //以奇数子串为前提开始
            int len1 = expandAroundCenter(s, i, i);
            //以偶数子串为前提
            int len2 = expandAroundCenter(s, i, i + 1);
            //比较两者谁更大
            int len = Math.max(len1, len2);
            //找到新串的位置
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    public int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;
    }

    
}

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

1
2
3
4
5
java复制代码示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
1
2
3
4
5
java复制代码示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
java复制代码对于一个子序列而言，如果它是回文子序列，并且长度大于 22，那么将它首尾的两个字符去除之后，它仍然是个回文子序列。因此可以用动态规划的方法计算给定字符串的最长回文子序列。

用 \textit{dp}[i][j]dp[i][j] 表示字符串 ss 的下标范围 [i, j][i,j] 内的最长回文子序列的长度。假设字符串 ss 的长度为 nn，则只有当 0 \le i \le j < n0≤i≤j<n 时，才会有 \textit{dp}[i][j] > 0dp[i][j]>0，否则 \textit{dp}[i][j] = 0dp[i][j]=0。

由于任何长度为 11 的子序列都是回文子序列，因此动态规划的边界情况是，对任意 0 \le i < n0≤i<n，都有 \textit{dp}[i][i] = 1dp[i][i]=1。

当 i < ji<j 时，计算 \textit{dp}[i][j]dp[i][j] 需要分别考虑 s[i]s[i] 和 s[j]s[j] 相等和不相等的情况：

如果 s[i] = s[j]s[i]=s[j]，则首先得到 ss 的下标范围 [i+1, j-1][i+1,j−1] 内的最长回文子序列，然后在该子序列的首尾分别添加 s[i]s[i] 和 s[j]s[j]，即可得到 ss 的下标范围 [i, j][i,j] 内的最长回文子序列，因此 \textit{dp}[i][j] = \textit{dp}[i+1][j-1] + 2dp[i][j]=dp[i+1][j−1]+2；

如果 s[i] \ne s[j]s[i] 

​
 =s[j]，则 s[i]s[i] 和 s[j]s[j] 不可能同时作为同一个回文子序列的首尾，因此 \textit{dp}[i][j] = \max(\textit{dp}[i+1][j], \textit{dp}[i][j-1])dp[i][j]=max(dp[i+1][j],dp[i][j−1])。

由于状态转移方程都是从长度较短的子序列向长度较长的子序列转移，因此需要注意动态规划的循环顺序。

最终得到 \textit{dp}[0][n-1]dp[0][n−1] 即为字符串 ss 的最长回文子序列的长度。


class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            char c1 = s.charAt(i);
            for (int j = i + 1; j < n; j++) {
                char c2 = s.charAt(j);
                if (c1 == c2) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

面试题

继续二叉树的阶段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
java复制代码//构建节点类
package tree;

public class node {
	public int val;
	public node left;//左孩子
	public node right;//右孩子
	public node() {
		
	}
	public node(int val,node left,node right) {
		this.val=val;
		this.left=left;
		this.right=right;
	}
	public node(int val, node left) {
		super();
		this.val = val;
		this.left = left;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
java复制代码package tree;

public class nodeNum {
	//全部节点个数
	public static int nodenum(node root) {
		if(root==null)return 0;
		int left=nodenum(root.left);
		int right=nodenum(root.right);
		
		return left+right+1;
	}
	//叶子节点个数
	public static int leafNodeNum(node root) {
		if(root==null)return null;
		if(root.left==null&&root.right==null) {
			return 1;
		}
		return leafNodeNum(root.left)+leafNodeNum(root.right);
	}
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%