数字范围按位与
给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。
示例 1：
输入：left = 5, right = 7
输出：4
示例 2：
输入：left = 0, right = 0
输出：0
示例 3：
输入：left = 1, right = 2147483647
输出：0
提示：
0 <= left <= right <= 2^31 - 1
解题思路：最开始的办法就是从 left 开始逐个求与，如果结果为 0 则返回结果。但是发现竟然案例全部通过超时。。。 后面想到一个提前返回的条件，就是当 right 大于 left 的两倍时，结果肯定是 0 的，但是这里需要注意 int 越界的问题。
后面发现其实这道题是找公共前缀问题，可以利用 Brian Kernighan 算法，用于清除二进制串中最右边的 1， 即 n & (n-1);
即这样运算的话，则 right 最终会小于或者等于 left，如果 right = 0 则表明不存在公共前缀，若大于 0 则表明为公共前缀。
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
if((long)right > ((long)left << 1)) return 0;
int res = left;
while(left != right) {
++left;
res &= left;
if(res == 0) break;
}
return res;
}
};
class Solution {
public:
int rangeBitwiseAnd(int left, int right) {
while(right > left) {
right = right & (right - 1);
}
return right;
}
};
快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
示例 1：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
示例 2：
输入：n = 2
输出：false
提示：
1 <= n <= 2^31 - 1
解题思路：利用 set 存储每次计算的结果，根据提示重复计算的过程只有两种结果，要不得到 1 ，要不无限循环。
所以思路就在与重复计算平方和，得到 1 返回 true，进入循环返回 false。
class Solution {
public:
bool isHappy(int n) {
set<int> MidRes;
bool res = false;
int mulSum = 0;
while(true) {
while(n > 0) {
int temp = n % 10;
mulSum += (temp * temp);
n /= 10;
}
if(MidRes.find(mulSum) == MidRes.end()) {
MidRes.insert(mulSum);
n = mulSum;
mulSum = 0;
}else {
if(mulSum == 1) res = true;
break;
}
}
return res;
}
};
移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
列表中的节点数目在范围 [0, 10^4] 内
1 <= Node.val <= 50
0 <= val <= 50
解题思路：遍历链表，删除节点。
/**
* Definition for singly-linked list.
* struct 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) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* res = new ListNode(-1, head);
ListNode* pre = res, *curr = head;
while(curr != nullptr) {
if(curr->val == val) {
pre->next = curr->next;
curr = curr->next;
}else {
pre = curr;
curr = curr->next;
}
}
return res->next;
}
};
计数质数
统计所有小于非负整数 n 的质数的数量。
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
提示：
0 <= n <= 5 * 10^6
解题思路：想着是一道简单题，应该暴力没有问题，但是还是超时了。。
可以提前将非质数提前标记出来，可以知道质数的倍数肯定就不是质数了，所以利用这一点，可以提前将非质数标记出来。
这样的话可以发现都不用去判断一个数是否是质数了，当遍历到这个数的时候，它还没有被标记，就说明它就是个质数。
但是这样标记的话，会发现有一些数会被重复标记，也会浪费一点时间，比如 6 既会被 2 标记，又会被 3 标记。
如果想要只标记一次，可以采用 线性筛 的方法，即标记的时候，对当前整数进行操作，
- 即 x * primes[0], x * primes[1], …，且在发现 x mod primes[i] = 0 的时候结束当前标记
- 因为 x mod primes[i] = 0，则表明 x * primes[i+1] 这个数一定会被 primes[i] 这个质数整除，保证每个非质数只会被其最小的质因数标记
- 所以也就保证了每个非质数只会被标记一次
class Solution {
public:
int countPrimes(int n) {
int res = 0;
vector<int> isPrime(n, 1);
for(int i = 2; i < n; ++i) {
if(isPrime[i]) {
res += 1;
if ((long long)i * i < n) {
for (int j = i * i; j < n; j += i) {
isPrime[j] = 0;
}
}
}
}
return res;
}
};
同构字符串
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例 1:
输入：s = "egg", t = "add"
输出：true
示例 2：
输入：s = "foo", t = "bar"
输出：false
示例 3：
输入：s = "paper", t = "title"
输出：true
提示：
可以假设 s 和 t 长度相同。
解题思路：既然是映射关系，那么就建立映射表，根据映射表来判断两个字符串是否是同构的。需要注意的是因为是强对应关系，需要管理两个映射表。
class Solution {
public:
bool isIsomorphic(string s, string t) {
if(s.size() != t.size()) return false;
unordered_map<char, char> sTt;
unordered_map<char, char> tTs;
for(int i = 0; i < s.size(); ++i) {
if(sTt.find(s[i]) == sTt.end() && tTs.find(t[i]) == tTs.end() ) {
sTt[s[i]] = t[i];
tTs[t[i]] = s[i];
}else {
if(s[i] != tTs[t[i]] || t[i] != sTt[s[i]]) return false;
}
}
return true;
}
};
反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解题思路：递归和迭代，两种方法。迭代是从前面开始反转，借助头前节点来完成反转。递归是从后面开始反转，直接记录最后一个节点为反转后的头结点。
/**
* Definition for singly-linked list.
* struct 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) {}
* };
*/
class Solution {
public:
// 递归版本
ListNode* ret = nullptr;
void reverse(ListNode* node) {
if(!node->next) {
ret = node;
return;
}
reverse(node->next);
node->next->next = node;
node->next = nullptr;
}
ListNode* reverseList(ListNode* head) {
if(head != nullptr) reverse(head);
return ret;
}
// 迭代版本
ListNode* reverseList(ListNode* head) {
ListNode* res = new ListNode(-1);
ListNode* curr = head;
while(curr) {
ListNode* next = curr->next;
curr->next = res->next;
res->next = curr;
curr = next;
}
return res->next;
}
};
课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：
1 <= numCourses <= 10^5
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同
解题思路：利用 set 记录已经学习的课程。利用 map 记录每个课程的全部前置课程。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//说明没有限制
if(prerequisites.size() == 0) return true;
set<int> started;
for(int i = 0; i < numCourses; ++i) started.insert(i);
map<int, set<int>> miv;
for(auto s : prerequisites) {
int temp = s[0];
int preTemp = s[1];
started.erase(temp);
auto it = miv.find(temp);
if(it == miv.end()) {
set<int> vi = {preTemp};
miv[temp] = vi;
}else {
miv[temp].insert(preTemp);
}
}
// 说明每个课程都有前置，那么肯定不能实现
if(numCourses == miv.size()) return false;
while(started.size() < numCourses) {
int pre = started.size();
for(auto it = miv.begin(); it != miv.end();) {
for(auto s = it->second.begin(); s != it->second.end();) {
if(started.find(*s) != started.end()) {
s = it->second.erase(s);
}else {
++s;
}
}
if(it->second.empty()) {
started.insert(it->first);
it = miv.erase(it);
}else {
++it;
}
}
if(pre == started.size()) break;
}
return started.size() >= numCourses;
}
};
实现 Trie (前缀树)
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
- Trie() 初始化前缀树对象。
- void insert(String word) 向前缀树中插入字符串 word 。
- boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
- boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次
解题思路：自己想到的办法就是利用两个 set 分别记录单词和前缀的集合，然后查找。在做的时候就想到这样肯定是不正确的，想着应该超时的，没想到竟然 ac 了。
看到题解得知正确的做法应该是要符合这道题的名字，建立前缀树，利用前缀树去查找。
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
//利用 set
class Trie {
public:
unordered_set<string> allWord;
unordered_set<string> allPrefix;
/** Initialize your data structure here. */
Trie() {
allWord.clear();
allPrefix.clear();
}
/** Inserts a word into the trie. */
void insert(string word) {
allWord.insert(word);
for(int i = 1; i <= word.size(); ++i) {
allPrefix.insert(word.substr(0,i));
}
}
/** Returns if the word is in the trie. */
bool search(string word) {
return allWord.find(word) != allWord.end();
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return allPrefix.find(prefix) != allPrefix.end();
}
};
//利用前缀树
class Trie {
public:
vector<Trie*> children;
bool isEnd;
Trie* searchPrefix(string prefix) {
Trie* node = this;
for (char ch : prefix) {
ch -= 'a';
if (node->children[ch] == nullptr) {
return nullptr;
}
node = node->children[ch];
}
return node;
}
/** Initialize your data structure here. */
Trie() {
children = vector<Trie* >(26, 0);
isEnd = false;
}
/** Inserts a word into the trie. */
void insert(string word) {
Trie* node = this;
for (char ch : word) {
ch -= 'a';
if (node->children[ch] == nullptr) {
node->children[ch] = new Trie();
}
node = node->children[ch];
}
node->isEnd = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Trie* node = this->searchPrefix(word);
return node != nullptr && node->isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
return this->searchPrefix(prefix) != nullptr;
}
};
长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
进阶：
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
解题思路：依次遍历，得到从每个数字开始达到 target 的最短长度，然后得到最终答案。
优化：
- 因为都是正整数，所以可以记录前缀和，直接利用二分法找到每个数字的最短长度。
- 利用滑动窗口，start 和 end 记录窗口的起始位置，若窗口总和小于 target，end 往后移，直到大于 target，更新长度；并且使 start 左移，直至小于 target，更新长度。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int res = INT_MAX;
for(int i = 0; i < nums.size(); ++i) {
int sum = 0;
for (int j = i; j < nums.size(); j++) {
sum += nums[j];
if (sum >= target) {
res = min(res, j - i + 1);
break;
}
}
}
return res == INT_MAX ? 0 : res;
}
};
课程表 II
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
提示:
这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序。
拓扑排序也可以通过 BFS 完成。
解题思路：按照题目的提示来，建立有向图，判断图中是否存在循环或者全部遍历完。做法还是和之前课程表的做法一样，利用 set 记录已经学习的课程。利用 map 记录每个课程的全部前置课程， 其实 map 记录的就是有向图的边。
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
set<int> started;
for(int i = 0; i < numCourses; ++i) started.insert(i);
if(prerequisites.size() == 0) return vector<int>(started.begin(), started.end());
map<int, set<int>> miv;
for(auto s : prerequisites) {
int temp = s[0];
int preTemp = s[1];
started.erase(temp);
auto it = miv.find(temp);
if(it == miv.end()) {
set<int> vi = {preTemp};
miv[temp] = vi;
}else {
miv[temp].insert(preTemp);
}
}
vector<int> res;
// 说明每个课程都有前置，那么肯定不能实现
if(numCourses == miv.size()) return res;
res = vecotr<int>(started.begin(), started.end());
while(res.size() < numCourses) {
int pre = res.size();
set<int> newadd;
for(auto it = miv.begin(); it != miv.end();) {
for(auto s = it->second.begin(); s != it->second.end();) {
if(started.find(*s) != started.end()) {
s = it->second.erase(s);
}else {
++s;
}
}
if(it->second.empty()) {
newadd.insert(it->first);
res.emplace_back(it->first);
it = miv.erase(it);
}else {
++it;
}
}
if(pre == res.size()) break;
started = newadd;
}
if(res.size() != numCourses) res.clear();
return res;
}
};
