123. Best Time to Buy and Sell Stock III

四刷 07/2022

Version #2 Constant space DP

重点就是要弄清题意是同一天可以既卖出又买入，而且问的是最多2transactions的profit，一个transaction也是可以的

Time O(N)

Space O(1)

Runtime: 6 ms, faster than 72.73% of Java online submissions for Best Time to Buy and Sell Stock III.

Memory Usage: 77.8 MB, less than 73.50% of Java online submissions for Best Time to Buy and Sell Stock III.

class Solution {

    public int maxProfit(int[] prices) {

        // max profit that we can get with one transaction on day i

        if (prices.length < 2) {

            return 0;

        }

        int minPrice = prices[0];

        int maxOneTransac = 0;

        int maxDiff = -prices[0];

        int max = 0;

        // minPrice  maxOneTransac    maxDiff      curr

        //  0            1             2            3

        for (int i = 1; i < prices.length; i++) {

            max = Math.max(max, prices[i] + maxDiff);

            minPrice = Math.min(minPrice, prices[i]);

            maxOneTransac = Math.max(maxOneTransac, prices[i] - minPrice);

            maxDiff = Math.max(maxDiff, maxOneTransac - prices[i]);

        }

        return max;

    }

}

3RD TRY
Version #1 Native DP

dp[i - 1][k] -> don't do anything on current day
dp[j][k - 1] + prices[i] - prices[j] -> buy from day j and sell it now

dp[i][k] = Math.max(dp[i - 1][k], dp[j][k - 1] + prices[i] - prices[j])

4.23 %
class Solution {
    public int maxProfit(int[] prices) {
        // dp[i][k] -> maxProfit we got until day i by using k transactions
// dp[i][k] = Math.max(dp[i - 1][k], dp[j][k - 1] + prices[i] - prices[j])
// dp[0][k] = 0;
// dp[i][0] = 0
        if (prices == null || prices.length < 2) {
            return 0;
        }
int[][] dp = new int[prices.length][3];
for (int k = 1; k <= 2; k++) {
            for (int i = 1; i < prices.length; i++) {
                int minCost = prices[0];
                for (int j = 1; j < i; j++) {
                    minCost = Math.min(minCost, prices[j] - dp[j][k - 1]);
                }
                dp[i][k] = Math.max(dp[i - 1][k], prices[i] - minCost);
            }
        }
return dp[prices.length - 1][2];
       
    }

}

Version #2
Time O(n) Space O(1)
Since we only have 2 transactions, we can use 4 variable to keep track of:
1.The min price we see so far -> for buy in for the 1st transaction
2. The max profit we can get for 1st transaction
3. The min cost we need to pay if we finish the 1st transaction and buy in the 2nd transaction
4. The global max profit we can get from the 2nd transaction
Initial values are:
1.leftMin -> buy at 1st day
2.preMax -> max profit start at 1st day -> buy at 1st day and sell at the same time
3.minCost -> buy at 1st day and sell and then buy in -> what cost us is price[0]
4. max -> buy twice and sell twice at the first day

95.69 %
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
return 0;
}
int max = 0;
int prevMax = 0;
int minCost = prices[0];
int leftMin = prices[0];
for (int price : prices) {
// What is the min price on the left so far
leftMin = Math.min(price, leftMin);
// What is the max we can get for 1 transaction
prevMax = Math.max(prevMax, price - leftMin);
// What is the min Cost for 1 transaction + 1 buy in
minCost = Math.min(minCost, price - prevMax);
max = Math.max(max, price - minCost);
}
return max;
    }

}




二刷
DP
Before Optimize:
Kadane's Algorithm, 求 maximum subarray of diff
Walk from left to right to get maximum subarray ends with index i
Walk from right to left to get maximum subarray starts with index i
-> Walk from left to right
-> 用一个max记录max of maximum subarray ends with index i
-> 这个max与maximum subarray starts with index i的和就是当前可以的到的最大profit
Time O(3n)
Space O(2n)
后来发现可以优化，只需要扫两遍

93.13 %
class Solution {
    public int maxProfit(int[] prices) {
        // Split from the middle
        // maxProfit end at current index and maxProfit start at current index + 1
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int[] endWithIndex = new int[prices.length];
        int[] startWithIndex = new int[prices.length];
        for (int i = 1; i < prices.length; i++) {
            endWithIndex[i] = prices[i] - prices[i - 1] + (endWithIndex[i - 1] > 0 ? endWithIndex[i - 1] : 0);
        }
        for (int j = prices.length - 2; j >= 0; j--) {
            startWithIndex[j] = prices[j + 1] - prices[j] + (startWithIndex[j + 1] > 0 ? startWithIndex[j + 1] : 0);
        }
        int leftMax = 0;
        int max = 0;
        for (int split = 0; split < prices.length ; split++) {
            leftMax = Math.max(leftMax, endWithIndex[split]);
            max = Math.max(max, leftMax + startWithIndex[split]);
        }
        return max;
    }
}

After optimized:
发现这个方法和一刷的基本一样的
果然是无招胜有招 啊
55.99 %
Time O(2n)
Space O(n)
class Solution {
    public int maxProfit(int[] prices) {
        // Split from the middle
        // maxProfit end at current index and maxProfit start at current index + 1
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int[] startWithIndex = new int[prices.length];
        for (int j = prices.length - 2; j >= 0; j--) {
            startWithIndex[j] = prices[j + 1] - prices[j] + (startWithIndex[j + 1] > 0 ? startWithIndex[j + 1] : 0);
        }
        int leftMax = 0;
        int max = 0;
        int dp = 0;
        for (int split = 0; split < prices.length ; split++) {
            if (split != 0) {
                int currDP = prices[split] - prices[split - 1] + (dp > 0 ? dp : 0);
                dp = currDP;
            }
            leftMax = Math.max(leftMax, dp);
            max = Math.max(max, leftMax + startWithIndex[split]);
        }
        return max;
    }

}


一刷
You may complete at most two transactions.
是一个比较常规的思路，因为要做两个transactions所以应该是以某一个index作为分割点，左边的maxProfit与右边的maxProfit相加
很容易想到的是那个左扫一遍记录一个array然后右扫一遍的同时比较出max的思路
好像是蓄水那道题吧
感觉这个不是dp的方法，不知道dp怎么做
哦！如果是半个dp的话就是左扫一遍的时候做dp，但是完全dp的方法还是不知道
77.56 % 
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        //leftMaxProfit[i] maxprofit in day[0, i]
        //rightMaxProfit[i] maxprofit in day[i, 0]
        int length = prices.length;
        int[] leftMaxProfit = new int[length];
        int leftMinPrice = prices[0];
 
                /*2 1 3 4 5 4 2 8 7
leftMinPrice      2 2 1 1 1 1 1 1 1
leftMaxProfit     0 0 2 3 4 3 1 7 6

max                           7   0  
rightMaxPrice                 8 8 7
rightMaxProfit                6 0 0
        */
        for (int i = 1; i < length; i++) {
            if (prices[i] > leftMinPrice) {
                leftMaxProfit[i] = Math.max(leftMaxProfit[i - 1], prices[i] - leftMinPrice);
            } else {
                leftMinPrice = prices[i];
                leftMaxProfit[i] = leftMaxProfit[i - 1];
            }
        }
        int max = 0;
        int rightMaxPrice = prices[length - 1];
        int rightMaxProfit = 0;
        for (int i = length - 2; i >= 0; i--) {
            if (prices[i] < rightMaxPrice) {
                rightMaxProfit = Math.max(rightMaxProfit, rightMaxPrice - prices[i]);
            } else {
                rightMaxPrice = prices[i];
            }
            max = Math.max(max, rightMaxProfit + leftMaxProfit[i]);
        }
        return max;
    }
}

120. Triangle

四刷 06/2022

Version #1 1D dp bottom up - not good

这个用了两个dp array交换

后来发现其实一个array就可以了

因为每次都是向后看

所以即使覆盖了自己也没关系

三角形 N^2个nodes，N-> length of the bottom layer

Time O(N^2)

Space O(N)

但是如果traverse所有的path应该是2^N paths，因为每次都可以向左走或者向右走

      *

  *      *

*    *    * 

Runtime: 2 ms, faster than 92.99% of Java online submissions for Triangle.

Memory Usage: 42.2 MB, less than 80.12% of Java online submissions for Triangle.

class Solution {

    public int minimumTotal(List<List<Integer>> triangle) {

        int lastIndex = triangle.size() - 1;

        List<Integer> bottom = triangle.get(lastIndex);

        int[][] dp = new int[2][bottom.size()];

        for (int i = 0; i < bottom.size(); i++) {

            dp[lastIndex % 2][i] = bottom.get(i);

        }

        for (int index = triangle.size() - 2; index >= 0; index--) {

            List<Integer> layer = triangle.get(index);

            for (int i = 0; i < layer.size(); i++) {

                dp[index % 2][i] = Math.min(dp[(index + 1) % 2][i], dp[(index + 1) % 2][i + 1]) + layer.get(i); 

            }

        }

        return dp[0][0];

    }

}

Version #2 1D dp bottom up -> optimal

Runtime: 2 ms, faster than 92.99% of Java online submissions for Triangle.

Memory Usage: 44.3 MB, less than 30.14% of Java online submissions for Triangle.

class Solution {

    public int minimumTotal(List<List<Integer>> triangle) {

        List<Integer> bottom = triangle.get(triangle.size() - 1);

        int[] dp = new int[bottom.size()];

        for (int i = 0; i < bottom.size(); i++) {

            dp[i] = bottom.get(i);

        }

        for (int index = triangle.size() - 2; index >= 0; index--) {

            List<Integer> layer = triangle.get(index);

            for (int i = 0; i < layer.size(); i++) {

                dp[i] = Math.min(dp[i], dp[i + 1]) + layer.get(i); 

            }

        }

        return dp[0];

    }

}

三刷

1D dp array -> top to bottom

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

站在当前level的当前Node, 可能有两种路径可以走向当前Node
1/上一层的i; 2/上一层的i-1
譬如5可以从3走来，也可以从4走来，所以dp[5] = 5 + Math.min(3, 4)
每一层的首尾都是corner case, 若i = 0 则没有 dp[i - 1], 若i = size - 1 则没有dp[i],但尾的情况不需要单独考虑因为dp[i]初始化为Integer.MAX_VALUE
所以Math.min(dp[i - 1], dp[i]) always select dp[i - 1]

Time O(n)
Space O(n) -> length of the leaf level

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        // i, i-1
        // dp[i] -> minimum path to get to current cell
        // dp[i] = cell + Math.min(dp[i+1], dp[i])
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int depth = triangle.size();
        int[] dp = new int[triangle.get(depth - 1).size()];
        dp[0] = triangle.get(0).get(0);
        for (int i = 1; i < depth; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i < depth; i++) {
            List<Integer> list = triangle.get(i);
            for (int j = list.size() - 1; j >= 0; j--) {
                if (j == 0) {
                    dp[j] = list.get(j) + dp[j];
                } else {
                    dp[j] = list.get(j) + Math.min(dp[j - 1], dp[j]);
                }
            }
        }
        int min = dp[0];
        for (int sum : dp) {
            min = Math.min(min, sum);
        }
        return min;
    }
}


这个是传统的dp的顺序
bottom to top
Start from the most detailed subproblem
95.75 %
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int[] dp = new int[triangle.get(triangle.size() - 1).size()];
        for (int row = triangle.size() - 1; row >= 0; row--) {
            List<Integer> level = triangle.get(row);
            for (int col = 0; col < level.size(); col++) {
                if (row == triangle.size() - 1) {
                    dp[col] = level.get(col);
                } else {
                    dp[col] = level.get(col) + Math.min(dp[col + 1], dp[col]);
                }
            }
           
        }
        return dp[0];
    }
}



Version #1 2D dp array

58.95 %
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null) return 0;
        int rows = triangle.size();
        if (rows == 0) return 0;
        int cols = triangle.get(rows - 1).size();
     
        int[][] dp = new int[rows][cols];
        for (int y = 0; y < cols; y++) {
            dp[rows - 1][y] = triangle.get(rows - 1).get(y);
            //System.out.println(dp[rows - 1][y]);
        }
        for (int x = rows - 2; x >= 0; x--) {
            for (int y = x; y >= 0; y--) {
                dp[x][y] = triangle.get(x).get(y) + Math.min(dp[x + 1][y], dp[x + 1][y + 1]);
            }
        }
        return dp[0][0];
    }
}

Version #2 1D rolling dp array
二刷
96.78 %
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null) return 0;
        int rows = triangle.size();
        if (rows == 0) return 0;
        int cols = triangle.get(rows - 1).size();
     
        int[] dp = new int[cols];
        for (int y = 0; y < cols; y++) {
            dp[y] = triangle.get(rows - 1).get(y);
            //System.out.println(dp[rows - 1][y]);
        }
        for (int x = rows - 2; x >= 0; x--) {
            for (int y = 0; y <= x; y++) {
                dp[y] = triangle.get(x).get(y) + Math.min(dp[y], dp[y + 1]);
            }
        }
        return dp[0];
    }
}

一刷

有一个简化代码的方法是
把dp size+1 然后不讨论 if (row == triangle.size() - 1)
也就是说把初始化省略
因为一开始dp array全是0
public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) throw new IllegalArgumentException();
        if (triangle.size() == 1) return triangle.get(0).get(0);
        int[] dp = new int[triangle.size()];
 
        //min path sum from bottom to curr layer
        for(int row = triangle.size() - 1; row >= 0; row--) {
            for (int col = 0; col <= row; col++) {
                if (row == triangle.size() - 1) dp[col] = triangle.get(row).get(col);
                else {
                    dp[col] = Math.min(dp[col], dp[col + 1]) + triangle.get(row).get(col);
                }
         
            }
        }
        return dp[0];
    }
}

72. Edit Distance

六刷 06/2022

Version #1 DP with optimized space

Time O(MN)

Space O(M)

Runtime: 12 ms, faster than 20.68% of Java online submissions for Edit Distance.

Memory Usage: 44 MB, less than 80.55% of Java online submissions for Edit Distance.

class Solution {

    public int minDistance(String word1, String word2) {

        int[][] dp = new int[2][word2.length() + 1];

        for (int i = 0; i <= word1.length(); i++) {

            for (int j = 0; j <= word2.length(); j++) {

                if (i == 0 || j == 0) {

                    dp[i % 2][j] = i + j; // delete all characters

                    continue;

                }

                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {

                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1];

                } else {

                    int min = Math.min(dp[(i - 1) % 2][j - 1], Math.min(dp[(i - 1) % 2][j], dp[i % 2][j - 1]));

                    dp[i % 2][j] = min + 1;

                }

            }

        }

        return dp[word1.length() % 2][word2.length()];

    }

}

五刷

18.16 %
class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null && word2 == null) return 0;
        if (word1 == null || word1.length() == 0) return word2.length();
        if (word2 == null || word2.length() == 0) return word1.length();
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        //  "" h o r s e
        //"" 0 1 2 3 4 5
        //r  1 2 3 2 3 4
        //o  2
        //s  3
        for (int i = 0; i <= word1.length(); i++) {
            for (int j = 0; j <= word2.length(); j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else {
                    if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
                    }
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

四刷
74.19 %
class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null && word2 == null) return 0;
        if (word1 == null) return word2.length();
        if (word2 == null) return word1.length();
        int[] dp = new int[word2.length() + 1];
        int prev = 0;
        int curr = 0;
        // prev -> dp[p1 - 1][p2 - 1]
        for (int p1 = 0; p1 <= word1.length(); p1++) {
            prev = dp[0];
            dp[0] = p1;
            for (int p2 = 1; p2 <= word2.length(); p2++) {
                if (p1 == 0) {
                    curr = p2;
                } else {
                    if (word1.charAt(p1 - 1) == word2.charAt(p2 - 1)) {
                        curr = prev;
                    } else {
                        curr = 1 + Math.min(prev, Math.min(dp[p2 - 1], dp[p2]));
                    }
                }
                prev = dp[p2];
                dp[p2] = curr;
            }
        }
        return dp[word2.length()];
    }
}

三刷
和Version#2 类似，区别在于每次用一个新的array来记录当前一行的dp
然后替换prev
40.38 %
class Solution {
    public int minDistance(String word1, String word2) {
        // dp[i][j] -> match word1 [0, i) to word2 [0, j)
        if (word1 == null && word2 == null) {
            return 0;
        }
        if (word1 == null) {
            return word2.length();
        }
        if (word2 == null) {
            return word1.length();
        }
        int[] prev = null;
        for (int i = 0; i <= word1.length(); i++) {
            int[] curr = new int[word2.length() + 1];
            curr[0] = i;
            for (int j = 1; j <= word2.length(); j++) {
                if (i == 0) {
                    curr[j] = j;
                    continue;
                }
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    curr[j] = prev[j - 1];
                } else {
                    curr[j] = 1 + Math.min(prev[j - 1], Math.min(prev[j], curr[j - 1]));
                }
            }
            prev = curr;
        }
        return prev[word2.length()];
    }
}

2ND TRY
Version #2 Optimized DP
Time O(mn) Space O(n)
99.73 %
class Solution {
    public int minDistance(String word1, String word2) {
if (word1 == null && word2 == null) {
return 0;
}
if (word1 == null) {
return word2.length();
}
if (word2 == null) {
return word1.length();
}
int[] dp = new int[word2.length() + 1];
int prev = 0;
int curr = 0;
// prev -> dp[p1 - 1][p2 - 1]
for (int p1 = 0; p1 <= word1.length(); p1++) {
for (int p2 = 0; p2 <= word2.length(); p2++) {
if (p1 == 0) {
curr = p2;
} else if (p2 == 0) {
curr = p1;
} else {
if (word1.charAt(p1 - 1) == word2.charAt(p2 - 1)) {
curr = prev;
} else {
curr = 1 + Math.min(prev, Math.min(dp[p2 - 1], dp[p2]));
}
}
prev = dp[p2];
dp[p2] = curr;
}
}
return dp[word2.length()];
}
}


Version #1 Naive DP
Time O(mn) Space O(mn)
State transfer function has some issue
When char1 == char2 -> dp[p1][p2] = dp[p1 - 1][p2 - 1]
Else either replace or delete or add

93.68 %
class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return 0;
        }
        // dp[p1][p2] -> min distance from word1 [0, p1) to word2 [0, p2)
        //    p1             p2
        // " h o r s e "  " r o s "
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for(int p1 = 0; p1 <= word1.length(); p1++) {
            for (int p2 = 0; p2 <= word2.length(); p2++) {
                if (p1 == 0) {
                    dp[p1][p2] = p2;
                } else if (p2 == 0) {
                    dp[p1][p2] = p1;
                } else {
                    if (word1.charAt(p1 - 1) == word2.charAt(p2 - 1)) {
                        dp[p1][p2] = dp[p1 - 1][p2 - 1];
                    } else {
                        dp[p1][p2] = 1 + Math.min(dp[p1 - 1][p2 - 1], Math.min(dp[p1 - 1][p2], dp[p1][p2 - 1]));
                    }
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}


1ST TRY
虽然写出来了但是还是不懂
看这个解释
 66.02 %
http://www.dreamxu.com/books/dsa/dp/edit-distance.html
public class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 ==  null) throw new IllegalArgumentException();
        if (word1.length() == 0) return word2.length();
        if (word2.length() == 0) return word1.length();
        int l1 = word1.length();
        int l2 = word2.length();
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        //dp[i1][i2]-> the edit distance for word1.substring[0, i1] 0<=i1<l1
                                          //word2.substring[0, i2] 0<=i2<l2
        //When i2 == 0 just delete i1 characters from word1
        for (int i1 = 0; i1 <= l1; i1++) {
            dp[i1][0] = i1;
        }
        //When i1 == 0 just insert i2 characters into word1
        for (int i2 = 0; i2 <= l2; i2++) {
            dp[0][i2] = i2;
        }
     
         for (int i1 = 1; i1 <= l1; i1++) {
            for (int i2 = 1; i2 <= l2; i2++) {
                if (word1.charAt(i1 - 1) == word2.charAt(i2 - 1)) {
                    dp[i1][i2] = dp[i1 - 1][i2 - 1];
                } else {
                    //dp[i1 - 1][i2] + 1 -> dp[i1][i2] delete i1 from word1
                    //dp[i1][i2 - 1] + 1 -> dp[i1][i2] insert i2 into word1
                    //dp[i1 - 1][i2 - 1] + 1 -> dp[i1][i2] replace i1 by i2
                    dp[i1][i2] = 1 + Math.min(Math.min(dp[i1 - 1][i2], dp[i1][i2 - 1]), dp[i1 - 1][i2 - 1]);
                }
            }
        }
        return dp[l1][l2];
    }
}

53. Maximum Subarray

三刷 07/2022

Version #3 Kadane's Algorithm

If the previous subarray sum is larger than zero, it's always nice to add the previous subarray sum

It calculates the maximum sum subarray ending at a particular position by using the maximum sum subarray ending at the previous position.

Time O(N)

Space O(1)

class Solution {

    public int maxSubArray(int[] nums) {

        int max = Integer.MIN_VALUE;

        int prevMax = 0;

        for (int i = 0; i < nums.length; i++) {

            int currMax = nums[i] + (prevMax > 0 ? prevMax : 0);

            prevMax = currMax;

            max = Math.max(max, currMax);

        }

        return max;

    }

}

二刷
Version #3
99.93 %
定义currMax为以当前nums[i]为结尾的最大的subArraySum
如果之前的sum为负， 就不加，只算当前nums[i]自己
但凡之前的sum为正，就加当前nums[i]上
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException();
        }
        int globalMax = Integer.MIN_VALUE;
        int currMax = 0;
        // max end with nums[i]
        for (int i = 0; i < nums.length; i++) {
            currMax = (currMax > 0 ? currMax : 0) + nums[i];
            globalMax = Math.max(globalMax, currMax);
        }
        return globalMax;
    }
}



Version #1 DP
三刷
56.95 %
class Solution {
    public int maxSubArray(int[] nums) {
        // dp[i] = max sub array sum end with nums[i]
        // dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]) -> nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0)
        if (nums == null || nums.length == 0) return 0;
        int prev = nums[0];
        int max = prev;
        for (int i = 1; i < nums.length; i++) {
            int curr = (prev > 0 ? prev : 0) + nums[i];
            max = Math.max(max, curr);
            prev = curr;
        }
        return max;
    }
}

一刷
78.03 %
需要注意因为初始化的是dp[0]
for loop是从index == 1开始的
所以要在一开始把max赋值为dp[0]
否则它没有机会与max进行比较

public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0){
            return 0;
        }
        int[] dp = new int[2];
        // dp[0] dp[1] dp[0] dp[1]...
        //[-2,    1,    -3,   4,   -1,2,1,-5,4]
        dp[0] = A[0];
        int max = dp[0];
        for (int i = 1; i < A.length; i++) {
            if (dp[(i - 1) % 2] > 0) dp[i % 2] = dp[(i - 1) % 2] + A[i];
            else dp[i % 2] = A[i];
            max = Math.max(max, dp[i % 2]);
        }
        return max;
    }
}

Version #2 Prefix sum
94.74 %
Find the most difference between prefix sum at index i and the minimum prefix sum before it
public class Solution {
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0){
            return 0;
        }
   
        int max = Integer.MIN_VALUE, sum = 0, minSum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
        }

        return max;
    }
}

32. Longest Valid Parentheses

二刷
Version #1 DP
95.24 %

当目前是')'的时候
找它前一个unmatched '('  -> prev  ->  i - 1 - dp[i - 1]
如果不存在，当前dp[i]就是0
如果存在，则该unmatched '(' 可以和current ')' match
dp[i] = dp[i - 1] + 2;
然而，unmatched '('  prev 之前可能存在valid substring
所以 dp[i] += dp[prev - 1];
Time O(n)
Space O(n)

class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        if (s == null || s.length() == 0) {
            return max;
        }
        char[] chars = s.toCharArray();
        // dp[i] -> longest length of valid substring end with index i
        int[] dp = new int[s.length()];
        // dp[0] = 0;
        // "()(())"
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == '(') {
                dp[i] = 0;
            } else {
                int prev = i - 1 - dp[i - 1];
                if (prev >= 0 && chars[prev] == '(') { // match
                    dp[i] = dp[i - 1] + 2;
                    if (prev - 1 >= 0) {
                        dp[i] += dp[prev - 1];
                    }
                }   
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }
}


Version #2 Stack
55.30 %
class Solution {
    public int longestValidParentheses(String s) {
        int max = 0;
        if (s == null || s.length() == 0) {
            return max;
        }
        char[] chars = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        int left = -1;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                stack.push(i);
            } else { // ')'
                // left -> start of valid substring
                if (stack.isEmpty()) {
                    left = i;
                } else {
                    stack.pop(); //"...()"
                    if (stack.isEmpty()) {
                        max = Math.max(max, i - left);
                    } else {
                        // (())
                        max = Math.max(max, i - stack.peek());
                    }
                }
            }
        }
        return max;
    }
}


一刷
Version #1 DP
dp定义为以当前index结尾的最长valid parentheses
 85.21 %
如果是'('，则一定为0
如果是')' 则尝试着将它与latest没有匹配过的'('进行匹配
  latest = currIndex - dp[curr - 1] - 1（检查几个可能越界的地方）
  1.latest<=0 不存在 || latest == ')' 那么证明无法匹配
  2. latest == '(' 正好可以跨越千山万水和当前的')' 匹配， 所以dp[curr] = dp[curr - 1] + 2
      注意！这里还没有结束因为"()()"
      有可能匹配之后正好与之前的接上，所以若prevIndex - 1 >= 0 的话，还要
      dp[curr] += dp[prevIndex - 1
思路还是很难的

public class Solution {
    public int longestValidParentheses(String s) {
        if (s ==  null || s.length() == 0) return 0;
        //The longest valid parentheses ends with current index
        int[] dp = new int[s.length()];
        int max = 0;
        char curr;
        for (int i = 0; i < s.length(); i++) {
            curr = s.charAt(i);
            if (curr == '(') {
                dp[i] = 0;
            } else {//curr == ')'
                if (i == 0) {
                    dp[i] = 0;
                    continue;
                }
                //The index of the latest invalid parentheses
                int prevIndex = i - dp[i - 1] - 1;
                if (prevIndex >= 0 && s.charAt(prevIndex) == '(') {
                    dp[i] = dp[i - 1] + 2;
                    if (prevIndex > 0) {
                        dp[i] = dp[i] + dp[prevIndex - 1];
                    }
                } else {
                    dp[i] = 0;
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

464. Can I Win

二刷
Version #2 Bit Manipulation

题目条件maxChoosableInteger will not be larger than 20
所以可以用一个int表示所有visited的情况

62.20 %
class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
            return false;
        }
        int visited = 0;
        // If number a is used, set bit a of visited = 1;
        Map<Integer, Boolean> map = new HashMap<>();
        return helper(maxChoosableInteger, desiredTotal, visited, map);   
    }
   
    private boolean helper(int maxChoosableInteger, int desiredTotal, int visited, Map<Integer, Boolean> map) {
        boolean flag = false;
        for (int i = 1; i <= maxChoosableInteger; i++) {
            if (!isUsed(visited, i)) {
                if (i >= desiredTotal) {
                    flag = true;
                    break;
                }
                int currVisited = setUsed(visited, i);
                if (!map.containsKey(currVisited)) {
                    map.put(currVisited, helper(maxChoosableInteger, desiredTotal - i, currVisited, map));
                }
                if (map.get(currVisited) == false) {
                    flag = true;
                    break;
                }     
            }
        }
        return flag;
    }
   
    private int setUsed(int visited, int num) {
        return visited | (1 << (num - 1));
    }
   
    private boolean isUsed(int visited, int num) {
        return ((visited >> (num - 1)) & 1) == 1;
    }
}

一刷
Version #1 Boolean array

效率很低1.08 %
这个题调了一晚上，一直通不过，一开始以为是toString这个函数用的有什么问题，后来发现不是
bug1
for (int i = used.length - 1; i > 0; i--)  写成for (int i = used.length - 1; i > 0 && !used[i]; i--)
这个bug可以说是非常有价值了，我忘记了中间的;;代表的是终止条件，也就是说一旦不满足就会立刻停止
bug2
对于 5 50这种情况，sum永远不会达到target，所以一开始就要返回FALSE啊！
总体来说boolean array toString效率很低很低，之后再重新写一个用Integer bit manipulation 做hash的

public class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) return false;
        //used[1] -> 1
        //used[i] -> i
        boolean[] used = new boolean[maxChoosableInteger + 1];
        //Key-Arrays.toString(used), Value-canIWin or not
        //Map<String, Boolean> visited = new HashMap<>();
        return canIWin(used, desiredTotal, new HashMap<String, Boolean>());
    }
    private boolean canIWin(boolean[] used, int desiredTotal, Map<String, Boolean> visited) {
        //System.out.println("String: " + Arrays.toString(used));
        Boolean currVisited = visited.get(Arrays.toString(used));
        if (currVisited != null) return currVisited;
     
        boolean result = false;
        for (int i = used.length - 1; i > 0; i--) {
            if (!used[i]) {
                if (i >= desiredTotal) {
                    //System.out.println(i + "i");
                    result = true;
                    visited.put(Arrays.toString(used), result);
                    return result;
                } else {
                    used[i] = true;
                    if (!canIWin(used, desiredTotal - i, visited)) result = true;
                    //backtracking
                    used[i] = false;
             
                    if (result) {
                        break;
                    }
                }
            }
        }
        visited.put(Arrays.toString(used), result);
        return result;
    }
}

403. Frog Jump

Version #3 HashMap of stones and Keep recording the failed tries
Give the k of last step, we know now we can only jump k-1, k, k+1
current position x + k-1/k/k+1 is not a valid stone position, then no need to explore
Pruning -> given a position x, if we have tried that there's no way for us to read the end given a k, then next time we come to x again, we know that we don't need to explore x with a k again
So I maintained a Map<Integer, Set<Integer>> whose key is position x, and value is set of invalid k

Time O(3^step) ??
Space O(nk) ??

79.15 %
class Solution {
    public boolean canCross(int[] stones) {
Set<Integer> stoneSet = new HashSet<>();
Map<Integer, Set<Integer>> failMap = new HashMap<>();
for (int stone : stones) {
stoneSet.add(stone);
failMap.put(stone, new HashSet<>());
}
if (!stoneSet.contains(1)) {
return false;
}
return dfs(failMap, stoneSet, 1, 1, stones[stones.length - 1]);
}

private boolean dfs(Map<Integer, Set<Integer>> failMap, Set<Integer> stoneSet, int x, int k, int target) {
if (x >= target) {
return true;
}
for (int nextK = k - 1; nextK <= k + 1; nextK++) {
if (nextK > 0 && stoneSet.contains(x + nextK)) {
if (!failMap.get(x).contains(nextK) && dfs(failMap, stoneSet, x + nextK, nextK, target)) {
return true;
} else {
failMap.get(x).add(nextK);
}
}
}
return false;
}
}


Version #2 HashMap of steps
二刷
感觉问题很直观，之前的Version#1思路挺有意思的，回头再看看
给每一个石头的position维护一个以position为key，能够往前走的steps set 为value的hashmap
每次走到一个石头，遍历它的set，如果从当前pos + k 能走到另外一个石头（hashmap contains key），那么就在能走到的那个石头的set里面加上k, k - 1, k + 1
如果pos + k恰好等于最后一块石头的pos，就直接返回true

一个bug是一直有 concurrent exception
问题大概出在对于set同时遍历又同时add
本来以为要一个iterator
后来发现在代码里加上 if (k > 1) {  set.add(k - 1) } 的限制条件就行了
这样保证正在iterate 的set 和之后add的set不会是同一个set
又仔细想了想，这个问题主要是针对 j = 0 (pos = 0) 和j = 1 (pos = 1)的时候两个edge case
走0步的时候会同时编辑正在iterate的set
62.82 %

class Solution {
    public boolean canCross(int[] stones) {
        if (stones == null || stones.length == 0) return false;
        if (stones.length == 1) return true;
        if (stones[1] > 1) return false;
        // key-stone position, value-set of possible steps
        Map<Integer, Set<Integer>> steps = new HashMap<>();
        int length = stones.length;
        for (int i = 0; i < length; i++) {
            steps.put(stones[i], new HashSet<>());
        }
        steps.get(0).add(1);
        Set<Integer> currKSet = null;
        Set<Integer> nextKSet = null;
        for (int j = 0; j < length - 1; j++) {
            for (int k : steps.get(stones[j])) {
                int next = stones[j] + k;
                if (next == stones[length - 1]) return true;
             
                nextKSet = steps.get(next);
                if (nextKSet != null) {
                    if (k > 1) {
                        nextKSet.add(k - 1);
                    }
                    nextKSet.add(k);
                    nextKSet.add(k + 1);
                }
            }
        }
        return false;
    }
}


Version #1
一个时间复杂度稍微有点高的方法，每次从position开始向后看所有的stones，如果小于dist就继续向后看，如果大于dist就break
这样当k很大的时候，相当于做了很多无用的搜索
优化方法是维护一个hashmap key是dist from start point，value是index
这样可以直接搜索出距离当前position 的距离为k-1, k, k+1的stone是否存在
优化有空再写

关键是要用memorization进行pruning，否则会TLE
因为这里对于每一个stone，k是不连续的，所以此处要对k用hashmap

所以是一个list of hashmap，每一个stone里面有一个相应的以k为key，canCross为value的hashmap
80.22 %
public class Solution {
    public boolean canCross(int[] stones) {
        if (stones == null) throw new IllegalArgumentException();
        if (stones.length <= 1) return true;
        //must jump 1 step
        if (stones[1] > 1) return false;
     
        //for every stone, there's a hash map
        //key-k(last step), value-canCross
        List<Map<Integer, Boolean>> visited = new ArrayList<>();
        for (int i = 0; i < stones.length; i++) {
            visited.add(new HashMap<Integer, Boolean>());
        }
     
        //Standing at the first stone && had jumped 1 step
        return canCross(stones, 1, 1, visited);
    }
    //Standing at each position, the frog can jump to the stone in k-1/k/k+1 units, k is the jumpint distance of the last step
    private boolean canCross(int[] stones, int position, int k, List<Map<Integer, Boolean>> visited) {
        Map<Integer, Boolean> visitedMap = visited.get(position);
        if (visitedMap.containsKey(k)) return visitedMap.get(k);
     
     
        if (position == stones.length - 1) return true;
        for (int nextPosition = position + 1; nextPosition < stones.length; nextPosition++) {
            int dist = stones[nextPosition] - stones[position];
            if (dist < k - 1) continue;
            if (dist > k + 1) break;
            //k-1 <= dist <= k+1
            if (canCross(stones, nextPosition, dist, visited)) {
                visitedMap.put(k, true);
                return true;
            }
        }
        visitedMap.put(k, false);
        return false;
    }
}

294. Flip Game II

二刷
Bug -> flag == ture的时候break, break之前没有reset array
注意backtracking 的所有出口，所有，不管是成功或者失败，都要reset status
96.98 % 
class Solution {
    public boolean canWin(String s) {
        if (s == null || s.length() == 0) return false;
        return helper(s.toCharArray(), new HashMap<>());
    }
   
    private boolean helper(char[] array, Map<String, Boolean> map) {
        boolean flag = false;
        for (int i = 1; i < array.length; i++) {
            // Try all flip possibilities, if one can make the next persion lose, then return true
            if (array[i] == '+' && array[i - 1] == '+') {
                array[i] = '-';
                array[i - 1] = '-';
                String curr = new String(array);
                if (!map.containsKey(curr)) {
                    map.put(curr, helper(array, map));
                }
                array[i] = '+';
                array[i - 1] = '+';
                if (map.get(curr) == false) {
                    flag = true;
                    break;
                }
            }
        }
        return flag;
    }
}

一刷
两个人同样聪明
如果能保证对手必输，则return true
如果对手能保证赢，则return false
这个题也是可以memorized
Version #1 Without Memorization
65.63 %
public class Solution {
    public boolean canWin(String s) {
        if (s == null && s.length() <= 2) return true;
        char[] chars = s.toCharArray();
        return canWin(chars);
    }
    //For every possible move, if there's one can make the competitor return false, then we can return true. Otherwise, return false
    private boolean canWin(char[] chars) {
        boolean result = false;
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] == '+' && chars[i + 1] == '+') {
                chars[i] = '-';
                chars[i + 1] = '-';
                if (canWin(chars) == false) result = true;
                //Set back
                chars[i] = '+';
                chars[i + 1] = '+';
            }
            if (result) return true;
        }
        return false;
    }
}

Version #2 Memorization with hashmap
93.75 %
If we see the same string that we have checked before, we can return that result directly

public class Solution {
    public boolean canWin(String s) {
        if (s == null && s.length() <= 2) return true;
        char[] chars = s.toCharArray();
        return canWin(chars, new HashMap<String, Boolean>());
    }
    //For every possible move, if there's one can make the competitor return false, then we can return true. Otherwise, return false
    private boolean canWin(char[] chars, Map<String, Boolean> visited) {
        Boolean haveVisited = visited.get(new String(chars));
        if (haveVisited != null) return haveVisited;
     
        boolean result = false;
        for (int i = 0; i < chars.length - 1; i++) {
            if (chars[i] == '+' && chars[i + 1] == '+') {
                chars[i] = '-';
                chars[i + 1] = '-';
                if (canWin(chars, visited) == false) {
                    result = true;
                }
                //Set back
                chars[i] = '+';
                chars[i + 1] = '+';
                visited.put(new String(chars), result);
                if (result) return true;
            }
        }
        return false;
    }
}

291. Word Pattern II

三刷 06/2022

Version #1 暴力DFS

这里一旦true以后就没有再做backtracking，直接返回

如果是那种需要加答案到result里面的题型就一定要backtracking

Time - the fanout factor could be N(length of the string) and the depth is M(length of the pattern), so a loose approximate estimate would be O(N^M)

Space - O(M + N)

Runtime: 3 ms, faster than 44.50% of Java online submissions for Word Pattern II.

Memory Usage: 42 MB, less than 62.25% of Java online submissions for Word Pattern II.

class Solution {

    public boolean wordPatternMatch(String pattern, String s) {

        Map<Character, String> map = new HashMap<>();

        Set<String> wordSet = new HashSet<>();

        return match(pattern, 0, s, 0, map, wordSet);

    }

    

    private boolean match(String pattern, int pIndex, String s, int sIndex, Map<Character, String> map, Set<String> wordSet) {

        if (pIndex == pattern.length() && sIndex == s.length()) {

            return true;

        }

        if (pIndex >= pattern.length() || sIndex >= s.length()) {

            return false;

        }

        char p = pattern.charAt(pIndex);

        if (map.containsKey(p)) {

            String word = map.get(p);

            if (sIndex + word.length() <= s.length() && word.equals(s.substring(sIndex, sIndex + word.length()))) {

                return match(pattern, pIndex + 1, s, sIndex + word.length(), map, wordSet);

            }

            return false;

        }

        for (int end = sIndex + 1; end <= s.length(); end++) {

            String word = s.substring(sIndex, end);

            if (wordSet.contains(word)) {

                continue;

            }

            map.put(p, word);

            wordSet.add(word);

            if (match(pattern, pIndex + 1, s, end, map, wordSet)) {

                return true;

            }

            map.remove(p);

            wordSet.remove(word);

        }

        return false;

    }

}

二刷
感觉就是暴力DFS解法
看了答案也没什么可优化的
顶多每次只传一个substring到下一层然后用一个startsWith(map.get(key))
同样的bug在 'ab' v.s. 'aa' 题意说的是bijection  就是one to one mapping
所以必须再用一个set记录mapped如果已经mapped过的String就不能成为另一个key的value， 即 we cannot have to keys pointing to the same string


52.62 %
class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern == null || str == null) {
            return false;
        }
        // dfs
        return dfs(pattern, 0, str, 0, new HashMap<>(), new HashSet<>());
    }
    private boolean dfs(String pattern, int pIndex,
                        String str, int sIndex, Map<Character, String> map, Set<String> mapped) {
        if (pIndex == pattern.length() && sIndex == str.length()) {
            return true;
        }
        if (pIndex == pattern.length() || sIndex == str.length()) {
            return false;
        }
        char key = pattern.charAt(pIndex);
        if (map.containsKey(key)) {
            String matchStr = map.get(key);
            for (int i = 0; i < matchStr.length(); i++) {
                if (sIndex + i >= str.length() || str.charAt(sIndex + i) != matchStr.charAt(i)) {
                    return false;
                }
            }
            return dfs(pattern, pIndex + 1, str, sIndex + matchStr.length(), map, mapped);
        }
     
        // key -> match str.substring(sIndex, j)
        for (int j = sIndex + 1; j <= str.length(); j++) {
            String matchStr = str.substring(sIndex, j);
            if (mapped.contains(matchStr)) {
                continue;
            }
            mapped.add(matchStr);
            map.put(key, str.substring(sIndex, j));
            if (dfs(pattern, pIndex + 1, str, j, map, mapped)) {
                map.remove(key);
                mapped.remove(matchStr);
                return true;
            }
            map.remove(key);
            mapped.remove(matchStr);
        }
        return false;
    }
}

一刷
比较正常的DFS
 46.65 %
有两个bug
一个是在(sIndex + i >= str.length() || pSubString.charAt(i) != str.charAt(sIndex + i)的时候要注意限制sIndex出界
一个是在下面这个例子
pattern - "ab"
string - "aa"
如果只用一个hashset的话，a和b会同时指向'a'，是不被允许的
所以还要加一个hashset保证每一个entry set里面的string都是唯一的
这个代码还有一些可以优化的地方，下次再改进


public class Solution {
    //Map<Character, String> key-char in pattern, value-substring in str
    public boolean wordPatternMatch(String pattern, String str) {
        if (pattern == null || str == null || pattern.length() > str.length()) return false;
        Map<Character, String> map = new HashMap<>();
        Set<String> visited = new HashSet<>();
        return wordPatternMatch(pattern, str, 0, 0, map, visited);
    }
 
    //if map.get(key) == null, trying to match pIndex->pLength substring seperately and do recursion call
    //Once we see a 'ture' we are OK to return true after 'backtracking'!
    //if map.get(key) != null, check if the value can match the substring in str starts at pIndex
    //if false return false, other wise return dfs(next layer)
    private boolean wordPatternMatch(String pattern, String str, int pIndex, int sIndex, Map<Character, String> map, Set<String> visited) {
        if (pIndex == pattern.length() && sIndex == str.length()) return true;
        if (pIndex == pattern.length() || sIndex == str.length()) return false;
     
        Character key = pattern.charAt(pIndex);
        String pSubString = map.get(key);
        boolean res = false;
        //1st time seen
        if (pSubString == null) {
            for (int i = sIndex + 1; i <= str.length(); i++) {
                String sub = str.substring(sIndex, i);
                if (visited.contains(sub)) continue;
                map.put(key, sub);
                visited.add(sub);
                //System.out.println(sub);
                if (wordPatternMatch(pattern, str, pIndex + 1, i, map, visited)) res = true;
                map.remove(key);
                visited.remove(sub);
                if (res) {
                    return res;
                }
            }
        } else {
            for (int i = 0; i < pSubString.length(); i++) {
                if (sIndex + i >= str.length() || pSubString.charAt(i) != str.charAt(sIndex + i)) return false;
            }
            return wordPatternMatch(pattern, str, pIndex + 1, sIndex + pSubString.length(), map, visited);
        }
        return false;
    }
}