大家好！好久不见！最近都没抽出时间写日记。今天一起写了吧！
上次我的进度好像是100题左右。
在我这6天的不懈努力下，我手撕了50道算法题！！！
具体数量不记得了，但是，medium题我做了好几道（大概40道左右）
我先是把链表的leetbook给刷完了！（难以置信，2个小时就做完了！）
之后上床睡觉是满脑子都是list->next，ListNode* node，return nullptr……（反正都是有关链表的语句）
我硬是躺了1个小时才睡……
之后几天我就从有关数组的题目。
这就是最近做的题目（有些是之前做的，因为我有时会到明天再提交一遍）
显示“6天前”或“5天前”的就是链表的题目了，其他的我虽然说了题目是数组的。但是，只要关于数组的，我都会去做。（就算涉及了其他知识也没关系）
总结一下：
707. 设计链表题是很基础的链表题。要求我们做一些链表的基础操作。
class MyLinkedList {
public:
MyLinkedList() {
this->n = 0;
this->head = new ListNode(0);
}
int get(int index) {
if (index < 0 || index >= n) {
return -1;
}
ListNode* list = head;
int i;
for (i = 0; i <= index; i++) {
list = list->next;
}
return list->val;
}
void addAtHead(int val) {
addAtIndex(0,val);
}
void addAtTail(int val) {
addAtIndex(n,val);
}
void addAtIndex(int index, int val) {
if (index > n) {
return;
}
index = max(0,index);
n++;
ListNode* list = head;
int i;
for (i = 0; i < index; i++) {
list = list->next;
}
ListNode* node = new ListNode(val);
node->next = list->next;
list->next = node;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= n) {
return;
}
n--;
ListNode* list = head;
int i;
for (i = 0; i < index; i++) {
list = list->next;
}
ListNode* node = list->next;
list->next = list->next->next;
delete node;
}
private:
int n;
ListNode* head;
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/430. 扁平化多级双向链表和328. 奇偶链表这两题个人认为应该是hard题（好难）……
430：
/*
// Definition for a Node.
class Node {
public:
int val;
Node* prev;
Node* next;
Node* child;
};
*/
class Solution {
public:
Node* flatten(Node* head) {
function<Node*(Node*)> dfs = [&](Node* node) {
Node *cur = node,*last = nullptr;
while (cur) {
Node* next = cur->next;
if (cur->child) {
Node* child_last = dfs(cur->child);
next = cur->next;
cur->next = cur->child;
cur->child->prev = cur;
if (next) {
child_last->next = next;
next->prev = child_last;
}
cur->child = nullptr;
last = child_last;
}else{
last = cur;
}
cur = next;
}
return last;
};
dfs(head);
return head;
}
};328：
/**
* 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* oddEvenList(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
ListNode *evenHead,*odd,*even;
evenHead = head->next;
odd = head;
even = evenHead;
while (even != nullptr && even->next != nullptr) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
};链表值得我说说的就这3道了。
那63. 不同路径 II我不知道哪错了，把测试数据放到“测试用例”哪里，跑出来却对了，提交上去就错了……
于是我急了，提交了好几次：
最后，把“dp[111][111]”改成“vector<vector> dp”就过了……（不明不白）
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int n = obstacleGrid.size(),m = obstacleGrid[0].size();
if (obstacleGrid[0][0] == 1 || n == 0) {
return 0;
}
int i/*,dp[111][111]*/;
vector<vector<int>> dp(n,vector<int>(m));
dp[0][0] = 1;
for (i = 1; i < m; i++) {
if (dp[0][i - 1] != 0 && obstacleGrid[0][i] == 0) {
dp[0][i] = 1;
}
}
for (i = 1; i < n; i++) {
if (dp[i - 1][0] != 0 && obstacleGrid[i][0] == 0) {
dp[i][0] = 1;
}
}
int j;
for (i = 1; i < n; i++) {
for (j = 1; j < m; j++) {
if (obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[n - 1][m - 1];
}
};有没有哪位告诉我一下为什么？
105. 从前序与中序遍历序列构造二叉树106. 从中序与后序遍历序列构造二叉树都好难啊！（我觉得是hard题才对）
105：
/**
* 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 {
private:
unordered_map<int, int> index;
TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
if (preorder_left > preorder_right) {
return nullptr;
}
int preorder_root = preorder_left;
int inorder_root = index[preorder[preorder_root]];
TreeNode* root = new TreeNode(preorder[preorder_root]);
int size_left_subtree = inorder_root - inorder_left;
root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
for (int i = 0; i < n; ++i) {
index[inorder[i]] = i;
}
return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}
};106：
/**
* 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 {
private:
int post_idx;
unordered_map<int, int> idx_map;
TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
if (in_left > in_right) {
return nullptr;
}
int root_val = postorder[post_idx];
TreeNode* root = new TreeNode(root_val);
int index = idx_map[root_val];
post_idx--;
root->right = helper(index + 1, in_right, inorder, postorder);
root->left = helper(in_left, index - 1, inorder, postorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
post_idx = (int)postorder.size() - 1;
int idx = 0;
for (auto& val : inorder) {
idx_map[val] = idx++;
}
return helper(0, (int)inorder.size() - 1, inorder, postorder);
}
};这几天收获很大！还了解了单调栈！
再见！
评论 (50)
