Leetcode 401-500
406. Queue Reconstruction by Height (Medium)¶
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
思路
一开始对vector排序，然后再依次插入，这里有个技巧是从大到小插入，这样每次交换到pair.second地方即可
对上述例子，先排序成为
[7, 0] [7, 1] [6, 1] [5, 0] [5, 2] [4, 4]
然后result为空的vector，按顺序访问，每次将p插入到p.second位置上，原来这个位置及之后元素后移一位
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
sort(people.begin(), people.end(), [](const pair<int, int>& a, const pair<int, int>& b)
bool { return (a.first > b.first) || (a.first == b.first && a.second < b.second);});
vector<pair<int, int> > result;
for (auto p : people) {
result.push_back(p);
for (int i = result.size() - 1; i > p.second; i --) swap(result[i], result[i-1]);
}
return result;
}
416. Partition Equal Subset Sum (Medium)¶
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Note:
- Each of the array element will not exceed 100.
- The array size will not exceed 200.
思路一 DP
dp[i][j] 表示nums前i位能否组合成j
过程中看dp[k][sum/2]是否为true即可，时间为40ms(84.89%)
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int num : nums) sum += num;
if (sum % 2) return false;
int n = nums.size();
bool **dp = new bool* [n];
for (int i = 0; i < n; i ++) dp[i] = new bool[sum/2+1]();
for (int i = 0; i < n; i ++) {
if (nums[i] <= sum/2) dp[i][nums[i]] = 1;
if (i == 0) continue;
for (int j = 1; j <= sum/2; j ++) {
if (dp[i-1][j]) {
dp[i][j] = 1;
if (j + nums[i] <= sum/2) dp[i][j+nums[i]] = 1;
}
}
if (dp[i][sum/2]) return true;
}
return false;
}
思路二 bitmap
因为sum/2不超过10000，因此可以用bitmap来做，每次将bits左移n位再与上原来的bitset，时间为 8ms(100%)
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 != 0) { return false; }
bitset<10001> bits(1);
sum = sum >> 1;
for (auto n : nums) {
bits |= bits << n;
if (bits[sum]) {
return true;
}
}
return false;
}
437. Path Sum III (Easy)¶
You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 Return 3. The paths that sum to 8 are: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11
思路
这里每个点都可以选和不选，如果以此递归总次数为2^N，不可取
因此声明两个函数，一个是确定选，一个是不选，来进行迭代，一共是2N次迭代
int pathSum(TreeNode* root, int sum) {
if(root == NULL) return 0;
return helper(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
}
int helper(TreeNode* root, int sum) {
if(root == NULL) return 0;
int count = 0;
if(root->val == sum) count++;
count += helper(root->left, sum - root->val);
count += helper(root->right, sum - root->val);
return count;
}
438. Find All Anagrams in a String (Easy)¶
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Input: s: "cbaebabacd" p: "abc" Output: [0, 6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
思路
统计字母出现次数即可，这里写法上比较巧妙的是用left和right双指针，同时用unmatch记录p中出现但s中没有出现的char个数，每次如果减1后不为负，unmatch减一，同样，加一后为正，则unmatch加1
vector<int> findAnagrams(string s, string p) {
vector<int> result;
if (s.size() == 0 || p.size() == 0 || p.size() > s.size()) return result;
int *letters = new int[26]();
for (char c : p) letters[c - 'a'] ++;
int unmatch = p.size();
for (int left = 0, right = 0; right < s.size();) {
letters[s[right ++] - 'a'] --;
if (letters[s[right-1] - 'a'] >= 0) unmatch --;
if (unmatch == 0) result.push_back(left);
if (right - left == p.size()) {
letters[s[left ++] - 'a'] ++;
if (letters[s[left-1] - 'a'] > 0) unmatch ++;
}
}
return result;
}
445. Add Two Numbers II (Medium)¶
两个非空链表，求相加所得链表
要求不翻转链表Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7
思路
用栈来存储两个串，并用栈来存储最后结果
s1: |7 2 4 3
s2: |5 6 4
result: |7087
最后将result转为链表即可
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1, s2, r;
for (ListNode* head = l1; head != nullptr; head = head->next)
s1.push(head->val);
for (ListNode* head = l2; head != nullptr; head = head->next)
s2.push(head->val);
int addition = 0;
while (!s1.empty() || !s2.empty()) {
int n1 = s1.empty() ? 0 : s1.top();
int n2 = s2.empty() ? 0 : s2.top();
int a = n1 + n2 + addition;
r.push(a % 10);
addition = a / 10;
if (!s1.empty()) s1.pop();
if (!s2.empty()) s2.pop();
}
if (addition > 0) r.push(addition);
ListNode *head = nullptr, *prev = nullptr;
while (!r.empty()) {
ListNode* node = new ListNode(r.top());
if (prev != nullptr) prev->next = node;
else head = node;
prev = node;
r.pop();
}
return head;
}
448. Find All Numbers Disappeared in an Array (Easy)¶
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Input: [4,3,2,7,8,2,3,1] Output: [5,6]
思路
直接在参数nums上进行修改，从左端开始，将nums[i]换到nums[nums[i]-1]上，因为只要换到之后就不会再被换出，因此扫描一遍即可
vector<int> findDisappearedNumbers(vector<int>& nums) {
for (int i = 0; i < nums.size();)
if (nums[i] == i+1 || nums[nums[i]-1] == nums[i]) i ++;
else swap(nums[i], nums[nums[i]-1]);
vector<int> result;
for (int i = 0; i < nums.size(); i ++)
if (nums[i] != i + 1) result.push_back(i+1);
return result;
}
450. Delete Node in a BST (Medium)¶
给一棵BST，删除其中指定值节点，返回这棵BST
递归
如果root就是要删的节点，直接返回nullptr，否则递归来删除左子树或右子树
删除时分三种情况
- 左右孩子都不存在，置为nullptr即可
- 左右孩子只存在一个，返回另一个
- 都存在，置为右边最左孩子的值，然后递归删除这个最左孩子
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return nullptr;
if (root->val > key) root->left = deleteNode(root->left, key);
else if (root->val < key) root->right = deleteNode(root->right, key);
else {
if (root->left == nullptr && root->right == nullptr) return nullptr;
else if (root->right == nullptr || root->left == nullptr)
return root->right == nullptr ? root->left : root->right;
else {
TreeNode* node = root->right;
while (node->left != nullptr) node = node->left;
root->val = node->val;
root->right = deleteNode(root->right, node->val);
}
}
return root;
}
非递归
首先找到key对应的节点，并且保存它的祖先节点parent
然后对node进行替换，还是分三种情况
- 左右孩子都没有，用nullptr替换
- 左右孩子其中一个没有，用另一个来替换
- 都有，这里用右边最左的孩子来替换，这里又分两种情况
- 右孩子没有左孩子，那么就等于把右边向上提一下
- 右孩子有左孩子，这里把这个左孩子父亲节点的左孩子改为左孩子的右孩子
最后对parent的孩子进行修改
TreeNode* deleteNode(TreeNode* root, int key) {
TreeNode* parent = nullptr, *node = root;
while (node != nullptr && node->val != key) {
parent = node;
if (node->val < key) node = node->right;
else node = node->left;
}
if (node == nullptr) return root;
TreeNode* replace = nullptr;
if (node->left == nullptr && node->right == nullptr) replace = nullptr;
else if (node->left == nullptr || node->right == nullptr)
replace = node->left == nullptr ? node->right : node->left;
else {
TreeNode *pre = nullptr, *cur = node->right;
while (cur->left != nullptr) {
pre = cur;
cur = cur->left;
}
node->val = cur->val;
if (pre != nullptr) pre->left = cur->right;
else node->right = cur->right;
delete cur;
replace = node;
}
if (parent == nullptr) return replace;
else {
if (parent->left == node) parent->left = replace;
else parent->right = replace;
return root;
}
}
461. Hamming Distance (Easy)¶
给0\leq x,y < 2^{31}，求x和y的汉明距离，即两者不一样的1个数
思路
循环31次异或即可
int hammingDistance(int x, int y) {
int distance = 0;
for (int i = 0; i < 31; i ++) distance += (((x >> i) & 1) ^ ((y >> i) & 1));
return distance;
}
494. Target Sum (Medium)¶
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3.
- The length of the given array is positive and will not exceed 20.
- The sum of elements in the given array will not exceed 1000.
- Your output answer is guaranteed to be fitted in a 32-bit integer.
思路一
还是动归思想，但这里必须每个数都用到，所以每次更新一次map
int findTargetSumWays(vector<int>& nums, int S) {
unordered_map <int, int> map;
map[0] = 1;
for (int num : nums) {
unordered_map<int, int> t;
for (auto p : map) {
t[p.first + num] += p.second;
t[p.first - num] += p.second;
}
map = t;
}
return (map.count(S)) ? map[S] : 0;
}
思路二
sum减去target，即变成部分数字加起来达到这个值即可的问题，加上题中sum范围有限，所以生命sum长度的dp，dp[i]表示和为i的方案数
int findTargetSumWays(vector<int>& nums, int S) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum < S || (sum-S)%2 == 1) return 0;
sum = (sum - S) / 2;
vector<int> dp(sum+1,0);
dp[0] = 1;
for(auto it : nums)
for(int i = sum; i >= it; i --)
dp[i] += dp[i-it];
return dp[sum];
}