Leetcode 270. Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:

• Given target value is a floating point.

• You are guaranteed to have only one unique value in the BST that is closest to the target.

Analysis:

Maintain a min value and update it with left and right .

Time complexity: O(logn)

Space complexity: O(1)

Code is below:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int closestValue(TreeNode root, double target) {
        // O(logn)
        
        int min = root.val;
        
        while (root != null) {
            min = Math.abs(target - root.val) < Math.abs(target - min) ? root.val : min;
            root = root.val < target ? root.right : root.left;
        }
        
        return min;
    }
}

Leetcode 151 & 186. Reverse Words in a String I& II

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue“,
return “blue is sky the“.

Analysis:

Use extra place. To split the whole string and get a string array, then go from the back and put them in a new string.

Time complexity : O(n)

Space complexity: O(n)

Code is below:

public class Solution {
    public String reverseWords(String s) {
        // O(n) O(n)
        
        if (s == null || s.length() == 0) {
            return "";
        }
        
        s = s.trim();
        String[] str = s.split(" ");
        StringBuilder sb = new StringBuilder();
        
        for (int i = str.length - 1; i >= 0; i--) {
            if (!str[i].equals("")) {
                sb.append(str[i]).append(" ");
            }
        }
        
        return sb.toString().trim();
    }
}

Followup:
Could you do it in-place without allocating extra space?

Analysis:
Use str.toCharArray() to change it to char array. Then reverse the whole array. Scan the array, if find a ‘ ‘, then reverse it from beginning. Update the start.

Time complexity : O(n)

Space complexity: O(1)

Code is below:

public class Solution {
    public void reverseWords(char[] s) {
        // O(n) O(1)
        
        if (s == null || s.length == 0) {
            return;
        }
        
        // reverse the whole array
        reverse(s, 0, s.length - 1);
        
        //reverse part of the words
        for (int i = 0, start = 0; i <= s.length; i++) {
            if (i == s.length || s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
    }
    
    public void reverse(char[] s, int start, int end) {
        while (start < end) {
            char c = s[start];
            s[start] = s[end];
            s[end] = c;
            start++;
            end--;
        }
    }
}