No.1 Check If N and Its Double Exist

解题思路

该题目比较简单, 遍历一次整个数组, 使用 Set 记录已经出现过的数字, 在遍历到一个新的元素 num 时, 检查 Set 中是否存在 num * 2 或者 num / 2

[注意一个细节]: 当 num 是奇数的时候, 不能检查 num / 2

代码展示

class Solution {
   public boolean checkIfExist(int[] arr) {
       Set<Integer> set = new HashSet<>();
       for (int num : arr) {
           if (set.contains(num * 2) || (num % 2 == 0 && set.contains(num / 2))) {
               return true;
           }
           set.add(num);
       }
       return false;
   }
}

No.2 Minimum Number of Steps to Make Two Strings Anagram

解题思路

通过修改使得两个 String 包含的每一种字符的数量都相等, 所以我们只需要知道两个字符串的差别有多少个字符即可. 使用 Map 统计出 String 中包含的每一种字符的数量, 然后计算差异.

比如对于 s = "leetcode", t = "practice"

那么 s 中每种字符的数量是: {'l': 1, 'e': 3, 't': 1, 'c': 1, 'o': 1, 'd': 1}

而 t 中每种字符的数量是: {'p': 1, 'r': 1, 'a': 1, 'c': 2, 't': 1, 'i': 1, 'e': 1}

s 中比 t 多字符有 'l', 'e', 'o', 'd', 分别多 1, 2, 1, 1 共 5 个字符, 那么我们只需要把这 5 个字符改成 t 中对应的字符即可.

s 比 t 多的字符共有 5 个, 反过来 t 比 s 多的字符也一定有 5 个.

代码展示

class Solution {
   public int minSteps(String s, String t) {
       Map<Character, Integer> map = new HashMap<>();
       // 统计出 s 中每种字符的数量
       for (char c : s.toCharArray()) {
           map.put(c, 1 + map.getOrDefault(c, 0));
       }
       // 计算 t 和 s 的差异
       int diff = 0;
       for (char c : t.toCharArray()) {
           int cnt = map.getOrDefault(c, 0);
           // 如果 s 中有字符 c, 那么先减去; 反之 diff++, 代表 t 比 s 多一个字符 c
           if (cnt > 0) {
               map.put(c, cnt - 1);    
           } else {
               diff++;
           }
       }
       return diff;
   }
}

No.3 Tweet Counts Per Frequency

解题思路

首先根据样例输入注意到 recordTweet() 的调用顺序与 time 无关.

我们使用 Map<String, List> 来维护数据. key 为 tweetName, value 为该用户发过推文的时间点列表.

在记录时, 只需要向 List 中 add 一个时间点即可; 在查询时, 遍历该用户对应的 List 即可.

在查询时, 出于便利, 先使用数组 int[] 记录每个时间段的推文数, 最后再转换成 List. 数组的初值全是 0, 数组的长度为时间段的数量, 即向上取整的除法: (endTime - startTime + 1) / duration (duration 表示时间段长度, 取值为 {60, 3600, 86400}). 在遍历时, 如果时间点 time 在 [startTime, endTime] 范围内, 那么通过计算 (time - startTime) / duration 得到它属于哪个时间段, 更新数组内对应的元素.

代码展示

class TweetCounts {

   private Map<String, List<Integer>> records;

   public TweetCounts() {
       records = new HashMap<>();
   }

   public void recordTweet(String tweetName, int time) {
       if (!records.containsKey(tweetName)) {
           records.put(tweetName, new ArrayList<>());
       }
       records.get(tweetName).add(time);
   }

   public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
       if (!records.containsKey(tweetName)) {
           return new ArrayList<>();
       }
       int duration = "minute".equals(freq) ? 60 : ("hour".equals(freq) ? 3600 : 86400);
       int[] res = new int[(endTime - startTime + duration) / duration];
       for (int t : records.get(tweetName)) {
           if (startTime <= t && t <= endTime) {
               res[(t - startTime) / duration]++;
           }
       }
       return Arrays.stream(res).boxed().collect(Collectors.toList());
   }
}

No.4 Maximum Students TakingExam

解题思路

这是一道比较难的动态规划问题, 需要进行状态压缩.

普通的按照座位定义状态是想不通的, 所以我们按照行来定义状态: 设 dp[i][j] 表示第 i 行的座位按照 j 坐人的情况下, 前 i 行最多能坐多少人. 注意 j 是一个集合, 表示在哪些位置坐人.

这样我们就很容易得到状态转移方程: dp[i][j] = max{ dp[i - 1][k] + size(j) }, 其中 k, j 需要满足一些条件 (size(j) 表示 j 集合中坐了多少人):

k, j 指定的坐人的位置都必须有好的座位, 也就是 .

k, j 这相邻的两列人之间无法作弊, 也就是说 j 的位置都无法偷窥到 k

k, j 这两列本身也无法作弊, 即它们本身不能安排相邻的座位 (其实这样的 dp[i][j] 可以被认为是非法状态)

初始化 dp[0][0] = 0, 而其它均为负无穷, 最终答案是 max{ dp[n][i] }, 即最后一排的所有坐人情况中取最大值.

明白了动态规划思路之后, 还有一个很大的问题, 就是怎么高效地表示 (i, j), 用 Map 套 Set 或是自定义类型不太现实. 我们注意到 n, m <= 8, 那么其实我们可以使用一个 8 位二进制数来表示 j, 也就是开数组最大只会访问到 dp[8][255], 占用内存很少.

然而, 既然我们使用二进制数来表示 j, 那么运算过程需要很多位运算, 具体运算以及含义见代码及注释.

代码展示

class Solution {
   public int maxStudents(char[][] seats) {
       int n = seats.length;
       int m = seats[0].length;
       int[] bit = new int[1 << m];     // bit[i] 表示 i 的二进制有多少个 1
       int[] bitseat = new int[n + 1];  // bitseat[i] 表示第 i 行的座位的二进制表示
       int[][] dp = new int[n + 1][1 << m]; // j 的范围是 0 ~ 2^m - 1, 数组开 1 << m 即可

       // 预处理 bit 数组, t & -t 得到的是 t 的二进制最低位的 1
       for (int i = 1; i < (1 << m); i++) {
           for (int t = i; t > 0; t -= t & -t) {
               bit[i]++;
           }
       }
       // 预处理 bitseat 数组(1-indexed)
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < m; j++) {
               if (seats[i][j] == '.') {
                   bitseat[i + 1] |= (1 << j);
               }
           }
       }
       // 给 dp 数组赋初始值
       for (int i = 0; i <= n; i++) {
           Arrays.fill(dp[i], -0x3f3f3f3f);
       }
       dp[0][0] = 0;

       // 动态规划计算
       int res = 0;
       for (int i = 1; i <= n; i++) {
           for (int j = 0; j < (1 << m); j++) {
               // 前半部分判断保证 j 指定的坐人的位置都必须有好的座位
               // 后半部分判断保证 j 指定的坐人位置没有相邻的
               if ((j | bitseat[i]) != bitseat[i] || (j & (j << 1)) > 0) {
                   continue;
               }
               for (int k = 0; k < (1 << m); k++) {
                   // 这个判断保证 j 和 k 没有斜向上的冲突
                   if (((k << 1) & j) == 0 && ((k >> 1) & j) == 0) {
                       dp[i][j] = Math.max(dp[i][j], dp[i - 1][k] + bit[j]);
                   }
               }
               res = Math.max(res, dp[i][j]);
           }
       }
       return res;
   }
}