303. Range Sum Query - Immutable
用一個(gè)數(shù)組保存從0到當(dāng)前位置的和。
class NumArray {
int[] sumnums;
public NumArray(int[] nums) {
if(nums.length==0)
return;
sumnums = new int[nums.length];
sumnums[0] = nums[0];
for(int i=1;i<nums.length;i++){
sumnums[i] = sumnums[i-1] + nums[I];
}
}
public int sumRange(int i, int j) {
if(i==0)
return sumnums[j];
return sumnums[j] - sumnums[i-1];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
304. Range Sum Query 2D - Immutable
借鑒303題的思路，同樣構(gòu)造一個(gè)求和的矩陣，行列關(guān)系共分為四種寞忿，需要仔細(xì)分析每種情況下的計(jì)算：
class NumMatrix {
int[][] summatrix;
public NumMatrix(int[][] matrix) {
if(matrix==null || matrix.length==0)
return;
summatrix = new int[matrix.length][matrix[0].length];
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[i].length;j++){
if(i==0 && j==0)
summatrix[i][j] = matrix[i][j];
else if(i==0)
summatrix[i][j] = summatrix[i][j-1] + matrix[i][j];
else if(j==0)
summatrix[i][j] = summatrix[i-1][j] + matrix[i][j];
else
summatrix[i][j] = summatrix[i-1][j] + summatrix[i][j-1] - summatrix[i-1][j-1] + matrix[i][j];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
if(row1==0 && col1==0)
return summatrix[row2][col2];
else if(row1==0)
return summatrix[row2][col2] - summatrix[row2][col1-1];
else if(col1==0)
return summatrix[row2][col2] - summatrix[row1-1][col2];
else
return summatrix[row2][col2] - summatrix[row1-1][col2] - summatrix[row2][col1-1] + summatrix[row1-1][col1-1];
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/
307. Range Sum Query - Mutable
這里同303題，用另一個(gè)數(shù)組保存了原數(shù)組中每個(gè)元素的值，每次更新的時(shí)候驾讲，不要忘記將該位置對(duì)應(yīng)元素的值進(jìn)行更新。
class NumArray {
int[] sumnums;
int[] orgnums;
public NumArray(int[] nums) {
if(nums==null || nums.length==0)
return;
sumnums = new int[nums.length];
sumnums[0] = nums[0];
orgnums = new int[nums.length];
orgnums[0] = nums[0];
for(int i=1;i<nums.length;i++){
sumnums[i] = sumnums[i-1] + nums[I];
orgnums[i] = nums[I];
}
}
public void update(int i, int val) {
for(int j=i;j<sumnums.length;j++){
sumnums[j] += (val - orgnums[I]);
}
orgnums[i] = val;
}
public int sumRange(int i, int j) {
if(i==0)
return sumnums[j];
return sumnums[j] - sumnums[i-1];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(i,val);
* int param_2 = obj.sumRange(i,j);
*/
309. Best Time to Buy and Sell Stock with Cooldown
使用回溯法席赂，超時(shí)吮铭。。
class Solution {
int maxProfit = 0;
public int maxProfit(int[] prices) {
backprop(prices,0,0,0,0);
return maxProfit;
}
public void backprop(int[] prices,int start,int profit,int buyPrice,int type){
if(start >= prices.length){
maxProfit = Math.max(maxProfit,profit);
}
if(type==0){
for(int i=start;i<prices.length;i++){
backprop(prices,i+1,profit,prices[i],1);
}
}
else if(type==1){
for(int i=start;i<prices.length;i++){
backprop(prices,i+2,profit + (prices[i]-buyPrice),0,0);
}
}
}
}
此題需要維護(hù)三個(gè)一維數(shù)組buy, sell颅停，和rest谓晌。其中：
buy[i]表示在第i天之前最后一個(gè)操作是買，此時(shí)的最大收益癞揉。
sell[i]表示在第i天之前最后一個(gè)操作是賣纸肉，此時(shí)的最大收益。
rest[i]表示在第i天之前最后一個(gè)操作是冷凍期喊熟，此時(shí)的最大收益柏肪。
我們寫出遞推式為：
buy[i] = max(rest[i-1] - price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])
rest[i] = max(sell[i-1], rest[i-1])
解讀一下，第一個(gè)公式buy[i]逊移，如果第i天可以買预吆，那么i-1天會(huì)是冷凍期，否則胳泉，不能進(jìn)行購買拐叉，因此比較rest[i-1] - price和 buy[i-1]的大小。第二個(gè)公式sell[i]扇商，可以賣的條件是凤瘦，i-1天之前最后一個(gè)操作時(shí)買入股票，否則案铺，不能賣出蔬芥，因此比較buy[i-1] + price和sell[i-1]。第三個(gè)式子，冷凍期的可能性有兩個(gè)笔诵，一個(gè)是昨天剛進(jìn)行賣的交易返吻，另一個(gè)是繼續(xù)冷凍期。
上述遞推式很好的表示了在買之前有冷凍期乎婿，買之前要賣掉之前的股票测僵。一個(gè)小技巧是如何保證[buy, rest, buy]的情況不會(huì)出現(xiàn)，這是由于buy[i] <= rest[i]谢翎， 即rest[i] = max(sell[i-1], rest[i-1])捍靠，這保證了[buy, rest, buy]不會(huì)出現(xiàn)。
另外森逮，由于冷凍期的存在榨婆，我們可以得出rest[i] = sell[i-1]，這樣褒侧，我們可以將上面三個(gè)遞推式精簡(jiǎn)到兩個(gè)：
buy[i] = max(sell[i-2] - price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])
因此良风，代碼如下:
class Solution {
public int maxProfit(int[] prices) {
if(prices==null || prices.length <2)
return 0;
int[] buy = new int[prices.length];
int[] sell = new int[prices.length];
buy[0] = -prices[0];
buy[1] = Math.max(-prices[0],-prices[1]);
sell[0] = 0;
sell[1] = Math.max(0,prices[1]-prices[0]);
for(int i=2;i<prices.length;i++){
buy[i] = Math.max(sell[i-2] - prices[i],buy[i-1]);
sell[i] = Math.max(buy[i-1] + prices[i],sell[i-1]);
}
return sell[prices.length-1];
}
}
310. Minimum Height Trees
答案只可能有一個(gè)或兩個(gè)節(jié)點(diǎn)。思路為依次刪除葉子節(jié)點(diǎn)璃搜，剩下的1/2個(gè)節(jié)點(diǎn)即為解拖吼。
速度問題：如果每次遍歷選出葉子節(jié)點(diǎn)，速度比較慢这吻，可以每次刪除當(dāng)前葉子節(jié)點(diǎn)時(shí)，將新的葉子節(jié)點(diǎn)記錄下來篙议。
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> leaves = new ArrayList<>();
if(n <= 1) {
return Collections.singletonList(0);
}
Map<Integer, Set<Integer>> graph = new HashMap<>(); // list of edges to Ajacency Lists
for(int i = 0; i < n; i++) {
graph.put(i, new HashSet<Integer>());
}
for(int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
for(int i = 0; i < n; i++) {
if(graph.get(i).size() == 1) {
leaves.add(i);
}
}
while(n > 2) {
n -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for(int leaf : leaves) {
for(int newLeaf : graph.get(leaf)) {
graph.get(leaf).remove(newLeaf);
graph.get(newLeaf).remove(leaf);
if(graph.get(newLeaf).size() == 1) {
newLeaves.add(newLeaf);
}
}
}
leaves = newLeaves;
}
return leaves;
}
}
