LeetCode刷题笔记——腾讯面试精选50题（5）

算法
, , ,

贪心算法和动态规划

爬楼梯

思路：不难看出这题本质上就是斐波那契数列，也是动态规划的经典问题。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        int a=1, b=2;
        for (int i=3; i<=n+1; i++) {
            int c = a+b;
            a = b;
            b = c;
        }
        return a;
    }
}

买卖股票的最佳时机

思路：每日结束时有两种状态：持有股票和未持有股票。每日的状态取决于昨日的状态与今日是否买入或卖出股票。可得状态转移方程：dp[i][0]=max(dp[i-1][0], dp[i-1][1]+prices[i])，dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i])。

更多关于股票问题的动态规划解法详细可见LeetCode：一个方法团灭 6 道股票问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n==0) return 0;
        int dp_i_0 = 0;
        int dp_i_1 = -prices[0];
        for (int i=1; i<n; i++) {
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(-prices[i], dp_i_1);
        }
        return dp_i_0;
    }
}

买卖股票的最佳时机 II

思路：只要第二天比第一天有涨，就可以卖出。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length<=1) 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];
        }
        return profit;
    }
}

格雷编码

思路：格雷编码的位数每增加一，就在原有数的二进制表示最前面加1。对原序列逆序排列再加1，此时可以保证相邻两数的不同位只有1个。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        for (int i = 1; i<=n; i++) {
            int plus = (int)Math.pow(2, i-1);
            for (int j = res.size()-1; j>=0; j--) {
                res.add(res.get(j)+plus);
            }
        }
        return res;
    }
}

不同路径

思路：走到一个格子有两条路径：从它的左边一格或者从它的上边一格。由此可得状态转移方程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int uniquePaths(int m, int n) {
        if (m==0 || n==0) return 0;
        int[][] matrix = new int[m][n];
        for (int r=0; r<m; r++) matrix[r][0] = 1;
        for (int c=0; c<n; c++) matrix[0][c] = 1;
        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                matrix[i][j] = matrix[i-1][j] + matrix[i][j-1];
            }
        }
        return matrix[m-1][n-1];
    }
}

回溯算法

子集

思路：回溯算法，交换元素迭代后再交换回来，完成一次回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        subsets(nums, res, temp, 0);
        return res;
    }

    public void subsets(int[] nums, List<List<Integer>> res, List<Integer> temp, int i) {
        res.add(new ArrayList<>(temp));
        for (int j=i; j<nums.length; j++) {
            temp.add(nums[j]);
            subsets(nums, res, temp, j+1);
            temp.remove(temp.size()-1);
        }
    }
}

全排列

思路：回溯算法。

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        permute(nums, 0, res);
        return res;

    }

    public void permute(int[] nums, int index, List<List<Integer>> res) {
        if (index==nums.length-1) {
            List<Integer> temp = new ArrayList<>();
            for (int i=0; i<nums.length; i++) {
                temp.add(nums[i]);
            }
            res.add(temp);
        } else {
            for (int i=index; i<nums.length; i++) {
                swap(nums, i, index);
                permute(nums, index+1, res);
                swap(nums, i, index);
            }
        }

    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}