reveal.js/leetcode-20230110.md

Leetcode 💻 寒假 20230110

---

179. Largest Number

给定一个非负整数列表 nums，将它们排列成最大的数并返回。

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> v;
        v.reserve(nums.size());
        for (auto const &i : nums) v.push_back(to_string(i));
        sort(v.begin(), v.end(), [](string &a, string &b) {
            return a + b > b + a;
        });
        string ret;
        for (auto const &s : v) ret += s;
        // 处理 ["0", "0", "0"] 的情况
        return ret.startswith('0') ? "0" : ret;
    }
};

Note:

'1' + '3' < '2'    # True
'1' + '3' < '22'   # True
'1' < '11'         # True
'1' + '0' == '10'  # True

---

179. Largest Number

Python 版本

from functools import cmp_to_key
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        strs = [str(i) for i in nums]
        strs.sort(key = cmp_to_key(
            lambda a, b: -1 if a + b > b + a else 1
        ))
        return '0' if strs[0] == '0' else ''.join(strs)

Note:

思路和刚刚的 c++ 是一样的，但我主要想给各位介绍一下python的写法， 因为我看群里用python的人还是不少的，当然这种写法是好是坏见仁见智了，我个人认为是比较好的。

4 首先我们用这个列表生成式将nums转为字符串strs， strs 是一个列表，列表中的每个元素是str(i),i是遍历nums得到的变量。

5-7 接着对strs进行排序，这个cmp to key 是python3的设计，他把一个比较用来比较大小的函数变成key函数， 这个比较函数做什么呢，他输入两个变量，如果a+b比b+a大，则这个比较函数返回-1,否则返回1,注意这里a和b的类型 都是字符串，a+b表示的是字符串a和字符串b拼接之后的结果

8 最后用一个三元表达式返回结果，和上面c++的思路是一样的， 注意这又有一个python好用的方法，字符串.join,后面跟一个数组， 意思是把这个数组用空字符串拼接起来

---

347. Top K Frequent Element

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for (auto const &n : nums)
            count[n]++;
        
        // 将 map 转为列表
        // [(0, 5), (1, 3), ... ]
        // 代表数字 0 出现 5 次，数字 1 出现 3 次
        vector<pair<int, int>> tmp;
        for (auto const &pair : count)
            tmp.push_back(pair);
        
        sort(tmp.begin(), tmp.end(), [](
            const pair<int, int> &a,
            const pair<int, int> &b) {
                return a.second > b.second;
            });
        
        vector<int> ret;
        for (auto const &pair : tmp) {
            if (ret.size() >= k)
                break;
            ret.push_back(pair.first);
        }

        return ret;
    }
};

---

347. Top K Frequent Element

Python 版本

import collections
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = collections.Counter(nums).most_common(k)
        return [i[0] for i in count]

---

75. Sort Colors

C++

void sortColors(vector<int> &nums) {
  auto low = nums.begin();
  auto high = nums.end() - 1;

  for (auto mid = nums.begin(); mid <= high;) {
    switch (*mid) {
    case 0:
      swap(*mid, *low);
      mid++;
      low++;
      break;
    case 1:
      mid++;
      break;
    case 2:
      swap(*mid, *high);
      high--;
      break;
    }
  }
}