图
图二分图二分图算法也称为染色法,是一种广度优先搜索。如果可以用两种颜色对图中的节点进行着色,并且保证相邻的节点颜色不同,那么图为二分。
Is Graph Bipartite?题目:
You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. 判断无向图是否是二分图。
题解:
用队列和广度优先搜索,我们可以对未染色的节点进行染色,并且检查是否有颜色相同的相邻节点存在。注意在代码中,我们用 0 表示未检查的节点,用 1 和 2 表示两种不同的颜色。
1234567891011121314151617181920212223242526bool isBipartite(vector<vector<int>>& graph) { int n = graph.size(); if (n == 0) return true; vector<int> color(n, 0); q ...
树
树作为链表的升级版,我们通常接触的树都是二叉树(binary tree),即每个节点最多有两个子节点;LeetCode 默认的树表示方法如下:
12345678struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};
树的递归Maximum Depth of Binary Tree题目:
Given the root of a binary tree, return its maximum depth.
A bin ...
链表
链表 链表是由节点和指针构成的数据结构,每个节点存有一个值,和一个指向下一个节点的指针,因此很多链表问题可以用递归来处理。LeetCode 默认的链表表示方法如下:
1234567struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {}};
由于在进行链表操作时,尤其是删除节点时,经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题:一是尽量处理当前节点的下一个节点而非当前节点本身,二是建立一个虚拟节点 (dummy node),使其指向当前链表的头节点,这样即使原链表所有节点全被删除,也会有一个 dummy 存在,返回 dummy->next ...
字符串
字符串字符串比较Valid Anagram题目:
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
anagram:相同字母异序词
Input: s = “anagram”, t = “nagaram”Output: true
题解:
直接 hash 数组即可
123456789101112131415bool isAnagram(string s, string t) { if (s.length() != t.length()) return false; int hash[26]; memset(hash, 0, siz ...
数据结构
数据结构STLSequence Containers
维持顺序的容器
vector:动态数组
list:双向链表
deque:双端队列
array:固定大小的数组
forward_list:单向链表
Container Adaptors
基于其它容器实现的数据结构
stack:栈:后入先出(LIFO)的数据结构
queue:队列:先入先出(FIFO)的数据结构
priority_queue:最大值先出的数据结构
Associative Containers
排好序的数据结构
set:有序集合,不可重复
multiset:可重复的 set
map:有序表,在 set 的基础上加上映射关系,可以对每个元素 key 存一个值 value。
multimap:可重复的 map
Unordered Associative Containers
对每个 Associative Containers 实现了哈希版本,即无序版本
unordered_set:哈希集合
unordered_multiset:可重复的哈希集合
unordered_map:哈希表
unordered_m ...
神奇的位运算
常用技巧位运算是算法题里比较特殊的一种类型,它们利用二进制位运算的特性进行一些奇妙的优化和计算。常用的位运算符号包括:“∧”按位异或(取不同)、“&”按位与(取交)、“|”按位或(取并)、“~”取反、“<<” 算术左移和“>>”算术右移。
除此之外,n & (n - 1) 可以去除 n 的位级表示中最低的那一位,例如对于二进制表示 11110100 ,减去 1 得到 11110011,这两个数按位与得到 11110000。n & (-n) 可以得到 n 的位级表示中最低的那一位,例如对于二进制表示 11110100,取负得到 00001100,这两个数按位与得到 00000100。
位运算基础问题汉明距离题面题解两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y,计算并返回它们之间的汉明距离。
示例 1:
输入:x = 1, y = 4输出:2解释:1 (0 0 0 1)4 (0 1 0 0)
示例 2:
输入:x = 3, y = 1输出:1
按位异或,统计 1 的个数即可
代 ...
巧解数学问题
公倍数与公因数辗转相除法利用辗转相除法,我们可以很方便地求得两个数的最大公因数(greatest common divisor,gcd);将两个数相乘再除以最大公因数即可得到最小公倍数(least common multiple, lcm)。
123456int gcd(int a, int b) { return b == 0 ? a : gcd(b, a% b);}int lcm(int a, int b) { return a * b / gcd(a, b);}
扩展欧几里得算法进一步地,我们也可以通过扩展欧几里得算法(extended gcd)在求得 a 和 b 最大公因数的同时,也得到它们的系数 x 和 y,从而使 ax + by = gcd(a, b)。
1234567891011int xGCD(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; ...
分治法
算法解释顾名思义,分治问题由“分”(divide)和“治”(conquer)两部分组成,通过把原问题分为子问题,再将子问题进行处理合并,从而实现对原问题的求解。我们在排序章节展示的归并排序就是典型的分治问题,其中“分”即为把大数组平均分成两个小数组,通过递归实现,最终我们会得到多个长度为 1 的子数组;“治”即为把已经排好序的两个小数组合成为一个排好序的大数组,从长度为 1 的子数组开始,最终合成一个大数组。
另外,自上而下的分治可以和 memoization 结合,避免重复遍历相同的子问题。如果方便推导,也可以换用自下而上的动态规划方法求解。
表达式问题为运算表达式设计优先级题面题解给你一个由数字和运算符(只包含+,-,*)组成的字符串 expression ,按不同优先级组合数字和运算符,计算并返回所有可能组合的结果。你可以按任意顺序返回答案。
生成的测试用例满足其对应输出值符合 32 位整数范围,不同结果的数量不超过 104。
示例 1:
输入:expression = “2-1-1”输出:[0,2]
示例 2:
输入:expression = “2*3-4*5”输出:[- ...
