Posted Updated LeetCode / Medium / 复习4 minutes read (About 534 words)

173. Binary Search Tree Iterator

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.
Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

此方法不用将所有节点一次性入栈，而是在获得next时更新栈内的节点，因此更省时间。
将根节点的所有左子节点入栈，此时栈顶为最小值。
next方法：返回当前的栈顶节点。如果栈顶节点存在右子节点，则将其所有的左子节点入栈。
hasNext方法：返回栈是否为空的非值。

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
/**
 * 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 BSTIterator {
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        updateStack(root);
    }
    
    public int next() {
        TreeNode node = stack.pop();
        updateStack(node.right);
        return node.val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    private void updateStack(TreeNode root){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

DFS搜索，中序搜索，从右子节点至左子节点，先将所有元素入栈。
next方法：挤出栈顶并返回。
hasNext方法： 返回栈是否为空的非值。

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
/**
 * 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 BSTIterator {
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        initiateStack(root);
    }
    
    public int next() {
        return stack.pop().val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    private void initiateStack(TreeNode root){
        if(root == null){
            return;
        }
        initiateStack(root.right);
        stack.push(root);
        initiateStack(root.left);
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */
Posted Updated LeetCode / Medium / 复习2 minutes read (About 334 words)

844. Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

辅助方法getNextValid，返回下一个有效值。
将两个指针分别设置在两个字符串的尾部。
当两指针有一个大于0时，进行循环。
每次都搜索两个指针的下一个有效值。
如果两个指针上的字符不同则返回false。

最后返回两个指针的停留位置是否相同。

注意：
如果有一个字符串指针先更新到0以下，另一个指针仍有可能更新到一个“#”字符位置。
此时最后的结应该是两个空字符串。
因此需要继续循环一次，得出其是否会归到零以下。如果此时归零则两者的指针位置仍然相等。

因此即使getNextValid返回的下一个值为负数也应该保留其数值。

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
class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length()-1;
        int j = t.length()-1;

        while(i >= 0 || j >= 0){
            i = getNextValid(s, i);
            j = getNextValid(t, j);
            if( i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)){    
                return false;
            }
            i--;
            j--;
        }
        return (i == j);
    }
    
    private int getNextValid(String s, int start){
        int i = start;
        int count = 0;
        while(i >= 0 && (s.charAt(i) == '#' || count != 0)){
            if(s.charAt(i) == '#'){
                count++;
            }
            else{
                count--;
            }
            i--;
        }
        return i;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 341 words)

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.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * 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;
    boolean flag;
    TreeNode[] wrong;
    public void recoverTree(TreeNode root) {
        wrong = new TreeNode[2];
        prev = new TreeNode(Integer.MIN_VALUE);
        flag = true;
        
        dfs(root);
        
        int swap = wrong[0].val;
        wrong[0].val = wrong[1].val;
        wrong[1].val = swap;
        
        
    }
    
    private void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        if(prev.val > root.val){
            if(flag){
                wrong[0] = prev;
                flag = false;
            }
            wrong[1] = root;
        }
        prev = root;
        dfs(root.right);
    }
}
240. Search a 2D Matrix II
Posted Updated LeetCode / Medium / 复习a minute read (About 137 words)

240. Search a 2D Matrix II

Question

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Solution

将起始点设置为第一行的最后一列。
如果搜寻目标大于该点则向下搜索。
如果搜寻目标小于该点则向左搜索。

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        
        while(i < matrix.length && j >= 0){
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 228 words)

82. Remove Duplicates from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

使用队列暂存遍历的节点。
初始化prev为一个dummy节点。
如果当前节点不等于队列里节点的值，则倾倒出队列里的值。如果队列此时只有一个值，则将其添加到prev.next。
遍历完毕后如果队列内只有一个值则将其设置到prev.next。
最后返回dummy.next。

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
/**
 * 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 deleteDuplicates(ListNode head) {
        Queue<ListNode> q = new LinkedList();
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        ListNode curr = head; 
        while(curr != null){
            if(q.isEmpty() || curr.val == q.peek().val){
                q.offer(curr);
                curr = curr.next;
            }
            else{
                if(q.size()==1){
                    prev.next = q.poll();
                    prev = prev.next;
                    prev.next = null;
                }
                else{
                    q.clear();   
                }
            }
        }
        
        if(q.size()==1){
            prev.next = q.poll();
        }
        
        return dummy.next;
    }

}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 394 words)

162. Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

二分搜索，由于只需要搜索任意一个山峰，因此只要向上走，一定可以走到一个峰。
当中值的下一个值是增长时（向上爬山），则更新左侧指针的位置为中值+1。继续搜索下一个中值。
否则更新右侧指针的位置为当前中值，等于向左侧进行搜索。
最后返回左侧指针停留的位置。
时间复杂度为O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findPeakElement(int[] num) {
        int left = 0;
        int right = num.length - 1;

        while (left < right) {
            int mid1 = (right - left) / 2 + left;
            int mid2 = mid1 + 1;
            if (num[mid1] < num[mid2])
                left = mid1+1;
            else
                right = mid1;
        }
        return left;
    }
}

一次遍历，找到峰值，返回其index。
时间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findPeakElement(int[] nums) {
        int peak = 0;
        
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > nums[peak]){
                peak = i;
            }
        }
        return peak;
    }
}

分治法，每次将数组分为两组，向下递归。
当数组长度为1时返回元素，比较返回来的两个数值的大小。
返回其中的峰值index。
此解法时间为O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findPeakElement(int[] nums) {
        return findPeak(nums,0,nums.length-1);
    }
    
    private int findPeak(int[] nums, int left, int right){
        if(left == right){
            return left; 
        }
        int mid = left + (right - left) / 2;
        int i = findPeak(nums, left, mid);
        int j = findPeak(nums, mid+1, right);
        
        if(nums[i] > nums[j]){
            return i;
        }
        else{
            return j;
        }
    }
}
48. Rotate Image
Posted Updated LeetCode / Medium / 复习3 minutes read (About 505 words)

48. Rotate Image

Question

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Solution 1

此方法是in-place算法。

visited[][]数组记录访问情况，遍历所有位置，如果已访问则跳过。
循环替换矩阵上的每一个位置，如果已经访问过则break。
如果未访问则将要替换位置的值保存，并且在visited[][]数组上记录。
然后继续遍历替换过的位置。

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
class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] visited = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(visited[i][j] == 1) continue;
                int x = i, y = j;
                int value = matrix[i][j];
                while(true){
                    int s = n-1-x, t = y;
                    if(visited[t][s] == 1) break;
                    int temp = matrix[t][s];
                    matrix[t][s] = value;
                    value = temp;
                    visited[t][s] = 1;
                    x = t;
                    y = s;
                }
            }
        }
    }
}

Solution 2

此方法类似Solution 1，但是并非原地算法。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] mat = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int s = n-1-i, t = j;
                mat[t][s] = matrix[i][j];
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = mat[i][j];
            }
        }
    }
}

Solution 3

辅助方法getPixel计算旋转后的像素位置。
旋转时候矩阵内的四个分区的像素会互相替换。
因此需要将需要旋转的初始位置记录进入队列。
旋转图像时根据getPixel方法计算出需要替换的位置。
然后依次替换像素。

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
30
31
32
33
34
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        Queue<Integer> queue = new LinkedList();
        for (int p = 0; p < n/2; p++){
            for(int q = 0; q < (n+1)/2; q++){
                queue.offer(p * n + q);
            }
        }

        while(!queue.isEmpty()){
            int i = queue.poll();
            int INDEX = i;
            boolean flag = true;
            int temp = matrix[i/n][i%n];
            while(i != INDEX || flag ){
                flag = false;
                int j = getPixel(n, i);
                int swap = matrix[j / n][j % n];
                matrix[j / n][j % n] = temp; 
                temp = swap;
                i = j;
            }
        }     
    }
    
    private int getPixel(int n, int o){
        int row = o / n;
        int col = o % n;
        int newRow = col;
        int newCol = n - (row + 1);
        return (newRow * n) + newCol;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 256 words)

153. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

二分搜索，寻找断裂点。
当left小于right时循环。
每次计算出mid，分为两种情况：

  • 如果nums[mid]小于nums[nums.length-1]，则右半侧为顺序的。
  • 反之则左半侧为顺序，右半侧为无序的。
    以此来更新搜索范围。
    由于mid计算公式向下取整。
    当更新left时更新为mid+1，向前一格。
    当更新right时更新为mid。
    最后返回nums[left]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findMin(int[] nums) {
        return findBreakPoint(nums,0,nums.length-1);
    }
    
    private int findBreakPoint(int[] nums, int left, int right){
        while(left < right){
            int mid = (right - left)/2 + left;
            if(nums[mid] < nums[nums.length-1]){
                right = mid;
            }
            else if(nums[mid] >= nums[0]){
                left = mid+1;
            }
            
        }
        return nums[left];
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 295 words)

75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

快速排序是原地排序，因此此问题可以采用快速排序解决。

选择left上的元素pivot，设置一个指针index为left+1。
遍历left+1至right的数组，如果遍历的值小于pivot则将nums[i]与nums[index]交换，然后将index向右移动。

因此index左侧的元素均小于pivot，index右侧的元素均大于pivot。
最后将nums[index]与pivot交换，此时pivot左侧元素均小于它，右侧元素均大于它，因此index不需要再动。
然后分别向下递归left至index-1，index+1至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
class Solution {
    public void sortColors(int[] nums) {
        quickSort(nums, 0, nums.length-1);
    }
    
    private void quickSort(int[] nums, int left, int right){
        if( right - left < 1 ){
            return;
        }
        int pivot = nums[left];
        int index = left+1;
        for(int i = index; i <= right; i++){
            if(nums[i] < pivot){
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                index++;
            }
        }
        index--;
        
        nums[left] = nums[index];
        nums[index] = pivot;
        
        quickSort(nums,left,index-1);
        quickSort(nums,index+1,right);
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 303 words)

33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

二分搜索，二分后将会形成两个区间，一个区间是顺序的，另一个是无序的。
如果target等于中间值则返回。
分别处理两种情况下移动指针的方式。
当顺序区间在左半边时：
当target在顺序区间内，则更新右指针的位置。
否则更新左指针位置。
当顺序区间在右半边时：
当target在顺序区间内，则更新左指针的位置。
否则更新右指针位置。

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 Solution {
    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length-1;
        
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target){
                return mid;
            }
            
            if( nums[mid] >= nums[0] ){
                if(target >= nums[0] && target < nums[mid] ){
                    right = mid - 1;
                }
                else{
                    left = mid + 1;
                }
            }
            else{
                if(target > nums[mid] && target <= nums[nums.length-1]){
                    left = mid + 1;
                }
                else{
                    right = mid -1;
                }
            }

        }
        return -1;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 355 words)

15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

三数之和，重点是如何遍历后去除重复的数组。
首先对数组进行排序。
遍历数组，三个数中最小的数字为nums[i]。
此时需要去除重复的nums[i]。如重复则继续下一次循环。
此时设置双指针left和right，分别在nums[i]右侧的子数组的首尾。

  • 当nums[i] + nums[left] + nums[right] > 0时，后两个数的和需要减小，right指针向左移动。
  • 当nums[i] + nums[left] + nums[right] < 0时，后两个数的和需要增大，left指针向右移动。
  • 当nums[i] + nums[left] + nums[right] = 0时，找到一个组合。
    此时需要去除重复的nums[left]和nums[right]。如重复则更新left或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
31
32
33
34
35
36
37
38
39
40
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length; i++){
            int left = i+1;
            int right = nums.length-1;
            if(i>0 && nums[i] == nums[i-1]){
                continue;   
            }
            
            while(left < right){
                if(nums[i]+nums[left]+nums[right]==0){
                    while(left+1 < nums.length && nums[left] == nums[left+1]){
                        left++;
                    }
                    while(right-1 > i && nums[right] == nums[right-1]){
                        right--;
                    }
                    List<Integer> list = new ArrayList();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    ans.add(list);
                    
                    left++;
                    right--;
                }
                else if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return ans;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 315 words)

34. Find First and Last Position in Sorted Array

问题
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

二分搜索，搜索中间项。
中间项等于左侧和右侧指针的中点，根据搜索左侧边界和右侧边界选择二分向下舍去或是二分向上补足。
当中间项小于目标，则更新左侧边界。
若中间项大于目标，则更新右侧边界。
当中间项等于目标时，根据搜索左侧边界还是右侧边界选择更新左侧或右侧。
由于有可能有重复元素存在，因此需要继续二分搜索下去，直到右侧边界大于左侧边界。

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{searchLeft(nums,target),searchRight(nums,target)};
    } 

    private int searchRight(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                left = mid+1;
            }
        }
        return result;
    }
    
    private int searchLeft(int[] nums, int target){
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int result = -1;
        
        while(left <= right){
            mid = (right-left+1)/2+left;
            if(nums[mid] < target){
                left = mid+1;
            }
            else if(nums[mid] > target){
                right = mid-1;
            }
            else{
                result = mid;
                right = mid-1;
            }
        }
        return result;
    }
}
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 / Medium / 复习2 minutes read (About 295 words)

120. Triangle

问题
Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

动态规划，先将最左侧一列的值算出。
然后[i+1][j+1]根据[i][j+1]和[i][j]得出。
该动态规划表应是为三角形。
因此当i等于j时，[i+1][i+j]的数值只根据[i][j]得出。

例子：
代码里插入了一个print方法打印动态规划表。
当输入列表 [[2],[3,4],[6,5,7],[4,1,8,3]] 时：
其动态规划表为：

  • 2, 0, 0, 0,
  • 5, 6, 0, 0,
  • 11, 10, 13, 0,
  • 15, 11, 18, 16,
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
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size()][triangle.size()];
        int min = Integer.MAX_VALUE;
        dp[0][0] = triangle.get(0).get(0);
        
        for (int i = 0; i < triangle.size()-1; i++){
            dp[i+1][0] = dp[i][0] + triangle.get(i+1).get(0);
        }        
        
        for (int i = 0; i < triangle.size()-1; i++){
            for (int j = 0; j <= i; j++){
                
                if ( i == j ){
                    dp[i+1][j+1] = dp[i][j] + triangle.get(i+1).get(j+1);
                }
                else{
                    dp[i+1][j+1] = Math.min(dp[i][j] + triangle.get(i+1).get(j+1),
                                        dp[i][j+1] + triangle.get(i+1).get(j+1));
                }
                
            }
        }
        //print(dp);
        for (int k = 0; k < triangle.size(); k++){
            min = Math.min(dp[triangle.size()-1][k],min);
        }
        return min;
    }
    
    private void print(int[][] text){
        for (int i = 0; i <text.length; i++){
            for (int j = 0; j < text[0].length; j++){
                System.out.print(text[i][j]+", ");
            }
            System.out.println();
        }
    }

}
Posted Updated LeetCode / Medium / 复习a minute read (About 224 words)

784. Letter Case Permutation

答案
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any 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
38
class Solution {
    List<String> ans;
    String _s;
    public List<String> letterCasePermutation(String s) {
        ans = new ArrayList();
        _s = s;
        
        backTrack(new StringBuilder(),0);
        return ans;
        
    }
    
    private void backTrack(StringBuilder sb, int i){
        if(i == _s.length()){
            ans.add(sb.toString());
            return;
        }
        char curr = _s.charAt(i);
        if ( isNums(curr) ){
            sb.append(curr);
            backTrack(sb, i+1);
        }
        else{
            StringBuilder sb2 = new StringBuilder(sb);
            sb.append(Character.toLowerCase(curr));
            backTrack(sb, i+1);
            sb2.append(Character.toUpperCase(curr));
            backTrack(sb2, i+1);
        }
    }
    
    private boolean isNums(char c){
        if ( (int)c >= (int)'0' && (int)c <= (int)'9' ){
            return true;
        }
        return false;
    }
}
Follow

Recents

Archives

Links

×