121. Best Time to Buy and Sell Stock
如果把数组中的两个数两两作差，那么这道题跟求数组中的和最大的子序列是相同的，我们可以参照前面的题的做法。
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int maxCur = 0;
int maxSoFar = 0;
for(int i=1;i<prices.length;i++){
maxCur = Math.max(0,Math.max(prices[i]-prices[i-1],maxCur + prices[i] - prices[i-1]));
maxSoFar = Math.max(maxCur,maxSoFar);
}
return maxSoFar;
}
}
123. Best Time to Buy and Sell Stock III
解法1
这个问题可以转换成Best Time to Buy and Sell Stock I问题。
两次股票交易的核心是可以定义一个交易点，在这个交易点之前可以做一次交易(赚的最大数目的钱为firstProf)，在这个交易点之后可以做一个交易(赚的最大数目的钱是secondProf)。那么要求的是max(firstProf+secondProf)。但是这个方法的时间复杂度是O(N^2)，空间复杂度是O(1)。leetcode中显示超时。
可以使用两次扫描的方法避免上面的双重循环。
不同于Best Time to Buy and Sell Stock I中定义的初始状态A[i]表示第i天卖出挣的最大数目的钱，这个更进一步直接定义A[i]表示前i天赚的最大数目的钱。minPrice表示从第0天到第i-1天中的最低价格。
A[0]=0。（初始状态）
A[1]=max(prices[1]-prices[0],A[0])
A[2]=max(prices[2]-minPrice,A[1])
.....
即A[i]=max(price[i]-minPrice,A[i-1]).
A[0]=0
另外一次扫描从数组后向前扫描，定义B[i]表示从第i天到最后一天n能赚的最大数目的钱。maxPrice表示第i+1天到n天的最高价格。
B[n]=0。（初始状态）
B[n-1]=max(maxPrice-prices[n-1],B[n])
B[n-2]=max(maxPrice-prices[n-2],B[n-1])
.....
即B[i]=max(maxPrice-prices[i],B[i+1])
B[n]=0
那么以第i天为分割点能赚的最多数目的钱为A[i]+B[i]
问题的解为max{A[i]+B[i]}。0<=i<=n。
时间复杂度是O(N)，空间复杂度是O(N)。
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int[] asc = new int[prices.length];
int[] desc = new int[prices.length];
int n = prices.length;
int minprice = prices[0];
int maxProf = 0;
asc[0] = 0;
for(int i=1;i<n;i++){
asc[i] = Math.max(prices[i] - minprice,maxProf);
minprice = Math.min(prices[i],minprice);
maxProf = asc[I];
}
desc[prices.length-1] = 0;
maxProf = 0;
int maxprice = prices[prices.length-1];
for(int i=prices.length-2;i>=0;i--){
desc[i] = Math.max(maxprice-prices[i],maxProf);
maxprice = Math.max(maxprice,prices[I]);
maxProf = desc[I];
}
maxProf = 0;
for(int i=0;i<prices.length;i++){
maxProf = Math.max(maxProf,asc[i] + desc[I]);
}
return maxProf;
}
}
解法2
在Discuss中看到一种很棒的解法，代码只有10行左右，但是不是很好理解。
第二种解法的核心是假设手上最开始只有0元钱，那么如果买入股票的价格为price，手上的钱需要减去这个price，如果卖出股票的价格为price，手上的钱需要加上这个price。
它定义了4个状态：
Buy1[i]表示前i天做第一笔交易买入股票后剩下的最多的钱；
Sell1[i]表示前i天做第一笔交易卖出股票后剩下的最多的钱；
Buy2[i]表示前i天做第二笔交易买入股票后剩下的最多的钱；
Sell2[i]表示前i天做第二笔交易卖出股票后剩下的最多的钱；
那么：
Sell2[i]=max{Sell2[i-1],Buy2[i-1]+prices[I]}
Buy2[i]=max{Buy2[i-1],Sell[i-1]-prices[I]}
Sell1[i]=max{Sell[i-1],Buy1[i-1]+prices[I]}
Buy1[i]=max{Buy[i-1],-prices[I]}
可以发现上面四个状态都是只与前一个状态有关，所以可以不使用数组而是使用变量来存储即可。
这是leetcode中的讨论网址：https://leetcode.com/discuss/18330/is-it-best-solution-with-o-n-o-1
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length<2)
return 0;
int sell2 = 0;
int sell1 = 0;
int buy1 = Integer.MIN_VALUE;
int buy2 = Integer.MIN_VALUE;
for(int i =0;i<prices.length;i++){
sell2 = Math.max(sell2,buy2+prices[I]);
buy2 = Math.max(buy2,sell1-prices[I]);
sell1 = Math.max(sell1,buy1+prices[I]);
buy1 = Math.max(buy1,-prices[I]);
}
return sell2;
}
}
124. Binary Tree Maximum Path Sum
A path from start to end, goes up on the tree for 0 or more steps, then goes down for 0 or more steps. Once it goes down, it can’t go up. Each path has a highest node, which is also the lowest common ancestor of all other nodes on the path.
A recursive method maxPathDown(TreeNode node) (1) computes the maximum path sum with highest node is the input node, update maximum if necessary (2) returns the maximum sum of the path that can be extended to input node’s parent.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int maxLen = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if(root==null)
return maxLen;
backtracking(root);
return maxLen;
}
public int backtracking(TreeNode root){
if(root==null)
return 0;
int left = Math.max(0,backtracking(root.left));
int right = Math.max(0,backtracking(root.right));
maxLen = Math.max(maxLen,left + right + root.val);
return Math.max(left,right) + root.val;
}
}
127. Word Ladder
使用BFS的算法，具体的解释见：https://www.jianshu.com/p/753bd585d57e
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> wordSet = new HashSet<String>(wordList);
Set<String> visited = new HashSet<String>();
visited.add(beginWord);
int dist = 1;
while(!visited.contains(endWord)){
Set<String> temp = new HashSet<>();
for(String word:visited){
for(int i=0;i<word.length();i++){
char[] chars = word.toCharArray();
for(int j=(int)'a';j<(int)'z'+1;j++){
chars[i] = (char)j;
String newWord = new String(chars);
if(wordSet.contains(newWord)){
temp.add(newWord);
wordSet.remove(newWord);
}
}
}
}
dist += 1;
if(temp.size()==0)
return 0;
visited = temp;
}
return dist;
}
}
128. Longest Consecutive Sequence
用HashSet保存出现过的数，由于HashSet的查找时间都是O(1)的，所以可以得到O(n)的时间复杂度。
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for(int num:nums){
num_set.add(num);
}
int longestStreak = 0;
for(int num:num_set){
if(!num_set.contains(num-1)){
int currentNum = num;
int currentStreak = 1;
while(num_set.contains(currentNum+1)){
currentNum ++;
currentStreak ++;
}
longestStreak = Math.max(longestStreak,currentStreak);
}
}
return longestStreak;
}
}
129. Sum Root to Leaf Numbers
回溯法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int sumNumbers(TreeNode root) {
if(root==null)
return 0;
int res = backtracking(root,0,0);
return res;
}
public int backtracking(TreeNode root,int res,int cur){
if(root.left==null && root.right ==null){
res += (cur * 10 + root.val);
return res;
}
if(root.left != null){
res = backtracking(root.left,res,cur * 10 + root.val);
}
if(root.right!= null){
res = backtracking(root.right,res,cur * 10 + root.val);
}
return res;
}
}
130. Surrounded Regions
从图的四周进行遍历，如果与图的四周相连的O，那么是不会变为X的，所以进行DFS搜索，把这些O变为-，那么剩下的O则是被X包围的。最后将O变为X，将-变为O即可。
class Solution {
public void solve(char[][] board) {
if(board==null || board.length==0)
return;
int row = board.length;
int col = board[0].length;
for(int i=0;i<row;i++)
for(int j=0;j<col;j++){
if((i==0 || i==row-1 || j==0 || j==col-1) && board[i][j]=='O')
check(board,i,j,row,col);
}
for(int i=0;i<row;i++)
for(int j=0;j<col;j++){
if(board[i][j]=='O')
board[i][j] = 'X';
if(board[i][j]=='-')
board[i][j] ='O';
}
}
public void check(char[][] board,int x,int y,int row,int col){
board[x][y] = '-';
if(x>1 && board[x-1][y]=='O')
check(board,x-1,y,row,col);
if(x<row-2 && board[x+1][y]=='O')
check(board,x+1,y,row,col);
if(y>1 && board[x][y-1]=='O')
check(board,x,y-1,row,col);
if(y<col-2 && board[x][y+1]=='O')
check(board,x,y+1,row,col);
}
}
