LeetCode Daily Question 29

May 14th 2022

5 月 14 日 每日一题

105. Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

1
2
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

思路

本题使用递归的写法，首先思考递归公式：

  1. 将 preoder 的局部第一位设为 root（left 区域的第一个 preorder 或 right 区域的第一个 preoder，因此需要一个 prestart 参数）。
  2. 找到该 preorder element 在 inorder 中的 index。
  3. 针对该 preorder element 的 left 区域进入子问题（因此需要 instart 和 inEnd 参数）。
  4. 针对该 preoder element 的 right 区域进入子问题。

第二步思考临界条件：
prestart >= preorder.size() || instart > inend 时返回 nullptr（无 node）

第三步实现代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 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:
    unordered_map<int, int> index;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i++){
            index[inorder[i]] = i;
        }
        return buildHelper(preorder, inorder, 0, 0, int(inorder.size() - 1), index);
    }
    TreeNode* buildHelper(vector<int>& preorder, vector<int>& inorder, int preStart, int inStart, int inEnd, unordered_map<int, int> &index){
        if(preStart >= preorder.size() || inStart > inEnd)
            return nullptr;
        TreeNode *root = new TreeNode{preorder[preStart], nullptr, nullptr};
        int curIndex = index[preorder[preStart]];
        root->left = buildHelper(preorder, inorder, preStart + 1, inStart, curIndex - 1, index);
        root->right = buildHelper(preorder, inorder, preStart + curIndex - inStart + 1, curIndex + 1, inEnd, index);
        return root;
    }
};
Read More
,

LeetCode Daily Question 28

May 11th 2022

5 月 11 日 每日一题

101. Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

1
2
Input: root = [1,2,2,3,4,4,3]
Output: true

思路

Recursive 写法：
首先思考问题与子问题的递归关系，可分为三种 case，第一种是只有一个 node，必然 true；第二种是三个 node，需要满足 left->val == right->val；第三种是 height 大于 3 的 completed tree，需要满足 left->val == right->val 并且 left->left tree 与 right->right tree 相同，left->right 与 right->left 相同。
之后思考 base case，left/right 有一个空或全空。
最后将以上归纳为函数代码(首先将 root->left，right）传入函数可以自然判断前两种 case。

Iterative 写法：
逻辑类似 BSF，首先将 root->left,right 放入 queue，while 判断条件为 queue 非空，在 while 内判断 val 并且按递归 case3 的顺序 push 进 queue.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root)
            return true;
        return SymmetricHelper(root->left, root->right);
    }
    bool SymmetricHelper(TreeNode *left, TreeNode *right){
        if(!left || !right)
            return left == right;
        if(left->val != right->val)
            return false;
        return SymmetricHelper(left->left, right->right) && SymmetricHelper(left->right, right->left);
    }
};


bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        queue<TreeNode*> queue;
        queue.push(root->left);
        queue.push(root->right);
        while(!queue.empty()) {
            TreeNode *left = queue.front(); queue.pop();
            TreeNode *right = queue.front(); queue.pop();
            if(!left || !right) return left == right;
            if(left->val != right->val) return false;
            queue.push(left->left);
            queue.push(right->right);
            queue.push(left->right);
            queue.push(right->left);
        }
        return true;
    }
Read More
,

LeetCode Daily Question 27

May 10th 2022

5 月 10 日 每日一题

题目：99. Recover Binary Search Tree

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

1
2
3
Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

思路

本题核心是利用 inorder traversal 检测错误点（BSF 的 inorder 应该为从小到大），如果检测到两组顺序不同的 node，则为第一组 node 的第一个位置和第二组 node 的第二个位置。因此需要两个 pointer first 和 second 记录这两个位置。需要注意的是 prev 的初始值应该为 infinitMin。
注意 prev 初始为 infmin

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode *firstRemove, *secondRemove, *prev;
    void recoverTree(TreeNode* root) {
        prev = new TreeNode(INT_MIN);
        inorderHelper(root);
        swap(firstRemove->val, secondRemove->val);
    }
    void inorderHelper(TreeNode *root){
        if(!root)
            return;
        inorderHelper(root->left);
        if(firstRemove == nullptr && root->val < prev->val)
            firstRemove = prev;
        if(firstRemove != nullptr && root->val < prev->val)
            secondRemove = root;
        prev = root;
        inorderHelper(root->right);
    }
};

Read More
,

LeetCode Daily Question 26

May 9th 2022

5 月 9 日 每日一题

题目：237. Delete Node in a Linked List

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

思路

一道 easy 题，先将下一个 node 的信息保存到该 node，然后删除下一 node。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        ListNode* forwarding = node->next->next;
        delete node->next;
        node->next = forwarding;
    }
};

Read More
,

LeetCode Daily Question 25

May 8th 2022

5 月 8 日 每日一题

题目：141. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

思路

两种思路，快慢指针和 hashmap/set，hashmap 需要注意 value 可能重复所以 key 应该使用 ListNode*类型。快慢指针需要考虑 head 为 nullptr，linkList 只有两个的 edge case（建议提前列出 0 1 2 3 个 Node 的情况。

需要注意的是，unorder_map 的 count 函数，如果该 key 存在，返回 1，不存在返回 0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast && fast->next ){
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast)
                return true;
        }
        return false;
    }
};
Read More
,

LeetCode Daily Question 24

May 7th 2022

5 月 7 日 每日一题

题目：284. Peeking Iterator

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

1
2
3
4
5
6
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]

思路

I. Dummy Node
用于避免 reverse 的 left 为 head 的 edge case，结束时返回 dummy node 的 next 即可。

II. 移动指针，将指针指向 left，并且需要记录 left 的前一个 node，以便结束时 connect。需要注意的是循环的运行次数应该为 left - 1.

III. 对要求区域进行 reverse，需要记录 curr，prev 和 forwarding，流程为，首先记录 current node 的 next，然后将 current node 的 next 指向 prev，然后将 prev 更新为 current node，current node 更新为 forwarding node。reverse 的次数为 right - left + 1，这是因为第一次循环 prev 为 nullptr。

IV. 连接 reverse 区域与其余区域，此时 current 指向 node after right，并且 leftPrev 的 next 为 reverse 前的 left。首先将 reverse 前的 left 的 next 指向 current。然后将 leftPrev 的 next 指向 prev（right）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left == right)
            return head;
        //dummy node
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        //go to left
        ListNode *leftPrev = dummy;
        ListNode *cur = dummy->next;
        for(int i = 0; i < left - 1; i++){
            leftPrev = cur;
            cur = cur->next;
        }//now cur points to left
        //reverse from left to right
        ListNode* prev = nullptr;
        for(int i = left; i < right + 1; i++){
            ListNode* forwarding = cur->next;
            cur->next = prev;
            prev = cur;
            cur = forwarding;
        }
        //connect
        leftPrev->next->next = cur;
        leftPrev->next = prev;
        return dummy->next;
    }
};

Read More
,

LeetCode Daily Question 23

May 6th 2022

5 月 6 日 每日一题

题目：284. Peeking Iterator

Design an iterator that supports the peek operation on an existing iterator in addition to the hasNext and the next operations.

Implement the PeekingIterator class:

PeekingIterator(Iterator nums) Initializes the object with the given integer iterator iterator.
int next() Returns the next element in the array and moves the pointer to the next element.
boolean hasNext() Returns true if there are still elements in the array.
int peek() Returns the next element in the array without moving the pointer.
Note: Each language may have a different implementation of the constructor and Iterator, but they all support the int next() and boolean hasNext() functions.

1
2
3
4
5
6
7
8
9
10
11
12
13
Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek();    // return 2, the pointer does not move [1,2,3].
peekingIterator.next();    // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next();    // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False

思路

这道题没什么好说的，看懂题就能做出来，奈何我没看懂题…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class PeekingIterator : public Iterator {
private:
    bool isHasNext;
    int nextVal;
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        // Initialize any member here.
        // **DO NOT** save a copy of nums and manipulate it directly.
        // You should only use the Iterator interface methods.
        isHasNext = Iterator::hasNext();
        if(isHasNext)
            nextVal = Iterator::next();
    }

    // Returns the next element in the iteration without advancing the iterator.
    int peek() {
        return nextVal;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    int next() {
        int currNext = nextVal;
        isHasNext = Iterator::hasNext();
        if(isHasNext)
            nextVal = Iterator::next();
        return currNext;
    }

    bool hasNext() const {
        return isHasNext;
    }
};
Read More

LeetCode Daily Question 22

May 6th 2022

5 月 6 日 每日一题

题目：169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

1
2
3
4
Example 1:

Input: nums = [3,2,3]
Output: 3

思路

本题使用 Boyer–Moore majority vote algorithm，因为条件是必然存在 majority，本质可以理解为为每一个元素寻找一个不同的元素进行配对，应该存在 n/2 个 pair，但 majority 一定出现多于 n/2 次，所以最终剩余的无法配对的元素就是 majority。截屏2022-05-06 下午11.44.32

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int majority = nums[0];
        for(auto &num: nums){
            if(count >= 1)
                count += (num == majority) ? 1 : -1;
            else{
                majority = num;
                count = 1;
            }
        }
        return majority;
    }
};
Read More

LeetCode Daily Question 21

May 6th 2022

5 月 5 日 每日一题

题目：11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

1
2
3
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

思路

本题是关于双指针和贪心的题目，Greedy 的逻辑为：从可能最大的宽度起始，如果左边小，则 left++，如果右边小则 right–。因为水面高度永远取最小，所以如果移动大的一边，体积必然下降。如果 greedy 后得出的体积比当前的 maxArea 大，则修改当前 maxArea。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxArea = 0;
        int left = 0;
        int right = static_cast<int>(height.size() - 1);
        while(left != right){
            maxArea = max(min(height[left], height[right]) * (right - left), maxArea);
            if(height[left] < height[right])
                left++;
            else
                right--;
        }
        return maxArea;
    }
};
Read More
,

写在22WN结束之后

May 2nd 2022

16521651549140_.pic_hd

Introduction

今天收到了 370 的 letter grade，有惊无险，算是圆满结束我的 22Winter Term。本篇文章旨在分析本学期几门课的学习效果。

EECS 281

本学期最重量级的一门专业课，workload 60%出头，在完成四个 project 之外，还需要每周完成 lab 的 quiz，coding assignment，和 written problem。这门课最奇怪的还是抽题制考试，每个人考题难度差距很离谱，例如我觉得极难的 midterm 选择题平均分 45 分，但我觉得相对简单很多的 final 选择题平均分却是 35 分。感谢这门课的 Final，把我抬上了 A+。

学习这门课只是停留在 lecture 是肯定不够的，搭配 IA 的 Leetcode List 可以帮助掌握知识点，有时间的话强烈建议读一遍 notes，notes 的内容要比 slides 更细节，也涉及了更多知识点。

EECS 370

本学期第二重量级的专业课，computer organization。内容偏重概念，project 是实现 Lc2k 的 assembler， simulator， linker 等一系列东西，以及写几个汇编软件。考试细心非常重要，我两次考得都一般，但 project 和 hw 拉满，所以拿 A 飘过了。

STATS 250

巨水的统计课，讲了几个分布，如何做 Hypothesis Test & Confidence Interval， 学了一些基础的 R， A+结束。

EARTH 114， LING 137， ELI 210 and ELI 131

前三门没有什么可说的，三门大水课，拿 A 了事。后两门 ELI 因为太忙，没有花多少时间，所以效果很差。

Summary

对于像我一样第一次学数据结构的学生，不建议在一个学期同时学 370 和 281，我个人感觉 281 没有学扎实，计划暑假继续刷题，夯实基础。

虽然没有上过 STATS 412，考虑到 412 不用做无聊的 lab，我觉得会是比 250 更好的选择。

Read More
Previous
Next