1. maximum-subarray
题目描述：请计算给出的数组（至少含有一个数字）中具有最大和的子数组（子数组要求在原数组中连续）
例如：给出的数组为[−2,1,−3,4,−1,2,1,−5,4],
子数组[−2,1,−3,4,−1,2,1,−5,4],具有最大的和:6.
拓展： 如果你已经提出了O(n)的解决方法，请尝试使用分治算法来解决这道题。这道题分治的解法更巧妙一些。
解题思路： 基本思想是用两个指针first last,first固定 last后移，如果sum(from f to l)为负，sum(from f to l+1)为正，则更新begin = last+1,该操作能筛选掉列表起始和末尾的一部分元素，我只能想到这了，决定去看一下其他人的讨论。
问题的关键在于只求最大max，并不要求记录起止位置，让问题简单得多。
最终的思路是 ： 从头开始累加，直到和为负。此时前面这段不能给后面的串带来正收益，应舍弃，sum清零，然后在开始统计最大的sum.
public int maxSubArray(int[] A) {
int sum = 0, max = -65535, i, begin = 0, end = 0;
if(A.length==1) return A[0];
for(i = 0; i<A.length; i++){
sum+=A[i];
end ++;
if(sum>max) max = sum;
if(sum<0) sum = 0;
}
return max;
}依题意再考虑分治方法来求解，怎样？分解成什么样的子问题？来做呢，经过十分钟的思考之后，我还是想不出来，于是又双 refer to 讨论部分了。
于是————意外收获动态规划的思路，受了启发后，自己写了动规方法的代码。
/*利用动态规划做题。
* 只遍历数组一遍，当从头到尾部遍历数组A， 遇到一个数有两种选择 （1）加入之前subArray （2）自己另起一个subArray
* 设状态S[i], 表示以A[i]结尾的最大连续子序列和，状态转移方程如下:
* S[i] = max(S[i-1] + A[i],A[i])
* 从状态转移方程上S[i]只与S[i-1]有关，与其他都无关，因此可以用一个变量来记住前一个的最大连续数组和就可以了。
* 这样就可以节省空间了。
* 时间复杂度：O(n) 空间复杂度：O(1)
*/
public int maxSubArray(int[] A) {
int max = A[0], i, sum = 0;
for(i = 0; i<A.length; i++) {
if(sum+A[i] < A[i]) sum = A[i];
else sum += A[i];
if(max<sum) max = sum;
}
return max;
}学习了分治法求解本题的思想：
- 将列表从中间分开,将解的域分为三部分：
左边子列的最大和、右边子列的最大和、以及中间拼接部分的最大和 - 用递归的方法分别求出三个解，得出最优解。
public class Solution {
public int maxSubArray(int[] A) {
return divide(A, 0, A.length-1);
}
public int divide(int[] A, int left, int right){
int mid = (left+right)/2;
if(left==right) return A[left];
int i, res, max, sumL = A[mid], sumR = A[mid+1];
int maxL = divide(A, left, mid);
int maxR = divide(A, mid+1, right);
//mid左侧和
for(i = mid-1, max = sumL; i>=left; i--){
sumL += A[i];
if(max<sumL)
max = sumL;
}
sumL = max;
//mid右侧和
for(i = mid+2, max = sumR; i<=right; i++){
sumR += A[i];
if(max < sumR)
max = sumR;
}
sumR = max;
res = Math.max(maxL, maxR);
return res > (sumL+sumR) ? res : (sumL+sumR);
}
}2. jump-game
题目描述：给出一个非负整数数组，你最初在数组第一个元素的位置
数组中的元素代表你在这个位置可以跳跃的最大长度
判断你是否能到达数组最后一个元素的位置
例如
A =[2,3,1,1,4], 返回 true.
A =[3,2,1,0,4], 返回 false.
解题思路：每一次都条约最大长度，以求最快到达，如遇阻碍（该位置最大步长为0），则回退。在第i次跳跃中回退分为两种情况（1）在该步内回退，本步跳跃非最大步长（2）回退至上一步，重新选择下一步起点
由于所给数组是最大跳跃长度，所以在最远点以前的全部点都可达，回退只要i--即可，特别地，回退时记录该点是否已经回退过就可以，防止陷入无限循环。
提交之后说循环有错真的是最糟糕的情况，他又不告诉是什么样的样例才会使程序跳不出循环，也许这时候才是从头梳理思路的好时候吧，尽量不到IDE中去调试，找出这个样例。
public class Solution {
public boolean canJump(int[] A) {
//尽可能大跳，如遇=0截止，回退跳-1格
if(A.length==1) return true;
int jump = A[0], i = 0, flag = 1;
while(i<A.length){
//前进
i += jump;
//回退
if(jump == 0)
if(i-flag<=0)//回退到不能再退，失败
return false;
i -= flag;
flag ++;
}
if(i >= A.length-1) break;
jump = A[i];
}
return true;
}
}3. jump-game ii
题目描述：给出一个非负整数数组，你最初在数组第一个元素的位置
数组中的元素代表你在这个位置可以跳跃的最大长度
你的目标是用最少的跳跃次数来到达数组的最后一个元素的位置
例如
给出数组 A =[2,3,1,1,4]
最少需要两次才能跳跃到数组最后一个元素的位置。（从数组下标为0的位置跳长度1到达下标1的位置，然后跳长度3到数组最后一个元素的位置）
解题思路： 要得出最少的跳跃次数，设想到极端情况[2,10,1,1,2,1,1]，可以看出，要得到最终解，要回退遍历到所有的方案，记下最小值。过程中要记录的是：
- 当前在第几步，走了几格
- 上一步的状态
想到的就是在上题的基础上再多记录一些过程量，肯定代码更加繁琐。想看看更好的思路，refer to 讨论：
Then get 动态规划的思想，dp[i]存放的是到i点的最小步数。public class Solution { public int jump(int[] A) { //存放 第i步走j格达到的最大位置 int dp[] = new int[A.length]; int i,j,furthest; dp[0] = 0; for(i = 0; i<A.length; i++){ furthest = Math.min(A.length-1, i + A[i]); //拿到本次跳跃最远可达点 for(j = i+1; j<=furthest; j++){ //标记该步能走到的所有点 if(dp[j]==0) dp[j] = dp[i] + 1; //中间有冗余的标记过程，看到有大神直接省略掉了 } } return dp[A.length-1]; } }
4. gas-station
题目描述：
环形路上有n个加油站，第i个加油站的汽油量是gas[i]. 你有一辆车，车的油箱可以无限装汽油。从加油站i走到下一个加油站（i+1）花费的油量是cost[i]，你从一个加油站出发，刚开始的时候油箱里面没有汽油。求从哪个加油站出发可以在环形路上走一圈。返回加油站的下标，如果没有答案的话返回-1。
注意： 答案保证唯一。
解题思路： 遵循贪心的思想，确定贪心选择标准:store[i] = gas[i]-cost[i],只有唯一答案，于是只有最优解才能满足题意，即只有最开始就尽可能多地积累油量，才能到达终点，于是我想到的思路是求store的最大子段和，起始下标即为待返回的解。
利用反证法可证明该解是唯一最优解。
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int i, max = -65535, sum = 0, tag = 0;
int[] store = new int[gas.length];
for(i = 0; i<gas.length; i++){
store[i] = gas[i]-cost[i];
sum += store[i];
}
//失败返回-1
if(sum<0) return -1;
//求最大子段和的 起始下标
for(i = 0, sum=0; i<gas.length; i++){
sum = Math.max(store[i], sum+store[i]);
if(sum==store[i])
tag = i;
}
return tag;
}
}5. minimum-window-substring
题目描述：给出两个字符串S和T，要求在O（n）的时间复杂度内在S中找出最短的包含T中所有字符的子串。
例如：S ="ADOBECODEBANC" T ="ABC", 找出的最短子串为"BANC".
注意：
如果S中没有包含T中所有字符的子串，返回空字符串 “”；
满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。
**解题思路： 在我看过了讨论中大家的想法，自己也经历了很久的尝试之后，就觉得这道题自己不能用一种很简洁漂亮的思路完成求解。回头再看，不得不承认讨论中被大家称赞的思路已经是这道题比较清晰和简洁的逻辑了。以下代码来自用户 ballontt.
这道题的思路是：
1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。记录窗口长度d
2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被包含在窗口，
3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
4) 如此循环知道end到S中的最后一个字符。
时间复杂度为O(n)
public class Solution {
public String minWindow(String S, String T) {
int[] map = new int[128];
//init map, 记录T中每个元素出现的次数
for(int i = 0; i < T.length(); i++) {
map[T.charAt(i)]++;
}
// begin end两个指针指向窗口的首位，d记录窗口的长度， counter记录T中还有几个字符没被窗口包含
int begin = 0, end = 0, d = Integer.MAX_VALUE, counter = T.length(), head = 0;
// end指针一直向后遍历
while(end < S.length()) {
// map[] > 0 说明该字符在T中出现，counter-- 表示对应的字符被包含在了窗口，counter--, 如果s中的字符没有在T中出现，则map[]中对应的字符-1后变为负值
if(map[S.charAt(end++)]-- > 0) {
counter--;
}
// 当counter==0时，说明窗口已经包含了T中的所有字符
while (counter == 0) {
if(end - begin < d) {
d = end - (head = begin);
}
if(map[S.charAt(begin++)]++ == 0) { // begin开始后移，继续向后寻找。如果begin后移后指向的字符在map中==0，表示是在T中出现的，如果没有出现，map[]中的值会是负值。
counter++; // 在T中的某个字符从窗口中移除，所以counter++。
}
}
}
return d==Integer.MAX_VALUE ? "" :S.substring(head, head+d);
}
}6. unique-paths
题目描述：一个机器人在m×n大小的地图的左上角（起点，下图中的标记“start"的位置）。
机器人每次向下或向右移动。机器人要到达地图的右下角。（终点，下图中的标记“Finish"的位置）。
可以有多少种不同的路径从起点走到终点？
上图是3×7大小的地图，有多少不同的路径？
备注：m和n小于等于100
解题思路：
- 初始化dp[0][],dp[][0]=0
- 计算dp[i][j]从起点到ij格有dp[i][j]种不同路径
过于简单，就不贴代码了。
7. unique-paths ii
题目描述：继续思考题目"Unique Paths":
如果在图中加入了一些障碍，有多少不同的路径？
分别用0和1代表空区域和障碍
例如 下图表示有一个障碍在3*3的图中央。
[↵ [0,0,0],↵ [0,1,0],↵ [0,0,0]↵]
有2条不同的路径 备注：m和n不超过100.
解题思路：
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int i, j;
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m+1][n+1];
//初始化
for(i = 0; i<=m; i++)
dp[i][0] = 0;
for(i = 0; i<=n; i++)
dp[0][i] = 0;
for(i = 1; i<=m; i++)
for(j = 1; j<=n; j++){
if(obstacleGrid[i-1][j-1]==1) //障碍点dp[i][j]=0;
dp[i][j] = 0;
else if(i==1&&j==1) dp[i][j] = 1;
else
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
return dp[m][n];
}
}8. candy
题目描述： 有N个小朋友站在一排，每个小朋友都有一个评分
你现在要按以下的规则给孩子们分糖果：每个小朋友至少要分得一颗糖果
分数高的小朋友要他比旁边得分低的小朋友分得的糖果多,你最少要分发多少颗糖果？
解题思路：
从前向后一次，从后向前一次（特别的题目中要他比旁边得分低的小朋友分得的糖果多，没有说相等的情况就要一样多哦），没有看别人的解法，自己想出来的。解完发现大家刚巧都是这一样的思路，有点意思嗷。
public class Solution {
public int candy(int[] ratings) {
int i, min = 65535, sum = 0;
int[] candylist = new int[ratings.length];
//从前向后，处理所有递增序列
if(ratings.length==1) return 1;
for(i = 1; i<ratings.length; i++){
if(ratings[i]>ratings[i-1])
candylist[i] = candylist[i-1] + 1;
}
//从后向前，处理所有递减序列
for(i = ratings.length-2; i>=0; i--){
if(ratings[i]>ratings[i+1] && candylist[i]<=candylist[i+1])
candylist[i] = candylist[i+1] + 1;
}
//可能会有负值
for(i = 0; i<ratings.length; i++)
if(candylist[i]<min)
min = candylist[i];
//每一个元素加上gap令最小值为1
for(i = 0; i<ratings.length; i++){
candylist[i] += (0-min+1);
sum += candylist[i];
}
return sum;
}
}8. edit-distance
题目描述：
给定两个单词word1和word2，请计算将word1转换为word2至少需要多少步操作。
你可以对一个单词执行以下3种操作：
a）在单词中插入一个字符
b）删除单词中的一个字符
c）替换单词中的一个字符
解题思路：自己思考后，没有分析明白题目中的状态，于是看了讨论的解法，理解后自己再写的思路和代码，是一次很好的思维训练。
public class Solution {
public int minDistance(String word1, String word2) {
/* 这是很纯正用动态规划思想的一道题了，状态dp[i][j]:从word1的前i个字符变换到
* word2的前j个字符所用的最少操作数。
* word1(i)==word2(j) dp[i][j]=dp[i-1][j-1]
* !=的情况，选择删除、插入、替换三种操作中操作数最少的方案
* 注意dp[][]矩阵的初始化及其意义
*/
int i, j;
//特殊情况特殊处理
if(word1==null && word2==null)
return 0;
else if(word1==null)
return word2.length();
else if(word2==null)
return word1.length();
//dp初始化
int[][] dp = new int[word1.length()+1][word2.length()+1];
for(i = 0; i<=word1.length(); i++)
dp[i][0] = i;
for(i = 0; i<=word2.length(); i++)
dp[0][i] = i;
//计算dp[i][j]
for(i = 1; i<=word1.length(); i++)
for(j = 1; j<=word2.length(); j++){
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
}
return dp[word1.length()][word2.length()];
}
}9. gray-code
题目描述：
格雷码是一种二进制编码系统，如果任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。
给定一个非负整数n，表示代码的位数，打印格雷码的序列。格雷码序列必须以0开头。
例如：给定n=2，返回[0,1,3,2]. 格雷码的序列为：
00 - 0↵01 - 1↵11 - 3↵10 - 2
注意：
对于一个给定的n，格雷码的序列不一定是唯一的，
例如：根据题目描述，[0,2,3,1]也是一个有效的格雷码序列
解题思路：觉得并不是很好的一个题，虽然不是传统的动规问题，有动态规划的思想在里面吧。但是解题思路要建立在“找规律”的基础上，n=i时状态在n=i-1状态基础上的变化规律。不能说不好，虽然没有让人在算法思想上长进，锻炼了思维的灵活性吧。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> grayCode(int n) {
int i,j;
ArrayList<Integer> res = new ArrayList<>();
res.add(0);
if(n == 0)
return res;
res.add(1);
for(i = 2; i<=n; i++){//计算n = i时的序列
for(j = 1<<i-1; j>0; j--){
res.add((1<<i-1)+res.get(j-1));
}
}
return res;
}
}9. interleaving-string
题目描述：给出三个字符串s1, s2, s3,判断s3是否可以由s1和s2交织而成。例如：给定
s1 ="aabcc",
s2 ="dbbca",
如果s3 ="aadbbcbcac", 返回true
如果s3 ="aadbbbaccc", 返回false
解题思路：按照直觉的简单思路，用两个指针从S1S2起始位置向后一次匹配，通过未通过的测试样例发现该思路并不行，遇到匹配失败不能回退到分岔路口。代码和错误用例如下：
public class Solution {
/*case通过率为12.12%用例: "aa","ab","aaba"
对应输出应该为:true 你的输出为:false*/
public boolean isInterleave(String s1, String s2, String s3) {
int i = 0, j = 0, k;
int[] dp = new int[s3.length()];
if(s3.length() != (s1.length()+s2.length())) return false;
for(k = 0; k<s3.length(); k++){
if(s1.length()>i && s1.charAt(i)==s3.charAt(k)) i++;
else if(s2.length()>j &&s2.charAt(j)==s3.charAt(k)) j++;
else return false;
}
return true;
}
}既然要记录中间状态，那还是要巧用动态规划，我依旧没有找到“状态”。于是refer to讨论,看了一眼人家的状态定义后，自己分析写出代码，优秀的思维训练呀，自己写代码还是有点急躁，稍微有点改进就想试试能不能通过，不愿意从头理清思路尽量考虑到所有的情况看自己的代码能不能够覆盖，之后要逼自己这样做呀。
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int i = 0, j = 0, k;
int[][] dp = new int[s1.length()+1][s2.length()+1];
//特殊情况要处理
if(s1.length()==0 && s2.length()==0)
if(s3.length()==0) return true;
else return false;
if(s1.length()+s2.length()!=s3.length())
return false;
//要初始化
dp[0][0] = 1;
for(i = 1; i<s1.length()+1; i++)
if(s1.charAt(i-1)==s3.charAt(i-1)) dp[i][0] = dp[i-1][0];
for(i = 1; i<s2.length()+1; i++)
if(s2.charAt(i-1)==s3.charAt(i-1)) dp[0][i] = dp[0][i-1];
//设dp[i][j]表示s3的前i+j个字符可以由s1的前i个字符和s2的前j个字符交织而成。
for(i = 1; i<s1.length()+1; i++){
for(j = 1; j<s2.length()+1; j++){
if(s1.charAt(i-1)==s3.charAt(i+j-1) && s2.charAt(j-1)==s3.charAt(i+j-1))
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
else if(s1.charAt(i-1)==s3.charAt(i+j-1))
dp[i][j] = dp[i-1][j];
else if(s2.charAt(j-1)==s3.charAt(i+j-1))
dp[i][j] = dp[i][j-1];
}
}
if((s1.length()+s2.length()==s3.length()) && dp[s1.length()][s2.length()]==1)
return true;
else return false;
}
}10. palindrome-partitioning-ii
题目描述：给出一个字符串s，分割s使得分割出的每一个子串都是回文串
计算将字符串s分割成回文分割结果的最小切割数
例如:给定字符串s="aab",
返回1，因为回文分割结果["aa","b"]是切割一次生成的。
解题思路：【这段BB可以不看！这道题的状态不难确定dp[i]是 s[0..i]包含最长回文子串的个数，难在状态转移的判断条件上。如何判断当前s(i)应并入s[k..i-1]回文串中还是另起一串呢? 我们需要找到整个序列中的回文串，再用动态规划求解dp[i]。通过思考和尝试我发现难以通过遍历和字符比较直接分析出哪一段子串是回文串。
将判断回文串的问题从原问题中剥离出来后，我们可以用f[i][j]表示s[i...j]是否是回文串。这个动态规划问题又难在状态转移上，思考无果于是refer to讨论】
最终整理思路如下：
首先是状态转移方程：
1、s[i...j]是回文字符串，则f[i][j] = 0;
2、增加一个切点p，将s[i][j]切割为两端s[i][p]、s[p+1][j],则f[i][j] = f[i][p]+f[p+1][j]
长子串的状态由子状态（更短子串的状态）构成，于是要从长度为0的子串依次填满f矩阵的值
（之前没有头绪就是没有想清楚状态和子状态的关系！）
public class Solution {
public int minCut(String s) {
int f[][] = new int[1000][1000];
//先求解小段的子序列
for(int t=0;t<=s.length();t++){
for(int i=0,j=t;j<s.length();i++,j++){
if(isPalindrome(s,i,j)) f[i][j] = 0;
else{
int min = s.length();
for(int p=i;p<j;p++)
min = min<(f[i][p]+f[p+1][j]+1) ? min: (f[i][p]+f[p+1][j]+1);
f[i][j] = min;
}//else
}// for i
}//for t
return f[0][s.length()-1];
}
//判断是否回文串
public boolean isPalindrome(String s,int i,int j){
while(i<j) {
if(s.charAt(i) != s.charAt(j))
return false;
i++;
j--;
}
return true;
}
}
京公网安备 11010502036488号