No.1能否连接形成数组

解题思路

题目所说 "数组内的元素互不相同" 是个很重要的条件.

直接从头开始看 arr, 根据当前的元素在 pieces 中找到相应的 piece 来拼接, 找不到或者拼接失败则返回 false.

代码展示

**classSolution** {     **public** boolean **canFormArray**(**int**[] arr, **int**[][] pieces){         Map<Integer, **int**[]> map = **new** HashMap<>();         **for** (**int**[] piece : pieces) {             map.put(piece[0], piece);         }         **for** (**int** i = 0; i < arr.length; ) {             **if** (!map.containsKey(arr[i])) {                 **return**false;             }             **int**[] piece = map.get(arr[i]);             **for** (**int** j = 0; j < piece.length; i++, j++) {                 **if** (arr[i] != piece[j]) {                     **return**false;                 }             }         }         **return**true;     } }

No.2 统计字典序元音字符串的数目 解题思路

可以看作动态规划, 不过比较简单.

递推公式: f(i, j) = sum(0, j)[f(i - 1, k)]

f(i, j) 表示长度为 i 的, 以元音 j 结尾的字典序字符串数目.

代码展示

class Solution {    public int countVowelStrings(int n) {         int[][] f = new int[n + 1][5];         Arrays.fill(f[1], 1);         for (int i = 2; i <=n; i++) {             for (intj = 0;j < 5; j++) {                 for (intk = 0;k <= j;k++) {                     f[i][j] += f[i-1][k];                 }             }         }         returnf[n][0] + f[n][1] + f[n][2] + f[n][3] + f[n][4];     } }

No.3可以到达的最远建筑

解题思路

二分答案.

判断是否可以到达建筑 mid, 只需要将到达该建筑前所有的 "上坡路" 排序, 坡度大的用梯子, 剩下的用砖块.

代码展示

class Solution {     publicint furthestBuilding(int[] heights, int bricks, int ladders) {         intleft = 0, right = heights.length;         while (left + 1 < right) {             intmid = (left + right) / 2;             if (check(mid, bricks, ladders, heights)) {                 left = mid;             } else {                 right = mid;             }         }         return (check(right, bricks, ladders, heights) ? right : left) - 1;     }

    boolean check(intmid, int bricks, int ladders, int[] heights) {         List diff = new ArrayList<>();         for (int i = 1; i < mid; i++) {             if (heights[i] > heights[i - 1]) {                 diff.add(heights[i] - heights[i - 1]);             }         }         Collections.sort(diff);         int sum = 0;         for (int i = 0; i <  diff.size() - ladders; i++) {             sum += diff.get(i);         }         return bricks >= sum;     } }

No.4 第K条最小指令

解题思路

先使用动态规划求出 count[i][j] 表示从 (i, j) 走到终点的方案数. 然后根据下一步的方案数判断应该往右走还是往下走.

代码展示

class Solution {     public String kthSmallestPath(int[] destination, int k) {         int row = destination[0];         int col = destination[1];         int[][] count = new int[row + 1][col + 1];         count[row][col] = 1;         dp(0, 0, count);

        StringBuilder res = new StringBuilder();         for (int x = 0, y = 0; x != row || y != col; ) {             if (x == row) {                 y++;                 res.append("H");             } else if (y == col) {                 x++;                 res.append("V");             } else if (y + 1 <=col && k <= count[x][y + 1]) {                 // 往右走的方案数不少于 k, 说明第 k 种方案在右边                 y++;                 res.append("H");             } else {                 // 往右走的方案数少于 k, 说明第 k 种方案在下边                 k-= count[x][y + 1];                 x++;                 res.append("V");             }         }         returnres.toString();     }

    privateintdp(intx, inty, int[][] count) {         if (count[x][y] > 0) {             return count[x][y];         }         if (x + 1 < count.length) {             count[x][y] += dp(x + 1, y, count);         }         if (y + 1 < count[0].length) {             count[x][y] += dp(x,y + 1, count);         }         returncount[x][y];     } }