08
10

发表于 • 被 212 人看爆

又是新的一周到了！要发工资了哈哈，好开心哦~~~

算法题

1. 有多少小于当前数字的数字

题目

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

 

示例 1：

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]

解释： 
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。 
对于 nums[3]=2 存在一个比它小的数字：（1）。 
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

输入：nums = [6,5,4,8]
输出：[2,1,0,3]

示例 3：

输入：nums = [7,7,7,7]
输出：[0,0,0,0]

 

提示：

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

题解

我的解

直接暴力循环！

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int result[] = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[i] > nums[j]){
                    result[i]++;
                }
            }
        }
        return result;
    }
}

官方解一：暴力法

  • 时间复杂度 O(n^2)，空间复杂度 O(n)
 public int[] smallerNumbersThanCurrent(int[] nums) {
     int len = nums.length;
     int[] res = new int[len];
     for (int i = 0; i < len; i++) { // 枚举所有元素
         for (int j = 0; j < len; j++) { // 枚举其他元素
             if (i == j) continue;
             if (nums[i] > nums[j]) res[i]++;
         }
     }
     return res;
 }

官方解二：排序 + 映射

  • 时间复杂度 O(nlog(n))，空间复杂度 O(n)

  • 你的索引是多少，就有多少个数字小于你

    • 严格说应该是 小于等于你
public int[] smallerNumbersThanCurrent(int[] nums) { // 8, 1, 2, 2, 3
    int len = nums.length;
    Map<Integer, Set<Integer>> valueIndex = new HashMap<>(len); // 预存每个值与索引对应
    for (int i = 0; i < len; i++) {
        if (!valueIndex.containsKey(nums[i])) valueIndex.put(nums[i], new HashSet<>());
        valueIndex.get(nums[i]).add(i);
    }
    int[] sortedArr = Arrays.copyOf(nums, len), res = new int[len];
    Arrays.sort(sortedArr); // 1, 2, 2, 3, 8
    for (int si = len - 1; si >= 0; si--) { // 倒序，方便处理同值的情况
        // 此行为补充优化：前面还有同值的，那就跳过这次，等下次再一并赋值
        if (si - 1 >= 0 && sortedArr[si] == sortedArr[si - 1]) continue;

        for (int i : valueIndex.get(sortedArr[si])) res[i] = si; // 同值的所有索引都更新
    }
    return res;
}

  • 对最后两层 for 的时间复杂度分析，及代码优化

    • 最好时间复杂度 O(n)，所有元素值都不相同，则内层每次 valueIndex.get(sortedArr[si]) 只有 1 个元素
    • 最坏时间复杂度 O(n^2)，所有元素都相同，则内层每次 valueIndex.get(sortedArr[si]) 会有 n 个元素
    • 更准确的时间复杂度可描述为 O((n - ab) + ab^2)，其中有 a 组相同，每组 b 个元素
      • 举例分析，考虑数组如 [1, 2, 3, 3, 3, 4, 4, 5, 6]，结合上述最好、最坏时间复杂度的理解后可知，此数组最后两层 for 的执行次数为：
        • 非重复的 + 重复的
        • 非重复的：[1, 2, 5, 6] 共 4 次
        • 重复的：[3, 3, 3] 共 33 = 9 次 + [4, 4] 共 22 = 4 次
        • 共 4 + 33 + 22 次
      • 归纳抽象，假设每个数字出现的概率相同，设共有 a 组相同元素（上例中的 全3 和 全4 共 2 组），每组内共 b 个元素
        • 非重复的：n - a * b
        • 重复的：a 组 b * b，即 ab^2
        • 最终的时间复杂度为 O((n - ab) + ab^2)
      • 考虑原题中的数据范围：nums.length <= 500，nums[i] <= 100
        • 根据 鸽巢原理/抽屉原理 可知，当元素个数 > 元素种类 时，必会出现重复的情况。在最大数据范围的情况下，出现重复的期望为 500/100 = 5，即「有 100 组元素重复，每组 5 个元素」
        • 代入 O((n - ab) + ab2)得 500 - 100 * 5 + 100 * 52 = 2500，可见远小于 O(n2) 的 5002 = 250000
        • 分析到此笔者认为已足够，不必再深入纠结与 O(n) 或 O(nlog(n)) 的关系，因为具体要看重复的情况。不如花更多精力看看能否优化成 O(n)
    • 代码优化两层 for 为 O(n)
      • 回到代码可知，在倒序过程中遇到重复时，有多少个重复，就会在内层执行多少次
// 1, 2, 2, 3, 8
for (int si = len - 1; si >= 0; si--) {
    for (int i : valueIndex.get(sortedArr[si])) res[i] = si;
}

- 而内层循环的目的是：把所有相同值的 原数组索引对应位置都更新为 si
- 一次性更新 就好了呀，如此一来，只会执行 n 次 res[i] = si; 的赋值操作

// 1, 2, 2, 3, 8
for (int si = len - 1; si >= 0; si--) {
    // 前面还有同值的，那就跳过这次，等最后一次再一并赋值
    if (si - 1 >= 0 && sortedArr[si] == sortedArr[si - 1]) continue;

    for (int i : valueIndex.get(sortedArr[si])) res[i] = si;
}

- 通过外站的实测效果（外站的代码执行速度比较稳定）从 7ms 提高到 5ms

官方解三：计数排序

  • 时间复杂度 O(n)，空间复杂度 O(1)
  • 空间复杂度 int[] freq 因题意限制 0 <= nums[i] <= 100 而定，不随数据量大小而改变
public int[] smallerNumbersThanCurrent(int[] nums) {
    // 统计出现频率 frequency
    int[] freq = new int[101]; // 索引即数值
    for (int num : nums) freq[num]++;

    // 对频率(而非对原数组nums)从前到后累加
    for (int i = 1; i < freq.length; i++) {
        freq[i] = freq[i] + freq[i - 1];
    }

    // 输出结果
    int[] res = new int[nums.length];
    for (int i = 0; i < res.length; i++) {
        if (nums[i] > 0) res[i] = freq[nums[i] - 1];
    }
    return res;
}

思考扩展

  • 思考这样一个问题：全国高考考生(大量元素)按成绩(0-750)排名问题
    • 如何排序，可参考计数排序——特殊的桶排序
    • 计数排序
    • 大体思想：扫描一遍所有人，按分数分到不同给的桶里，桶内无需再排序，仅需统计各桶内数量
    • 适用性：数据量大、数据范围不大的情况
  • 假设数据已排序如 [748, 748, 747, ..., 730, 730, ..., 730, 729, ...]
    • 问：有多少人在 729 前面？（同分同名次，如 747 是第三名，没有第二名）
    • 答：即 第一个 729 的索引

总结

我只能说官方太强了！现在不想看官方，明天再看吧！

2. 统计位数为偶数的数字

题目

给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。

 

示例 1：

输入：nums = [12,345,2,6,7896]
输出：2

解释：
12 是 2 位数字（位数为偶数） 
345 是 3 位数字（位数为奇数）  
2 是 1 位数字（位数为奇数） 
6 是 1 位数字 位数为奇数） 
7896 是 4 位数字（位数为偶数）  
因此只有 12 和 7896 是位数为偶数的数字

示例 2：

输入：nums = [555,901,482,1771]
输出：1 
解释： 
只有 1771 是位数为偶数的数字。

提示：

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 10^5

题解

我的解

这么久了，我还是只能想出最简单的实现方式，循环就完事了。

class Solution {
    public int findNumbers(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            int length = 0;
            while (nums[i] > 0){
                nums[i] = nums[i] / 10;
                length++;
            }
            if (length%2 ==0){
                result++;
            }
        }
        return result;
    }
}

官方解：枚举 + 字符串

解题思路

1、用一个循环，遍历数组中每一个数
2、把每一位数，转换成字符串，为了便于统计整数的个数
3、把转换的字符串，%2 == 0

代码

class Solution {
    public int findNumbers(int[] nums) {
        int ans = 0;
		 
		 for(int i = 0 ; i < nums.length ;i++){
			 String s = "" + nums[i]; //转换为字符串
			 if(s.length() % 2 ==0){  //字符串长度 % 2 等于0就是偶位数
				 ans++;
			 }
		 }
		 return ans;
    }
}

总结

终究还是跟官方解差了一步。

突然发现，其实我的方法效率更高哈哈！这波不亏！

3. 在既定时间做作业的学生人数

题目

给你两个整数数组 startTime（开始时间）和 endTime（结束时间），并指定一个整数 queryTime 作为查询时间。

已知，第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。

请返回在查询时间 queryTime 时正在做作业的学生人数。形式上，返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。

 

示例 1：

输入：startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
输出：1

解释：一共有 3 名学生。
第一名学生在时间 1 开始写作业，并于时间 3 完成作业，在时间 4 没有处于做作业的状态。
第二名学生在时间 2 开始写作业，并于时间 2 完成作业，在时间 4 没有处于做作业的状态。
第三名学生在时间 3 开始写作业，预计于时间 7 完成作业，这是是唯一一名在时间 4 时正在做作业的学生。

示例 2：

输入：startTime = [4], endTime = [4], queryTime = 4
输出：1

解释：在查询时间只有一名学生在做作业。

示例 3：

输入：startTime = [4], endTime = [4], queryTime = 5
输出：0

示例 4：

输入：startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
输出：0

示例 5：

输入：startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
输出：5

提示：

  • startTime.length == endTime.length
  • 1 <= startTime.length <= 100
  • 1 <= startTime[i] <= endTime[i] <= 1000
  • 1 <= queryTime <= 1000

题解

我的解

朴实无华！

class Solution {
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int result = 0;
        for (int i = 0; i < endTime.length; i++) {
            if (endTime[i] >= queryTime && startTime[i] <= queryTime){
                result++;
            }
        }
        return result;
    }
}

官方解

真是不好意思，我的解就是官方解。

总结

哈哈开心哦~~~

4. 旅行终点站

题目

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。

 

示例 1：

输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo" 

解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

示例 2：

输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"

解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
显然，旅行终点站是 "A" 。

示例 3：

输入：paths = [["A","Z"]]
输出："Z"

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。

 

示例 1：

输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出："Sao Paulo"
解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。
示例 2：

输入：paths = [["B","C"],["D","B"],["C","A"]]
输出："A"
解释：所有可能的线路是：
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
显然，旅行终点站是 "A" 。
示例 3：

输入：paths = [["A","Z"]]
输出："Z"
 

提示：

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityAi != cityBi
  • 所有字符串均由大小写英文字母和空格字符组成。

题解

我的解

哦吼！
哈哈，我的思路是玄幻判断就完事了！

class Solution {
    public String destCity(List<List<String>> paths) {
        String result = paths.get(0).get(1);
        for (int i = 1; i < paths.size(); i++) {
            if (result.equals(paths.get(i).get(0))){
                result = paths.get(i).get(1);
                i = 0;
            }
        }
        return result;
    }
}

官方解一：Hashmap


class Solution {
    public String destCity(List<List<String>> paths) {
        Map<String,String> map = new HashMap<>();
        // 将所有路径的起点与终点存入map
        for(List<String> list : paths){
            map.put(list.get(0), list.get(1));
        }
        for(String s : map.keySet()){
            // 如果某个路径的终点不是另一个路径的起点，则该点就是旅行终点
            if(map.get(map.get(s)) == null)
                return map.get(s);
        }
        // 返回默认null，由题意是不会走到这里返回的
        return null;
    }
}

官方解二：List


class Solution {

    public String destCity(List<List<String>> paths) {
        Set tos = new HashSet();
        for (List<String> path : paths) {   // 录入所有终点
            tos.add(path.get(1));
        }
        for (List<String> path : paths) {   // 检查并删除 “非终点元素”
            tos.remove(path.get(0));
        }
        return (String) tos.iterator().next();  // 返回结果
    }

}

总结

官方解还是巧妙啊！

5. 将每个元素替换为右侧最大元素

题目

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

示例：

输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]

提示：

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i] <= 10^5

题解

我的解

渐入佳境！可惜算法效率有点低！

class Solution {
    public int[] replaceElements(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int max = 0;
            for (int j = i + 1; j < arr.length; j++) {
                if (max < arr[j]){
                    max = arr[j];
                }
            }
            arr[i] = max;
        }
        arr[arr.length-1] = -1;
        return arr;
    }
}

官方解一：逆序遍历

  • 定义result数组，使其最后一项为-1
  • 逆序遍历数组，若该数的前一个数大于max
  • 则max = arr[i + 1]，result[i] = max
class Solution {
    public int[] replaceElements(int[] arr) {
        int[] result = new int[arr.length];
        int max = -1;
        result[arr.length - 1] = -1;
        for(int i = arr.length - 2; i >= 0; i--)
        {
            if(arr[i + 1] > max)
            {
                max = arr[i + 1];
            }
            result[i] = max;
        }
        return result;
    }
}

官方解二：copy

**但这个方法超出了时间限制
**

  • 定义一个index
  • 定义一个current[]数组
  • 每次将index下标后的数组复制到current数组中
  • 利用求出其中的最大值
  • 使得result[index] = max
class Solution {
    public int[] replaceElements(int[] arr) {
        int[] result = new int[arr.length];
        int index = 0;
        while(index < arr.length - 1)
        {
            int[] current = Arrays.copyOfRange(arr, index + 1, arr.length);
            int max = Arrays.stream(current).max().getAsInt();
            result[index] = max;
            index++;
        }
        result[arr.length - 1] = -1;
        return result;
    }
}

总结

博大精深，就是博大精深！

6. 删除最外层的括号

题目

有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。

如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。

对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

 

示例 1：

输入："(()())(())"
输出："()()()"

解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。

示例 2：

输入："(()())(())(()(()))"
输出："()()()()(())"

解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：

输入："()()"
输出：""

解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。

提示：

  • S.length <= 10000
  • S[i] 为 "(" 或 ")"
  • S 是一个有效括号字符串

题解

我的解

官方解一

官方解二

总结

7. 汉明距离

题目

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：

  • 0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4
输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

题解

我的解

写不出来。

思路是转换成二进制，再双指针逐个比较。

官方解一：内置位计数功能

大多数编程语言中，都存在各种内置计算等于 1 的位数函数。如果这是一个项目中的问题，应该直接使用内置函数，而不是重复造轮子。

但这是一个力扣问题，有人会认为使用内置函数就好像使用 使用 LinkedList 实现 LinkedList。对此，我们完全赞同。因此后面会有手工实现的位计数算法。

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y); 
    }
}

复杂度分析

  • 时间复杂度：O(1)。

    • 该算法有两个操作。计算 XOR 花费恒定时间。
    • 调用内置的 bitCount 函数。最坏情况下，该函数复杂度为 O(k)，其中 kk 是整数的位数。在 Python 和 Java 中 Integer 是固定长度的。因此该算法复杂度恒定，与输入大小无关。

  • 空间复杂度：O(1)，使用恒定大小的空间保存 XOR 的结果。

    • 假设内置函数也使用恒定空间。

官方解二：移位

为了计算等于 1 的位数，可以将每个位移动到最左侧或最右侧，然后检查该位是否为 1。

更准确的说，应该进行逻辑移位，移入零替换丢弃的位。

这里采用右移位，每个位置都会被移动到最右边。移位后检查最右位的位是否为 1 即可。检查最右位是否为 1，可以使用取模运算（i % 2）或者 AND 操作（i & 1），这两个操作都会屏蔽最右位以外的其他位。

class Solution {
  public int hammingDistance(int x, int y) {
    int xor = x ^ y;
    int distance = 0;
    while (xor != 0) {
      if (xor % 2 == 1)
        distance += 1;
      xor = xor >> 1;
    }
    return distance;
  }
}

复杂度分析

  • 时间复杂度：O(1)，在 Python 和 Java 中 Integer 的大小是固定的，处理时间也是固定的。 32 位整数需要 32 次迭代。

  • 空间复杂度：O(1)，使用恒定大小的空间。

官方解三：布赖恩·克尼根算法

方法二是逐位移动，逐位比较边缘位置是否为 1。寻找一种更快的方法找出等于 1 的位数。

是否可以像人类直观的计数比特为 1 的位数，跳过两个 1 之间的 0。例如：10001000。

上面例子中，遇到最右边的 1 后，如果可以跳过中间的 0，直接跳到下一个 1，效率会高很多。

这是布赖恩·克尼根位计数算法的基本思想。该算法使用特定比特位和算术运算移除等于 1 的最右比特位。

当我们在 number 和 number-1 上做 AND 位运算时，原数字 number 的最右边等于 1 的比特会被移除。

基于以上思路，通过 2 次迭代就可以知道 10001000 中 1 的位数，而不需要 8 次。

class Solution {
  public int hammingDistance(int x, int y) {
    int xor = x ^ y;
    int distance = 0;
    while (xor != 0) {
      distance += 1;
      // remove the rightmost bit of '1'
      xor = xor & (xor - 1);
    }
    return distance;
  }
}

**注意：**该算法发布在 1988 年 《C 语言编程第二版》的练习中（由 Brian W. Kernighan 和 Dennis M. Ritchie 编写），但是 Donald Knuth 在 2006 年 4 月 19 日指出，该方法第一次是由 Peter Wegner 在 1960 年的 CACM3 上出版。顺便说一句，可以在上述书籍中找到更多位操作的技巧。

复杂度分析

  • 时间复杂度：O(1)。

    • 与移位方法相似，由于整数的位数恒定，因此具有恒定的时间复杂度。
    • 但是该方法需要的迭代操作更少。

  • 空间复杂度：O(1)，与输入无关，使用恒定大小的空间。

总结

我被干住了！

8. 重新排列字符串

题目

给你一个字符串 s 和一个 长度相同 的整数数组 indices 。

请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。

返回重新排列后的字符串。

示例 1：

输入：s = "codeleet", indices = [4,5,6,7,0,2,1,3]
输出："leetcode"

解释：如图所示，"codeleet" 重新排列后变为 "leetcode" 。

示例 2：

输入：s = "abc", indices = [0,1,2]
输出："abc"

解释：重新排列后，每个字符都还留在原来的位置上。

示例 3：

输入：s = "aiohn", indices = [3,1,4,2,0]
输出："nihao"

示例 4：

输入：s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
输出："arigatou"

示例 5：

输入：s = "art", indices = [1,0,2]
输出："rat"

提示：

  • s.length == indices.length == n
  • 1 <= n <= 100
  • s 仅包含小写英文字母。
  • 0 <= indices[i] < n
  • indices 的所有的值都是唯一的（也就是说，indices 是整数 0 到 n - 1 形成的一组排列）。

题解

我的解

算了算了~~

官方解一：模拟

创建一个新字符串 result 来存储答案。对于 s 每个下标 i，将 result[indices[i]] 处的字符设成 s[i] 即可。

class Solution {
    public String restoreString(String s, int[] indices) {
        int length = s.length();
        char[] result = new char[length];

        for (int i = 0; i < length; i++) {
            result[indices[i]] = s.charAt(i);
        }
        return new String(result);
    }
}

复杂度分析

  • 时间复杂度：O(N)，其中 N 为字符串 ss 的长度。我们只需对字符串 s 执行一次线性扫描即可。

  • 空间复杂度：O(1) 或 O(N)。除开辟的存储答案的字符串外，我们只需要常数空间存放若干变量。如果使用的语言不允许对字符串进行修改，我们还需要 O(N) 的空间临时存储答案。

官方解二：原地修改

本题也可以通过原地修改输入数据的方式来求解。

直观的想法是：对于下标 i，需要把字符 s[i] 移动到 indices[i] 的位置上；然后，我们前进到位置 indices[i]，并将字符 s[indices[i]] 移动到 indices[indices[i]] 的位置上。类似的过程以此类推，直到最终回到起点 i。此时，封闭路径 i→indices[i]→indices[indices[i]]→...→i 上的所有字符，都已经被设置成正确的值。

我们只要找到 indices[i] 中所有这样的封闭路径，并进行对应的移动操作，就能够得到最终的答案。

这样做有一个小小的问题：当在第二步试图把字符 s[indices[i]] 移动到 indices[indices[i]] 的位置上时，会发现字符 s[indices[i]] 已经在第一步被覆写了。因此，在每一步移动前，需要先额外记录目标位置处字符的原有值。

另一个隐含的问题是如何避免处理重复的封闭路径。为了解决此问题，我们每处理一个封闭路径，就将该路径上的 indices 数组的值设置成下标自身。这样，当某个封闭路径被处理完毕后，扫描到该路径的另一个下标时，就不会处理该封闭路径了。

由于许多语言中的字符串类型都是不可更改的，实现原地修改较为麻烦，因此下面只给出 C++ 的参考代码。

class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        int length = s.length();
        for (int i = 0; i < length; i++) {
            if (indices[i] != i) {
                char ch = s[i]; // 当前需要被移动的字符
                int idx = indices[i]; // 该字符需要被移动的目标位置
                while (idx != i) {
                    swap(s[idx], ch); // 使用 swap 函数，在覆写 s[idx] 之前，先将其原始值赋给变量 ch
                    swap(indices[idx], idx); // 将封闭路径中的 indices 数组的值设置成下标自身
                }
                // 退出循环后，还要再覆写起点处的字符
                s[i] = ch;
                indices[i] = i;
            }
        }
        return s;
    }
};

复杂度分析

  • 时间复杂度：O(N)，其中 NN 为字符串 s 的长度。尽管代码看上去有两层循环，但因为不会处理相同的封闭路径，每个下标实际上只被处理了一次，故时间复杂度是线性的。

  • 空间复杂度：O(1)。我们只需开辟常量大小的额外空间。

总结

博大精深，哎。

9. 转换成小写字母

题目

实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。

示例 1：

输入: "Hello"
输出: "hello"

示例 2：

输入: "here"
输出: "here"

示例 3：

输入: "LOVELY"
输出: "lovely"

题解

我的解

也别逼逼赖赖了，直接用内部的方法不就完事了！

class Solution {
    public String toLowerCase(String str) {
        return str.toLowerCase();
    }
}

官方解：操作ASCII码

class Solution {
    public String toLowerCase(String str) {
        char[] chars = str.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            if (chars[i] <= 90 && chars[i] >= 65) {
                chars[i] = (char) (chars[i] + 32);
            }
        }
        return String.valueOf(chars);
    }
}

总结

也别操作了，直接调用方法就完事了！

10. 高度检查器

题目

学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。

请你返回能让所有学生以 非递减 高度排列的最小必要移动人数。

注意，当一组学生被选中时，他们之间可以以任何可能的方式重新排序，而未被选中的学生应该保持不动。

示例：

输入：heights = [1,1,4,2,1,3]
输出：3 

解释：
当前数组：[1,1,4,2,1,3]
目标数组：[1,1,1,2,3,4]
在下标 2 处（从 0 开始计数）出现 4 vs 1 ，所以我们必须移动这名学生。
在下标 4 处（从 0 开始计数）出现 1 vs 3 ，所以我们必须移动这名学生。
在下标 5 处（从 0 开始计数）出现 3 vs 4 ，所以我们必须移动这名学生。

示例 2：

输入：heights = [5,1,2,3,4]
输出：5

示例 3：

输入：heights = [1,2,3,4,5]
输出：0

提示：

  • 1 <= heights.length <= 100
  • 1 <= heights[i] <= 100

题解

我的解

官方解一

官方解二

总结

数据库题

1. 分数排名

题目

编写一个 SQL 查询来实现分数排名。

如果两个分数相同，则两个分数排名（Rank）相同。请注意，平分后的下一个名次应该是下一个连续的整数值。换句话说，名次之间不应该有“间隔”。

IdScore
13.50
23.65
34.00
43.85
54.00
63.65

例如，根据上述给定的 Scores 表，你的查询应该返回（按分数从高到低排列）：

ScoreRank
4.001
4.001
3.852
 3.653
3.653
3.504

**重要提示：**对于 MySQL 解决方案，如果要转义用作列名的保留字，可以在关键字之前和之后使用撇号。例如 Rank

题解

我的解

我摊牌了，不挣扎了，不会写。

官方解：窗口函数

【题目】
下图是"班级"表中的内容，记录了每个学生所在班级，和对应的成绩。

现在需要按成绩来排名，如果两个分数相同，那么排名要是并列的。

正常排名是1，2，3，4，但是现在前3名是并列的名次，排名结果是：1，1，1，2。

【解题思路】

1.涉及到排名问题，可以使用窗口函数

2.专用窗口函数rank, dense_rank, row_number有什么区别呢？

它们的区别我举个例子，你们一下就能看懂：

select *,
   rank() over (order by 成绩 desc) as ranking,
   dense_rank() over (order by 成绩 desc) as dese_rank,
   row_number() over (order by 成绩 desc) as row_num
from 班级

得到结果：

从上面的结果可以看出：

1）rank函数：这个例子中是5位，5位，5位，8位，也就是如果有并列名次的行，会占用下一名次的位置。比如正常排名是1，2，3，4，但是现在前3名是并列的名次，结果是：1，1，1，4。

2）dense_rank函数：这个例子中是5位，5位，5位，6位，也就是如果有并列名次的行，不占用下一名次的位置。比如正常排名是1，2，3，4，但是现在前3名是并列的名次，结果是：1，1，1，2。

3）row_number函数：这个例子中是5位，6位，7位，8位，也就是不考虑并列名次的情况。比如前3名是并列的名次，排名是正常的1，2，3，4。

这三个函数的区别如下：

根据题目要求的排名规则，这里我们使用dense_rank函数。所以，最终的sql语句是：

select *,
   dense_rank() over (order by 成绩 desc) as dese_rank
from 班级

【本题考点】

1.考察如何使用窗口函数
2.专用窗口函数排名的区别：rank, dense_rank, row_number

【举一反三】

涉及到排名的问题，都可以使用窗口函数来解决。记住rank, dense_rank, row_number排名的区别。

回到本题，参考答案：

SELECT Score, 
    DENSE_RANK() OVER(ORDER BY Score DESC) AS 'Rank'
FROM Scores;

注意，mysql版本8已至此窗口函数这个功能，虽然在leetcode上运行不成功，可能的原因是后台的mysql数据库版本不是最新的。

总结

sql 博大精深！

2. 连续出现的数字

题目

编写一个 SQL 查询，查找所有至少连续出现三次的数字。

IdNum
11
21
31
42
51
62
72

例如，给定上面的 Logs 表， 1 是唯一连续出现至少三次的数字。

ConsecutiveNums
1

题解

我的解

我是真滴不会！

官方解：用 DISTINCT 和 WHERE

连续出现的意味着相同数字的 Id 是连着的，由于这题问的是至少连续出现 3 次，我们使用 Logs 并检查是否有 3 个连续的相同数字。

SELECT *
FROM
    Logs l1,
    Logs l2,
    Logs l3
WHERE
    l1.Id = l2.Id - 1
    AND l2.Id = l3.Id - 1
    AND l1.Num = l2.Num
    AND l2.Num = l3.Num
;
IdNumIdNumIdNum
112131

注意：前两列来自 l1 ，接下来两列来自 l2 ，最后两列来自 l3 。

然后我们从上表中选择任意的 Num 获得想要的答案。同时我们需要添加关键字 DISTINCT ，因为如果一个数字连续出现超过 3 次，会返回重复元素。

SELECT DISTINCT
    l1.Num AS ConsecutiveNums
FROM
    Logs l1,
    Logs l2,
    Logs l3
WHERE
    l1.Id = l2.Id - 1
    AND l2.Id = l3.Id - 1
    AND l1.Num = l2.Num
    AND l2.Num = l3.Num
;

总结

心乱了呀~~~

3. 第N高的薪水

题目

编写一个 SQL 查询，获取 Employee 表中第 n 高的薪水（Salary）。

IdSalary
1100
2200
3300

例如上述 Employee 表，n = 2 时，应返回第二高的薪水 200。如果不存在第 n 高的薪水，那么查询应返回 null。

getNthHighestSalary(2)
200

题解

我的解

再见！

官方解一

此方法不是很符合题意，因为给的不是一句sql，而是1个变量定义+1个sql

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  SET n = N-1;
  RETURN (     
  SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT n,1
  );
END

官方解二

第二个方案，按符合题意的思路来，只用一个sql，那么要先查出前N薪水，然后取最小就好了，注意可能总数不够前N，count一下比较即可

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  RETURN (     
  SELECT  IF(count<N,NULL,min) 
  FROM
    (SELECT MIN(Salary) AS min, COUNT(1) AS count
    FROM
      (SELECT DISTINCT Salary
      FROM Employee ORDER BY Salary DESC LIMIT N) AS a
    ) as b
  );
END

总结

哎呀！哎呀！哎呀！

8. 部门工资最高的员工

题目

Employee 表包含所有员工信息，每个员工有其对应的 Id, salary 和 department Id。

IdNameSalaryDepartmentId
1Joe700001
2  Jim  90000  1            
3Henry800002
4Sam600002
5Max900001

Department 表包含公司所有部门的信息。

IdName
1IT
2Sales

编写一个 SQL 查询，找出每个部门工资最高的员工。对于上述表，您的 SQL 查询应返回以下行（行的顺序无关紧要）。

DepartmentEmployeeSalary
ITMax90000
IT        Jim      90000  
SalesHenry80000

解释：

  • Max 和 Jim 在 IT 部门的工资都是最高的，Henry 在销售部的工资最高。

题解

我的解

直接来吧！

官方解：使用 JOIN 和 IN

因为 Employee 表包含 Salary 和 DepartmentId 字段，我们可以以此在部门内查询最高工资。

SELECT
    DepartmentId, MAX(Salary)
FROM
    Employee
GROUP BY DepartmentId;

注意：有可能有多个员工同时拥有最高工资，所以最好在这个查询中不包含雇员名字的信息。
DepartmentIdMAX(Salary)
190000
280000

然后，我们可以把表 Employee 和 Department 连接，再在这张临时表里用 IN 语句查询部门名字和工资的关系。

SELECT
    Department.name AS 'Department',
    Employee.name AS 'Employee',
    Salary
FROM
    Employee
        JOIN
    Department ON Employee.DepartmentId = Department.Id
WHERE
    (Employee.DepartmentId , Salary) IN
    (   SELECT
            DepartmentId, MAX(Salary)
        FROM
            Employee
        GROUP BY DepartmentId
	)
;
DepartmentEmployeeSalary
SalesHenry80000
ITMax90000

总结

唉呀妈呀怎么办！

5. 体育馆的人流量

题目

X 市建了一个新的体育馆，每日人流量信息被记录在这三列信息中：序号 (id)、日期 (visit_date)、 人流量 (people)。

请编写一个查询语句，找出人流量的高峰期。高峰期时，至少连续三行记录中的人流量不少于100。

例如，表 stadium：

idvisit_datepeople
12017-01-0110
22017-01-02109
32017-01-03150
42017-01-0499
52017-01-05145
62017-01-061455
72017-01-07199
82017-01-08188

对于上面的示例数据，输出为：

idvisit_datepeople
52017-01-05145
62017-01-061455
72017-01-07199
82017-01-08188

 

提示：

  • 每天只有一行记录，日期随着 id 的增加而增加。

题解

我的解

为什么还不发工资啊！

官方解：使用 JOIN 和 WHERE

思路

在表 stadium 中查询人流量超过 100 的记录，将查询结果与其自身的临时表连接，再使用 WHERE 子句获得满足条件的记录。

算法

第一步：查询人流量超过 100 的记录，然后将结果与其自身的临时表连接。

select distinct t1.*
from stadium t1, stadium t2, stadium t3
where t1.people >= 100 and t2.people >= 100 and t3.people >= 100
;
iddatepeopleiddatepeopleiddatepeople
22017-01-0210922017-01-0210922017-01-02109
32017-01-0315022017-01-0210922017-01-02109
52017-01-0514522017-01-0210922017-01-02109
62017-01-06145522017-01-0210922017-01-02109
72017-01-0719922017-01-0210922017-01-02109
82017-01-0818822017-01-0210922017-01-02109
22017-01-0210932017-01-0315022017-01-02109
32017-01-0315032017-01-0315022017-01-02109
52017-01-0514532017-01-0315022017-01-02109
62017-01-06145532017-01-0315022017-01-02109
72017-01-0719932017-01-0315022017-01-02109
82017-01-0818832017-01-0315022017-01-02109
22017-01-0210952017-01-0514522017-01-02109
32017-01-0315052017-01-0514522017-01-02109
52017-01-0514552017-01-0514522017-01-02109
62017-01-06145552017-01-0514522017-01-02109
72017-01-0719952017-01-0514522017-01-02109
82017-01-0818852017-01-0514522017-01-02109
22017-01-0210962017-01-06145522017-01-02109
32017-01-0315062017-01-06145522017-01-02109
52017-01-0514562017-01-06145522017-01-02109
62017-01-06145562017-01-06145522017-01-02109
72017-01-0719962017-01-06145522017-01-02109
82017-01-0818862017-01-06145522017-01-02109
22017-01-0210972017-01-0719922017-01-02109
32017-01-0315072017-01-0719922017-01-02109
52017-01-0514572017-01-0719922017-01-02109
62017-01-06145572017-01-0719922017-01-02109
72017-01-0719972017-01-0719922017-01-02109
82017-01-0818872017-01-0719922017-01-02109
22017-01-0210982017-01-0818822017-01-02109
32017-01-0315082017-01-0818822017-01-02109
52017-01-0514582017-01-0818822017-01-02109
62017-01-06145582017-01-0818822017-01-02109
72017-01-0719982017-01-0818822017-01-02109
82017-01-0818882017-01-0818822017-01-02109
22017-01-0210922017-01-0210932017-01-03150
32017-01-0315022017-01-0210932017-01-03150
52017-01-0514522017-01-0210932017-01-03150
62017-01-06145522017-01-0210932017-01-03150
72017-01-0719922017-01-0210932017-01-03150
82017-01-0818822017-01-0210932017-01-03150
22017-01-0210932017-01-0315032017-01-03150
32017-01-0315032017-01-0315032017-01-03150
52017-01-0514532017-01-0315032017-01-03150
62017-01-06145532017-01-0315032017-01-03150
72017-01-0719932017-01-0315032017-01-03150
82017-01-0818832017-01-0315032017-01-03150
22017-01-0210952017-01-0514532017-01-03150
32017-01-0315052017-01-0514532017-01-03150
52017-01-0514552017-01-0514532017-01-03150
62017-01-06145552017-01-0514532017-01-03150
72017-01-0719952017-01-0514532017-01-03150
82017-01-0818852017-01-0514532017-01-03150
22017-01-0210962017-01-06145532017-01-03150
32017-01-0315062017-01-06145532017-01-03150
52017-01-0514562017-01-06145532017-01-03150
62017-01-06145562017-01-06145532017-01-03150
72017-01-0719962017-01-06145532017-01-03150
82017-01-0818862017-01-06145532017-01-03150
22017-01-0210972017-01-0719932017-01-03150
32017-01-0315072017-01-0719932017-01-03150
52017-01-0514572017-01-0719932017-01-03150
62017-01-06145572017-01-0719932017-01-03150
72017-01-0719972017-01-0719932017-01-03150
82017-01-0818872017-01-0719932017-01-03150
22017-01-0210982017-01-0818832017-01-03150
32017-01-0315082017-01-0818832017-01-03150
52017-01-0514582017-01-0818832017-01-03150
62017-01-06145582017-01-0818832017-01-03150
72017-01-0719982017-01-0818832017-01-03150
82017-01-0818882017-01-0818832017-01-03150
22017-01-0210922017-01-0210952017-01-05145
32017-01-0315022017-01-0210952017-01-05145
52017-01-0514522017-01-0210952017-01-05145
62017-01-06145522017-01-0210952017-01-05145
72017-01-0719922017-01-0210952017-01-05145
82017-01-0818822017-01-0210952017-01-05145
22017-01-0210932017-01-0315052017-01-05145
32017-01-0315032017-01-0315052017-01-05145
52017-01-0514532017-01-0315052017-01-05145
62017-01-06145532017-01-0315052017-01-05145
72017-01-0719932017-01-0315052017-01-05145
82017-01-0818832017-01-0315052017-01-05145
22017-01-0210952017-01-0514552017-01-05145
32017-01-0315052017-01-0514552017-01-05145
52017-01-0514552017-01-0514552017-01-05145
62017-01-06145552017-01-0514552017-01-05145
72017-01-0719952017-01-0514552017-01-05145
82017-01-0818852017-01-0514552017-01-05145
22017-01-0210962017-01-06145552017-01-05145
32017-01-0315062017-01-06145552017-01-05145
52017-01-0514562017-01-06145552017-01-05145
62017-01-06145562017-01-06145552017-01-05145
72017-01-0719962017-01-06145552017-01-05145
82017-01-0818862017-01-06145552017-01-05145
22017-01-0210972017-01-0719952017-01-05145
32017-01-0315072017-01-0719952017-01-05145
52017-01-0514572017-01-0719952017-01-05145
62017-01-06145572017-01-0719952017-01-05145
72017-01-0719972017-01-0719952017-01-05145
82017-01-0818872017-01-0719952017-01-05145
22017-01-0210982017-01-0818852017-01-05145
32017-01-0315082017-01-0818852017-01-05145
52017-01-0514582017-01-0818852017-01-05145
62017-01-06145582017-01-0818852017-01-05145
72017-01-0719982017-01-0818852017-01-05145
82017-01-0818882017-01-0818852017-01-05145
22017-01-0210922017-01-0210962017-01-061455
32017-01-0315022017-01-0210962017-01-061455
52017-01-0514522017-01-0210962017-01-061455
62017-01-06145522017-01-0210962017-01-061455
72017-01-0719922017-01-0210962017-01-061455
82017-01-0818822017-01-0210962017-01-061455
22017-01-0210932017-01-0315062017-01-061455
32017-01-0315032017-01-0315062017-01-061455
52017-01-0514532017-01-0315062017-01-061455
62017-01-06145532017-01-0315062017-01-061455
72017-01-0719932017-01-0315062017-01-061455
82017-01-0818832017-01-0315062017-01-061455
22017-01-0210952017-01-0514562017-01-061455
32017-01-0315052017-01-0514562017-01-061455
52017-01-0514552017-01-0514562017-01-061455
62017-01-06145552017-01-0514562017-01-061455
72017-01-0719952017-01-0514562017-01-061455
82017-01-0818852017-01-0514562017-01-061455
22017-01-0210962017-01-06145562017-01-061455
32017-01-0315062017-01-06145562017-01-061455
52017-01-0514562017-01-06145562017-01-061455
62017-01-06145562017-01-06145562017-01-061455
72017-01-0719962017-01-06145562017-01-061455
82017-01-0818862017-01-06145562017-01-061455
22017-01-0210972017-01-0719962017-01-061455
32017-01-0315072017-01-0719962017-01-061455
52017-01-0514572017-01-0719962017-01-061455
62017-01-06145572017-01-0719962017-01-061455
72017-01-0719972017-01-0719962017-01-061455
82017-01-0818872017-01-0719962017-01-061455
22017-01-0210982017-01-0818862017-01-061455
32017-01-0315082017-01-0818862017-01-061455
52017-01-0514582017-01-0818862017-01-061455
62017-01-06145582017-01-0818862017-01-061455
72017-01-0719982017-01-0818862017-01-061455
82017-01-0818882017-01-0818862017-01-061455
22017-01-0210922017-01-0210972017-01-07199
32017-01-0315022017-01-0210972017-01-07199
52017-01-0514522017-01-0210972017-01-07199
62017-01-06145522017-01-0210972017-01-07199
72017-01-0719922017-01-0210972017-01-07199
82017-01-0818822017-01-0210972017-01-07199
22017-01-0210932017-01-0315072017-01-07199
32017-01-0315032017-01-0315072017-01-07199
52017-01-0514532017-01-0315072017-01-07199
62017-01-06145532017-01-0315072017-01-07199
72017-01-0719932017-01-0315072017-01-07199
82017-01-0818832017-01-0315072017-01-07199
22017-01-0210952017-01-0514572017-01-07199
32017-01-0315052017-01-0514572017-01-07199
52017-01-0514552017-01-0514572017-01-07199
62017-01-06145552017-01-0514572017-01-07199
72017-01-0719952017-01-0514572017-01-07199
82017-01-0818852017-01-0514572017-01-07199
22017-01-0210962017-01-06145572017-01-07199
32017-01-0315062017-01-06145572017-01-07199
52017-01-0514562017-01-06145572017-01-07199
62017-01-06145562017-01-06145572017-01-07199
72017-01-0719962017-01-06145572017-01-07199
82017-01-0818862017-01-06145572017-01-07199
22017-01-0210972017-01-0719972017-01-07199
32017-01-0315072017-01-0719972017-01-07199
52017-01-0514572017-01-0719972017-01-07199
62017-01-06145572017-01-0719972017-01-07199
72017-01-0719972017-01-0719972017-01-07199
82017-01-0818872017-01-0719972017-01-07199
22017-01-0210982017-01-0818872017-01-07199
32017-01-0315082017-01-0818872017-01-07199
52017-01-0514582017-01-0818872017-01-07199
62017-01-06145582017-01-0818872017-01-07199
72017-01-0719982017-01-0818872017-01-07199
82017-01-0818882017-01-0818872017-01-07199
22017-01-0210922017-01-0210982017-01-08188
32017-01-0315022017-01-0210982017-01-08188
52017-01-0514522017-01-0210982017-01-08188
62017-01-06145522017-01-0210982017-01-08188
72017-01-0719922017-01-0210982017-01-08188
82017-01-0818822017-01-0210982017-01-08188
22017-01-0210932017-01-0315082017-01-08188
32017-01-0315032017-01-0315082017-01-08188
52017-01-0514532017-01-0315082017-01-08188
62017-01-06145532017-01-0315082017-01-08188
72017-01-0719932017-01-0315082017-01-08188
82017-01-0818832017-01-0315082017-01-08188
22017-01-0210952017-01-0514582017-01-08188
32017-01-0315052017-01-0514582017-01-08188
52017-01-0514552017-01-0514582017-01-08188
62017-01-06145552017-01-0514582017-01-08188
72017-01-0719952017-01-0514582017-01-08188
82017-01-0818852017-01-0514582017-01-08188
22017-01-0210962017-01-06145582017-01-08188
32017-01-0315062017-01-06145582017-01-08188
52017-01-0514562017-01-06145582017-01-08188
62017-01-06145562017-01-06145582017-01-08188
72017-01-0719962017-01-06145582017-01-08188
82017-01-0818862017-01-06145582017-01-08188
22017-01-0210972017-01-0719982017-01-08188
32017-01-0315072017-01-0719982017-01-08188
52017-01-0514572017-01-0719982017-01-08188
62017-01-06145572017-01-0719982017-01-08188
72017-01-0719972017-01-0719982017-01-08188
82017-01-0818872017-01-0719982017-01-08188
22017-01-0210982017-01-0818882017-01-08188
32017-01-0315082017-01-0818882017-01-08188
52017-01-0514582017-01-0818882017-01-08188
62017-01-06145582017-01-0818882017-01-08188
72017-01-0719982017-01-0818882017-01-08188
82017-01-0818882017-01-0818882017-01-08188

共有 6 天人流量超过 100 人，笛卡尔积 后有 216（666） 条记录。
前 3 列来自表 t1，中间 3 列来自表 t2，最后 3 列来自表 t3。

表 t1，t2 和 t3 相同，需要考虑添加哪些条件能够得到想要的结果。以 t1 为例，它有可能是高峰期的第 1 天，第 2 天，或第 3 天。

  • t1 是高峰期第 1 天：(t1.id - t2.id = 1 and t1.id - t3.id = 2 and t2.id - t3.id =1) -- t1, t2, t3
  • t1 是高峰期第 2 天：(t2.id - t1.id = 1 and t2.id - t3.id = 2 and t1.id - t3.id =1) -- t2, t1, t3
  • t1 是高峰期第 3 天：(t3.id - t2.id = 1 and t2.id - t1.id =1 and t3.id - t1.id = 2) -- t3, t2, t1
select t1.*
from stadium t1, stadium t2, stadium t3
where t1.people >= 100 and t2.people >= 100 and t3.people >= 100
and
(
	  (t1.id - t2.id = 1 and t1.id - t3.id = 2 and t2.id - t3.id =1)  -- t1, t2, t3
    or
    (t2.id - t1.id = 1 and t2.id - t3.id = 2 and t1.id - t3.id =1) -- t2, t1, t3
    or
    (t3.id - t2.id = 1 and t2.id - t1.id =1 and t3.id - t1.id = 2) -- t3, t2, t1
)
;
iddatepeople
72017-01-07199
62017-01-061455
82017-01-08188
72017-01-07199
52017-01-05145
62017-01-061455

可以看到查询结果中存在重复的记录，再使用 DISTINCT 去重。

select distinct t1.*
from stadium t1, stadium t2, stadium t3
where t1.people >= 100 and t2.people >= 100 and t3.people >= 100
and
(
	  (t1.id - t2.id = 1 and t1.id - t3.id = 2 and t2.id - t3.id =1)  -- t1, t2, t3
    or
    (t2.id - t1.id = 1 and t2.id - t3.id = 2 and t1.id - t3.id =1) -- t2, t1, t3
    or
    (t3.id - t2.id = 1 and t2.id - t1.id =1 and t3.id - t1.id = 2) -- t3, t2, t1
)
order by t1.id
;

总结

风萧萧兮易水寒，壮士一去不复返！

分享到：