Closed jasperzhong closed 3 years ago
jasperzhong
commented
3 years ago https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
看了题解才知道要用partition. https://en.cppreference.com/w/cpp/algorithm/partition partition函数的作用就是: if条件为真就把这个ele放到前面.
cxx两行搞定
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
std::partition(nums.begin(), nums.end(), [](int n){return n & 1;});
return nums;
}
};https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
快慢指针. 快的先走k步.
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* fast, *slow;
fast = slow = head;
while (fast && k--) {
fast = fast->next;
}
while (fast) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
};https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
三个指针.
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *prev, *cur, *next;
prev = nullptr;
cur = head;
while (cur) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
加一个函数用来判断是否是B是A子结构，然后遍历A即可.
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (!A || !B) return false;
return dfs(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
bool dfs(TreeNode* A, TreeNode* B) {
if (!B) return true;
if (!A) return false;
return A->val == B->val && dfs(A->left, B->left) && dfs(A->right, B->right);
}
};https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if (root) {
root->left = mirrorTree(root->left);
root->right = mirrorTree(root->right);
std::swap(root->left, root->right);
}
return root;
}
};https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
和26差不多.
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (root) {
return compare(root->left, root->right);
}
return true;
}
bool compare(TreeNode* left, TreeNode* right) {
if (!left && !right) return true;
if (!left || !right) return false;
return left->val == right->val && compare(left->right, right->left) && compare(left->left, right->right);
}
};https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
很经典的题了...
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int r = matrix.size();
if (r == 0) return {};
int c = matrix[0].size();
int i = 0, j = 0, cnt = 0;
int up = 0, down = r - 1, left = 0, right = c - 1;
std::vector<int> ans;
while (cnt < r * c - 1) {
while (j < right && cnt < r * c - 1) {
ans.push_back(matrix[i][j]);
j++; cnt++;
}
up++;
while (i < down && cnt < r * c - 1) {
ans.push_back(matrix[i][j]);
i++; cnt++;
}
right--;
while (j > left && cnt < r * c - 1) {
ans.push_back(matrix[i][j]);
j--; cnt++;
}
down--;
while (i > up && cnt < r * c - 1) {
ans.push_back(matrix[i][j]);
i--; cnt++;
}
left++;
}
ans.push_back(matrix[i][j]);
return ans;
}
};https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
多用个栈专门存min
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
int cur_min;
if (!_min.empty()) {
cur_min = _min.top();
if (x < cur_min) cur_min = x;
} else {
cur_min = x;
}
_s.push(x);
_min.push(cur_min);
}
void pop() {
_s.pop();
_min.pop();
}
int top() {
return _s.top();
}
int min() {
return _min.top();
}
private:
std::stack<int> _s, _min;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/submissions/
辅助栈
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
std::stack<int> s;
int n = pushed.size();
int i = 0, j = 0;
while (i < n || j < n) {
if (s.empty()) {
s.push(pushed[i]);
i++;
} else if (s.top() == popped[j]){
s.pop();
j++;
} else {
if (i < n) {
s.push(pushed[i]);
i++;
} else {
break; // nothing to do
}
}
}
return s.empty();
}
};https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
分治. 只有0/1/2个节点的时候停止.
class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
return divide(postorder, 0, postorder.size());
}
bool divide(vector<int>& nums, int lo, int hi) {
if (lo == hi - 1 || lo == hi || lo == hi - 2) return true;
int root = nums[hi-1];
int mid = lo;
while (mid < hi && nums[mid] < root) mid++;
// check
int idx = mid;
while (idx < hi && nums[idx] > root) idx++;
if (idx != hi - 1) return false;
return divide(nums, lo, mid) && divide(nums, mid, hi-1);
}
};https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
dfs. 注意是路径，得搜到根节点.
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int target) {
vector<vector<int>> ans;
vector<int> nums;
if (root)
dfs(root, target, 0, nums, ans);
return ans;
}
void dfs(TreeNode* root, int target, int cur_sum, vector<int>& nums, vector<vector<int>>& vector_list) {
cur_sum += root->val;
// on leaf node
if (!root->left && !root->right) {
if (target == cur_sum) {
nums.push_back(root->val);
vector_list.push_back(nums);
nums.pop_back();
return;
}
}
nums.push_back(root->val);
if (root->left)
dfs(root->left, target, cur_sum, nums, vector_list);
if (root->right)
dfs(root->right, target, cur_sum, nums, vector_list);
nums.pop_back();
}
};https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
这题的题解做得非常漂亮.
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == nullptr) return nullptr;
Node *cur = head;
std::map<Node*, Node*> m;
while (cur) {
m[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
while (cur) {
m[cur]->next = m[cur->next];
m[cur]->random = m[cur->random];
cur = cur->next;
}
return m[head];
}
};https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
可以中序遍历的时候on-the-fly改.
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if (!root) return nullptr;
prev = nullptr;
inOrder(root);
head->left = prev;
prev->right = head;
return head;
}
void inOrder(Node* cur) {
if (cur) {
inOrder(cur->left);
if (!prev) {
head = prev = cur;
} else {
cur->left = prev;
prev->right = cur;
prev = cur;
}
inOrder(cur->right);
}
}
private:
Node *prev, *head;
};https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
比较恶心的题目. 题目没说清楚是怎么保存的. 不是完全二叉树.
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
std::queue<TreeNode*> q;
q.push(root);
std::string s;
while (!q.empty()) {
auto front = q.front();
q.pop();
if (front) {
s += std::to_string(front->val);
q.push(front->left);
q.push(front->right);
} else {
s += "n";
}
s += ",";
}
// if (s.back() == ',') s.pop_back();
return s;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
TreeNode dummy;
std::queue<TreeNode*> q;
q.push(&dummy);
int idx = 0, size = data.size();
int left = false;
while (idx < size) {
int beg = idx;
while (idx < size && data[idx] != ',') idx++;
auto str = data.substr(beg, idx - beg);
// std::cout << str << " ";
TreeNode* node = nullptr;
if (str != "n") {
node = new TreeNode(std::stoi(str));
}
auto front = q.front();
if (left) {
front->left = node;
} else {
front->right = node;
q.pop();
}
left = !left;
if (node) {
q.push(node);
}
idx++;
}
return dummy.right;
}
};
https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
dfs生成可重集的permutation. 用set保证某个位置上不出现重复元素.
class Solution {
public:
vector<string> permutation(string s) {
if (s.empty()) return {};
vector<string> ans;
dfs(s, 0, ans);
return ans;
}
void dfs(string s, int cur, vector<string>& ans) {
if (cur == s.size()) {
ans.push_back(s);
return;
}
set<char> st;
for (int i = cur; i < s.size(); ++i) {
if (st.find(s[i]) != st.end()) continue;
st.insert(s[i]);
swap(s[i], s[cur]);
dfs(s, cur+1, ans);
swap(s[i], s[cur]);
}
}
};https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
摩尔投票法
class Solution {
public:
int majorityElement(vector<int>& nums) {
int cnt = 0, x;
for (auto num: nums) {
if (cnt == 0) x = num;
cnt += x == num ? 1 : -1;
}
return x;
}
};https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
最大堆.
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
if (k == 0) return {};
std::vector<int> ans(k);
int size = 0;
for (auto num: arr) {
if (size < k) {
ans[size] = num;
size++;
std::push_heap(ans.begin(), ans.begin()+ size);
} else {
int top = ans[0];
if (num < top) {
std::pop_heap(ans.begin(), ans.begin()+size);
ans[size-1] = num;
std::push_heap(ans.begin(), ans.begin()+size);
}
}
}
return ans;
}
};https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
看了题解. 做法是用双堆（最大堆+最小堆），保持两个堆大小一样或者某一个多一个元素（奇数）. 这样求median就是一个O(1)的操作，因为median一定存在于两个堆的top上. 这样空间复杂度是O(n).
class MedianFinder {
public:
/** initialize your data structure here. */
MedianFinder() {}
void addNum(int num) {
maxq.push(num);
minq.push(maxq.top());
maxq.pop();
if (minq.size() > maxq.size()) {
maxq.push(minq.top());
minq.pop();
}
}
double findMedian() {
if (maxq.size() > minq.size()) return maxq.top();
else return double(maxq.top() + minq.top()) / 2;
}
private:
std::priority_queue<int, vector<int>, std::greater<int>> minq;
std::priority_queue<int> maxq;
};https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
做烂的题目.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0, max = -100;
for (auto num: nums) {
sum += num;
max = std::max(max, sum);
if (sum < 0) sum = 0;
}
return max;
}
};跳过了43, 44.... 太不喜欢找规律的数学题了.
jasperzhong
commented
3 years ago https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
看了题解. 直接字符串比较就行了—— str(x) + str(y) < str(y) + str(x). 我好菜啊.
class Solution {
public:
string minNumber(vector<int>& nums) {
std::sort(nums.begin(), nums.end(), [](int x, int y) {
auto x_y = to_string(x) + to_string(y);
auto y_x = to_string(y) + to_string(x);
return x_y < y_x;
});
string s;
for (auto num: nums) {
s += to_string(num);
}
return s;
}
};https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
用dfs做复杂了...因为不需要输出字符串. 直接dp就可以了.
class Solution {
public:
int translateNum(int num) {
auto str = to_string(num);
int dp[str.size()+1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= str.size(); ++i) {
if (str[i-2] == '1' || (str[i-2] == '2' && str[i-1] < '6'))
dp[i] = dp[i-1] + dp[i-2];
else
dp[i] = dp[i-1];
}
return dp[str.size()];
}
};https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
f(i, j) = max(f(i-1, j), f(i, j-1)) + grid(i, j)
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 && j == 0) continue;
else if (i == 0) grid[i][j] += grid[i][j-1];
else if (j == 0) grid[i][j] += grid[i-1][j];
else
grid[i][j] += std::max(grid[i][j-1], grid[i-1][j]);
}
}
return grid[m-1][n-1];
}
};
基本保持每日一题. 主要用cxx.
以前面试实习前都会过一遍这本书.