No.1 How Many Numbers Are Smaller Than the Current Number

★解题思路

注意到这个问题的数字范围是 0 ~ 100, 那么我们可以直接用一个数组储存下每个数值的出现次数. 然后统计计算出前缀和就可以直接查询到比每个数字小的数字数量了.

时间复杂度 O(nk) 其中 k 表示数字的大小范围, 在这里也就是最大不超过 101

代码展示

class Solution {
   public int[] smallerNumbersThanCurrent(int[] nums) {
       if (nums == null) {
           return null;
       }
       int[] cnt = new int[101];
       // 计算: cnt[i] 表示 i 出现的次数
       for (int num : nums) {
           cnt[num]++;
       }
       // 计算前缀和: cnt[i] 表示 0 ～ i 出现的次数之和
       for (int i = 1; i <= 100; i++) {
           cnt[i] += cnt[i - 1];
       }
       // 统计答案, 此时 num 出现的次数就是 cnt[num - 1]
       int[] res = new int[nums.length];
       for (int i = 0; i < nums.length; i++) {
           res[i] = nums[i] == 0 ? 0 : cnt[nums[i] - 1];
       }
       return res;
   }
}

No.2 Rank Teams by Votes

★解题思路

这个问题比较简单, 按照题意所述, 统计出每个队伍在每个名次的得票数, 然后排序即可.

代码展示

class TeamRank {
   public char c;
   public List<Integer> cnt;
   public TeamRank(char c, List<Integer> cnt) {
       this.c = c;
       this.cnt = cnt;
   }
}

class Solution {
   public String rankTeams(String[] votes) {
       // 统计出每个队伍在每个名次的得票数
       // 由于最多有 26 个队伍, 所以从队名(char)映射到一个长度为 26 的 List
       Map<Character, List<Integer>> voteRes = new HashMap<>();
       for (String v : votes) {
           for (int i = 0; i < v.length(); i++) {
               char c = v.charAt(i);
               if (!voteRes.containsKey(c)) {
                   List<Integer> cnt = new ArrayList<>(26);
                   for (int j = 0; j < 26; j++) {
                       cnt.add(0);
                   }
                   voteRes.put(c, cnt);
               }
               List<Integer> cnt = voteRes.get(c);
               cnt.set(i, cnt.get(i) + 1);
           }
       }
       // 将已经统计好的键值对包装放入 TeamRank 实例, 然后排序
       List<TeamRank> tr = new ArrayList<>();
       for (Map.Entry<Character, List<Integer>> entry : voteRes.entrySet()) {
           tr.add(new TeamRank(entry.getKey(), entry.getValue())) ;
       }
       tr.sort((t1, t2) -> {
           // 按照每种排名的数量递减
           for (int i = 0; i < 26; i++) {
               if (!t1.cnt.get(i).equals(t2.cnt.get(i))) {
                   return t2.cnt.get(i) - t1.cnt.get(i);
               }
           }
           // 如果每种排名得票数量相同, 则按照队名的字典序
           return t1.c - t2.c;
       });
       // 构造答案字符串
       StringBuilder sb = new StringBuilder();
       for (TeamRank t : tr) {
           sb.append(t.c);
       }
       return sb.toString();
   }
}

No.3 Linked List in Binary Tree

★解题思路

通过深度优先遍历求出根到每一个叶子节点的路径, 然后查看是否存在一条路径包含链表.

代码展示

class Solution {
   public boolean isSubPath(ListNode head, TreeNode root) {
       List<Integer> path = new ArrayList<>();
       return dfs(root, path, head);
   }

   /**
    * dfs 遍历二叉树, 返回二叉树中是否有一直向下的路径和链表中的元素相等
    * @param node 二叉树节点
    * @param path 当前路径
    * @param head 链表头节点
    * @return true 表示存在这样的路径
    */
   private boolean dfs(TreeNode node, List<Integer> path, ListNode head) {
       if (node == null) {
           return containsList(path, head);
       }
       path.add(node.val);
       boolean res = dfs(node.left, path, head) || dfs(node.right, path, head);
       path.remove(path.size() - 1);
       return res;
   }

   /**
    * 判断列表中是否包含链表
    * @param path 列表
    * @param head 链表
    * @return true 表示 path 中包含 head
    */
   private boolean containsList(List<Integer> path, ListNode head) {
       int n = path.size();
       // 暴力求解, 枚举 path 的每一个位置作为起点
       // 比较能否与 head 完全匹配
       // 时间复杂度 o(nm)              n = size(path), m = size(head)
       // 优化: 使用 KMP 算法 o(n + m)
       for (int i = 0; i < n; i++) {
           boolean res = true;
           ListNode tmp = head;
           for (int j = i; j < n && tmp != null; j++, tmp = tmp.next) {
               if (!path.get(j).equals(tmp.val)) {
                   res = false;
                   break;
               }
           }
           if (res && tmp == null) {
               return true;
           }
       }
       return false;
   }
}

No.4 Minimum Cost to Make at Least One Valid Path in a Grid

★解题思路

可以看成最短路问题, 然后套用已有的最短路算法即可.

问题相当于在一个有向图中求起点 (0, 0) 到终点 (m - 1, n - 1) 的最短路径. 任意两个相邻的点之间都有有向边, 而边的长度是 0 或 1, 取决于该边的方向是否与 grid 中描述的方向一致.

而最短路中必然不会重复经过一个点, 所以不会出现一个点被改变两次方向的情况.

可选的最短路算法有:

Dijkstra 算法

Bellman-Ford 算法

SPFA 算法

其中 SPFA 算法不被国际认可, 因为该算法很容易退化到与 Bellman-Ford 一样的时间复杂度, 但是实际上大多数时候表现比 Bellman-Ford 优秀很多, 而且容易实现, 所以这里采用 SPFA 算法. SPFA 算法与 BFS 很相似, 但是一个节点可能会多次入队, 算法流程解释见代码注释.

代码展示

class Solution {
   public int minCost(int[][] grid) {
       final int[] dx = {0, 0, 0, 1, -1};
       final int[] dy = {0, 1, -1, 0, 0};
       int m = grid.length;
       int n = grid[0].length;
       // dis[x][y] 表示从起点到 (x, y) 的最短路径长度
       int[][] dis = new int[m][n];
       for (int i = 0; i < m; i++) {
           Arrays.fill(dis[i], Integer.MAX_VALUE);
       }
       dis[0][0] = 0;
       // 队列, 表示等待去优化其它点的最短路的点
       Queue<Integer> q = new LinkedList<>();
       // 初始队列中只有起点 (0, 0)
       q.offer(0);
       q.offer(0);
       while (!q.isEmpty()) {
           int x = q.poll();
           int y = q.poll();
           // 从队列中取出一个节点, 枚举它可以到达的点, 尝试去优化它可以到达的点的最短路径
           for (int i = 1; i <= 4; i++) {
               int nx = x + dx[i];
               int ny = y + dy[i];
               if (nx < 0 || ny < 0 || nx >= m || ny >= n) {
                   continue;
               }
               int cost = grid[x][y] == i ? dis[x][y] : dis[x][y] + 1;
               // 如果可以优化, 那么把这个被优化之后的点加入队列, 等待去优化其它点
               if (dis[nx][ny] > cost) {
                   dis[nx][ny] = cost;
                   q.offer(nx);
                   q.offer(ny);
               }
           }
       }
       return dis[m - 1][n - 1];
   }
}