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 7
After 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]; } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
方向选择(嵌入式 大数据 java)
时间匆匆,不知不觉大二后半期了。晚上开了会要确定方向选择,嵌入式,大数据,java三个方向。 犹豫了好久,因为学了一段时间的java还是偏向于java的 不过也想学大数据,因为最近很火 大家都 知道的。现在来简单介绍一下吧! 嵌入式:单片机之类的 比如指纹解锁底层就是此技术,反正就是和硬件打交道。 大数据:最近很火的概念技术 有点玄玄乎乎的,前途不好定义,不过门槛也是高的,对算法之类的要求还是比较高的 主要挖掘爬取数据。而且学历方面也是比较高,本人二本计科 ,学历上已经落后了,技术其次考虑。 大数据 人工智能,算法 我们这些二本院校的人 可能不受大公司优先考虑,毕竟有更好的学校的毕业生,简历敲门砖都不行,技术先不考虑(因为还没有学,现在只是客观考虑方向问题) java:应用最广泛的一种语言,起码在中国前景还是不错的。服务器后台90%都是java的天下 就业路广泛,其实 大数据也是要有java基础的,网上也有很多java工程师转大数据的例子。 java有两大方向 一个是安卓 前几年很火 不过现在不行了;还有一个是JSP服务器后台,这个也是现在岗位最多的,外面公司都是量招的,还可以做微信小...
- 下一篇
Python远程连接服务器上的Oracle数据库
Python远程连接服务器上的Oracle数据库 1、正确的开启方式 在你的IPython或者是Anaconda的jupyter中输入一下代码,其中: ‘username’—— 用户名 ‘password’——密码 ‘192.168.1.1:1521/service_name’——IP/端口号/服务名称 import cx_Oracle conn = cx_Oracle.connect('username','password','192.168.1.1:1521/service_name') 如果以上代码不会报错,那么你应该是已经成功连接数据库了。而如果报错,检查一下是什么问题。 2、暴露问题 (1)cx_Oracle未安装 如果上位安装cx_Oracle包,可以在cmd状态下,到Python安装目录下,使用pip命令完成安装。 pip install cx_Oracle (2)缺少instanctclient 如果本机没有安装Oracle数据库,又要通过Python访问远程服务器上的Oracle,那么需要在本机上安装instantclient。安装可以从Oracle官网获取安装包,...
相关文章
文章评论
共有0条评论来说两句吧...