位运算
异或：^
- 任何数与0异或都是其本身
- 任何数与其本身进行异或都是0
利用以上几点小技巧可以实现x ^ 0 = xx ^ 1s = ~x (1s = ~0) #全1x ^ ~x = 1sx ^ x = 0c = a ^ b => a = c ^ b => b = a ^ c
LeetCode_136：只出现一次的值
class Solution():def findsingle(self, nums):temp = 0for i in nums:temp ^= ireturn temp
LeetCode_260：有两个只出现一次的值
这个相比于例子a多了另外一个只出现了一次的数,那么如果所有数进行异或处理,最终的结果将会是a ^ b
我们的目标是实现分组异或,将a,b分到两个不同的组进行异或,同时将其余相同的数随机分到一组,这样两个分别进行异或,就可以得到a和b
当a^b只有在a和b某个位的值不一样时才会得到1的结果,而相同的数每一位都是相同,因此可以再次遍历所有数,通过计算这个位的值是否相同,从而随机分组,且可以确保a和b会被分到两个不同的组def findsingle2(self, nums): temp = 0 for i in nums: temp ^= i temp2 = 1 while temp & temp2 == 0: temp2 <<= 1 # temp2最终的结构是a和b首个不相同的位 a, b = 0, 0 for i in nums: if i & temp2 == 0: # temp2的结果可能是00001000 因此与出来的结果要么是0要么不是0 a ^= i else: b ^= i return [a, b]LeetCode_137：一个数出现1次，其余数出现3次
对于这种题目,实现的思路是:
按照顺序判断
1)如果一个数第一次出现,那么存在容器one里面
2)如果一个数第二次出现,那么先从one里面删除,然后添加在容器two
3)如果一个数第三次出现,那么从容器two里面删除
这样遍历结果是,出现3次的数都不见了,而one里面保存了出现了一次的数 ```python class Solution: def singleNumber(self, nums: List[int]) -> int:ones, twos = 0, 0 for num in nums: ones = (ones ^ num) & ~twos twos = (twos ^ num) & ~ones return ones
初始时ones, twos都是0 ones^num 的结果为 num ~twos 的结果是对twos的值进行取反 如果two里面有值,且含有num的话,则相当于 num & ~num 其结果等于0 因此,第一次遍历时: (ones^num) & ~twos = num (twos ^ num) & ~ones = 0
第二次遍历时: (ones^num) & ~twos = 0, 因为one = num, num ^ num = 0 (twos ^ num) & ~ones = num
第三次遍历时 (ones^num) & ~twos = 0, (twos ^ num) & ~ones = 0
扩展到2N+1的情况: 如5次: ones, twos, threes, fours = 0, 0, 0, 0 for num in nums: ones = (ones ^ num) & ~twos & ~threes & ~fours twos = (twos ^ num) & ~ones & ~threes & ~fours threes = (threess ^ num) & ~ones & ~twos & ~fours fours = (fours ^ num) & ~ones & ~twos & ~threes return ones
<a name="mcs9W"></a>
### 与或非（& | ~)
```python
1. 将x最右边的n位清零: x & (~0 << n)
2. 获取x的第n位值(0或者1): (x >> n) & 1
3. 获取x的第n位的幂值: x & (1 << (n-1))
4. 仅将第n位设置为1: x | (1 << n)
5. 仅将第n位设置为0: x & (~(1 << n))
6. 将x最高位至第n位(含)清零: x & ((1 << n) - 1)
7. 将第n位至第0位(含)清零: x & (~((1 << (n + 1)) - 1))
8. 判断奇偶: x & 1 == 1 or x & 1 == 0
9. 除以2: x >> 1 ==> x // 2
10. 清零最低位的1: x & (x-1)
11. 得到最低位的1: x & -x
12. x & ~x = 0
栈的应用
关联性数据
一般用来计算那些前后有关联性,需要根据现在的值,再去联合上一个值进行判断的,可用栈进行解决
LeetCode_20：有效括号
class Solution:
def isValid(self, s: str) -> bool:
mystack = []
for i in s:
if i == '{':
mystack.append('}')
elif i == '(':
mystack.append(')')
elif i == '[':
mystack.append(']')
elif not mystack:
return False
elif i != mystack.pop():
return False
if not mystack:
return True
return False
单调栈
LeetCode_42：接雨水
class Solution:
def trap(self, height: List[int]) -> int:
stack = []
result = 0
for i in range(len(height)):
while stack != [] and height[i] > height[stack[-1]]: # 形成单调栈最重要的步骤
mid_height = height[stack[-1]]
stack.pop()
if not stack: break # 如果栈已经是空的,退出,因为不可能接雨水
l = height[stack[-1]]
r = height[i]
result += (min(l, r) - mid_height) * (i - stack[-1] - 1)
stack.append(i)
return result
class Solution {
public:
int trap(vector<int>& height) {
stack<int> myStack;
int res = 0;
for (int i = 0; i < height.size(); ++i)
{
while (!myStack.empty() && height[myStack.top()] < height[i])
{
int preHeight = height[myStack.top()];
while (!myStack.empty() && height[myStack.top()] == preHeight) myStack.pop();
if (myStack.empty()) break;
int left = myStack.top();
int leftHight = height[left];
res += (min(height[i], leftHight) - preHeight) * (i - left - 1);
}
myStack.push(i);
}
return res;
}
};
数组的应用
数组下标
数据根据下标与值对应替换，实现O(n)复杂度的寻找重复值，如:
[3, 2, 1, 4, 0, 8]
数组翻转
对于数组以k为分界线进行翻转时,可采用分段翻转,然后再整合翻转的方式
LeetCode_189：旋转数组
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k %= n
def swap(start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
swap(0, n - k - 1)
swap(n - k, n - 1)
swap(0, n - 1)
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %= nums.size();
swapNums(nums, 0, nums.size()-k-1);
swapNums(nums, nums.size()-k, nums.size()-1);
swapNums(nums, 0, nums.size()-1);
}
void swapNums(vector<int>& nums, int left, int right)
{
while (left < right)
{
swap(nums[left], nums[right]);
left++;
right--;
}
}
};
双指针
双指针一般应用的形式可以有:
- 快慢指针,用来判断链表是否有环,也可以以快指针 = 2倍慢指针的方式,用来计算获取链表的中间值
- 间隔k的指针,用来获取链表的后k的值
- 根据条件移动的指针,这类指针一般用来实现某些条件替换,指针A指向条件1, 指针B指向条件2。可用于dp的状态压缩
LeetCode_283：移动零
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
point = -1 # 指向数组最左边的零
for i in range(len(nums)):
if nums[i] != 0 and point != -1:
nums[i], nums[point] = nums[point], nums[i]
point += 1
elif nums[i] == 0 and point == -1:
point = i
else:
continue
hash表
hash存入的时间可以认为是O(1),读取时间也为O(1)，可进行加速
一般的用法是先遍历一遍数据存入dict中,然后再根据条件读取dict
LeetCode_49：异位词统计
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
count_dict = {}
for i in strs:
sort_i = tuple(sorted(i)) # 注意这里测试发现使用tuple转换的效率高于使用str
old_list = count_dict.get(sort_i, [])
old_list.append(i)
count_dict[sort_i] = old_list
return list(count_dict.values()) # 注意这里要用list()进行转换
也可以使用defaultdict()
import collections
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
count_dict = collections.defaultdict(list) # defaultdict() 可以填入的参数有tuple,dict,list等,规定当取不到值时的返回值类型
for i in strs:
count_dict[tuple(sorted(i))].append(i)
return list(count_dict.values())
链表
链表的一些技巧是把某些逻辑抽成一个独立的函数处理，这样避免考虑太多参数而增加了代码编写难度
通常定义一个dummy节点可以少处理很多边界问题
链表翻转
LeetCode_92：反转链表II
/**
* 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* reverseBetween(ListNode* head, int left, int right) {
if (left == right) return head;
ListNode* dummy = new ListNode();
ListNode* first = dummy;
int i = 0;
while (i < left-1)
{
first->next = head; // first停在left之前的位置，有可能是nullptr
first = first->next;
head = head->next; // 最终head停在left指向的位置
i++;
}
head = reverse(head, right-left);
first->next = head;
return dummy->next;
}
ListNode* reverse(ListNode* head, int num)
{
ListNode* pre_node = nullptr;
ListNode* last_node = head;
int i = 0;
while (i < num+1)
{
ListNode* temp = head->next;
head->next = pre_node;
pre_node = head;
head = temp;
i++;
}
// 循环之后，head停在了原right的下一个
// pre_node 是原right节点
last_node->next = head;
return pre_node;
}
};
LeetCode_25：k个一组翻转链表
/**
* 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* reverseKGroup(ListNode* head, int k) {
if (k == 1) return head;
ListNode* dummy = new ListNode(0, head);
ListNode* pre = dummy;
int count = 0;
while (head != nullptr)
{
count++;
if (count % k == 0)
{
// 此时pre指向的是需要翻转的链表节点的前一个，head指向的是需要翻转链表节点的最后一个
ListNode* head_next = head->next;
ListNode* pre_next = pre->next;
pre->next = doReverse(pre->next, head);
pre = pre_next;
head = head_next;
}
else
{
head = head->next;
}
}
return dummy->next;
}
ListNode* doReverse(ListNode* first, ListNode* end)
{
ListNode* pre = nullptr;
ListNode* last_node = first;
while (true)
{
ListNode* first_next = first->next;
first->next = pre;
pre = first;
first = first_next;
if (pre == end) break;
}
last_node->next = first;
return pre;
}
};
有环链表
- 判断是否有环，使用快慢指针，如果有环则
-
LeetCode_142：环形链表II
```cpp /**
- Definition for singly-linked list.
- struct ListNode {
- int val;
- ListNode *next;
- ListNode(int x) : val(x), next(NULL) {}
}; / class Solution { public: ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode* fast = head; while (fast != NULL) {
slow = slow->next; fast = fast->next; if (fast == NULL) return NULL; fast = fast->next; if (slow == fast) break;}
if (fast == NULL) return NULL;
ListNode* start = head; while (start != slow) {
start = start->next; slow = slow->next;}
return start; } };
/*
假设整条链由: 非循环段: a 循环b段: b (slow 和 fast 相遇的点) 循环c段:c 当slow和fast相遇时,他们的路程关系有: 2(a+b) = a + n(b+c) + b 可得出: a = (n-1)*(b+c) + c
所以当在b点相遇后,重新定义一个third指针,从最开始出发与slow相同的步长,当third指针走了a距离,则slow走了(n-1)*(b+c) + c的距离,此时两个节点刚好相遇
*/
<a name="PAhlV"></a>
## n数之和
<a name="noLe3"></a>
### 两数之和
直接使用map结构形成值与下标的映射即可
<a name="AW1j4"></a>
### 三数之和
<a name="ZX0eo"></a>
#### LeetCode_15：三数之和
```cpp
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 先进行排序
vector<vector<int>> res;
for (int i = 0; i < nums.size(); ++i)
{
if (i > 0 && nums[i] == nums[i-1]) continue; // 重复值
int left = i+1, right = nums.size()-1;
while (left < right)
{
while (left < right && left > i+1 && nums[left] == nums[left-1]) left++; // 重复值
while (left < right && right < nums.size()-1 && nums[right] == nums[right+1]) right--; // 重复值
if (left >= right) break; // 不满足条件则跳出
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0)
{
res.push_back({nums[i], nums[left], nums[right]});
right--;
}
else if (sum > 0)
{
right--;
}
else
{
left++;
}
}
}
return res;
}
};
双端队列
双向队列的用处和栈类似,应用于那些需要处理前N个数据的算法场景
LeetCode_239：滑动窗口的最大值
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> myQue;
int index = 0;
int n = nums.size();
vector<int> res;
while (index < n)
{
if (!myQue.empty() && index >= myQue.front() + k)
{
myQue.pop_front();
}
while (!myQue.empty() && nums[index] >= nums[myQue.back()])
{
myQue.pop_back();
}
myQue.push_back(index);
if (index >= k - 1)
{
res.emplace_back(nums[myQue.front()]);
}
index++;
}
return res;
}
};
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
dq = deque()
result_list = []
for i in range(len(nums)):
if dq and dq[0] == i - k:
dq.popleft()
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
if i >= k-1:
result_list.append(nums[dq[0]])
return result_list
深度优先和广度优先
深度优先遍历（dfs）
LeetCode_剑指offer_12：单词搜索
class Solution {
public:
vector<vector<int>> posList{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool exist(vector<vector<char>>& board, string word) {
for (int i = 0; i < board.size(); ++i)
{
for (int j = 0; j < board[0].size(); ++j)
{
if (board[i][j] == word[0])
{
char temp = board[i][j];
board[i][j] = '.';
if (dfs(board, word, i, j, 1)) return true;
board[i][j] = temp;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& board, string& word, int x, int y, int len)
{
if (len == word.size()) return true;
for (auto& pos : posList)
{
int new_x = x + pos[0];
int new_y = y + pos[1];
if (new_x < 0 || new_x >= board.size() || new_y < 0 || new_y >= board[0].size() || !isalpha(board[new_x][new_y]) || board[new_x][new_y] != word[len]) continue;
char temp = board[new_x][new_y];
board[new_x][new_y] = '.';
if (dfs(board, word, new_x, new_y, len+1)) return true;
board[new_x][new_y] = temp;
}
return false;
}
};
LeetCode_200：岛屿数量
class Solution {
public:
vector<vector<int>> posList{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); ++i)
{
for (int j = 0; j < grid[0].size(); ++j)
{
if (grid[i][j] == '1')
{
backtrace(grid, i, j);
count++;
}
}
}
return count;
}
void backtrace(vector<vector<char>>& grid, int x, int y)
{
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] != '1') return;
grid[x][y] = '0';
for (auto& pos: posList)
{
backtrace(grid, x+pos[0], y+pos[1]);
}
}
};
广度优先算法（bfs）
LeetCode_127：单词接龙
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (wordSet.find(endWord) == wordSet.end()) return 0;
unordered_set<string> beginSet{beginWord};
unordered_set<string> endSet{endWord};
unordered_set<string> filterSet{beginWord, endWord};
//vector<string> beginVec{beginWord}; // 使用vec要使用std::find方法，时间复杂度是O(n)，因为本身没有顺序所以只能一个一个遍历，而map/set是有序的，因此有内置版本的find，时间复杂度是O(logn) / O(1)，O(1)是unordered_map/set
//vector<string> endVec{endWord};
int count = 0;
while (!beginSet.empty() && !endSet.empty())
{
if (beginSet.size() > endSet.size()) swap(beginSet, endSet);
unordered_set<string> tempSet;
count++;
for (auto word: beginSet)
{
for (int i = 0; i < word.size(); ++i)
{
char tmepWord = word[i];
for (char j = 'a'; j <= 'z'; j++)
{
word[i] = j;
if (endSet.find(word) != endSet.end()) return count+1;
if (wordSet.find(word) == wordSet.end() || filterSet.find(word) != filterSet.end()) continue;
tempSet.insert(word);
filterSet.insert(word);
}
word[i] = tmepWord;
}
}
beginSet = tempSet;
}
return 0;
}
};
N叉树
N叉树的构造一般是：
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
LeetCode_429：N叉树的层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
if (root == NULL) return {};
vector<vector<int>> res;
queue<Node*> myQue;
myQue.push(root);
while (!myQue.empty())
{
int n = myQue.size();
vector<int> temp;
for (int i = 0; i < n; ++i)
{
Node* root = myQue.front();
myQue.pop();
temp.push_back(root->val);
if (!root->children.empty())
{
for (auto& child : root->children)
{
myQue.push(child);
}
}
}
res.push_back(temp);
}
return res;
}
};
LeetCode_589：N叉树的前序遍历
// 递归解法
class Solution {
public:
vector<int> res;
vector<int> preorder(Node* root) {
if (root == NULL) return res;
res.push_back(root->val);
for (auto& child: root->children)
{
preorder(child);
}
return res;
}
};
// 非递归解法
class Solution {
public:
vector<int> preorder(Node* root) {
if (root == NULL) return {};
vector<int> res;
stack<Node*> myStack;
myStack.push(root);
while (!myStack.empty())
{
root = myStack.top();
myStack.pop();
res.push_back(root->val);
for (int i = root->children.size()-1; i >= 0; --i)
{
myStack.push(root->children[i]);
}
}
return res;
}
};
LeetCode_590：N叉树的后序遍历
// 递归解法
class Solution {
public:
vector<int> res;
vector<int> postorder(Node* root) {
if (root == NULL) return {};
for (auto& child: root->children)
{
postorder(child);
}
res.push_back(root->val);
return res;
}
};
// 非递归解法
class Solution {
public:
vector<int> postorder(Node* root) {
if (root == NULL) return {};
vector<int> res;
stack<Node*> myStack;
myStack.push(root);
while (!myStack.empty())
{
root = myStack.top();
myStack.pop();
for (int i = 0; i < root->children.size(); ++i)
{
myStack.push(root->children[i]);
}
res.push_back(root->val);
}
return vector(res.rbegin(), res.rend()); // 这里进行翻转
}
};
快速幂
LeetCode_剑指offer_16：数值的整数次方
class Solution {
public:
double myPow(double x, int n) {
long b = n; // 注意这里会越界，需要转换成long处理
if (b == 0) return 1;
if (b < 0)
{
x = 1/x;
b = -b;
}
double res = 1;
while (b != 0)
{
if (b & 1 == 1) // 奇数
{
res *= x;
b -= 1;
}
else
{
x *= x;
b /= 2;
}
}
return res; // 最后不需要再res*x，因为最后n为0时，必定执行了res*=x;
}
};
二叉搜索树
特点:左子树的所有值均小于根节点,右子树的所有值均大于根节点
利用此特性有个非常巧妙的方法是:当中序遍历该二叉搜索树时,会得到一个升序的结果
LeetCode_98：验证二叉搜索树
class Solution {
public:
bool isValidBST(TreeNode* root) {
// 中序遍历
stack<TreeNode*> myStack;
vector<int> res;
while (!myStack.empty() || root != nullptr)
{
while (root != nullptr)
{
myStack.push(root);
root = root->left;
}
root = myStack.top();
myStack.pop();
res.push_back(root->val);
root = root->right;
}
for (int i = 1; i < res.size(); ++i)
{
if (res[i] <= res[i-1]) return false;
}
return true;
}
};
class Solution {
public:
bool isValidBST(TreeNode* root) {
return helper(root->left, root->val, -pow(2, 31)-1) && helper(root->right, pow(2,31), root->val);
}
bool helper(TreeNode* root, double maxNum, double minNum)
{
if (root == nullptr) return true;
if (root->val > minNum && root->val < maxNum)
{
return helper(root->left, root->val, minNum) && helper(root->right, maxNum, root->val);
}
return false;
}
};
回溯算法
所谓的回溯算法就是递归的过程中根据某些条件打断递归,并将状态回滚到上一个递归状态
组合
LeetCode_77：组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combine(int n, int k) {
vector<int> path;
backtrace(0, n, k, path);
return res;
}
void backtrace(int index, int n, int k, vector<int> path)
{
if (path.size() == k)
{
res.push_back(path);
return;
}
for (int i = index; i < n; ++i)
{
path.push_back(i+1);
backtrace(i+1, n, k, path);
path.pop_back();
}
}
};
LeetCode_39：组合总和
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int> path;
backtrace(candidates, 0, target, path);
return res;
}
void backtrace(vector<int>& candidates, int index, int target, vector<int>& path)
{
// if (target == 0)
// {
// res.push_back(path);
// return;
// }
for (int i = index; i < candidates.size(); ++i)
{
target -= candidates[i];
if (target < 0) break; // 因为是排序后的，如果前面已经超过了target，则退出
if (target == 0) // 改为这种方式后，减少了不必要的函数调用，用时0ms
{
path.push_back(candidates[i]);
res.push_back(path);
target += candidates[i];
path.pop_back();
break;
}
path.push_back(candidates[i]);
backtrace(candidates, i, target, path);
target += candidates[i];
path.pop_back();
}
}
};
LeetCode_40：组合总和II
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<int> path;
backtrace(candidates, 0, target, path);
return res;
}
void backtrace(vector<int>& candidates, int index, int target, vector<int>& path)
{
for (int i = index; i < candidates.size(); ++i)
{
if (i > index && candidates[i] == candidates[i-1]) continue; // 处理重复值的技巧
target -= candidates[i];
if (target < 0) break;
if (target == 0)
{
path.push_back(candidates[i]);
res.push_back(path);
path.pop_back();
break;
}
path.push_back(candidates[i]);
backtrace(candidates, i+1, target, path);
target += candidates[i];
path.pop_back();
}
}
};
排列
LeetCode_46：全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
全排序和组合类问题的区别在于组合类型的问题寻找新组合时只能是向后遍历,而全排序则需要考虑前后的数据
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permute(vector<int>& nums) {
vector<int> path;
backtrace(nums, path);
return res;
}
void backtrace(vector<int>& nums, vector<int>& path)
{
if (nums.empty())
{
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
int num = nums[i];
path.push_back(num);
nums.erase(nums.begin() + i);
backtrace(nums, path);
nums.insert(nums.begin() + i, num);
path.pop_back();
}
}
};
LeetCode_47：全排列II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
对于含有重复数字然后要返回不重复排列数据的,需要首先对序列进行排序
当从上一个递归中回溯时,判断下一个数是否已经与上一个遍历到的同层数相同,如果相同,则忽略
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int> path;
backtrace(nums, path);
return res;
}
void backtrace(vector<int>& nums, vector<int>& path)
{
if (nums.empty())
{
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); ++i)
{
if (i > 0 && nums[i] == nums[i-1]) continue; // 处理重复值的技巧
int num = nums[i];
nums.erase(nums.begin()+i);
path.push_back(num);
backtrace(nums, path);
nums.insert(nums.begin()+i, num);
path.pop_back();
}
}
};
子集
LeetCode_78：子集
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> path;
backtrace(nums, path, 0);
return res;
}
void backtrace(vector<int>& nums, vector<int>& path, int index)
{
res.push_back(path);
for (int i = index; i < nums.size(); ++i)
{
path.push_back(nums[i]);
backtrace(nums, path, i+1);
path.pop_back();
}
}
};
LeetCode_90：子集II
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 涉及到重复，需要先进行排序
vector<int> path;
backtrace(nums, path, 0);
return res;
}
void backtrace(vector<int>& nums, vector<int>& path, int index)
{
res.push_back(path);
for (int i = index; i < nums.size(); ++i)
{
if (i > index && nums[i] == nums[i-1]) continue;
path.push_back(nums[i]);
backtrace(nums, path, i+1);
path.pop_back();
}
}
};
字母
凡是限定26个字母的，可以考虑使用int类型表示，如a对应1位，b对应2位，z对应26位等
贪心算法
贪心算法的精髓是尽可能的满足,因此很多情况下先对数组进行升序排列从而解决问题
LeetCode_55：跳跃游戏
class Solution {
public:
bool canJump(vector<int>& nums) {
int maxIndex = nums[0];
for (int i = 1; i < nums.size(); ++i)
{
if (i <= maxIndex)
{
maxIndex = max(i + nums[i], maxIndex); // range记录的是当前最大下标索引
}
else
{
return false;
}
}
return true;
}
};
动态规划
LeetCode_322：零钱兑换
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// 根据题目要求组成的最少个数，因此我们先假定dp[i]表示组成i的最少个数
// 那么根据题意，如果i>=coin，那么就可以使用这个硬币，此时dp[i] = dp[i-coin] + 1
// 又因为我们目标是取最小值，而且硬币有多种情况，因此初始化时dp的值要为某个大值，最开始我设定的是INT_MAX，但是运行报错了，因为需要计算dp[i-coiin]+1，有可能造成溢出，因此修改为amount+1；而dp[i] = min(dp[i], dp[i-coin]+1)：这个意思就是 min(不用这个硬币，用这个硬币) 两种情况的取最小。
// 因为 i-coin < i，因此i需要从小到大增长
if (amount <= 0) return 0;
int MAX = amount+1;
vector<int> dp(amount+1, MAX);
dp[0] = 0;
for (int i = 1; i < amount+1; ++i)
{
for (auto& coin: coins)
{
if (i >= coin)
{
dp[i] = min(dp[i], dp[i-coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
};
LeetCode_55：跳跃游戏
class Solution {
public:
bool canJump(vector<int>& nums) {
// 最开始设想dp[i]代表能够达到，但是无法有效的得出dp公式，只能放弃
// 假设dp[i]代表当前能够到达的最长距离
vector<int> dp(nums.size());
dp[0] = nums[0];
for (int i = 1; i < nums.size(); ++i)
{
if (dp[i-1] < i) return false;
dp[i] = max(dp[i-1], i + nums[i]);
}
return true;
}
};
LeetCode_45：跳跃游戏II
class Solution {
public:
int jump(vector<int>& nums) {
int end = 0;
int step = 0;
int maxIndex = 0;
for (int i = 0; i < nums.size()-1; ++i) // 最后一个不用判断，否则会多算一步
{
maxIndex = max(i + nums[i], maxIndex);
if (i == end)
{
end = maxIndex;
step++;
}
}
return step;
}
};
若有收获，就点个赞吧
0 人点赞
