leetcode算法题解(Java版)-8-动态规划+状态压缩
一、树
题目描述
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set toNULL.
Initially, all next pointers are set toNULL.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL思路
- 题目的意思可能看文字有点不明白，没关系！看明白它给的两个图就行了，就是图上描绘的意思。
- 这道题有点像链表，二叉树中多了个链表，其实解法也应该往链表上去想，一般考虑用两个指针一个当前的，控制外部循环，一个是移动的，控制内部小循环。二叉树不断往下走，一边走一边从左向右实现同一层节点之间链表的链接
代码
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null){
return;
}
TreeLinkNode p=root;
TreeLinkNode q=root;
while(p.left!=null){
q=p;
while(q!=null){
q.left.next=q.right;
if(q.next!=null){
q.right.next=q.next.left;
}
q=q.next;
}
p=p.left;
}
return;
}
}二、动态规划
题目描述
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,"ACE"is a subsequence of"ABCDE"while"AEC"is not).
Here is an example:
S ="rabbbit", T ="rabbit"
Return3.
思路
- 又是典型的动态规划~~重新的复习了一下：
动态规划：
参考：CSDN
动态规划解题的一般思路：
- 将原问题分解为子问题：子问题和原问题类似
- 确定状态：即是dp数组，存储了子问题的状态
- 确定初始状态（边界）的值：这个需要想一下，但其实一般都是由套路的，比如都是0或者都是1。实在不知道，可以用几个值试一试
- 写出状态转移方程
动态规划解题的特点：
- 问题具有最优子结构：如果原问题的最优解也是子问题的最优解。
- 无后效性：当前的状态之和它之前的某些特定位置的状态有关，和路径等无关，即后来产生的值不会影响前面已经确定的值。
回到题目中来
- 好了，那么来看这一道题：首先可以分解为子问题，而且子问题的最优解也是原问题的最优解。
- dpi就是所谓的子问题，也是状态空间，表示S[0~i-1]中包含的T[0~j-1]的subsequences（这个定义看题目）数目。然后具体分析请看代码
- 推荐在草稿画出dp数组，一边看代码一边填dp。
代码
public class Solution {
public int numDistinct(String S, String T) {
int lenS=S.length();
int lenT=T.length();
if(lenS==0||lenT==0){
return 0;
}
int row=lenS+1;
int col=lenT+1;
int [][] dp=new int [row][col];
for(int i=1;i<col;i++){
dp[0][i]=0;
}
for(int j=0;j<row;j++){
dp[j][0]=1;
}
for(int i=1;i<row;i++){
//这里在纸上画字符串数组分析的时候，把字符串的下表可以从“1”开始，便于思维理解
for(int j=1;j<col;j++){
if(S.charAt(i-1)==T.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+dp[i-1][j];//这里可能稍微难理解，
//要记住这一步的目的是解决字符串可以是不连续的，只要满足在原来串中顺序不变即可称为subsequence
//结合这个区想这一步为啥这么相加，就能理解了，我是用这个笨方法想的。。。
}
else{
dp[i][j]=dp[i-1][j];//既然S[i-1]和T[j-1]不一样，那么不妨不要S[i]，
//可不能也不要T[j]噢，因为我们的目标是找到S中包含T的所有subsequences
}
}
}
return dp[row-1][col-1];
}
}状态压缩+细节优化过的代码
详细见代码注释，动态规划一般都是可以压缩一下状态的。
public class Solution {
public int numDistinct(String S, String T) {
int lenS=S.length();
int lenT=T.length();
if(lenS==0||lenT==0){
return 0;
}
int col=lenT+1;
int row=lenS+1;
int dp[]=new int[col];
for(int i=0;i<col;i++){
if(i==0){
dp[i]=1;
continue;
}
dp[i]=0;
}
for(int i=1;i<row;i++){
for(int j=j=Math.min(i,col-1);j>0;j--){
//其实这里还能再优化，写成 "j=Math.min(i,col-1)"
//因为S[0~i]不可能包含长度比他大的T[0~j]
if(S.charAt(i-1)==T.charAt(j-1)){
dp[j]=dp[j-1]+dp[j];
}
else{
dp[j]=dp[j];
}
}
}
return dp[col-1];
}
}
