PC's Blog

Life is short, Play more!

0%

LeetCode cheetsheet for C++

发表于 分类于
本文字数： 5.3k 阅读时长 ≈ 5 分钟

https://zhuanlan.zhihu.com/p/349940945
692 done

排序

自定义排序

1
2
3
4
static bool compare(vector<int> &a, vector<int> &b) {
    return a[0] < b[0];
}
sort(intervals.begin(), intervals.end(), compare);

数组(vector)

初始化

1
2
vector<int> v(size);
vector<int> v(size, init_value);

遍历数组

1
2
3
for (int i = 0; i < vec.size(); ++i) {
	vec[i] = i;
}

数组追加到另一个数组

1
vec1.insert(vec1.end(), vec2.begin(), vec2.end());

排序数组+去重

1
2
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());

逆序排序

1
sort(nums.begin(), nums.end(), greater<int>());

二维vector初始化

1
vector<vector<bool>> visited(rows, vector<bool>(cols, false));

优先级队列/堆(priority_queue)

求第k大的数

  • 大根堆: 建大小为n的堆, 弹出k-1次，堆顶为第k大的数
  • 小根堆: 维护大小为k的堆，取堆顶元素

大根堆(默认)

1
2
3
4
5
6
7
8
9
10
int findKthLargest(vector<int> &nums, int k) {
	priority_queue<int, vector<int>, less<int>> pq;
	for (int i = 0; i < nums.size(); ++i) {
		pq.push(nums[i]);
	}
	for (int i = 0; i < k - 1; ++i) {
		pq.pop();
	}
	return pq.top();
}

小根堆

1
2
3
4
5
6
7
8
9
10
11
int findKthLargest(vector<int> &nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < k; ++i) {
        pq.push(nums[i]);
    }
    for (int i = k; i < nums.size(); ++i) {
        pq.push(nums[i]);
        pq.pop();
    }
    return pq.top();
}

自定义优先级(仿函数)

求k个最小距离的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    struct cmp{
        bool operator() (vector<int> &a, vector<int> &b) {
            int dis1 = a[0] * a[0] + a[1] * a[1];
            int dis2 = b[0] * b[0] + b[1] * b[1];
            return dis1 > dis2;
        }
    };
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        vector<vector<int>> ans;
        priority_queue<vector<int>, vector<vector<int>>, cmp> pq;
        for (auto &vec: points) {
            pq.push(vec);
        }
        for (int i = 0; i < k; ++i) {
            ans.push_back(pq.top());
            pq.pop();
        }
        return ans;
    }
};

集合(unordered_set)

基本操作

1
2
s.insert(key);
s.erase(key);

寻找两个链表相交的节点

1
2
3
4
5
6
7
8
9
10
11
12
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    unordered_set<ListNode *> s;
    for(ListNode *h = headA; h != nullptr; h = h->next) {
        s.insert(h);
    }
    for (ListNode *h = headB; h != nullptr; h = h->next) {
        if (s.find(h) != s.end()) {
            return h;
        }
    }
    return nullptr;
}

哈希表(unordered_map)

删除

1
2
unordered_map<int, DLinkedNode*> ht;
ht.erase(key);

队列(Queue)

1
2
3
4
5
6
queue<int> q;
q.front() #队首
q.push()
q.pop()
q.size()
q.empty()

双端队列(Deque)

1
2
3
4
5
6
7
8
9
deque<int> dq;
push_back
pop_back
pop_front
front
back
for (auto iter = dq.begin(); iter != dq.end(); ++iter) {
	*iter
}

字符串(String)

比较两个字符串的字典序

1
s1.compare(s2) < 0

整数转字符串

1
string s = to_string(10);

去除所有空格

末尾添加字符

1
2
string s;
s.push_back('c');

链表

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;

    ListNode *prev = nullptr;
    ListNode *cur = head;
    ListNode *tmp = nullptr;
    while (cur != nullptr) {
        tmp = cur->next;
        cur->next = prev;
        prev = cur;
        cur = tmp;
    }
    return prev;
}

快慢指针找中间节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if (head == nullptr || head->next = nullptr) return head;
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast != nullptr) {
            fast = fast->next;
            if (fast != nullptr) {
                fast = fast->next;
				slow = slow->next;
            }
        }
        return slow;
    }
};

双向链表节点

1
2
3
4
5
6
7
8
struct DLinkedNode {
    DLinkedNode *prev;
    DLinkedNode *next;
    int key;
    int value;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int k, int v): key(k), value(v), prev(nullptr), next(nullptr) {}
};

枚举类型

1
enum Direction {RIGHT, DOWN, LEFT, UP};

LeetCode py

自定义排序

Python匿名函数

1
2
3
# intervals: List[List[int]])
intervals.sort(key=lambda p: p[0])
intervals.sort(key=lambda p: p[0], reverse=True)

Python命名函数排序

1
2
3
4
5
6
7
def compare(x, y):
	s1 = str(x) + str(y)
	s2 = str(y) + str(x)
	if s1 > s2:
		return -1
	return 1
nums.sort(key=cmp_to_key(compare))

遍历list

enumerate正向遍历索引和值

1
for index,value in enumerate(list):

range逆序遍历 (起始索引(含)，结束索引(不含), 步长)

1
2
for idx in range(len(nums)-1, -1, -1):
	nums[idx] = ...

小根堆

Python heapq默认是小根堆

1
2
3
4
5
6
7
8
9
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_heap = []
        for i in range(k):
            heapq.heappush(min_heap, nums[i])
        for i in range(k, len(nums), 1):
            heapq.heappush(min_heap, nums[i])
            heapq.heappop(min_heap)
        return min_heap[0]

集合(set)

1
2
3
4
s = set()
s.add(e)
if e in s:
	...

队列

1
2
3
4
5
6
7
8
9
10
11
from collections import deque
d = deque()
d = deque([1, 2, 3])

d.append(4)
d.appendleft(0)
removed_element = d.pop()
removed_element = d.popleft()
d[0]
d[-1]
d.remove(2)

https://leetcode.cn/problems/first-unique-number/