Tag: 数据结构

Posted 2022-09-02Updated 2022-09-02LeetCode / Esaya minute read (About 209 words)

Question

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10<sup>-5</sup> of the actual answer will be accepted.

Solution

BFS搜索，记录单层的总和sum和单层的个数count。
每次遍历一个层级的所有节点，并更新sum和count。
遍历完毕后将当层级的平均数加入列表，同时将sum和count清零。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        
        double sum = 0, count = 0;
        int level = 1;
        q.add(root);
        
        while(!q.isEmpty()){
    
            for(int i = 0; i < level; i++){
                TreeNode curr = q.poll();
                if(curr.left != null) q.add(curr.left);
                if(curr.right != null) q.add(curr.right);
                count++;
                sum += curr.val;
            }
            res.add(sum/count);
            sum = 0;
            count = 0;
            level = q.size();
        }
        return res;
    }
}

Posted 2022-09-01Updated 2022-09-01LeetCode / Mediuma minute read (About 161 words)

1448. Count Good Nodes in Binary Tree

Question

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Solution

DFS搜索，每次传入当前分支的最大值。
如果当前值大于等于最大值，则count+1。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int count;
    public int goodNodes(TreeNode root) {
        count = 0;
        dfs(root, Integer.MIN_VALUE);
        return count;
    }
    
    private void dfs(TreeNode root, int max){
        if(root == null) return;
        if(root.val >= max){
            count++;
            max = root.val;
        }

        dfs(root.left, max);
        dfs(root.right, max);
    }
}

Posted 2022-08-03Updated 2022-08-03LeetCode / Medium / 复习2 minutes read (About 361 words)

729. My Calendar I

Question

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

MyCalendar() Initializes the calendar object.

boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Solution

有更快速的解法，需要用到TreeMap，有时间再研究。

使用一个队列记录已经预定的范围。
添加无穷大到队列中，方便后期计算。

当预定新的时间段时，遍历队列，如果上一个数组的最大值小于start和end且当前遍历数组大于start和end，则可以预定，将当前的数组插入当前位置，并返回true。
如果没有满足条件的，则返回false。

Code

class MyCalendar {
    List<int[]> arr;
    public MyCalendar() {
        arr = new ArrayList<>();
        int[] inf = new int[2];
        inf[0] = Integer.MAX_VALUE;
        inf[1] = Integer.MAX_VALUE;
        arr.add(inf);
    }
    
    public boolean book(int start, int end) {
        int[] last = new int[2];
        for(int i = 0; i < arr.size(); i++){
            int[] curr = arr.get(i);
            if(last[1] < end && last[1] <= start && curr[0] >= end && curr[0] > start){
                int[] n = new int[2];
                n[0] = start;
                n[1] = end;
                arr.add(i, n);
                return true;
            }
            last = curr;
        }
        return false;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

Posted 2022-07-27Updated 2022-07-27LeetCode / Medium / 复习2 minutes read (About 343 words)

114. Flatten Binary Tree to Linked List

Question

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

The “linked list” should be in the same order as a pre-order** traversal** of the binary tree.

Solution

全局变量prev，初始化为null，用来记录上一个访问的节点。

由于最后要达到先序遍历（根节点-左子节点-右子节点）的数据结构顺序，因此在进行访问时需要与先序遍历的操作相反，首先递归右子节点，然后递归左子节点，最后修改当前节点。

先遍历当前节点的右侧节点，再遍历当前节点的左侧节点。
最后处理当前节点，将左子节点设置为null，右子节点设置为prev。
最后将当前节点保存在prev上。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode prev = null;
    public void flatten(TreeNode root) {
        if(root == null) return;
        flatten(root.right);    //traverse right nodes first
        flatten(root.left); //traverse left nodes
        root.left = null;   //set current node's left child node to null
        root.right = prev;  //set current node's right child node to previous node
        prev = root;    //update previous node
    }
}

Posted 2022-07-22Updated 2022-07-22LeetCode / Medium3 minutes read (About 442 words)

86. Partition List

Question

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Solution 1

生成前后两个部分的dummy链表头。
遍历原链表，当当前值小于x时则将当前节点添加到第一个链表头后。
当当前值大于x时则将当前节点添加到第二个链表头后。

遍历完成后将第二个链表头的下一个节点添加到第一个链表的下一个节点上。然后将第二个链表的尾部指向null。

返回第一个dummy链表节点的下一个节点即可。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(), dummy2 = new ListNode();
        ListNode hd1 = dummy1, hd2 = dummy2;
        while(head != null){
            if(head.val < x){
                dummy1.next = head;
                dummy1 = dummy1.next;
            }
            else{
                dummy2.next = head;
                dummy2 = dummy2.next;
            }
            head = head.next;
        }
        dummy1.next = hd2.next;
        dummy2.next = null;
        
        return hd1.next;
    }
}

Solution 2

遍历整个链表，根据各个节点的值将其保存在两个队列中。

设置一个dummy节点头，将两个队列中的节点按顺序挤出并生成新链表。
返回dummy节点头的下一个节点即可。

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        Queue<ListNode> q1 = new LinkedList<>();
        Queue<ListNode> q2 = new LinkedList<>();
        while(head != null){
            if(head.val < x) q1.add(head);
            else q2.add(head);
            head = head.next;
        }
        
        ListNode dummy = new ListNode();
        ListNode res = dummy;
        
        while(!q1.isEmpty()){
            res.next = q1.poll();
            res = res.next;
        }
        
        while(!q2.isEmpty()){
            res.next = q2.poll();
            res = res.next;
        }
        res.next = null;
        return dummy.next;
    }
}

Posted 2022-06-19Updated 2022-06-18LeetCode / Medium / 复习2 minutes read (About 366 words)

1268. Search Suggestions System

Question

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Solution

字典树+优先级队列。
在TrieNode节点中保存PriorityQueue，以记录该节点下的三个单词。
注意PriorityQueue中的String需要按倒序排列，以保证维护时可以直接poll掉字符顺序较后的单词。

add()方法

创建并添加TrieNode节点，同时在移动当前节点位置时，需要维护PriorityQueue，当长度大于3时，则挤出字典顺序排列较后的单词。

search()方法

在查找前缀时，将每个TrieNode节点上的PriorityQueue倒序加入List。

Code

class Solution {
    class TrieNode{
        boolean end;
        TrieNode[] children = new TrieNode[26];
        PriorityQueue<String> q = new PriorityQueue<>((a, b) -> b.compareTo(a));
    }
    
    TrieNode root;
    
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ret = new ArrayList<>();
        root = new TrieNode();
        for(String word : products){
            add(word);
        }
        return search(searchWord);
    }
    
    private void add(String word){
        TrieNode curr = root;
        for(char c : word.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
            curr.q.add(word);
            if(curr.q.size() > 3) curr.q.poll();
        }
        curr.end = true;
    }
    
    private List<List<String>> search(String prefix){
        List<List<String>> ret = new ArrayList<>();
        TrieNode curr = root;
        for(char c : prefix.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
            List<String> temp = new ArrayList<>();
            while(!curr.q.isEmpty()){
                temp.add(curr.q.poll());
            }
            Collections.reverse(temp);
            ret.add(temp);
        }
        return ret;
    }
}

Posted 2022-06-18Updated 2022-06-17Medium / 复习4 minutes read (About 600 words)

208. Implement Trie (Prefix Tree)

Question

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.

void insert(String word) Inserts the string word into the trie.

boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.

boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Solution

参考：实现 Trie :「二维数组」&「TrieNode」方式

前缀树，字典树结构实现。

前缀树 Trie

前缀树结构用“边”记录有无字符，用“点”记录单词结尾以及后续的字符串字符。
root节点记录字典的根节点。

TrieNode节点

用TrieNode节点实现前缀树。
真值end记录是否为字符串的结尾，创建时默认为false。
数组TrieNode[] children记录子节点。

insert()方法

从根节点root开始，遍历字符串。
如果对应的子节点位置为空，则创建新的TrieNode节点。
向下移动当前节点。

将最后一个节点设置为end，使得整个字符串被字典记录。

search()方法

从根节点root开始，遍历字符串。
如果子节点位置为空，则这个字符串不在字典中，返回false。
否则向下移动当前节点。

遍历完毕，如果当前节点的end为true，则存在该字符串，返回true。

startsWith()方法

从根节点root开始，遍历前缀字符串。
如果子节点位置为空，则这个前缀不在字典中，返回false。
否则向下移动当前节点。

最后返回true。

Code

class Trie {
    class TrieNode {
        boolean end;
        TrieNode[] children = new TrieNode[26];
    }
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode curr = root;
        for(char c : word.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) curr.children[i] = new TrieNode();
            curr = curr.children[i];
        }
        curr.end = true;
    }
    
    public boolean search(String word) {
        TrieNode curr = root;
        for(char c : word.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) return false;
            curr = curr.children[i];
        }
        return curr.end;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for(char c : prefix.toCharArray()){
            int i = c - 'a';
            if(curr.children[i] == null) return false;
            curr = curr.children[i];
        }
        return true;
    }
    
    
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Posted 2022-06-18Updated 2022-06-17Hard / 复习10 minutes read (About 1452 words)

968. Binary Tree Cameras

Question

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

Solution 1

贪心算法，后序遍历。每次递归根据下面两个子节点的状态来决定当前节点的状态。

每个节点一共有三种状态：

未被监控，返回0。
摄像头，返回1。
已被监控，返回2。

递归，当当前节点为空，则返回2，表示已被监控。这样叶子节点则为未被监控的状态。

如果下面的子节点有一个未被监控，则当前节点需要设置相机，返回1，计数res+1。
如果下面的子节点有一个为摄像头，则当前节点已被监控，返回2。
否则下面的节点均为已被监控，此时返回未被监控0。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0; //记录摄像头个数
    public int minCameraCover(TreeNode root) {
        if(judge(root) == 0) res++;  //如果根节点未被监控，则需要增加一个摄像机
        return res;
    }
    public int judge(TreeNode root){
        if(root == null) return 2;   //根节点为空时返回2，这样叶子节点变为未被监控
        int left = judge(root.left);
        int right = judge(root.right);

        if(left == 0 || right == 0){    //如果左右子节点有未被监控的节点，则当前节点设置为摄像机，结果加一，返回1
            res++;
            return 1;
        }
        if(left == 1 || right == 1) return 2;    //如果左右子节点中有摄像机，则当前节点已被监控，返回2
        return 0;   //如果左右子节点都被监控，则当前节点未被监控，返回0
    }
}

Solution 2

参考：从递归优化到树形DP

树形DP。
递归，每次返回当前节点所有子节点的最小相机数。
每一个节点有三种状态：

放置了相机。
没有相机，但是被父节点parent监控。
没有相机，但是被子节点son监控。

将三种状态分别传入minCam()方法。

递归方法 minCam()

在递归时传入两个参数hasCamera和isWatched，来判断当前节点是否有相机，是否被监控。
当当前节点为空节点时，如果设置应当有相机（做不到）则返回无限大，消除这个返回值。如果不应该有相机，则返回0。

向下递归子节点。

当当前节点应该有相机时：
子节点一定被监控因此isWatched为true。
子节点可以放置或不放置相机，因此hasCamera可以为true或false。
注意当前位置放置相机，则子节点最多放置一个相机，因此一共有三种组合。
由于相机至少有一个，因此返回其中的最小值+1。
当当前节点没有放置相机，但被父节点监控时：
左右节点一共有四种组合，分别同时将子节点的监控状态向下递归。
返回其中的最小值。
当当前节点没有放置相机，也没有被父节点监控，而是被子节点监控时：
子节点至少有一个相机，向下递归状态，一共有三种组合。
返回其中的最小值

然后分别调用minCam(root, true, true)和minCam(root, false, fasle)，取两者中的小值，即可得到答案。

树形dp优化剪枝

上面的方法实际采用时会超时，因为我们重复了三次调用一个子树下的三种状态的minCam。
因此我们可以将三种状态下的minCam分别保存在数组中返回。

withCam: 当前子树root有相机。
noCamWatchedByParent: 当前子树root没有相机，被父节点监控。
noCamWatchedBySon: 当前子树root没有相机，被子节点监控。

在每次递归时，获取数组minCam(root.left)和minCam(root.right)。
然后根据左右子节点的三个参数来计算当前节点的新的三个参数，将其返回。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        return Math.min(minCam(root, true, true), minCam(root, false, false));
    }
    
    private int minCam(TreeNode root, boolean hasCamera, boolean isWatched){
        if(root == null) return hasCamera ? Integer.MAX_VALUE / 2 : 0;

        if(hasCamera){
            int min = Math.min(minCam(root.left, false, true) + minCam(root.right, false, true), minCam(root.left, true, true) + minCam(root.right, false, true));
            min = Math.min(min, minCam(root.left, false, true) + minCam(root.right, true, true));
            return 1 + min;
        }
        else if(isWatched){
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, false, false));
            return min;
        }
        else{
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            return min;
        }
    }
}

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        int[] res = minCam(root);
        return Math.min(res[0], res[2]);
    }
    
    private int[] minCam(TreeNode root){
        if(root == null){
            return new int[] {Integer.MAX_VALUE/2, 0, 0};
        }
        int[] left = minCam(root.left);
        int[] right = minCam(root.right);

        int withCam = 1 + Math.min(left[1] + right[1], Math.min(left[0] + right[1], left[1] + right[0]) );
        int noCamWatchedByParent = Math.min( left[0] + right[0], Math.min( left[0] + right[2], Math.min( left[2] + right[0], left[2] + right[2] )));
        int noCamWatchedBySon = Math.min( left[0] + right[0], Math.min( left[0] + right[2], left[2] + right[0]));
        return new int[] {withCam, noCamWatchedByParent, noCamWatchedBySon};
    }
}

Posted 2022-05-08Updated 2022-05-08LeetCode / Medium3 minutes read (About 391 words)

341. Flatten Nested List Iterator

Question

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.

int next() Returns the next integer in the nested list.

boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

Solution

将所有的NestedInteger展开后加入全局变量队列。

辅助方法buildQueue():
递归，如果当前元素是列表，则向下递归列表内的所有元素。
如果当前元素是单个整数，则将其加入队列。

next():
返回并挤出队列中的下一个元素，返回其整数。

hasNext():
返回队列是否为空。

Code

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    Queue<NestedInteger> q;
    public NestedIterator(List<NestedInteger> nestedList) {
        q = new LinkedList<>();
        for(NestedInteger item : nestedList){
            buildQueue(item);
        }
    }
    
    private void buildQueue(NestedInteger ni){
        if(!ni.isInteger()){
            for(NestedInteger item : ni.getList()){
                buildQueue(item);
            }
        }
        else{
            q.offer(ni);
        }
    }

    @Override
    public Integer next() {
        return q.poll().getInteger();
    }

    @Override
    public boolean hasNext() {
        return !q.isEmpty();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

Posted 2022-05-05Updated 2022-05-05LeetCode / Easy2 minutes read (About 366 words)

225. Implement Stack using Queues

Question

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.

int pop() Removes the element on the top of the stack and returns it.

int top() Returns the element on the top of the stack.

boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.

Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Solution

用两个队列实现栈。一个队列存放压入的元素。

push()

将当前元素加入到第一个队列。

top() & pop()

当需要挤出或者查看栈顶时，第一个队列只保留一个元素，其余元素加入第二个队列。最后一个元素就是栈顶。当第一个队列为空时，交换第一个队列与第二个队列。

empty()

返回两个队列是否均为空。

Code

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
        q1 = new LinkedList<Integer>();
        q2 = new LinkedList<Integer>();
        
    }
    
    public void push(int x) {
        q1.add(x);
    }
    
    public int pop() {
        move();
        return q1.poll();
    }
    
    public int top() {
        move();
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
    
    private void move(){
        if(q1.isEmpty()){
            Queue<Integer> temp = q1;
            q1 = q2;
            q2 = temp;
        }
        while(q1.size() != 1){
            q2.add(q1.poll());
        }
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Posted 2022-05-05Updated 2022-05-04LeetCode / Hard4 minutes read (About 589 words)

297. Serialize and Deserialize Binary Tree

Question

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Solution

编码过程

编码时采用BFS搜索，将二叉树按层级组成字符串。
当当前节点不等于null时，添加当前节点的值和一个符号。
然后将其左右子节点加入队列。
当当前节点为null时，添加一个非数字字符和一个符号。

解码过程

解码时同样采用BFS搜索，按层级恢复二叉树。
首先将字符串根据符号进行分割，变为字符串数组。
如果第一个字符表示为null，返回null。

否则将第一个数字组成根节点并加入队列。创建一个指针i记录位置。
当队列不为空，且指针i未越界时，根据指针i上的字符串创建当前节点的左子节点。
将指针右移，如果没有越界则创建当前节点的右子节点，然后将指针右移。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder data = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(curr == null) data.append("n,");
            else {
                data.append(curr.val + ",");
                q.add(curr.left);
                q.add(curr.right);
            }
        }
        return data.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] values = data.split(",");
        if(values[0].equals("n")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;     
        while(!q.isEmpty() && i < values.length){
            TreeNode curr = q.poll();
            curr.left = values[i].equals("n") ? null : new TreeNode(Integer.parseInt(values[i]));
            if(i++ < values.length) curr.right = values[i].equals("n") ? null : new TreeNode(Integer.parseInt(values[i]));
            if(curr.left != null) q.add(curr.left);
            if(curr.right != null) q.add(curr.right);
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

Posted 2022-05-03Updated 2022-05-02LeetCode / Medium / 复习5 minutes read (About 767 words)

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.

先序遍历时，访问的顺序是[根节点 - 左子节点 - 右子节点]。
中序遍历时，访问的顺序是[左子节点 - 根节点 - 右子节点]。
可以注意到根节点与左子节点的顺序是相反的，因此我们可以利用栈将节点储存起来，当挤出时顺序自然是调转的。

按照先序遍历来创建树，遍历先序数组。同时将指针指向中序遍历的数组的头部。
先创建根节点，并将其放入栈中。分为两种情况讨论。

情况一，处理当前根节点的左子节点，并将其入栈：

当栈顶的节点值与中序遍历当前的节点值不同时，说明当前的根节点仍有左子节点。

先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

此时将栈顶的节点的左子节点设置为先序数组对应的节点，继续遍历下一个先序数组。

栈内：[根节点 - 左子节点]
先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

情况二，寻找栈内节点们的右子节点：

当栈顶的节点与中序遍历当前的节点值相同时，说明我们经过了当前根节点的先序遍历中的最后一个左子节点。
当前先序数组指针指向了当前栈内节点一个右子节点。

栈内：[根节点 - 左子节点]
先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

此时我们开始向右移动中序遍历的指针，寻找先序遍历指针中的节点应该是当前栈内哪一个节点的右子节点。
此时栈内节点的顺序，与中序遍历的左子节点顺序正好相反。当栈顶与中序遍历的指针相等时，挤出栈顶并将中序指针右移，直到两者不相等或栈空。
此时将最后挤出的根节点的右子节点设置为当前先序数组对应的节点，继续遍历下一个先序数组。

当遍历完成后，返回根节点即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int j = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.add(root);
        
        for(int i = 1; i < preorder.length; i++){
            TreeNode curr = new TreeNode(preorder[i]);
            TreeNode prev = stack.peek();
            if(inorder[j] != prev.val){
                prev.left = curr;
                stack.add(curr);
            }
            else{
                while(!stack.isEmpty() && inorder[j] == stack.peek().val){
                    prev = stack.pop();
                    j++;
                }
                prev.right = curr;
                stack.add(curr);
            }
        }
        return root;
    }
}

Posted 2022-04-30Updated 2022-04-29LeetCode / Easy / 复习a minute read (About 203 words)

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.

void push(int val) pushes the element val onto the stack.

void pop() removes the element on the top of the stack.

int top() gets the top element of the stack.

int getMin() retrieves the minimum element in the stack.

分别将数据保存在一个Priority Queue和一个栈中。
pop方法pop掉stack的内容，然后将其从优先队列中移除。
top方法返回stack的栈顶。
getMin方法返回优先队列的顶。

class MinStack {
    Queue<Integer> pq;
    Stack<Integer> stack;
    public MinStack() {
        pq = new PriorityQueue<>();
        stack = new Stack<>();
    }
    
    public void push(int val) {
        pq.add(val);
        stack.add(val);
    }
    
    public void pop() {
        int i = stack.pop();
        pq.remove(i);
        
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return pq.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Posted 2022-04-25Updated 2022-04-24LeetCode / Mediuma minute read (About 217 words)

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.

使用队列储存迭代器里的数据，根据需要返回队列里的数据。

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    Queue<Integer> q;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
	    q = new LinkedList<>();
        while(iterator.hasNext()){
            q.add(iterator.next());
        }
	}
	
    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        return q.peek();
	}
	
	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
	    return q.poll();
	}
	
	@Override
	public boolean hasNext() {
	    return !q.isEmpty();
	}
}

Posted 2022-04-18Updated 2022-04-19LeetCode / Easy / 复习3 minutes read (About 431 words)

706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

哈希表，先设置一个素数Prime作为map的尺寸。
（这里设置成素数是为了减少可能的碰撞。）
创建一个Pair类记录key和value。

map初始化时需要生成一个LinkedList数组。

hash方法计算哈希值。用key % Prime并返回。
put方法，根据key计算其哈希值h。如果列表中有则重新设置当前Pair的value。
get方法，根据哈希值h搜索并查找链表中的Pair，如果找到则返回Pair，否则返回-1。
remove方法，根据哈希值h搜索并remove链表中的Pair。

class MyHashMap {
    final int PRIME = 1009;
    List<Pair>[] map;
    public MyHashMap() {
        map = new LinkedList[PRIME];
        for(int i = 0; i < PRIME; i++){
            map[i] = new LinkedList<Pair>();
        }
    }
    
    public void put(int key, int value) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                p.setValue(value);
                return;
            }
        }
        Pair p = new Pair(key, value);
        map[h].add(p);
    }
    
    public int get(int key) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                return p.value;
            }
        }
        return -1;
    }
    
    public void remove(int key) {
        int h = hash(key);
        for(Pair p : map[h]){
            if(p.getKey() == key){
                map[h].remove(p);
                return;
            }
        }
    }
    
    private int hash(int key){
        return key % PRIME;
    }
}

class Pair {
    int key;
    int value;
    public Pair(int k, int v){
        key = k;
        value = v;
    }
    
    public int getKey(){
        return key;
    }
    public int getValue(){
        return value;
    }
    public void setValue(int v){
        value = v;
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

add()方法

search()方法

Code

Question

Solution

前缀树 Trie

TrieNode节点

insert()方法

search()方法

startsWith()方法

Code

Question

Solution 1

Code

Solution 2

递归方法 minCam()

树形dp优化剪枝

Code

Code

Question

Solution

Code

Question

Solution

push()

top() & pop()

empty()

Code

Question

Solution

编码过程

解码过程

Code

Recents

Archives

Links