ARTS Week 5

Algorithm

This week’s LeetCode problem is 102. Binary Tree Level Order Traversal

Description: Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level). Here is an example.

1
  / \
 2   3
/    /\
4   5  6
[[1],[2,3],[4,5,6]]

Solution Idea: the basic idea of hierarchical traversal, using a queue to record the current layer, and then traversing it, recording the values of the nodes and their left and right children. One thing to note: get the length of the queue before traversal (i.e. the length of the layer).

Accepted 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<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int length = queue.size();
            List<Integer> tmpArr = new ArrayList<>();
            for (int i = 0; i < length; i++) {
                TreeNode tmpNode = queue.poll();
                if (tmpNode ! = null) {
                    tmpArr.add(tmpNode.val);
                    queue.offer(tmpNode.left);
                    queue.offer(tmpNode.right);
                }
            }
            if (!tmpArr.isEmpty()) {
                ans.add(tmpArr);
            }
        }
        return ans;
    }
}

Review

This week’s Review is for the following article: Tools for thinking

In the article, the author introduces several tools he uses to record his own thinking. The first category is large files to record, and the second category is online web note tools such as Kinopio and Joplin.

1. Large text files or tables. Create a text file or table, this file is like a sticky note. You can write anything or content in this file, such as a cell phone number, something to do, the name of a book or movie you found good, something to buy, a temporary note, etc.. You can relieve your brain of the task by recording the content in the file, just like a memo in general. You can periodically organize the contents of this file to discover what needs to be kept for a long time. You can use any text editor to take notes, such as Notepad, Notepad++, VS Code, Vim, etc. The important thing to note is that you need to save this file in time so that it doesn’t lose information. Tables and text files are similar, depending on your needs.
2. Kinopio. Kinopio is quite interesting to use, you can visit its page to learn more.
3. Joplin. Joplin is great for taking notes about specific topics and linking them together, grouped by tags and notebooks. Looks a lot like Evernote, but Joplin differs from Evernote in that it supports Markdown and code highlighting, and it’s free.

Tip

Arithmetic Right Shift V.S. Logical Right Shift

We know that when computers represent signed integers, the first bit is called the sign bit and is used to identify positive and negative numbers. In an arithmetic right shift, the left-hand side is 0 or 1 depending on the original sign bit, while in a logical right shift, the left-hand side is always 0. That is, when shifting a negative number, you need to figure out whether you are doing a logical or an arithmetic right shift.

For example, -2 will be represented as 11111110 with 8 bits and the sign bit is 1, so an arithmetic right shift will result in 11111111 which is -1, while a logical right shift will result in 01111111 which is 127.

In Java, the >> operator represents an arithmetic right shift, while the >>> operator represents a logical right shift. The sample code is as follows.

public class Main {
    public static void main(String[] args) {
        int num1 = 2;
        System.out.println(num1 >> 2); // 0
        System.out.println(num1 >> 2); // 0
        int num2 = -2;
        System.out.println(num2 >> 2); // -1
        System.out.println(num2 >>>> 2); // 1073741823
    }
}

Share

Focus on the usual accumulation. This week’s ARTS was written in one go, but the actual writing didn’t go so smoothly because I spent a lot of time looking for material. This reminds me that I need to pay attention to accumulating material. Firstly, I don’t have to spend time to decide what to write about. Secondly, I can prepare the content and publish it when it’s ready. And thirdly I can use the time saved to create a new essay instead of ARTS.