Posted Updated LeetCode / Mediuma minute read (About 164 words)

230. Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

DFS搜索，遍历的时候更新全局变量count。
采用中序搜索，当count等于k时，将全局变量ans设置为root.val。
搜索完毕返回ans。

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
35
36
37
/**
 * 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 ans;
    int count;
    public int kthSmallest(TreeNode root, int k) {
        ans = -1;
        count = 0;
        dfs(root,k);
        return ans;
    }
    
    private void dfs(TreeNode root, int k){
        if(root == null){
            return;
        }
        dfs(root.left,k);
        count++;
        if (k == count){
            ans = root.val;
        }
        dfs(root.right,k);
    }
}
Posted Updated LeetCode / Easya minute read (About 210 words)

897. Increasing Order Search Tree

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

DFS搜索，在递归时将in-order遍历节点，并将其加入队列。
从队列中挤出节点，将上一个节点的右子节点设置为下一个节点。
同时需要将下一个节点的左子节点设置为null。
`

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
35
36
37
38
39
40
/**
 * 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 {
    Queue<TreeNode> q;
    public TreeNode increasingBST(TreeNode root) {
        q = new LinkedList();
        dfs(root);
        TreeNode head = q.poll();
        TreeNode curr = head;
        while(!q.isEmpty()){
            curr.left = null;
            curr.right = q.poll();
            curr = curr.right;
        }
        curr.left = null;
        return head;
    }
    
    private void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        q.offer(root);
        dfs(root.right);
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 243 words)

538. Convert BST to Greater Tree

问题
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

  • The left subtree of a node contains only >->- nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.
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
35
36
37
38
39
40
/**
 * 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;
 *     }
 * }
 */

DFS搜索，设置一个成员变量记录上一个节点的值。
先递归右侧节点。
设置当前节点的值为自身的值加上temp中的值。
更新temp中的值，再递归左侧节点。


class Solution {
    int temp;
    public TreeNode convertBST(TreeNode root) {
        temp = 0;
        dfs(root);
        return root;
    }
    
    private void dfs(TreeNode root){
        if(root == null){
            return;
        } 
        dfs(root.right);
        root.val += temp;
        temp = root.val;
        dfs(root.left);
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 291 words)

669. Trim a Binary Search Tree

问题
Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

DFS搜索，每次递归带上搜索的范围值。
如果当前节点小于搜索范围，递归当前节点的右子节点。
反之递归当前节点的左子节点。
如果当前节点在搜索范围中，则其左子节点等于递归后的左子节点，右子节点等于递归后的右子节点。
然后返回当前节点。

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
/**
 * 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 Updated LeetCode / Easy / 复习2 minutes read (About 263 words)

70. Climbing Stairs

问题
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，右子节点大于节点本身）
如果当前节点大于搜索的最高点，则抛弃该节点，继续搜索其左子节点。
如果当前节点在搜索范围内，则保留该节点，继续递归该节点的两个子节点。
最后返回根节点。

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
/**
 * 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 Updated LeetCode / 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.

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

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
/**
 * 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 Updated LeetCode / Mediuma minute read (About 140 words)

59. Spiral Matrix II

问题
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

循环，创建一个上界和一个下界。
当达到界限时，改变方向。
更新上界和下界的数值。
当上界小于下界时返回。

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
35
36
37
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int upperBound = n;
        int lowerBound = 0;
        int i = 0;
        int j = 0;
        int count = 1;
        ans[0][0] = 1;
 
        while ( lowerBound < upperBound ){
            while ( j < upperBound-1 ){
                j++;
                count++; 
                ans[i][j] = count;           
            }
            while ( i < upperBound-1 ){
                i++;
                count++;
                ans[i][j] = count;
            }
            while ( j > lowerBound ){
                j--;
                count++;
                ans[i][j] = count;
            }
            upperBound--;
            lowerBound++;
            while ( i > lowerBound ){
                i--;
                count++;
                ans[i][j] = count;
            }
        }
        return ans;
    }
}
Posted Updated LeetCode / Medium3 minutes read (About 381 words)

289. Game of Life

问题
According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  1. Any live cell with fewer than two live neighbors dies as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population.
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

辅助方法，计算每个位置四周有生命的总和。
根据规则填写到新数组。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public void gameOfLife(int[][] board) {
        int[][] ans = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                int neighbors = countNeighbors(board, i, j);
                if ( neighbors < 2 && board[i][j] == 1 ){
                    ans[i][j] = 0;
                }
                else if( neighbors <= 3 && board[i][j] == 1 ){
                    ans[i][j] = 1;
                }
                else if( neighbors > 3 && board[i][j] == 1 ){
                    ans[i][j] = 0;
                }
                else if( neighbors == 3 && board[i][j] == 0){
                    ans[i][j] = 1;
                }
                
            }
        }
        
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                board[i][j] = ans[i][j];
            }
        }
    }
    
    
    private int countNeighbors(int[][] board, int r, int c){
        int neighbors = 0;
        int row = board.length;
        int col = board[0].length;
        
        if(r + 1 < row && board[r+1][c] == 1){ neighbors++; }
        if(r - 1 >= 0 && board[r-1][c] == 1){ neighbors++; }
        if(c + 1 < col && board[r][c+1] == 1){ neighbors++; }
        if(c - 1 >= 0 && board[r][c-1] == 1){ neighbors++; }
        
        if(r + 1 < row && c + 1 < col && board[r+1][c+1] == 1){ neighbors++; }
        if(r + 1 < row && c - 1 >= 0 && board[r+1][c-1] == 1 ){ neighbors++; }
        if(r - 1 >= 0 && c + 1 < col && board[r-1][c+1] == 1 ){ neighbors++; }
        if(r - 1 >= 0 && c - 1 >= 0 && board[r-1][c-1] == 1 ){ neighbors++; }
        
        return neighbors;
    }
}
Posted Updated LeetCode / 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.

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

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
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 Updated LeetCode / 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:

  1. An integer x - Record a new score of x.
  2. “+” - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores.
  3. “D” - Record a new score that is double the previous score. It is guaranteed there will always be a previous score.
  4. “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加和，返回。

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
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;
    }
}
695. Max Area of Island
Posted Updated LeetCode / Medium / 复习2 minutes read (About 292 words)

695. Max Area of Island

Question

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Solution

DFS搜索, 维护一个变量count，为连续执行DFS搜索的次数。
遍历地图上所有为1的位置。

运行BFS时每次将全局变量count增加1。
执行完毕后BFS时将全局变量count清零。

遍历每个等于1的地图块。
递归周围四个地图块，当超越数组范围，或者当前位置不为1时返回。
进行搜索时将搜索过的地图块标记为0，不再重复搜索。

Code

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
class Solution {
    int[][] visited, directions;
    int count;
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int x = 0; x < grid.length; x++){
            for(int y = 0; y < grid[0].length; y++){
                if(grid[x][y] == 1){
                    count = 0;
                    dfs(grid, x, y);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }
    
    private void dfs(int[][] grid, int x, int y){
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) return;
        grid[x][y] = 0;
        count++;
        for(int[] direction : directions){
            int i = x + direction[0];
            int j = y + direction[1];
            dfs(grid, i, j);
        }
    }
}
Posted Updated LeetCode / Mediuma minute read (About 176 words)

347. Top K Frequent Elements

Question

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Solution

遍历，使用哈希表保存遍历次数。
再次遍历，根据元素出现的次数将其填入优先级队列实现的大根堆。
遍历取出k个最大值。

  • getOrDefault()：
    方便的遍历并生成哈希表。
  • lambda：
    （）内表示传入的数值。
    -> 后表示返回值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ans = new int[k];
        HashMap<Integer,Integer> map = new HashMap();
        for (int num : nums){
            map.put( num, map.getOrDefault(num , 0) + 1 );
        }
        PriorityQueue<Integer> pq = new PriorityQueue((a,b) -> map.get(b) - map.get(a));
        for (int key : map.keySet()){
            pq.add(key);
        }
        for (int i = 0; i < k ; i++){
            ans[i] = pq.poll();
        }
        return ans;
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 175 words)

703. Kth Largest Element in a Stream

问题
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

  • KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
  • int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

优先级队列，插入所有元素，小元素在前。
当队列长度大于k时，poll掉前面的元素。

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
class KthLargest {
    PriorityQueue<Integer> pq;
    int kth;
    public KthLargest(int k, int[] nums) {
        pq = new PriorityQueue<Integer>();
        kth = k;
        for (int num : nums){
            pq.add(num);
        }
    }
    
    public int add(int val) {
        pq.add(val);
        while (pq.size() > kth){
            pq.poll();
        }  
        return pq.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */
Posted Updated LeetCode / Easy / 复习a minute read (About 144 words)

680. Valid Palindrome II

问题
Given a string s, return true if the s can be palindrome after deleting at most one character from it.

双指针，字符串两边对比。
如果两边字符不相等，则更新两边指针，并分别传入辅助方法再次对比。
两个结果有一个是true则返回true。

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
class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right){
            if (s.charAt(left) == s.charAt(right) ){
                left++;
                right--;
            }
            else{
                return ( checkPalindrome(s, left+1, right) || checkPalindrome(s, left, right-1));
            }
        }
        return true;
    }
    private boolean checkPalindrome(String s, int left, int right){
        while (left < right){
            if (s.charAt(left)==s.charAt(right)){
                left++;
                right--;
            }
            else{
                return false;
            }
        }
        return true;
    }    
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 264 words)

923. 3Sum With Multiplicity

Given an integer array arr, and an integer target, return the number of tuples i, j, k such that i < j < k and arr[i] + arr[j] + arr[k] == target.

As the answer can be very large, return it modulo 109 + 7.

首先遍历元素，根据元素的值和出现次数建立哈希表。
然后再哈希表中选择三个元素，如果和等于target，则计算三个元素出现次数的乘积。
最后除以重复计算的次数。
由于数值较大，因此中途计算应该采用长整型long。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    public int threeSumMulti(int[] arr, int target) {
        //enumberate every element and put them into the map
        HashMap<Integer, Long> map = new HashMap<Integer, Long>();
        long count = 0;
        
        for ( int num : arr ){
            if (!map.containsKey(num)){
                map.put(num, (long)1);
            }
            else{
                map.put(num, map.get(num)+1);
            }
        }
        
        //traverse whole elements and select three numbers
        
        for ( int a : map.keySet() ){
            long totalA = map.get(a);
            for (int b : map.keySet()){
                long totalB = map.get(b);
                if ( a == b ){
                    if (totalB < 2){
                        continue;
                    }
                    totalB = totalB - 1;
                }

                int c = target - a - b;
                if ( map.containsKey(c) ){
                    long totalC = map.get(c);
                    long total = 0;
                    if ( a == b && b == c ){
                        total = totalA * totalB * ( totalC - 2 ) ;
                    }
                    else if ( b == c || a == c ){
                        total = totalA * totalB * ( totalC - 1 ) ;
                    }
                    else{
                        total = totalA * totalB * totalC;
                    }
                    if ( total > 0 ){
                        count += total;
                    }

                }
            }
        }
        count/=6;
        int ans = (int) (count % 1000000007);
            
        return ans;
    }
}

Follow

Recents

Archives

Links

×