Leetcode-DP(Dynamic Programming)
Leetcode 5. Longest Palindromic Substring. 【Medium】【Green】
palindrome: [n.]回文/回环。Palindromic, [adj.]。例如 "dad","cdadc", "abba"
题目简介：找出最长的回环substring。
一个典型写法：for遍历整个string，在for循环内用helper函数来计算以第i个或(i和i+1)个字符为中心的substring是不是回环。可以把max写到全局变量，写返回void的helper。若不写全局变量，就返回substring。有用boolean[][]的dp写法，但太难写。
Time：O(n^2), Space: O(1).
若不写全局变量：
class Solution {
public String longestPalindrome(String s) {
String max = "";
for(int i=0; i<s.length(); i++){
String s1 = helper(s,i,i);
String s2 = helper(s,i,i+1);
if(s1.length()>max.length()) max = s1;
if(s2.length()>max.length()) max = s2;
}
return max;
}
private String helper(String s, int a, int b){
while(a>=0 && b<s.length()){
if(s.charAt(a) != s.charAt(b)) break;
a--;
b++;
}
return s.substring(a+1,b);
}
}
若写全局变量：
String max = "";
public String longestPalindrome(String s) {
if(s==null || s.length()<=1) return s;
for(int i=0; i<s.length(); i++){
helper(s,i,i);
helper(s,i,i+1);
}
return max;
}
private void helper(String s, int a, int b){
while(a>=0 && b<s.length()){
if(s.charAt(a) != s.charAt(b)) break;
a--;
b++;
}
if(b-a-1>max.length()) max = s.substring(a+1,b);
//return s.substring(a+1,b);
}
Leetcode 53. Maximum Subarray. 【Easy】【Green】
题目简介：找出sum最大的subarray; 有followUp，要求用divide & conquer.
设置dp[]来记录每一项的情况。(设置int curMax更好，因为只需要O(1)空间。) 遍历数组，判断cur，判断res。
public int maxSubArray(int[] nums) {
int dp[] = new int[nums.length];
dp[0] = nums[0];
int res = nums[0];
for(int i=1; i<nums.length; i++){
dp[i] = dp[i-1]<0? nums[i]: dp[i-1]+nums[i];
res = Math.max(res, dp[i]);
}
return res;
}
FollowUp：" How would we solve this given that there is an endless incoming stream of numbers ?" 若是endless，我们就无法定义int[] dp。需要设置cur来记录当前的max。这就是Kadane's Algorithm. (发音/ka:'dein/)
public int maxSubArray(int[] nums) {
int cur= nums[0];
int res = nums[0];
for(int i=1; i<nums.length; i++){
cur = cur<0? nums[i]:nums[i]+cur; // 或者用max写: cur = Math.max(nums[i],cur+nums[i])
res = Math.max(res, cur); // //或者用max写： res = Math.max(res,cur);
}
return res;
}
FollowUp: 若是需要记录开始和结束位置呢？
public int maxSubArray(int[] nums) {
int curMax = nums[0];
int globalMax = nums[0];
int start=0, end=0,globalStart=0,globalEnd=0;
for(int i=1; i<nums.length; i++){
if(curMax<0){
curMax=nums[i];
start=i;
end=i;
} else {
curMax += nums[i];
end++;
}
if(curMax>globalMax){
globalMax = curMax;
globalStart=start;
globalEnd = end; //其实也可以写一个end就行，不需两个end
}
}
return new int[globalMax,globalStart,globalEnd];
}
FollowUp: subarray should have At least k number.
没答案。
原题FollowUp：用divide & conquer 解决(时间复杂度)。
https://blog.csdn.net/xshengh/article/details/12708291
public int maxSubArray(int[] nums) {
return divide(nums,0,nums.length-1);
}
private int divide(int[] nums,int start, int end){
if(start>=end) return nums[start];//大于的情况就当是中间情况了
int mid=(start+end)/2;
int maxleft=divide(nums,start,mid-1);//左边最大和
int maxright=divide(nums,mid+1,end);
//计算包含中间的连续最大和
int midMax = nums[mid];
for(int temp=mid-1,leftSum=nums[mid];temp>=start;temp--){//计算左边
leftSum+=nums[temp];
midMax=midMax>leftSum?midMax:leftSum;
}
for(int temp=mid+1,sum=midMax;temp<=end;temp++){//计算右边
sum+=nums[temp];
midMax=midMax>sum?midMax:sum;
}
return Math.max(maxleft,Math.max(maxright,midMax));//最大子串在左边，最大子串在右边，或者包含中间那个数
}
Leetcode 121. Best Time to Buy and Sell Stock.【Green】【Easy】
题目简介：股票买一次卖一次，求最大利润。
Time: O(n), Space: O(1).
设置int min和profit，用Math.min和Math.max, 遍历一次即可，类似Leetcode 53的解法。
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<=1) return 0;
int min = prices[0];
int profit = 0;
for(int price: prices){
min = Math.min(min,price); //参照123的写法，可以写: buy=Math.max(buy, -price) 找出-price最大即最小的price
profit = Math.max(profit,price-min);
}
return profit;
}
}
Follow Up1:
Leetcode 122. Best Time to Buy and Sell Stock II 【Easy】【Yellow】
题目简介：股票买卖多次，求最大利润。
贪心Greedy解法。设置profit，遍历数组，若prices[i] > prices[i-1] 就把差值加入到profit。
Time: O(n), Space: O(1).
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2) return 0;
int profit = 0;
for(int i=1; i<prices.length; i++){
//if(prices[i]>prices[i-1]) profit += prices[i]-prices[i-1];
profit += prices[i]>prices[i-1]? prices[i]-prices[i-1]:0;
}
return profit;
}
}
FollowUp2:
Leetcode 123. Best Time to Buy and Sell Stock III 【Hard】【Yellow】
题目简介：股票仅买卖两次, (sell1完成后才能进行buy2), 求最大利润。
https://blog.csdn.net/MebiuW/article/details/52764801
设置buy1, buy2为MIN_VALUE(这里是将price记为-price, 求的是max), sell1, sell2为0. 遍历数组，在for循环内写buy1,sell1；然后写buy2，sell2. 和121区别是，buy2里面写了sell1-price。也可以写Math.max().
Time: O(n), Space: O(1).
public int maxProfit(int[] prices) {
int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
int sell1 = 0, sell2 = 0;
for(int price : prices){
//if ( buy1 < -price) buy1 = -price; //The first buy, always choose the cheapest one currently to buy, same logic as Leetcode 121
//if ( sell1 < buy1 + price ) sell1 = buy1 + price; //The max profit for the first buy, same logic as Leetcode 121
//if ( buy2 < sell1 - price) buy2 = sell1 - price; //Notice that in buy2 we have added sell1. So the profit for first buy has been included in second buy
//if ( sell2 < buy2 + price ) sell2 = buy2 + price; //The second buy, we can have profit for both first buy and second buy.
Math.max 格式：
buy1 = Math.max(buy1, -price);
sell1 = Math.max(sell1,buy1+price);
buy2 = Math.max(buy2, sell1-price);
sell2 = Math.max(sell2, buy2+price);
}
return sell2;
}
若是按照121的写法(buy1和buy2记为正数price)，就是这样的代码写法：
class Solution {
public int maxProfit(int[] prices) {
//Integer buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
Integer buy1 = Integer.MAX_VALUE, buy2 = Integer.MAX_VALUE;
Integer sell1 = 0, sell2 = 0;
for(int price: prices){
// buy1 = Math.max(buy1, -price);
// sell1 = Math.max(sell1,buy1+price);
// buy2 = Math.max(buy2, sell1-price);
// sell2 = Math.max(sell2, buy2+price);
buy1 = Math.min(buy1, price);
sell1 = Math.max(sell1,price-buy1);
buy2 = Math.min(buy2, -sell1+price);
sell2 = Math.max(sell2, price-buy2);
}
return sell2;
}
}
FollowUp3:
Leetcode 188. Best Time to Buy and Sell Stock IV. 【Hard】【Medium】
题目简介：
FollowUp4:
Leetcode 【】
题目简介：
FollowUp5:
Leetcode 【】
题目简介：
FollowUp6:
Leetcode 【】
题目简介：
Leetcode 【】
题目简介：
Leetcode 【】
题目简介：
Leetcode 975. Odd Even Jump. 【Hard】【Green】
题目简介：给一个int array, 从每一项开始跳，跳的规则是奇数次跳(第1,3,5,...)跳向后面的min 大于本项的值，偶数次跳(第2,4,6,...)跳向max 小于本项的值，求能到达最后一项的个数。
想法：最后一项肯定能到达最后一项，所以res可以设定为1.
（1）倒序遍历。
（2）需要用boolean[] jumpToHigher 和boolean[] jumpToLower 来记录从这一项出发能否通过跳到high和跳到lower，并最终达到目标。若本项的jumpToHigher为true，说明本项可以跳到最后一项。
（3）倒序遍历每一项时，需要找到下一步higher或lower的位置，那么就需要在内部进行顺序遍历。为了避免顺序遍历，就需要存储在map中。而要找到higher和lower的位置，最好是map内元素是有序的，那么TreeMap就满足规则。要满足跳的规则，需要用TreeMap来记录，key是某项的值(TreeMap默认对key值进行排序)，value是该项的index。用TreeMap.floorKey()和ceilingKey()方法找到下次跳跃的值，然后用TreeMap.get()知道下次跳跃的index。
【改进：或者用Map.Entry, floorEntry()和ceilingEntry()，直接获得entry，然后(int) Entry.getValue()方法获得index，这样可以避免get方法导致的O(logn). 】
TreeMap特点：
1.无序，不允许重复（无序指元素顺序与添加顺序不一致）
2.TreeMap集合默认会对键进行排序，所以键必须实现自然排序和定制排序中的一种
3..底层使用的数据结构是二叉树
class Solution {
public int oddEvenJumps(int[] A) {
if(A==null || A.length==0) return 0;
boolean[] jumpToHigher = new boolean[A.length], jumpToLower = new boolean[A.length];
jumpToHigher[A.length-1] = true;
jumpToLower[A.length-1] = true;
int res = 1;
TreeMap<Integer,Integer> treeMap = new TreeMap<>();
treeMap.put(A[A.length-1],A.length-1);
for(int i=A.length-2; i>=0; i--){
//Map.Entry lowEntry = treeMap.floorEntry
Integer lowKey = treeMap.floorKey(A[i]), highKey = treeMap.ceilingKey(A[i]);
if(lowKey != null) jumpToLower[i] = jumpToHigher[treeMap.get(lowKey)];
if(highKey != null) jumpToHigher[i] = jumpToLower[treeMap.get(highKey)];
if(jumpToHigher[i]) res++;
treeMap.put(A[i],i);
}
return res;
}
}
改进：由treeMap.floorKey()和ceilingKey()换为treeMap.floorEntry()和ceilingEntry()。
for(int i=A.length-2; i>=0; i--){
Map.Entry lowEntry = treeMap.floorEntry(A[i]), highEntry = treeMap.ceilingEntry(A[i]);
//Integer lowKey = treeMap.floorKey(A[i]), highKey = treeMap.ceilingKey(A[i]);
if(lowEntry != null) jumpToLower[i] = jumpToHigher[Integer.parseInt(lowEntry.getValue().toString())];
if(highEntry != null) jumpToHigher[i] = jumpToLower[Integer.parseInt(highEntry.getValue().toString())];
if(jumpToHigher[i]) res++;
treeMap.put(A[i],i);
}
Leetcode 10. Regular Expression Matching. 【Hard】【Green】
题目简介：模式匹配题，' . '匹配任意一个英文字符, ' * ' 匹配0或多个previous char(前一个字符)。
做法1，dp ( Time:O(mn) )；做法2，Recursion(TimeComplexity高,不推荐)
dp的做法，
需要在双层for循环之前，加上一个for循环，用于排除 p的全端是 "abc ..."匹配了s的0个字符的情况【特殊情况K】。
需要用二维array：boolean[][]来记录匹配情况，之所以设置[sLength+1][pLength+1], 是因为需要dp[0][0]来表示s的前0个字符和p的前0个字符相匹配(we need to set dp[0][0]=true to present the starting state)。这样dp[i][j] 表示的是s的前i个字符和p的前j个字符是否匹配。
Base case:
(1) origin: dp[0][0]: they do match, so dp[0][0] = true.
(2) first row: dp[0][j]: for String p starts with 多个 任意字母+, all true. (p若以多个abc开头,可以匹配0个s的字符, 即dp[0][xx]=true (xx是连续多个abc*的位置))
Base case(1)要求 dp = boolean[s.length()+1][p.length()+1]
Base case(2)需要写一个for循环，遍历p。
然后写两层for循环，for循环内的判断条件是：
- if(字符匹配或 . 匹配: sc[i-1]==pc[j-1] || pc[j-1]=='.') dp[i][j] = dp[i-1][j-1];
- else if( * 匹配: pc[j-1]=='*')
分两种情况：
if (上一个p字符匹配当前s字符: pc[j-2] =='.' ||pc[j-2] == sc[i-1]) dp[i][j] = (dp[i][j-1]||dp[i][j-2]]||dp[i-1][j); 【 Condition1，2，3. 】
else : dp[i][j] = dp[i][j-2] 【Condition2】
p[j]='*'条件下, p[j-1]==s[i]或'.'时, 3种Condition.jpg
3 conditions :
Condition1: dp[i][j]=dp[i][j-1], s前i个字符 matches p前j-1个字符
Condition2: dp[i][j]=dp[i][j-2], s前i个字符 matches p前j-2个字符
Condition3: dp[i][j]=dp[i-1][j], s前i-1个字符 matches p前j个字符
英文表述：
Condition1: (first i chars of s matches first j-1 chars of p)
Condition2: (first i chars of s matches first j-2 chars of p)
Condition3: (first i-1 chars of s matches first j chars of p)
把String转为char[] 的写法： 【也可以用String.charAt()。】
class Solution {
public boolean isMatch(String s, String p) {
char[] sc = s.toCharArray(), pc = p.toCharArray();
int sLength = sc.length, pLength = pc.length;
boolean[][] dp = new boolean[sLength+1][pLength+1];
dp[0][0] = true;
//Base case: 这个for循环是针对 p前端"a*b*e*"匹配了s前0个字符的情况，直接先写，是没有问题的
for(int i=2; i<=pLength; i++){ // 注意：<= pLength。另外：
if(pc[i-1]=='*'){
dp[0][i] = dp[0][i-2];
}
}
// 双层 for循环
for(int i=1; i<=sLength; i++){
for(int j=1; j<=pLength; j++){
if(sc[i-1]==pc[j-1] || pc[j-1]=='.'){
dp[i][j] = dp[i-1][j-1];
} else if(pc[j-1]=='*'){
if(pc[j-2] =='.' ||pc[j-2] == sc[i-1]){
dp[i][j] = (dp[i][j-1]||dp[i][j-2]]||dp[i-1][j); //3种特殊情况
}else {
dp[i][j] = dp[i][j-2]; //we have to cut j-1 and j //只有特殊情况2
}
}
}
}
return dp[sLength][pLength];
}
}
本题也可以用 Recursion 来做。
Time: O(n 2^n)
核心判断是：p的第二个字符是否为'*'.若是，就有可能删除前两个字符(写if判断)，也有可能是比较p第一个字符是否匹配s第一个字符(写if判断)。若否，就判断第一个字符是否匹配。
public boolean isMatch(String s, String p) {
if (p.length() == 0) {
return s.length() == 0;
}
if (p.length() >=2 && p.charAt(1) == '*') { // second char is '*'
if (isMatch(s, p.substring(2))) {
return true;
}
if(s.length() > 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0))) {
return isMatch(s.substring(1), p);
}
return false;
} else { // no second char Or second char is not '*'
if(s.length() > 0 && (p.charAt(0) == '.' || s.charAt(0) == p.charAt(0))) {
return isMatch(s.substring(1), p.substring(1));
}
return false;
}
}
为了避免substring导致的O(n), 可以用helper函数+charAt()来代替。
Time: O(2^n)
public boolean isMatch(String s, String p) {
if(s.length()==0 && p.length()==0) return true;
return helper(s,p,0,0);
}
private boolean helper(String s, String p, int sIndex, int pIndex){
if(pIndex == p.length()){ // 易错点，这里不是 == p.length()-1
return sIndex == s.length();
}
if( pIndex <= p.length()-2 && p.charAt(pIndex+1) == '*'){
if(helper(s,p,sIndex,pIndex+2)) return true;
if(sIndex<=s.length()-1 && (p.charAt(pIndex)=='.' || s.charAt(sIndex)==p.charAt(pIndex))) return helper(s,p,sIndex+1,pIndex);
return false;
} else {
if(sIndex<=s.length()-1 && (p.charAt(pIndex)=='.' || s.charAt(sIndex)==p.charAt(pIndex) ) ) return helper(s,p,sIndex+1,pIndex+1);
return false;
}
}
Leetcode 44. Wildcard Matching. 【Hard】【Yellow】
题目简介：模式匹配题，' ? '匹配任意一个字符，' * '匹配任意0或多个字符。
可以用二维dp做，也可以用普通的判断 。
做法1， dp。Time: O(mn).
dp的做法，用 boolean[][] 来记录情况。
dp[i][j]: true if the first i char in String s matches the first j chars in String p。
Base case:
(1) origin: dp[0][0]: they do match, so dp[0][0] = true.
(2) first row: dp[0][j]: for String p starts with , all true. (p若以多个开头,可以匹配0个s的字符, 即dp[0][xx]=true (xx是连续多个的位置))
Base case(1)要求 dp = boolean[s.length()+1][p.length()+1]
Base case(2)需要写一个for循环，遍历p。
然后写双层for循环。逻辑是：
- if(字符匹配或?匹配: s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1)=='?') dp[i][j] = dp[i-1][j-1] ;
- else if (匹配: p.charAt(j-1) == '') dp[i][j] = dp[i-1][j] || dp[i][j-1];
-for dp[i-1][j], means that * acts like an empty sequence. 例: ab, ab*
-for dp[i][j-1], means that * acts like any sequences 例: abcd, ab*
public boolean isMatch(String s, String p) {
// if(s.length()==0 && p.length()==0) return true;
// if(s.length()==0 || p.length()==0) return false; 别写这句,因为"" 匹配了"*"
//模式匹配题，别写if null || length()==0 的判断
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0]=true;
//base case:
for(int i=1; i<=p.length(); i++){
if(p.charAt(i-1)=='*'){
dp[0][i] = true;
} else break;
}
for(int i=1; i<= s.length(); i++){
for(int j=1; j<= p.length(); j++){
if( (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1)=='?')){
dp[i][j] = dp[i-1][j-1] ;
} else if (p.charAt(j-1) == '*'){
dp[i][j] = dp[i-1][j] || dp[i][j-1];
}
}
}
return dp[s.length()][p.length()];
}
做法2，不推荐。用两个pointer：starIndex和sAfterMatchingStar记录。Time: O(m*n)(最差情况)。
class Solution {
public boolean isMatch(String s, String p) {
int sIndex =0, pIndex = 0;
Integer starIndex = null,sAfterMatchingStar = null;
while(sIndex < s.length()){
//if(pIndex >= p.length()) return false; 错误,因为*可能是p的最后一位.例："ab"与"*"匹配
if(pIndex<p.length() && (s.charAt(sIndex)==p.charAt(pIndex) || p.charAt(pIndex)=='?')){
sIndex++;
pIndex++;
} else if (pIndex<p.length() && p.charAt(pIndex)=='*'){
starIndex = pIndex;
pIndex++;
sAfterMatchingStar = sIndex; //表示 * match 0 个字符
} else if ( starIndex != null){
pIndex = starIndex +1;
sAfterMatchingStar++;
sIndex = sAfterMatchingStar; // 表示 * 多match了一个字符
} else {
return false;
}
}
while( pIndex<p.length() && p.charAt(pIndex)=='*'){
pIndex++;
}
return pIndex == p.length();
}
}
Leetcode 72. Edit Distance. 【Hard】【Yellow】
题目简介：给定两个字符串word1,word2, 求word1转变为word2所需的最少操作数量。操作有三种: 插入,删除,取代。
用dp方法。Time: O( m*n ).
dp的做法，用 int[][] 来记录情况。
dp[i][j] : minimum cost (or steps) required to convert first i characters of word1 to first j characters of word2.
Base case:
- word1的0个字符,匹配word2的0个字符,需要0步.不需要写代码。
- word1的0个字符,对应word2的i个字符, 需要i步操作(即插入i个字符)
- word2的0个字符,对应word1的i个字符, 需要i步操作(即插入i个字符)
然后写双层for循环。逻辑是：
- if(匹配：word1.charAt(i-1)==word2.charAt(j-1) ) dp[i][j] = dp[i-1][j-1];
- else : dp[i][j] = 1+ min(dp[ i-1 ][ j-1 ], dp[ i-1 ][ j ], dp[ i ] [ j-1 ] )
Leetcode72和Leetcode 221 共同点：写一个matrix来记录，并用min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 （三者最小值+1）来计算。
class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length()+1][word2.length()+1];
//dp[0][0] = 0;
for(int i=1; i<=word1.length(); i++){
dp[i][0] = i;
}
for(int i=1; i<=word2.length(); i++){
dp[0][i] = i;
}
for(int i=1; i<=word1.length(); i++){
for(int 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()];
}
}
Leetcode 322. Coin Change. 【Medium】【Green】
题目简介：给数组coins和数字amount，求 = amount的coins最小数量。
dp做法，用int[] 来记录。
dp[i]: amount= i 的coins最小数量。
Base case：
- 由于求min，需要先把dp内的值赋为amount+1, 且dp[0]=0. 需要写for循环。
然后写双层for循环，遍历amount和遍历coins (哪个在内外都没关系)。双层for循环内，有一个if判断： if(i>=coin)dp[i] = Math.min(dp[i], dp[i-coin]+1);
在return时需要判断 dp[amount] 的值是否 == amount+1。
class Solution {
public int coinChange(int[] coins, int amount) {
//if(coints==)
int[] dp = new int[amount+1];
//Arrays.fill(dp, amount+1); //这个写法容易漏了dp[0]=0;所以还是建议直接写for循环
//dp[0] = 0; // 用amount+1而不是Integer.MAX_VALUE,因为MAX导致dp[i-coin]+1越界
for(int i=1; i<=amount; i++){
dp[i] = amount+1;
}
for(int coin: coins){ //双层for循环是可以内外互换的。
for(int i=1; i<=amount; i++){
if(i>=coin)dp[i] = Math.min(dp[i], dp[i-coin]+1);
}
}
return dp[amount] == amount+1 ? -1:dp[amount];
}
}
Leetcode 91. Decode Ways 【Medium】【Green】
题目简介：A-Z 字母分别对应1-26. 给一个全数字的字符串，要求decoding ways数量。
dp做法，Time: O(n), Space: O(n).
设 dp：int[s.length()+1]来做。
dp[i]: 前i个数字的decoding ways有 dp[i]个。
Base Case:
- dp[1] 需要先判断 s第一个字符是否能decode。
- dp[0] = 1. 这里难解释，可以等到for循环中再处理。
for循环：截取两个substring，for循环内部两个if判断：
- if ( first != 0 ) 就赋值给 dp[i] = dp[i-1].
- if ( second 在10-26之间) dp[i] += ( ... ) 【需要判断 i==2】
class Solution {
public int numDecodings(String s) {
//It's a Non-Empty string.
int n = s.length();
int[] dp = new int[n+1];
//dp[0] = 1;
dp[1] = s.charAt(0) != '0' ? 1 : 0;
for(int i = 2; i <= n; i++) {
int first = Integer.valueOf(s.substring(i-1, i));
int second = Integer.valueOf(s.substring(i-2, i));
if(first != 0) {
dp[i] = dp[i-1];
}
if(second >= 10 && second <= 26) {
dp[i] += ( i==2? 1: dp[i-2] ); //重点,若不判断i==2就需要写dp[0].这里解释困难。
}
}
return dp[n];
}
}
Space: O(1) Time O(n)的方法，但稍微有点绕。设置s1，s2分别记录情况，返回的是s1.
s1, s2 store ways of the s(0 ~ i-1) and s( 0 ~ i-2 )
public int numDecodings(String s) {
//if(s.charAt(0)=='0') return 0; //避免 '0'的情况
int s1 = s.charAt(0)=='0'? 0:1, s2 = 1; //这里很关键，若设s1=1就需要上面的一句判断
//s1, s2 store ways of the s(0 ~ i-1) and s( 0 ~ i-2 )
for(int i=1; i<s.length(); i++){
if(s.charAt(i)=='0') s1 =0;
if(s.charAt(i-1)=='1' || (s.charAt(i-1)=='2'&&s.charAt(i)<='6') ){
int temp = s1;
s1 = s1 + s2;
s2 = temp;
} else {
s2 = s1;
}
}
return s1;
}
Leetcode 62. Unique Paths 【Medium】【Yellow】
题目简介：二维grid，从左上角到右下角的走法，有几种。
用dp做法。Time: O(mn), Space: O(mn).
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
dp[0][0]=1;
for(int i=0; i<m;i++){
dp[i][0] =1;
}
for(int j=0; j<n;j++){
dp[0][j] =1;
}
for(int i=1; i<m; i++){
for(int j=1; j<n; j++){
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
dp做法改进：Space O(n, 或者说 min(m,n)).
ignore the space for the columns. Each column has only one space to store the information.
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
dp[0]=1;
for(int i=0; i<m; i++){ //从0开始,从而遍历m行
for(int j=1; j<n; j++){
dp[j] = dp[j]+dp[j-1];
}
}
return dp[n-1];
}
阶乘的做法。Time: O(min(m,n)), space: O(1).
计算公式： factorial(m+n-2)/(fact(m-1)fact(n-1)).
假设n>m, 约去(n-1), 得到 (m+n-2)...n / (m-1)...*1. 都有m-1项，而且相差为n-1.
class Solution {
public int uniquePaths(int m, int n) {
double res = 1;
for(int i=1; i<=m-1; i++){
res = res * (i+n-1)/i;
}
return (int)res;
}
}
Leetcode 70. Climbing Stairs.【Easy】【Yellow】
题目简介：爬楼梯，每次爬1步或2步, 求到达n的ways数量。
recursion做法，超时了。Time: O(2^n). 近似 费波那契数列.
dp做法，用 int[] dp来记录。Time: O(n), Space: O(n).
class Solution {
public int climbStairs(int n) {
if(n==1)return 1;
// if(n==2)return 2;
int[] dp = new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n; i++){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
}
改进版: Space：O(1).
class Solution {
public int climbStairs(int n) {
if(n==1) return 1;
if(n==2) return 2;
int k2 = 1; // 2 steps before current stair
int k1 = 2; // 1 step before current stair
int k = 0; // current stair
for(int i=3; i<=n; i++){ //注意index，从3到n。
k = k1+k2; // calculate k.
k2 = k1; //k2 move forward
k1 = k; //k1 move forward
}
return k;
}
}
Leetcode 509. Fibonacci Number. 【Easy】【Yellow】
题目简介：计算 Fibonacci Number.
用 Iterative. 设3个数：sum，a，b。写一个for循环就解决。
class Solution {
public int fib(int N) {
if(N<=1) return N;
int sum = 0;
int a=0, b=1;
for(int i=2; i<=N; i++){
sum = a+b;
a = b;
b = sum;
}
return sum;
}
}
Leetcode 139. Word Break. 【Medium】【Green】
题目简介：给一个字符串和List字典，问字符串能否分割为在字典中都能查到的单词。
dp题，关键是设置boolean[] 来记录dp[j]，从而知道在 j 之前是否都能找到单词。两个for循环就解决。
做法1，用 List.contains()操作，Time O(n^3), 不推荐。
Time: O(n^3), 因为List.contains()是O(n)的 (String.substring()方法是O(1))。
Space: O(n).
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length()+1];
dp[0]=true;
for(int i=1; i<=s.length();i++){
for(int j=0; j<i; j++){
if(dp[j] && wordDict.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[dp.length-1];
}
}
改进：用 set 来实现 set.contains()。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>();
set.addAll(wordDict);
boolean[] dp = new boolean[s.length()+1];
dp[0]=true;
for(int i=1; i<=s.length();i++){
for(int j=i-1; j>=0; j--){ //倒序遍历，会比顺序遍历好, improve performance.
if(dp[j] && set.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[dp.length-1];
}
}
类似做法一，以下是dp的典型写法，for循环遍历其中一个input： String s, 另一个for循环遍历另外的一个input：wordDict。
String.equals()是O(n)，但这里word的长度可以认为是一个常数，与s.length()没关系。所以: Time: O(m*n)，或者说O(n^2).
缺点是wordDict过大的话会麻烦。
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
// 从这个位置向前考虑能否match某个word，如果match并且前面也为true的话，那么这一段我们可以将其设置为true
for (String word : wordDict) {
// 至少i要在word之后吧，如果这个位置根本放不下这个word，那就下一个
if ( i >= word.length() && dp[i - word.length()] && word.equals(s.substring(i - word.length(),i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
Leetcode 140.Word Break II. 【Hard】【Yellow】
题目简介：给一个字符串和List wordDict，返回一个List<String>, 包含所有可能的分割方式。
需要用Recursion(back-tracking)。
设一个Map<String,List<String>> map，map记录的是 被截取前端一部分之后的s和它对应的多种分割方式。比如说，"... catsanddog", map中就记录了("catsanddog",对应的result记录的分割方式)。这样当 ... 解析到 "catsanddog" 时，就不需要再重新对它进行分割，而是直接调取之前已经记录在map中的代码。（若不使用map，就会TLE(Time Limit Exceeded.) ）
最简洁的答案：
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
return backtrack(s,wordDict,new HashMap<String, List<String>>());
}
// backtrack returns an array including all substrings derived from s.
public List<String> backtrack(String s, List<String> wordDict, Map<String,List<String>> map){
if(map.containsKey(s)) return map.get(s);
List<String> result = new ArrayList<String>(); //result 可理解为 mapValue
for(String word: wordDict){
if(s.startsWith(word)) {
//s = "...catsxxx",word可以为cat/cats,word=cat时下面的代码会把"catxxxx"的各种break情况记录到result中;然后轮到word=cats,把"catsxxx"的情况记录到result中
String next = s.substring(word.length());
if(next.length()==0){
result.add(word);
} else {
List<String> nextStr = backtrack(next, wordDict, map);
for(int i=0; i<nextStr.size(); i++){
result.add(word + " " + nextStr.get(i));
}
// for(String subStr: backtrack(next, wordDict, map)) { 也可以用for(String str:)写法
// result.add(word+" "+subStr);
// }
}
}
}
map.put(s, result); //含有：s="catsanddog", 对应的s的result: "cats and dog","cat sand dog"
return result;
}
}
分析1:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
s="catsanddog", NEW res,
(1)word=cat, next=sanddog,
backtrack1()得到list ("sand dog"),subStr处理,得到res("cat sand dog"),
backtrack1(), word=sand,next=dog,backtrack2()得到的是含有("dog")的List,对于每一个subStr,add进当前res,有res("sand dog"),map.put("sanddog",res),return res返回上一级
backtrack2(), s=dog, word=dog, next="",res.add("dog"),map.add("dog",res),return res返回上一级
(2)word=cats,next=anddog,backtrackA(),
backtrackA(), 得到("and dog")的list,subStr处理，res原基础("cat sand dog")上加入"cats and dog"
backtrackA(),word=and,next=dog,backtrackB()得到含有("dog")的List,有res("and dog"),map.put("anddog",res),return res返回上一级
backtrackB(),返回map.get("dog")
map.put("catsanddog",res) (res两个元素，"cat sand dog"和"cats and dog")
return res，就是答案
分析2：
s= "catsandcatsand"
dict = ["cat","cats","and","sand","dog"]
s="catsandcatsand", NEW res, (1)word=cat, next=sandcatsand,
backtrack1()得到list ("sand cat sand","sand cats and"),subStr处理,得到res("cat sand cat sand","cat sand cats and"),map.put("catsandcatsand",res)
backtrack1(), word=sand,next=catsand,backtrack2()得到的是含有("cat sand","cats and")的List,对于每一个subStr,add进当前res,有res("sand cat sand","sand cats and"),map.put("sandcatsand",res),return res返回上一级
backtrack2(), s=catsand,(1)word=cat,next=sand,下一级完成后res.add("cat sand"),res有("cat sand"),检验其他word
(2)word=cats,next=and,下一级完成后res.add("cats and"),res有("cat sand","cats and"),map.put("catsand",res)返回上一级
backtrack3(), (1)s=sand,word=sand,next="",result.add("sand"),map.put("sand",result) return res返回上一级
(2)s=and,word=and,next="",res.add("and"),map.put("and",result) return res返回上一级
(2) word = cats, next=andcatsand, backtrackA(),把subStr加入到res,res.ADD("cats and cat sand","cats and cats and")
backtrackA(),s=andsand,word=and,next=catsand,backtrackB()得到"cat sand","cats and"
backtrackB(),s=catsand,返回map.get("catsand")
map.put("catsandcatsand",res),res含有："cat sand cat sand","cat sand cats and","cats and cat sand","cats and cats and"
RETURN res
Leetcode 410. Split Array Largest Sum. 【Hard】【Green】
题目简介：将一串数字截为m段，使得每段之和的最大值 最小(minimize the largest sum of the subarrays)。求这个值。
用二分法来解决。ruler是每段之和的最大值。
最开始以nums中最大值max为left，以nums的全体sum为right，需要通过helper()方法来判断 left增大还是right缩小。
class Solution {
public int splitArray(int[] nums, int m) {
int max = 0;
long sum = 0;
for(int num: nums){
max = Math.max(max,num);
sum += num;
}
if(m==1) return (int)sum;
long left = max, right = sum;
while(left<right){ //left可取，right不可取：[left,right)
long mid = left + (right-left)/2;
if(binarySearch(mid,nums,m)){
right = mid;
} else {
left = mid+1;
}
}
return (int)left;
}
private boolean binarySearch(long target,int[] nums, int m){
int count = 1; //这是因为最后一段是不经历count++的,比如说，只分为2段，那么只经历了一次count++。
long sum = 0;
for(int num: nums){
sum += num;
if(sum>target){ ///why? 因为target就代表了一段数字的max,是可以取等号的max
count++;
sum = num;
if(count>m){
return false;
}
}
}
return true;
}
}
Leetcode 84. Largest Rectangle in Histogram. 【Hard】【Yellow】
题目简介：给一串数组,代表柱形图，求最大矩形面积。
用 stack做。(无论stack还是queue，都用LinkedList初始化. ) 每次遇到递增的index，就offerFirst()加入到stack中; 一遇到减少的index i, 就把stack 中 >=heights[i]的一个个pollFirst()推出来,并计算面积。
Stack class 很慢，已经很少用了。
stack和queue的初始化：(Deque, interface of 双向链表)
- Deque<Integer> stack = new LinkedList<>();
- Deque<Integer> queue = new LinkedList<>();
也可以写: Queue<Integer> queue = new LinkedList<>();用Queue的方法。
//每次遇到递增的index，就offerFirst()加入到stack中; 一遇到减少的index i, 就把stack中
// >=heights[i]的一个个pollFirst()推出来,并计算面积
class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0;
Deque<Integer> stack = new LinkedList<>();
//Deque<xxx> queue = new LinkedList<>();
for(int i=0; i<= heights.length; i++){ //**注意: 从0到n,共n+1项
int cur = i== heights.length? 0: heights[i]; //难点1,与**有关
while( !stack.isEmpty() && heights[stack.peekFirst()] >= cur){
int height = heights[stack.pollFirst()]; //难点2
int left = stack.isEmpty()? 0:stack.peekFirst()+1; //难点3,+1可以从第一个情况推导出来.第一次情况,i-1被推出,peekFirst()得到的是i-2.而i-1处宽度是1.要i-left=1,那么应该让peekFirst()+1.
// stack中只能存比cur小的,若是没有了,说明cur是全队最小,所以需要从index=0算起
res = Math.max(res, height * (i-left)); //这里只算位于i之前的面积,所以是从0遍历到n,需要最后补上一个0(**与难点一有关)
}
stack.offerFirst(i);
}
return res;
}
}
Leetcode 85. Maximal Rectangle. 【Hard】【Yellow】
题目简介：给一个二维char数组, 都是0和1的值，问元素都是1的最大矩形面积。
和84题做法基本相同。难点在于理解为何设置heights数组(长度为n+1)：原因在于累计其高度，这样就可以转化为84题。
[
[1,0,1,0,0]
[1,0,1,1,1]
[1,1,1,1,1]
[1,0,0,1,0]
]
处理得到 heights数组：
(最后一位是补零的操作,参照84题的做法)
经历第1行后：[1,0,1,0,0,0]
经历第2行后：[2,0,2,1,1,0]
经历第3行后：[3,1,3,2,2,0]
经历第4行后：[4,0,0,3,0,0]
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length==0 || matrix[0].length ==0) return 0;
int m = matrix.length, n= matrix[0].length;
int[] heights = new int[n+1];
int res = 0;
for(int i=0; i<m; i++){
Deque<Integer> stack = new LinkedList<>();
for(int j=0; j<=n; j++){
if(j!=n){
if(matrix[i][j] == '1') heights[j]+=1;
else heights[j]=0;
}
while( !stack.isEmpty() && heights[stack.peekFirst()] >= heights[j]){
int height = heights[stack.pollFirst()];
int width = stack.isEmpty() ? j: j-stack.peekFirst()-1;
res = Math.max(res, height*width);
}
stack.offerFirst(j);
}
}
return res;
}
}
Leetcode 935. Knight Dialer. 【Medium】【Yellow】
题目简介：一个knight骑士棋子有特定跳跃规则, 问能打多少种电话号码。
法1，Time: O(N), Space: O(1). 【推荐】
设置两个long array: pre和cur，记录上一步情况和当前情况。关键是理解: cur[0]=(pre[4]+pre[6])%mod，这一步跳到0的ways = 上一步跳到4和6的ways之和。
class Solution {
public int knightDialer(int N) {
long mod = 1000000007;
if(N==1) return 10;
long[] pre = new long[10];
long[] cur = new long[10];
Arrays.fill(pre,1); // 记住Arrays.fill()
pre[5] = 0; //关键点，pre[5]=0
while(--N>0){
cur[0]=(pre[4]+pre[6])%mod;
cur[1]=(pre[6]+pre[8])%mod;
cur[2]=(pre[7]+pre[9])%mod;
cur[3]=(pre[4]+pre[8])%mod;
cur[4]=(pre[3]+pre[9]+pre[0])%mod;
//cur[5]=0;
cur[6]=(pre[1]+pre[7]+pre[0])%mod;
cur[7]=(pre[2]+pre[6])%mod;
cur[8]=(pre[1]+pre[3])%mod;
cur[9]=(pre[2]+pre[4])%mod;
//pre = cur; //Wrong for it's address copy. 错误，这是地址拷贝了,导致出错
//for(int i=0; i<10; i++) pre[i]=cur[i]; 这个for循环也可以用，但不如下面方便
int[] temp = pre;
pre = cur;
cur = pre; //把cur赋给pre，然后cur指向pre，这样就不需要新设数组int[]也不需要for循环赋值
}
long sum = 0;
for(int i=0; i<10; i++){
sum = (sum+cur[i])%mod;
}
return (int)sum;
}
}
可以进一步将Time削减到O(logN). 用Matrix来记录，并使用Matrix的乘方(^)。太难写，所以不推荐。
(1) 为什么可以用Matrix的相乘来得到ways？
The m(i,j) in Matrix Mk means starting at i, ending at j, through k+1 hops.
(THE ways for first hop =0 because 10 numbers can be the starting point with equal possibility. So hop1 = M0 = 10. )
M1 = np.matrix([[0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 1, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0]])
M1 is the starting matrix, k=1, and the dots indicates where the horse can be after 2 hops.
For example, the first row means starting at 0, a horse can jump to 4 and 6.
And when k=2, we multiply two M1s, and get M2.
M2 = np.matrix([[2, 1, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 2, 0, 1, 0, 0, 0, 1, 0, 0],
[0, 0, 2, 0, 1, 0, 1, 0, 0, 0],
[1, 1, 0, 2, 0, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 3, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 3, 0, 1, 0],
[1, 1, 0, 0, 0, 0, 0, 2, 0, 1],
[0, 0, 0, 0, 1, 0, 1, 0, 2, 0],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 2]])
M2 (4,4)=3, which means there are 3 ways to start at 4, ending at 4 in 3 jumps. 【3ways: 4-3-4, 4-9-4, 4-0-4】
M2 (4,4) = M1(4,0)*M1(0,4)+M1(4,1)*M1(1,4)+M1(4,2)*M1(2,4)+...+M1(4,9)*M1(9,4). 【Matrix multiplying】
In this way we can use matrix to calculate number of paths.
(2) 为什么可以将 O(N) 削减到 O(LogN)？
M60 = M30*M30 = M30^2,(even number of Matrix can reduce half the calculation.)
M61 = M1 * M30 * M30 = M1 * M30^2 = M1 * M60, (odd number Matrix can be modified to even number Matrix calculation. )
O(logN) Space O(1)的解法：
class Solution {
public int knightDialer(int N) {
if(N==1) return 10;
long mod = 1000000007;
long[][] matrix = {
{0, 0, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
{1, 0, 0, 1, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 1, 0, 0, 0},
{0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 1, 0, 0, 0, 0, 0},
};
long[][] resultMatrix = new long[10][10];
boolean resultNotEmpty = false;
N = N-1;
while(N>0){ //这里最关键。处理方式很巧妙，Leetcode应该有同类型的二分法的题
if(N%2==1){
if(resultNotEmpty){
resultMatrix = matrixMultiply(resultMatrix, matrix);
} else {
resultNotEmpty = true;
resultMatrix = matrix;
}
}
matrix = matrixMultiply(matrix, matrix);
N/=2;
}
long sum = 0;
for(int i=0; i<10; i++){
for(int j=0; j<10; j++){
// sum += resultMatrix[i][j];
// sum %= mod;
sum = (sum+resultMatrix[i][j])%mod;
}
}
return (int)sum;
}
private long[][] matrixMultiply(long[][] matrix1, long[][]matrix2){
long mod = 1000000007;
long[][] resultMatrix = new long[10][10];
for(int i=0; i<10; i++){
for(int j=0; j<10; j++){
for(int k=0; k<10; k++){
// resultMatrix[i][j] += matrix1[i][k]*matrix2[k][j];
// resultMatrix[i][j] %= mod;
resultMatrix[i][j] = (resultMatrix[i][j]+matrix1[i][k]*matrix2[k][j])%mod;
}
}
}
return resultMatrix;
}
}
while() { N%2==0 ... } 的大致题意：【time (logN)内让res从0到达N】
给定一个数N，N就是res()方法或者res数字需要操作的次数。
( 用一个int：exponential 用来记录 2的指数 )
初始：res=0，exponential = 1.
典型处理代码：
while(N>0){
if(N%2==1){
if(res==0){
res = exponential;
else {
res += exponential;
}
}
exponential = exponential * 2 ;
N = N/2;
}
Leetcode 688. Knight Probability in Chessboard. 【Yellow】【Medium】
题目简介：棋子有特定的跳跃规则，问k步跳跃之后还留在棋盘上的概率。
dp方法。可以设置dp[K][N][N], 计算公式是:
dp[k+1][newX][newY] = dp[k][x][y].
视频：https://www.youtube.com/watch?v=4W1Gvahf_Hg
但我们可以发现， dp[k][x][y] 只会使用一次，所以我们不需要三维的array，只需要 两个二维array，double[][] pre和cur 即可。
用double[][] pre和cur 记录 probability chessboard, 写三层for循环，第四层for循环是指每一步都可以走八个位置，概率都是1/8. 难点在于pre和cur的处理，放在第一层for循环(因为pre和cur就是为了k和k+1步的关系而准备的)，先设double[][] pre=cur，然后cur= new double[][]，即把原cur标记为pre，并把cur清空。
Time: O(KN^2), Space: O(N^2).
class Solution {
public double knightProbability(int N, int K, int r, int c) {
double[][] cur = new double[N][N]; //or new double[25][25]
cur[r][c] = 1;
int[] dx = {1,1,-1,-1,2,2,-2,-2};
int[] dy = {2,-2,2,-2,1,-1,1,-1};
for(int k=0; k<K; k++){
double[][] pre = cur; //mark cur as the previous matrix
cur = new double[N][N]; //cur should be an empty matrix
for(int x=0; x<N; x++){
for(int y=0; y<N; y++){
for(int count=0; count<8; count++){
int newX = x + dx[count];
int newY = y + dy[count];
if(newX>=0 && newX<N && newY>=0 && newY<N) cur[newX][newY]+=pre[x][y]*0.125;
}
}
}
}
double res = 0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
res += cur[i][j]; //sum of all possibility
}
}
return res;
}
}
Leetcode 32. Longest Valid Parentheses. 【Yellow】【Hard】
题目简介：给一个字符串, 只包含 '(' 和 ')'，找出最长的合规substring的长度。
用 LinkedList<Integer> stack 来做。遍历一次数组，每次遇到 ( 就把index加入stack，遇到 ) 就先判断stack是否empty，若empty就设置start，不empty就直接pop一次，并计算res (分两种情况，一是stack变空了而是stack还有元素)。
特点：遇到 ) ，判断是否empty，然后pop，再判断是否empty。
class Solution {
public int longestValidParentheses(String s) {
int res = 0;
LinkedList<Integer> stack = new LinkedList<>();
int start = -1;
for(int i=0; i<s.length(); i++){
if(s.charAt(i)=='('){
stack.push(i);
} else {
if(stack.isEmpty()){
start = i;
} else {
stack.pop();
if(stack.isEmpty()){
res = Math.max(res,i-start);
} else {
res = Math.max(res,i-stack.peek());
}
}
}
}
return res;
}
}
Leetcode 221. Maximal Square. 【Yellow】【Medium】
题目简介： 给一个二维char数组, 都是0和1的值，问元素都是1的最大正方形面积。(和85题目相似，85题目是求矩形面积)
用原matrix来记录情况（或者设置一个dp[][] 来记录情况,但这样space更高所以不推荐），双层for循环内判断逻辑是：
- if ( ==1 ), 就 说明它可以作为正方形的右下角，那么就去找三者最小值：
- Math.min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1, 由于比如说dp[i-1][j]=k，说明dp[i-1][j]是边长side-length为k的正方形，依此类推到dp[i-1][j-1]和dp[i][j-1]，说明dp[i][j]可以做边长为min+1的正方形的右下角。
可以设置一个dp[][] 来记录情况(最原始的解法1, time(mn), space(mn))。然后发现并不需要保存整个二维dp，将space提升到O(n)，这是解法2. 最后，可以直接在原matrix上操作，将 space提升到 O(1).
由于是在原matrix操作，需要检查matrix[i-1][j-1],所以双层for循环都是从index=1开始，因此对于index=0的row和column，需要另外写两个单层for循环来遍历。
Leetcode72和Leetcode 221 共同点：写一个matrix来记录，并用min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 （三者最小值+1）来计算。
class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int max = 0;
for(int i = 1; i < m && max != 1; i++) if(matrix[i][0] == '1') max = 1;
for(int j = 0; j < n && max != 1; j++) if(matrix[0][j] == '1') max = 1;
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(matrix[i][j] == '1'){
int s = Math.min(matrix[i-1][j] - '0', Math.min(matrix[i - 1][j - 1] - '0', matrix[i][j-1] - '0')) + 1;
matrix[i][j] = (char)('0' + s);
max = Math.max(max, s);
}
}
}
return max * max;
}
}
Leetcode 741. Cherry Pickup. 【Hard】【Yellow】
题目简介：有一个N*N的矩形Grid(网格), 一个人从左上角走到右下角，再返回左上角，每个网格cell 有两种可能，1) -1，说明这是栅栏，不能通过；2) 非负数(k)，说明这个网格有k个樱桃cherry。问这个人可以摘到樱桃的最大数量。
解题思路：题意相当于由两个人同时从左上角走到右下角。用dp解法。设一个 int[][][] dp = new int[n+1][n+1][n+1], (dp常常都是设置n+1因为可以避免dp[x-1] x=0时的越界情况)。
1).Base case: 先赋值min_value, 赋值dp[1][1][1] = grid[0][0]; 2). 在三层for循环内，赋值y2, 判断y2是否越界以及grid是否为栅栏; 然后计算pre, 前一步的max值(max(四种可能))，若前一步<0, continue, 否则就根据pre 以及 x1和x2是否相等，来赋值给dp[x1][y1][x2].
class Solution {
public int cherryPickup(int[][] grid) {
int n = grid.length;
int[][][]dp = new int[n + 1][n + 1][n + 1];
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
Arrays.fill(dp[i][j], Integer.MIN_VALUE); //为了后面的判断.在这一题，设置任何负数都行
}
}
dp[1][1][1] = grid[0][0];
for(int x1 = 1; x1 <= n; x1++){
for(int y1 = 1; y1 <= n; y1++){
for(int x2 = 1; x2 <= n; x2++){
int y2 = x1 + y1 - x2;
//out of boundary || cannot access
if( y2 < 1 || y2 > n || grid[x1 - 1][y1 - 1] == -1 || grid[x2 - 1][y2 - 1] == -1)continue;
int pre = Math.max(Math.max(dp[x1 - 1][y1][x2], dp[x1 - 1][y1][x2 - 1]), Math.max(dp[x1][y1 - 1][x2], dp[x1][y1 - 1][x2 - 1]));
if(pre < 0) continue; // 1)使得起点是grid[0][0]; 2)对应grid中的那个点左边和上边若都是-1,那么这个点的值应该也是min_value
if(x1 != x2){
dp[x1][y1][x2] = pre + grid[x1 - 1][y1 - 1] + grid[x2 - 1][y2 - 1];
} else {
dp[x1][y1][x2] = pre + grid[x1 - 1][y1 - 1];
}
}
}
}
return dp[n][n][n] <= 0 ? 0 : dp[n][n][n];
}
}
Leetcode 300. Longest Increasing Subsequence.【Medium】【Yellow】
题目简介： 找到最长的递增subsequence。注意，没有规定consecutive相邻, 就是可以是不相邻的。
要求：Time O(nlogn). 所以需要用二分法。
用int[] sequence 记录情况。for循环遍历，并做以下处理：
(1) if x is larger than all tails, append it, increase the size by 1
(2) if tails[i-1] < x <= tails[i], update tails[i].
这种做法源于 patience sorting 耐心排序。
Time: O(nlogn), space: O(n).
推荐写法：
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums==null || nums.length==0) return 0;
int[] sequence = new int[nums.length];
int length = 0;
sequence[length++] = nums[0];
for(int i=1; i<nums.length; i++){
if(nums[i]>sequence[length-1]){
sequence[length++] = nums[i];
} else {
int left = 0, right = length-1;
while(left < right){ // 当left>=right时跳出循环.其实只能是left==right,不会出现left>right并跳出的情况
int mid = left+(right-left)/2;
if(sequence[mid]<nums[i]){
left = mid+1;
} else {
right = mid;
}
}
sequence[left] = nums[i];
}
}
//System.out.print(Arrays.toString(sequence)); //Arrays.toString(xxArray)这个写法很好用，用于代码测试
return length;
}
}
简化版：（不推荐）
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0;
for (int x : nums) {
int i = 0, j = size;
while (i != j) {
int m = (i + j) / 2;
if (tails[m] < x)
i = m + 1;
else
j = m;
}
tails[i] = x;
if (i == size) ++size;
}
return size;
}
Leetcode 97. Interleaving String. 【Hard】【Yellow】
题目简介：有两个string s1, s2, 判断另一个string s3 是否由s1和s2交错得到。interleaving: 交错。 注意：是将s1,s2分别截成多个substring，并拼接得到s3，但s1的多个substring的顺序仍是原顺序, s2同理。
解题思路：
用dp解决。设一个二维数组，boolean[][] dp = new boolean[s1.length()+1][s2.length()+1]; 来记录情况。dp[i][j]表示s1前i个字符,s2前j个字符，匹配s3的前i+j个字符。
Base case:
- dp[0][0] = true, 即s1前0个字符,s2前0个字符，匹配s3的前0+0个字符。
- 遍历第一列dp[i][0]，即在s2不出字符的情况下，s1和s3匹配情况。
- 遍历第一行dp[0][j]，即在s1不出字符的情况下，s2和s3匹配情况。
双层for循环遍历，内部判断条件：
1）s3[i+j+1] 字符匹配 来自s1的字符：dp[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1).
2）s3[i+j+1] 字符匹配 来自s2的字符：dp[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1).
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1 == null || s1.length()==0) return s2.equals(s3);
if(s2 == null || s2.length()==0) return s1.equals(s3);
if(s1.length()+s2.length() != s3.length()) return false;
boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
dp[0][0] = true;
for(int i=1; i<dp.length; i++){
dp[i][0] = dp[i-1][0] && s1.charAt(i-1)==s3.charAt(i-1);
}
for(int j=1; j<dp[0].length; j++){
dp[0][j] = dp[0][j-1] && s2.charAt(j-1)==s3.charAt(j-1);
}
for(int i=1; i<dp.length; i++){
for(int j=1; j<dp[0].length; j++){
dp[i][j] = (dp[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1) )
|| (dp[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1));
}
}
return dp[s1.length()][s2.length()];
}
}
Leetcode 312. Burst Balloons. 【Hard】【Yellow】
题目简介：扎气球，给一串int，每扎一个气球，就要加上气球两端数字的乘积，求max。
用二维int[][] dp来记录情况。dp[start][end]表示nums第start个到第end个气球被扎爆所得的max值。
Time：O(), Space: O(n^2).
核心逻辑是：若要扎第i个气球，dp[start][end] = dp[start][i-1] + 扎i气球得到的值 + dp[i+1][end].
先新建数组，给原数组两端加上1，然后helper方法，helper中for循环遍历一次arr，（核心逻辑）每次都求出cur并赋给dp[start][end].
dp[i][j]图示.png
class Solution {
public int maxCoins(int[] nums) {
int[] arr = new int[nums.length+2];
for(int i=1; i<=nums.length; i++){
arr[i] = nums[i-1];
}
arr[0] = 1;
arr[arr.length-1] = 1;
int[][] dp = new int[arr.length][arr.length];
//dp[start][end]表示nums第start个到第end个气球被扎爆所得的max值
return helper(1, nums.length, arr, dp);
}
private int helper(int start, int end, int[] arr, int[][] dp){
if(start>end){
return 0;
}
if(dp[start][end]>0) return dp[start][end];
for(int i=start; i<=end; i++){
int cur = helper(start,i-1,arr,dp)+
arr[start-1]*arr[i]*arr[end+1]+
helper(i+1,end,arr,dp);
dp[start][end] = Math.max(dp[start][end], cur);
//dp[start][end]会经历多次自我比较,需要以题目的例子[3,1,5,8]来理解
}
return dp[start][end];
}
}
Leetcode 【】
题目简介：
Leetcode 1155. Number of Dice Rolls With Target Sum. 【Medium】【Blue】
题目简介：
class Solution {
public int numRollsToTarget(int d, int f, int target) {
int mod = 1000*1000*1000+7;
int[][] dp = new int[d+1][target+1];
dp[0][0]=1;
for(int iDice=1; iDice<=d; iDice++){
for(int jTarget=1; jTarget<=target; jTarget++){
if(jTarget > f*iDice){
continue; // or dp[iDice][jTarget]=0;
}else{
for(int kValue=1; kValue<=f && kValue<=jTarget; kValue++){
dp[iDice][jTarget]=(dp[iDice][jTarget]+dp[iDice-1][jTarget-kValue])%mod;
}
}
}
}
return dp[d][target]%mod;
}
}
Leetcode 【】
题目简介：
```Leetcode 【】
题目简介：
Leetcode 【】
题目简介：
Leetcode 【】
题目简介：
