6.15号刷题

第一题 62. Unique Paths

题目描述

一个机器人位于m x n隔板的左上角（在图中标记为“起点”）。

机器人在任意一点只可以向下或者向右移动一步。机器人尝试到达隔板的右下角（图中标记为“终点”）

有多少种可能的路径？

注意：m和n最多为100

算法

利用公式

经过推到，我们可以知道，对于 m n 的地图，机器人需要向下走m - 1 次，向右走n - 1次。令 N = m + n - 2的话。我们所有的可能性为C(N, m-1) C(n-1, n-1)。可以直接求解

public class uniquePaths62 {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) return 1;
        int down = m - 1, left = n - 1;
        int all = down + left;
        double sum = 1;

        for (int i = 1; i <= down; i++) {
            sum = sum * (all - down + i) / i;
        }
        return (int) sum;
    }
}

DP求解

对于地图中的任意一格map[i][j]， 都是要么由map[i-1][j]到达要么由map[i][j-1]到达。因此，我们可以从头开始累积，计算出最后的所有可能性

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] map = new int[m][n];
        if (m == 1 || n == 1) return 1;
        for (int i = 0; i < m; i++) {
            map[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            map[0][j] = 1;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                map[i][j] = map[i-1][j] + map[i][j-1];
            }
        }
        
        return map[m - 1][n - 1];        
    }
}

第二题 63. Unique Paths II

题目描述

现在，在机器人前进的道路上可能存在障碍，仍然求有多少条道路可以到达目的地。

算法

动态规划算法，方法与之前一样

public class uniquePathsWithObstacles63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;

        int[] dp = new int[m];
        dp[0] = 1;

        for (int[] row : obstacleGrid) {
            for (int j = 0; j < m; j++) {
                if (row[j] == 1) {
                    dp[j] = 0;
                } else if (j > 0) {
                    dp[j] += dp[j - 1];
                }
            }
        }

        return dp[m - 1];
    }
}

第三题 46. Permutations

题目描述

给定一个唯一数字的集合，返回所有可能的排列。

测试用例如题目描述。

算法

利用回溯，模板是相同的，只是结束的条件稍微不同。

public class permute46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curRes = new ArrayList<>();
        backtrack(res, curRes, nums);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> curRes, int[] nums) {
        if (curRes.size() == nums.length) {
            res.add(new ArrayList<>(curRes));
            return;
        } else {
            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];
                if (curRes.contains(num)) continue;
                curRes.add(num);
                backtrack(res, curRes, nums);
                curRes.remove(curRes.size() - 1);
            }
        }
    }
}

第四题 47. Permutations II

题目描述

这次给定的集合中，有重复的数字

算法

增加一个判定矩阵used[]来决定是否加入当前的数字，如果前一个used[i-1]是未使用过的，且当前数字与前一个相同的话，就跳过

public class permuteUnique47 {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curRes = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(res, curRes, nums, used);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> curRes, int[] nums, boolean[] used) {
        if (curRes.size() == nums.length) {
            res.add(new ArrayList<>(curRes));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (used[i]) continue;
                if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) continue;
                curRes.add(nums[i]);
                used[i] = true;
                backtrack(res, curRes, nums, used);
                used[i] = false;
                curRes.remove(curRes.size() - 1);
            }
        }
    }
}

第五题 131. Palindrome Partitioning

题目描述

给定一个String，在不改变顺序的情况下，将这个String分成任意份，要求每一份都是由回文字符组成。求所有的可能性

算法

依然使用回溯的方法，对每一段判断是否是一个回文字符，是的话进行操作，不是的话继续循环。

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> curRes = new ArrayList<>();
        
        backtrack(res, curRes, s, 0);
        return res;
    }
    public void backtrack (List<List<String>> res, List<String> curRes, String s, int start) {
        if (start == s.length()) {
            res.add(new ArrayList<>(curRes));
        } else {
            for (int i = start; i < s.length(); i++) {
                if (isPalindrome(s.substring(start, i + 1))) {
                    curRes.add(s.substring(start, i + 1));
                    backtrack(res, curRes, s, i + 1);
                    curRes.remove(curRes.size() - 1);
                }
            }
        }
    }
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++; right--;
        }
        return true;
    }
}

第六题 526. Beautiful Arrangement

题目描述

如果整数1到N的排列，第i个数满足下列规则之一，则称该排列为“美丽排列”

第i个位置的数字可以被i整除

1. i可以被第i个位置的数字整除
2. 给定数字N，求有多少个美丽排列

注意：N是正整数并且不超过15

算法

回溯

自己的

public class countArrangement526 {
    int sum;
    public int countArrangement(int N) {
        sum = 0;
        boolean[] used = new boolean[N + 1];
        List<Integer> nums = new ArrayList<>();
        nums.add(0);
        backtrack(N, used, nums);
        return sum;
    }
    public void backtrack(int N, boolean[] used, List<Integer> nums) {
        if (nums.size() == N + 1) sum++;
        else {
            for (int i = 1; i < N + 1; i++) {
                if (used[i]) continue;
                used[i] = true;
                int numAti = i, ith = nums.size();
                if (numAti % ith == 0 || ith % numAti == 0) {
                    nums.add(numAti);
                    backtrack(N, used, nums);
                    nums.remove(nums.size() - 1);
                }
                used[i] = false;
            }
        }
    }
}

改进后

public class Solution {
    int sum;
    public int countArrangement(int N) {
        if (N == 0) return 0;
        sum = 0;
        boolean[] used = new boolean[N + 1];
        backtrack2(N, used, 1);
        return sum;
    }
    
    public void backtrack2(int N, boolean[] used, int position) {
        if (position > N) {
            sum++;
        } else {
            for (int i = 1; i < N + 1; i++) {
                if (used[i]) continue;
                used[i] = true;
                if (position % i == 0 || i % position == 0) {
                    backtrack2(N, used, position + 1);
                }
                used[i] = false;
            }
        }
    }
}

第七题 401. Binary Watch

题目描述

一个二进制手表顶端有4盏LED灯表示小时(0-11)，底部有6盏LED灯表示分钟(0-59)。

每一盏LED灯表示一个0或1，最右端为最低位。

例如上图中的例子读数为”3:25”。

给定一个非负整数n表示当前燃亮的LED灯数，返回所有可能表示的时间。

注意：

输出顺序不重要。

小时不可以包含前缀0，例如”01:00”是无效的，应当为”1:00”。

分钟必须包含两位数字，可以包含前导0，例如”10:2”是无效的，应当为”10:02”。

算法

位运算（Bit Manipulation）

10盏灯泡的燃亮情况可以通过0-1024进行表示，然后计数二进制1的个数即可。

利用位运算将状态拆分为小时和分钟。

public class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> times = new ArrayList<>();
        for (int h = 0; h < 12; h++)
            for (int m = 0; m < 60; m++)
                if (Integer.bitCount(h) + Integer.bitCount(m) == num)
                    times.add(String.format("%d:%02d", h, m));
        return times;
    }
}