2.2#
括号生成 (掌握程度：中)#
一个典型回溯题，除了dfs的中间的处理有点略微记不起来，其余一点问题都没有
class Solution {
public:
vector<string> ans;
string path;
void dfs(int n, int close, int open) {
if (close == n) {
ans.push_back(path);
return ;
}
if (open < n) {
path.push_back('(');
dfs(n, close, open + 1);
path.pop_back();
}
if (close < open) {
path.push_back(')');
dfs(n, close + 1, open);
path.pop_back();
}
}
vector<string> generateParenthesis(int n) {
dfs(n, 0, 0);
return ans;
}
};排序链表 (掌握程度：低)#
看到题都不知道怎么写了，但是看到题解才发现真的很简单，就是归并排序再合并两个链表
/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while(list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
if (list1) {
cur->next = list1;
} else {
cur->next = list2;
}
return dummy->next;
}
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* fast = head->next;
ListNode* slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
ListNode* mid = slow->next;
slow->next = nullptr;
ListNode* left = sortList(head);
ListNode* right = sortList(mid);
return mergeTwoLists(left, right);
}
};用栈实现队列 (掌握程度： 高)#
很简单的设计题，用两个栈实现队列
type MyQueue struct {
inStack []int
outStack []int
}
func Constructor() MyQueue {
return MyQueue{}
}
func (q *MyQueue) Push(x int) {
q.inStack = append(q.inStack, x)
}
func (q *MyQueue) in2out() {
for len(q.inStack) > 0 {
q.outStack = append(q.outStack, q.inStack[len(q.inStack)-1])
q.inStack = q.inStack[:len(q.inStack)-1]
}
}
func (q *MyQueue) Pop() int {
if (len(q.outStack) == 0) {
q.in2out()
}
x := q.outStack[len(q.outStack) - 1];
q.outStack = q.outStack[:len(q.outStack) - 1]
return x
}
func (q *MyQueue) Peek() int {
if (len(q.outStack) == 0) {
q.in2out()
}
return q.outStack[len(q.outStack) - 1]
}
func (q *MyQueue) Empty() bool {
return len(q.inStack) == 0 && len(q.outStack) == 0
}
/**
* Your MyQueue object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(x);
* param_2 := obj.Pop();
* param_3 := obj.Peek();
* param_4 := obj.Empty();
*/二分查找 (掌握程度：高)#
简单题，如何二分的教学，这个也不会的话，我得回炉重造remake了
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}
};二叉树的中序遍历 (掌握程度：高)#
很难想象我以前这道题竟然还好几次想不起来怎么写
/**
* Definition for a binary tree node.
* struct 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) {}
* };
*/
class Solution {
public:
vector<int> ans;
void dfs(TreeNode* node) {
if (node == nullptr) return;
dfs(node->left);
ans.push_back(node->val);
dfs(node->right);
}
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return ans;
}
};