# Leetcode 💻 寒假 20230109

---

### 169. Majority Element

> The majority element is the element that appears more than [n / 2] times.

```python [3]
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[(len(nums)) // 2]
```

以下操作等价

```python
print(int(5 / 2))  # 2
print(5 // 2)  # 2
```

Note:
第169题，找出列表中出现次数最多的元素。
题目给了一个关键信息，就是这个要找的元素出现次数超过n/2,
也就是超过这个列表长度的一半。
那么最简单的写法就是对数组进行排序，然后返回他的中位数。
注意我这里写了两个除号，这是python整除的意思

---

### 56. Merge Intervals

```python [|2|4|5-7|9-12|14-15]
def merge(self, intervals):
  intervals.sort(key = lambda i: i[0])
  ret = []
  for begin, end in intervals:
    if not ret:
      ret.append([begin, end])
      continue

    # overlap
    if ret[-1][1] >= begin:
      ret[-1][1] = max(end, ret[-1][1])
      continue

    ret.append([begin, end])
  return ret
```

Note:
（2）首先对intervals进行排序，注意intervals里灭个元素都是一个列表，
这里key参数我们给他传入一个lambda临时函数，
这个函数是干什么的呢，他的任务就是输入一个i,然后返回i的第零个元素，
意思是告诉排序函数，啊，你在排序的时候，要用i的第零个元素作为排序的依据

（4）接着我们用begin和end这两个变量遍历intervals数组，

（5-7）我们先处理第一种特殊情况，就是ret数组为空，
这种情况直接把当前遍历到的begin和end添加进去就行了

（9-12）第二种情况是发生了overlap我们需要把ret最后一个元素的end，更新为最大的end.

（14-15）如果上面两种特殊情况都没有发生，那么我们正常把begin和end添加到列表里就行了

---

### 避免嵌套

坏👎

```python []
if gpa < 2:
  return 'failed'
else:
  if gpa < 3:
    return "good"
  else:
    return "excellent"
```

好👍

```python []
if gpa < 2:
  return "failed"
if gpa < 3:
  return "good"
return "excellent"
```

Note:
这里有个函数，根据一个整数gpa变量，返回对应的字符串。
假设这里用 if 判断，第一种比较接近自然语言，如果gpa小于2则返回failed，
不然的话接着判断，如果gpa小于3则返回good,不然就返回4。

第二种方法则比较符合程序设计思想，
先从条件范围小的情况开始处理，先处理gpa小于2,然后处理gpa小于3 ，

最后一个return是精髓，保证这个函数无论在什么情况下都有一个返回值。
第一种情况下很多人写着写着就忘了返回值，然后各种内存报错又找不到在哪里出错，非常痛苦

---

### 避免嵌套基本思想

```python []
if 特殊情况:
    处理特殊情况()
    return
if 其他特殊情况:
    处理其他特殊情况()
    return
做该做的事情()
```

Note:
避免嵌套的基本思想就是early return,就是说进入函数之后，
先处理特殊情况和各种边界情况，处理完之后直接return这个函数，也就是early return.
最后再开始做函数该做的事情，一般来说这都是比较好的写法，如果你去看golang代码，
你能看到大量这样的写法，这也是golang社区和官方建议的写法。

---

### 15. 3Sum

```python [|4-8|6]
import itertools
class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
    ret = {
      tuple(sorted(test))
      for test in itertools.combinations(nums, 3)
      if sum(test) == 0
    }
    return list(ret)
```

### List Comprehensions

求 0 到 100 所有能被 7 整除数的平方和

```python []
sum([i ** 2 for i in range(100) if i % 7 == 0])
```

### 迭代器

标准库提供的多种高效排列组合工具

```python []
list(itertools.combinations([1,2,3,4], 3))
# [(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
```

Note:
这题的解法其实也就一行，就是4-8行的这个列表生成式，那么列表生成式是什么捏。
列表生成式又叫做List comprehensions, 这里有个例子，假设我们要求0到100所有能被7整除数的平方和，
这个计算用列表生成式一行就能实现。首先最开始是个sum函数，sum函数里面是一个列表，
这个列表是中的每一个元素都是i的平方，那么i从哪里来的呢，i是for i in range(100) 这个循环中出来的，
并且i满足i除以7的余数是0这个条件。

回到4-8行，ret是一个集合，集合中每个元素是 **经过排序** 的 **元组** test,
test从哪里来呢，test 是 第七行 这个for循环迭代出来的变量，并且这个test满足第八行的这个求和等于0的条件。

那么这个itertools.combinations是什么函数呢，它是标准库中提供的排列组合迭代器。
下面给各位回忆一下高中排列组合的知识，假设我们有一个列表，列表中有元素1 2 3 4,每次取三个不同的元素，
那么一共有多少中不同的排列组合呢。用combinations函数就能非常方便的帮我们遍历所有排列组合。

理论上，这题就这么可以解出来了，但是实际上是不行的
```

---

但是时间复杂度 `$O(n^3)$`

3000 数组长度就是 27,000,000,000 次循环（百亿）😢

python for 循环在一般电脑上一秒钟能跑一千万次左右

思路：哈希表（字典）具有 `$O(1)$` 查找速度，使用字典代替最深的一层循环，将算法优化为 `$O(n^2)$`

```python [|5-7|9-14|16-17|18-21|22-25|27-34|36-38]
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()

        # 处理全是相同数字的特殊情况
        if min(nums) == max(nums) and sum(nums) == 0:
            return [[min(nums)] * 3]

        # 生成反向字典，之后用于加速查找
        reverse = {}
        for key, val in enumerate(nums):
            if reverse.get(val) is None:
                reverse[val] = []
            reverse[val].append(key)
        
        # 创建集合，集合中元素是不可重复的
        ret = set()
        for index_i in range(len(nums)-2):
            i = nums[index_i]
            for index_j in range(index_i+1, len(nums)-1):
                j = nums[index_j]
                # 由于 sum((i,j,k)) == 0，计算出需要的 k 是多少
                k = -(i + j)  

                test = reverse.get(k)
                
                # 情况1：字典没有满足 sum((i,j,k))==0 的k
                if test is None:
                    continue
                # 情况2&3：字典中有满足需求的k，但它的索引是 i 或者 j
                if len(test) == 1 and (index_i in test or index_j in test):
                    continue
                if len(test) == 2 and (index_i in test and index_j in test):
                    continue

                # 对 (i,j,k) 排序后放入元组中
                # 利用元组不可重复的特性去掉重复结果
                ret.add(tuple(sorted([i, j, k])))
        return list(ret)
```

---

### 406. Queue Reconstruction by height

利用 list.insert() 能在指定位置插入元素，并把后面的元素往后移动的特点

```python [|2-3,6-8|]
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
  # 按 p[0] 降序排，p[0] 相同的情况下按 p[1] 升序排
  people.sort(key = lambda p: (-p[0], p[1]))
  res = []
  for p in people:
    # 在 p[1] 位置插入 p，后面的元素会向后移动一位
    # [TODO] 使用链表优化性能，但这已经AC了，能AC的就是好的👍
    res.insert(p[1], p)
  return res

# [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
```

⚠ python 标准库中有双向链表 `collections.deque`
⚠ c++ 标准库中也有链表 list

Note:
这道题其实也就两行代码，第一行是将people排序，第二行是在新数组中指定位置插入元素。
解题的关键就在利用了插入排序的特性，列表中后来插入的元素把之前插入的元素往后推一个位置。

但题外话我想提一下，
我们写算法关注算法性能，这没问题，但我自己个人是把代码简洁度看得比性能更重的。
写程序像写作一样，不光要机器能跑，还要其他人能看得懂，不光要看得懂，还要看得舒服，
怎么才算看得舒服呢，我个人认为是代码符合思维直觉，一个屏幕长度内的代码表达的信息量恰到好处，
不像流水账一样冗余，也不像汇编语言那样要盯着一行思考很久，当然我说了不算，
有本书叫《代码简洁之道》就专门讨论这类软件工程问题，感兴趣的可以找来看看。

还有就是标准库很重要，当然不是说要你把标注库背下来，
只是说要了解标准库能做到什么，还有了解你用的语言有哪些语法糖，
比如说三元表达式，不知道三元表达式这个语法糖的可以自己去查一下，
大部分现代语言比如python或者c++都有三元表达式这个语法糖，它能让代码更简短更简洁，
总的来说标准库的作用就是等你要用到相关功能的时候就知道去哪里查，而不是说自己重复造轮子

---

## C++

```cpp [|4|6-7|9-12|14-18]
#include <algorithm>

int main() {
  std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

  // 默认升序排序
  std::sort(s.begin(), s.end());

  // 自定义降序排序函数
  std::sort(s.begin(), s.end, [](int a, int b) {
    return a > b;
  })

  // 循环输出
  for (auto const &i : s) {
    std::cout << i << " ";
  }
  std::cout << std::endl;

  return 0;
}
```

---

### C++ 标准库中的排序（以C11为例）

- 快速排序平均复杂度为 `$O(N log N)$` ，最坏情况下为 `$O(N^2)$`，快排递归带来额外开销
- 堆排序比快排慢，但最坏情况下为 `$(N log N)$`
- 插入排序在大致有序的情况下表现非常好

`std::sort` 实现了 Introspective sorting，集成了三种算法各自的优点

---

## End 🎉