LeetCode 185, 30, 230

185. 部门工资前三高的所有员工

题目链接

185. 部门工资前三高的所有员工

表

• 表Employee的字段为id、name、salary和departmentId。
• 表Department的字段为id和name。

要求

公司的主管们感兴趣的是公司每个部门中谁赚的钱最多。一个部门的 高收入者 是指一个员工的工资在该部门的 不同 工资中 排名前三 。

编写解决方案，找出每个部门中 收入高的员工 。

以 任意顺序 返回结果表。

知识点

1. count()：统计个数的函数。
2. join on：内连接，使用on做条件限制。
3. distinct：对某字段去重。

思路

本题总体来说不难，只是对数据的限制比较难想，怎样将员工的工资限制到每个部门的前三名工资里？这里可以换个思路，工资在部门里排前三 不就是 在这个部门中找不到第三个比这个工资大的工资，所以可以查询部门中比当前工资大的工资的个数，由于本题限制 排名前三 的工资指的是前三个 不同 的工资，所以在查询时得去重distinct。

除此之外就是使用内连接join将Employee和Department这两张表的数据查询到一起，然后使用on限制Employee.departmentId = Department.id。

代码

selectd.name Department,e.name Employee,salary Salary
fromEmployee e
joinDepartment d
one.departmentId = d.id
where(selectcount(distinct eC.salary)fromEmployee eCwhereeC.salary > e.salaryande.departmentId = eC.departmentId) < 3

30. 串联所有单词的子串

题目链接

30. 串联所有单词的子串

标签

哈希表 字符串 滑动窗口

思路

本题的思想很像438. 找到字符串中所有字母异位词，438题的思想是统计字符出现的次数，而本题需要统计短字符串出现的次数，共同点就是都不关心内部字符（或短字符串）的顺序，所以可以使用int[]（对于短字符串的出现次数，由于字符串不能作为数组索引，所以使用Map<String, Integer>）统计出现次数。

获取短字符串需要将原字符串s划分为指定长度的小段，指定的长度该如何确定？答案是与字符串数组words中每个字符串的长度wordLen保持一致，因为最后这些短字符串的比较对象就是字符串数组words中的字符串。

这种划分的方法共有wordLen种，例如对于s = "barfoothefoobarman", words = ["foo","bar"]，划分的结果有以下3种：bar, foo, the, foo, bar, man，arf, oot, hef, oob, arm，rfo, oth, efo, oba, rma。可以看出来不同的划分只是划分的起始字符不同，第一种划分从第一个字符s[0]开始，第二种划分从第二个字符s[1]开始，…，第wordLen种划分从第wordLen个字符s[wordLen]开始，共有wordLen种不同的划分。这里将划分的起始字符的索引称为划分起始索引。注意一点：原字符串s并不一定能够划分为wordNum个长度为wordLen字符串，如果不够划分，就返回结果。

与438题相同，使用滑动窗口的思想，不过这次滑动窗口中保存的不是一个一个的字符，而是一个一个的短字符串。先初始化滑动窗口，将前wordNum个短字符串加入窗口。初始化滑动窗口后统计words中的字符串出现的次数。

这里可以不使用两个Map分别存储窗口和words的短字符串出现次数，然后判断两个Map是否相同。而是复用一个Map，一个字符串在窗口中出现一次，就让这个字符串的出现次数加一；一个字符串在words中出现一次，就让这个字符串的出现次数减一，当一个字符串在Map中出现0次，将这个字符串从Map中移除。在判断窗口内的字符串是否与words的字符串完全一致时直接判断Map是否为空，如果为空，则说明完全一致。

这里不多做描述了，如果很熟悉438题的做法，那么知道上面这些后看代码会好一点。

代码

class Solution {public List<Integer> findSubstring(String s, String[] words) {List<Integer> res = new ArrayList<>();int wordNum = words.length; // 字符串数组的字符串个数int wordLen = words[0].length(); // 字符串数组中每个字符串的长度int sLen = s.length(); // 原字符串的长度for (int i = 0; i < wordLen; i++) { // i是划分起始索引if (i + wordNum * wordLen > sLen) { // 如果不够划分，则退出循环break;}// 初始化滑动窗口Map<String, Integer> cnt = new HashMap<>(); // 统计各字符串出现的次数for (int j = 0; j < wordNum; j++) { // j是已划分子串的个数String word = divide(s, i, j, wordLen);cnt.put(word, cnt.getOrDefault(word, 0) + 1);}// 统计words字符串数组的字符串情况，这里复用了cntfor (String word : words) {cnt.put(word, cnt.getOrDefault(word, 0) - 1);if (cnt.get(word) == 0) {cnt.remove(word);}}// 判断cnt是否为空，如果为空，则将窗口的第一个短字符串(的第一个字符)的索引加入结果链表if (cnt.isEmpty()) {res.add(i);}// 滑动窗口，start为窗口的第一个字符串(的第一个字符)的索引for (int start = i + wordLen; start < sLen - wordNum * wordLen + 1; start += wordLen) {String word = divide(s, start, wordNum - 1, wordLen); // 获取新短字符串cnt.put(word, cnt.getOrDefault(word, 0) + 1); // 将新短字符串加入窗口if (cnt.get(word) == 0) { // 如果一个短字符串在Map中出现0次cnt.remove(word); // 则将它从Map中移除}word = s.substring(start - wordLen, start); // 获取窗口中的第一个短字符串cnt.put(word, cnt.getOrDefault(word, 0) - 1); // 移除窗口中的第一个短字符串if (cnt.get(word) == 0) { // 如果一个短字符串在Map中出现0次cnt.remove(word); // 则将它从Map中移除}// 判断cnt是否为空，如果为空，则将窗口的第一个短字符串(的第一个字符)的索引加入结果链表if (cnt.isEmpty()) {res.add(start);}}}return res;}// 返回字符串s在 划分起始索引为i的 划分的 第j个 短字符串private String divide(String s, int i, int j, int wordLen) {return s.substring(i + j * wordLen, i + (j + 1) * wordLen);}
}

230. 二叉搜索树中第K小的元素

题目链接

230. 二叉搜索树中第K小的元素

标签

树 深度优先搜索 二叉搜索树 二叉树

思路

二叉搜索树经常与中序遍历组合出现，本题也不例外，找二叉搜索树中第K小的元素 就是 找遍历结果的第k个数，对中序遍历不了解的可以看这篇文章：94. 二叉树的中序遍历。

代码

class Solution {public int kthSmallest(TreeNode root, int k) {LinkedList<TreeNode> stack = new LinkedList<>();TreeNode curr = root; // 当前节点TreeNode pop = null; // 上一个被弹出栈的节点while (!stack.isEmpty() || curr != null) {if (curr != null) { // 没有处理左子节点的情况stack.push(curr);curr = curr.left; // 向左子节点移动} else {TreeNode peek = stack.peek();if (peek.right == null || peek.right != pop) { // 没有处理右子节点的情况if (--k == 0) { // 当遍历到第k个节点时会返回peek.valreturn peek.val;}curr = peek.right; // 向右子节点移动pop = stack.pop();} else { // 处理完右子节点的情况pop = stack.pop();}}}return -1;}
}