No.1 Generate a String With Characters That Have Odd Counts

解题思路

从解题的角度来看, 我们只需要两个字符就可以构造出符合条件的字符串. 如果 n 是奇数, 那么直接返回同一种字符重复 n 次即可; 如果 n 是偶数, 那么返回单个字符 a 加上字符 b 重复 n - 1 次即可.

代码展示

class Solution {
   public String generateTheString(int n) {
       if (n % 2 == 0) {
           return "a" + "b".repeat(n - 1);
       } else {
           return "a".repeat(n);
       }
   }
}

class Solution {
   public String generateTheString(int n) {
       if (n % 2 == 0) {
           char[] arr = new char[n - 1];
           Arrays.fill(arr, 'b');
           return "a" + new String(arr);
       } else {
           char[] arr = new char[n];
           Arrays.fill(arr, 'a');
           return new String(arr);
       }
   }
}

No.2 Bulb Switcher III 解题思路

若某一时刻 t 所有亮着的灯都是蓝色, 那么该时刻亮着的灯一定是第 1 盏到第 t 盏灯. 也就是说 light[0] ~ light[t - 1] 都是 [1, t] 之间的数值.

由于灯不会被重复打开, 所以当 light[0] ~ light[t - 1] 的最大值为 t 时, 就说明这 t 个时刻把第 1 盏到第 t 盏灯都打开了. 所以, 我们只需要统计满足 max{light[0] ~ light[t - 1]} == t 的时刻的数量即可.

代码展示

class Solution {
   public int numTimesAllBlue(int[] light) {
       int max = 0;
       int res = 0;
       for (int i = 0; i < light.length; i++) {
           max = Math.max(light[i], max);
           res += (max == i + 1) ? 1 : 0;
       }
       return res;
   }
}

No.3 Time Needed to Inform All Employees 解题思路

消息从树根发出, 层层向下通知, 最终到达叶子节点. 所有节点被通知的时间也就是最后一个接收到通知的叶子节点接收通知所花费的时间.

所以我们只需要求出距离根节点最远的叶子节点的距离即可.

代码展示

class Solution {
   public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
       // 建图, sons[i] 表示节点 i 的子节点
       List<List<Integer>> sons = new ArrayList<>();
       for (int i = 0; i <= n; i++) {
           sons.add(new ArrayList<>());
       }
       // 依次添加每一条边
       for (int i = 0; i < n; i++) {
           if (manager[i] >= 0) {
               sons.get(manager[i]).add(i);
           }
       }
       // 一次遍历得到答案
       return maxLength(headID, sons, informTime);
   }

   private int maxLength(int cur, List<List<Integer>> sons, int[] informTime) {
       // 返回 cur 到叶子节点的最长路径
       int res = 0;
       for (int next : sons.get(cur)) {
           // cur 到 next 的边长为 informTime[cur]
           res = Math.max(maxLength(next, sons, informTime) + informTime[cur], res);
       }
       return res;
   }
}

No.4 Frog Position After T Seconds 解题思路

以下两种情况青蛙无法在 t 秒后到达 target

时间不足, target 与起点的距离超过了 t

路过但是无法停留, 即 target 与起点的距离不足 t, 并且到达 target 后还能继续跳跃. 那么青蛙不会再回到 target.

而如果青蛙最终可以停留在 target, 那么概率很容易计算, 我们只需要统计从起点到 target 一共经历了几次岔路口, 每一个岔路口有多少个岔路即可. 题目示例 1 即是经过了两次岔路口, 第一次在 1, 有三条岔路, 第二次在 2, 有两条岔路, 所以答案就是 1/3 * 1/2 = 1/6.

注意这个题目的遍历过程需要传入上一个节点(父节点), 与上一个题目不同. 这是因为这道题目给定这棵树的方式是 _n - 1_ 条无向边, 而上一个题目是直接告知每一个点的父节点.

代码展示

class Solution {
   public double frogPosition(int n, int[][] edges, int t, int target) {
       // 建图, nei[i] 表示节点 i 的邻居
       List<List<Integer>> nei = new ArrayList<>();
       for (int i = 0; i <= n; i++) {
           nei.add(new ArrayList<>());
       }
       // 添加一条 edge[0] <-> edge[1] 之间的无向边
       for (int[] edge : edges) {
           nei.get(edge[0]).add(edge[1]);
           nei.get(edge[1]).add(edge[0]);
       }
       // 遍历整个图, 找到起点到 target 的路线, 同时统计出答案
       return dfs(1, 0, target, 1.0, t, nei);
   }

   /**
    * 返回从 cur 走 t 步走到 target 的概率
    * @param cur       当前点
    * @param pre       上一个点 (即从哪个点走到的当前点)
    * @param target    目标点
    * @param prob      从起点走到当前点的概率
    * @param t         剩余时间
    * @param nei       每个节点的相邻节点
    * @return          概率, 范围是 [0, 1]
    */
   private double dfs(int cur, int pre, int target, double prob, int t, List<List<Integer>> nei) {
       // 计算当前点的岔路的数量, 即当前节点子节点的数量
       // 如果当前点是起点, 那么岔路口的数量就是它的邻居的数量; 否则需要 - 1, 即减去它在树中的父节点 pre
       int cnt = nei.get(cur).size() - (pre > 0 ? 1 : 0);
       // 如果没有岔路或者剩余时间为 0, 应该返回; 此时如果不在 target, 应该返回 0
       if (cnt == 0 || t == 0) {
           return cur == target ? prob : 0.0; 
       }
       // 枚举所有的岔路, 但是其中最多只有一条可以到达 target
       // 即只有一个可能返回 (0, 1] 之间的数值, 其它均返回 0
       for (int next : nei.get(cur)) {
           if (next != pre) {  // 防止走回到父节点
               // 因为通过了一个 cnt 岔路口, 所以到达 next 的概率需要乘以 1/cnt
               double res = dfs(next, cur, target, prob / cnt, t - 1, nei);
               if (res > 0.0) return res;
           }
       }
       // 如果每一条岔路均返回 0.0, 说明无法到达 target, 返回 0.0
       return 0.0;
   }
}