Category: Easy

Posted 2022-04-15Updated 2022-04-14LeetCode / Easy / 复习2 minutes read (About 263 words)

问题
You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

递归，传入根节点，进行BFS搜索。
如果当前节点小于搜索的最低点，则抛弃该节点，继续搜索其右子节点。（由于是BST，右子节点大于节点本身）
如果当前节点大于搜索的最高点，则抛弃该节点，继续搜索其左子节点。
如果当前节点在搜索范围内，则保留该节点，继续递归该节点的两个子节点。
最后返回根节点。

/**
 * 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 trimBST(TreeNode root, int low, int high) {
        if(root == null){
            return null;
        }
        if(root.val < low){
            return trimBST(root.right, low, high);
        }
        if(root.val > high){
            return trimBST(root.left, low, high);
        }
        
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

Posted 2022-04-14Updated 2022-04-14LeetCode / Easy / 复习a minute read (About 206 words)

191. Number of 1 Bits

问题
Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.

In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

位运算，[n-1]的二进制数字为[n]的二进制数字退一位。
二者的与运算结果相当于二进制下[n]减少最右侧的1。
例如0100100的0100011
两者的与运算结果为0100000。相当于减少了一位1。
计算循环次数就可以得出1的总数。

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            n = (n & (n-1));
            count++;
        }
        return count;
    }
}

Posted 2022-04-14Updated 2022-04-14LeetCode / Easy / 复习a minute read (About 163 words)

231. Power of Two

问题
Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

位运算，由于2^n^的二进制为[100…00]，当2^n^-1时，其二进制为[11..11]（少一位）。
两者进行按位与（&）运算，得到[000…00]，与0相等。

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0){
            return false;
        }
        return (n & (n - 1)) == 0;
    }
}

递归，当（n <= 0）时，返回false。
当n等于1时，返回true。
当（n % 2）有余数时，返回false。
递归（n / 2）。

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0){
            return false;
        }
        if (n == 1){
            return true;
        }
        if (n%2 != 0){
            return false;
        }
        return isPowerOfTwo(n/2);
    }
}

Posted 2022-04-14Updated 2022-05-02LeetCode / Easy / 复习a minute read (About 216 words)

112. Path Sum

问题
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

递归，如果当前节点为null则返回false。
计算并更新当前节点的值。
如果当前节点为叶节点，且当前节点的值等于target，则返回true。
递归左子节点和右子节点，返回两者的或运算。

/**
 * 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 boolean hasPathSum(TreeNode root, int targetSum) {
        return hasPathSum(root,0,targetSum);
    }
    
    private boolean hasPathSum(TreeNode root, int parentVal, int target){
        if (root == null){return false;}
        root.val = root.val + parentVal;
        if (root.left == null && root.right == null && root.val == target){
            return true;
        }
        return ( hasPathSum(root.left, root.val, target) || hasPathSum(root.right, root.val, target));
    }
}

Posted 2022-04-14Updated 2022-04-13LeetCode / Easya minute read (About 188 words)

700. Search in a Binary Search Tree

问题
You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

搜索二叉树。
递归，如果现有根节点为空则返回空。
如果根节点的值大于搜索值则搜索其左子节点。
如果根节点的值小于搜索值则搜索其左右节点。

/**
 * 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 searchBST(TreeNode root, int val) {
        if (root == null){
            return null;
        }
        else if (root.val < val){
            return searchBST(root.right,val);
        }
        else if (root.val > val){
            return searchBST(root.left,val);
        }
        else{
            return root;
        }
    }
}

Posted 2022-04-13Updated 2022-04-13LeetCode / Easya minute read (About 156 words)

226. Invert Binary Tree

问题
Given the root of a binary tree, invert the tree, and return its root.

翻转二叉树。
交换当前节点的左右子节点。
分别递归其左右子节点。
当当前节点的两个节点均为null时返回。

/**
 * 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 invertTree(TreeNode root) {
        if (root == null){
            return root;
        }
        invert(root);
        return root;
    }
    
    private void invert(TreeNode root){
        if ( root.left == null && root.right == null){
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        if ( root.left != null ){
            invert(root.left);
        }
        if ( root.right != null ){
            invert(root.right);
        }
    }
}

Posted 2022-04-13Updated 2022-04-13LeetCode / Easya minute read (About 187 words)

101. Symmetric Tree

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

递归root1的左子节点和root2的右子节点以及root2的左子节点以及root1的右子节点。如两者不相等则返回false。
如果传入的两个数值有一个为null，则两者不相等时返回false。反之返回true。

/**
 * 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 boolean isSymmetric(TreeNode root) {
        return isSymmetric(root,root);
    }
    
    public boolean isSymmetric(TreeNode root1, TreeNode root2){
        if ( root1 == null || root2 == null ){
            if(root1 == root2){return true;}
            else{return false;}
        }
        if ( root1.val == root2.val ){
            return isSymmetric(root1.left,root2.right) && isSymmetric(root1.right,root2.left);
        }
        else{
            return false;
        }
    }
}

Posted 2022-04-13Updated 2022-04-13LeetCode / Easy / 复习a minute read (About 215 words)

104. Maximum Depth of Binary Tree

问题
Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

递归，每次返回左子节点和右子节点中较大的结果+1。
当节点为null时返回0。

/**
 * 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 maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

BFS搜索，每次倾倒出队列里所有的元素并将level+1。
搜索完毕返回level。

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> q = new LinkedList();
        q.offer(root);
        int level = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for (int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                if(curr.left!=null){q.offer(curr.left);}
                if(curr.right!=null){q.offer(curr.right);}
            }
            level++;
        }
        return level;
    }
}

Posted 2022-04-12Updated 2022-04-11LeetCode / Easya minute read (About 126 words)

145. Binary Tree Postorder Traversal

问题
Given the root of a binary tree, return the postorder traversal of its nodes’ values.

后序遍历。
先递归左子节点。
然后递归右子节点。
最后将当前节点加入数组。

/**
 * 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 {
    List<Integer> ans;
    public List<Integer> postorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        traversal(root.left);
        traversal(root.right);
        ans.add(root.val);
        return;
    }
}

Posted 2022-04-12Updated 2022-04-11LeetCode / Easya minute read (About 126 words)

94. Binary Tree Inorder Traversal

问题
Given the root of a binary tree, return the inorder traversal of its nodes’ values.

中序遍历。
先递归左子节点。
然后将当前节点加入数组。
最后递归右子节点。

/**
 * 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 {
    List<Integer> ans;
    public List<Integer> inorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        traversal(root.left);
        ans.add(root.val);
        traversal(root.right);
        return;
    }
}

Posted 2022-04-12Updated 2022-04-11LeetCode / Easya minute read (About 126 words)

144. Binary Tree Preorder Traversal

问题
Given the root of a binary tree, return the preorder traversal of its nodes’ values.

先序遍历。
先将当前节点加入数组。
然后递归左子节点。
最后递归右子节点。

/**
 * 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 {
    List<Integer> ans;
    public List<Integer> preorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        ans.add(root.val);
        traversal(root.left);
        traversal(root.right);
        return;
    }
}

Posted 2022-04-12Updated 2022-04-11LeetCode / Easy / 复习2 minutes read (About 320 words)

232. Implement Queue using Stacks

问题
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue.

int pop() Removes the element from the front of the queue and returns it.

int peek() Returns the element at the front of the queue.

boolean empty() Returns true if the queue is empty, false otherwise.
Notes:

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

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

创建两个栈。
当入队列时，将元素压入第一个栈。
当出队列或进行其他操作时，如第二个栈为空，则将第一个栈的元素倒出到第二个栈。
此时第二个栈内的内容为顺序。

class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
        
    public MyQueue() {
        s1 = new Stack();
        s2 = new Stack();
    }
    
    public void push(int x) {
        s1.add(x);
    }
    
    public int pop() {
        if (s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.add(s1.pop());
            }
            return s2.pop();
        }
        else{
            return s2.pop();
        }
        
    }
    
    public int peek() {
        if (s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.add(s1.pop());
            }
            return s2.peek();
        }
        else{
            return s2.peek();
        }
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

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

Posted 2022-04-11Updated 2022-04-10LeetCode / Easya minute read (About 176 words)

1260. Shift 2D Grid

问题
Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

Element at grid[i][j] moves to grid[i][j + 1].
Element at grid[i][n - 1] moves to grid[i + 1][0].
Element at grid[m - 1][n - 1] moves to grid[0][0].
Return the 2D grid after applying shift operation k times.

遍历整个数组，将索引值加上移动的次数，得到新的位置。

class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        int row = grid.length;
        int col = grid[0].length;
        int size = row * col;
        Integer[][] mat = new Integer[row][col];
        
        for (int i = 0; i < size; i++){
            int j = i + k;
            if ( j > size - 1){
                j %= size;
            }
            int nr = j / col;
            int nc = j % col;
            int or = i / col;
            int oc = i % col;
            
            mat[nr][nc] = grid[or][oc];
        }
        
        for (int i = 0; i < row; i++){
            List<Integer> nums = Arrays.asList(mat[i]);
            ans.add(nums);
        }
        
        return ans;
    }
}

Posted 2022-04-11Updated 2022-04-20LeetCode / Easy2 minutes read (About 243 words)

682. Baseball Game

问题
You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds’ scores.

At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following:

An integer x - Record a new score of x.

“+” - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores.

“D” - Record a new score that is double the previous score. It is guaranteed there will always be a previous score.

“C” - Invalidate the previous score, removing it from the record. It is guaranteed there will always be a previous score.

Return the sum of all the scores on the record.

遍历选项，根据内容决定对ArrayList的操作。
然后遍历将ArrayList加和，返回。

class Solution {
    public int calPoints(String[] ops) {
        int ans = 0;
        List<Integer> records = new ArrayList();
        
        for (String op : ops){
            switch(op){
                case "+":
                    records.add(records.get(records.size()-1)+records.get(records.size()-2));
                    break;
                case "D":
                    records.add(records.get(records.size()-1)*2);
                    break;
                case "C":
                    records.remove(records.size()-1);
                    break;
                default:
                    records.add(Integer.parseInt(op));
            }
        }
        
        for (int record : records){
            ans += record;
        }                 
        return ans;
    }
}

Posted 2022-04-10Updated 2022-04-10LeetCode / Easy / 复习2 minutes read (About 319 words)

542. 01 Matrix

问题
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.

由于是搜索最近的距离，因此可以采用BFS搜索。
首先创建一个距离矩阵，将所有原矩阵为0的位置填上距离0，将其他位置填上无穷大。
使用BFS搜索，将所有0的坐标放入队列。
取出队列头元素，将其周围的距离矩阵的元素与自身距离矩阵的元素+1比较，将较小的值设置在周围的距离矩阵上。
同时，将改变数值的坐标再次放入队列。

class Solution{
    public int[][] updateMatrix(int[][] mat) {

        Queue<Integer> q = new LinkedList();
        int row = mat.length;
        int col = mat[0].length;
        int[][] ans = new int[row][col];
                                   
        for ( int i = 0; i < row; i++ ){
            for (int j = 0; j < col; j++){
                if (mat[i][j] == 0){
                    ans[i][j] = 0;
                    q.add(i*col + j);
                }
                else{
                    ans[i][j] = Integer.MAX_VALUE;
                }
            }
        }

            
        while(!q.isEmpty()){
            int i = q.peek() / col;
            int j = q.poll() % col;
            
            if(i-1 >= 0 && ans[i][j]+1 < ans[i-1][j]){
                ans[i-1][j] = ans[i][j]+1;
                q.add((i-1)*col + j);
            }
            if(i+1 < row && ans[i][j]+1 < ans[i+1][j]){
                ans[i+1][j] = ans[i][j]+1;
                q.add((i+1)*col + j);
            }
            if(j-1 >= 0 && ans[i][j]+1 < ans[i][j-1]){
                ans[i][j-1] = ans[i][j]+1;
                q.add(i*col + (j-1));
            }
            if(j+1 < col && ans[i][j]+1 < ans[i][j+1]){
                ans[i][j+1] = ans[i][j]+1;
                q.add(i*col + (j+1));
            }
        }
        return ans;
    }
}

Recents

Archives

Links