Posted Updated LeetCode / Medium / 复习2 minutes read (About 295 words)

120. Triangle

问题
Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

动态规划，先将最左侧一列的值算出。
然后[i+1][j+1]根据[i][j+1]和[i][j]得出。
该动态规划表应是为三角形。
因此当i等于j时，[i+1][i+j]的数值只根据[i][j]得出。

例子：
代码里插入了一个print方法打印动态规划表。
当输入列表 [[2],[3,4],[6,5,7],[4,1,8,3]] 时：
其动态规划表为：

  • 2, 0, 0, 0,
  • 5, 6, 0, 0,
  • 11, 10, 13, 0,
  • 15, 11, 18, 16,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size()][triangle.size()];
        int min = Integer.MAX_VALUE;
        dp[0][0] = triangle.get(0).get(0);
        
        for (int i = 0; i < triangle.size()-1; i++){
            dp[i+1][0] = dp[i][0] + triangle.get(i+1).get(0);
        }        
        
        for (int i = 0; i < triangle.size()-1; i++){
            for (int j = 0; j <= i; j++){
                
                if ( i == j ){
                    dp[i+1][j+1] = dp[i][j] + triangle.get(i+1).get(j+1);
                }
                else{
                    dp[i+1][j+1] = Math.min(dp[i][j] + triangle.get(i+1).get(j+1),
                                        dp[i][j+1] + triangle.get(i+1).get(j+1));
                }
                
            }
        }
        //print(dp);
        for (int k = 0; k < triangle.size(); k++){
            min = Math.min(dp[triangle.size()-1][k],min);
        }
        return min;
    }
    
    private void print(int[][] text){
        for (int i = 0; i <text.length; i++){
            for (int j = 0; j < text[0].length; j++){
                System.out.print(text[i][j]+", ");
            }
            System.out.println();
        }
    }

}
Posted Updated LeetCode / Mediuma minute read (About 192 words)

198. House Robber

问题
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

动态规划。
dp数组记录经过i个房子后可以获得的最大值。
dp[i+1]的值等于dp[i-1]加上现有房子的钱（抢这个房子）与dp[i]的值（不抢这个房子）中的较大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int rob(int[] nums) {

        int[] money = new int[nums.length+1];
        money[0] = 0;
        money[1] = nums[0];
        
        for (int i = 1; i < nums.length; i++){
            money[i+1] = Math.max(money[i-1]+nums[i],money[i]);
            
        }
            
        return money[nums.length];
        
    }
}
Posted Updated LeetCode / Easy / 复习a few seconds read (About 86 words)

118. Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

动态规划，直接按照杨辉三角形的定义计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> generate(int numRows) {
        ArrayList<List<Integer>> ans = new ArrayList<List<Integer>>(numRows);

        for (int i = 0; i < numRows ; i++){
            List<Integer> arr = new ArrayList<Integer>(i+1);
  
            for (int j = 0; j <= i; j++){
                if ( j == 0 || j == i ){
                    arr.add(1);
                }
                else{
                    arr.add(ans.get(i-1).get(j-1)+ans.get(i-1).get(j));
                }
            }
            ans.add(arr);
        }
        return ans;
    }
}

Posted Updated LeetCode / Easya minute read (About 155 words)

121. Best Time to Buy and Sell Stock

问题描述
You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

采用dp的思想，先计算一遍盈利差，再计算一遍最大收益。
空间上还可以优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxProfit(int[] prices) {
        int best = 0;
        int[] difference = new int[prices.length];
        difference[0] = 0;
        for (int i = 1; i < prices.length; i++ ){
            difference[i] = prices[i] - prices[i - 1];
            if ( difference[i] + difference[i - 1] > difference[i] ){
                difference[i] = difference[i] + difference[i - 1];
            }
            if (difference[i] > best){
                best = difference[i];
            }
        }
        return best;
    }
}


Follow

Recents

Archives

Links

×