LeetCode(93) -- 153, 162, 209, 222, 230

P153. Find Minimum in Rotated Sorted Array (Medium)

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

My Solution

public class P153_FindMinimuminRotatedSortedArray {
    public int findMin(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (mid > 0 && nums[mid] < nums[mid - 1] || mid == 0 && nums[mid + 1] > nums[mid]) {
                return nums[mid];
            }
            if (nums[mid] >= nums[0]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if (l == nums.length) {
            return nums[0];
        }
        return l;
    }
}

100%

Solution

这个题坑其实挺多的。首先，如果这个数组并没有rotated，直接就是升序的，那怎么检测这种情况？我自己的办法是，如果最后退出循环时，l == nums.length，就说明找到最右边都没有，说明它的升序的。答案的办法是，如果最后一个数大于第一个数，那么这个数组就是升序的。

然后为了找关键点，我们必须发现的一个规律就是，所有在关键点左边的数，一定大于数组的第一个数；所有在关键点右边的数，一定小于数组的第一个数。

class Solution {
  public int findMin(int[] nums) {
    // If the list has just one element then return that element.
    if (nums.length == 1) {
      return nums[0];
    }

    // initializing left and right pointers.
    int left = 0, right = nums.length - 1;

    // if the last element is greater than the first element then there is no rotation.
    // e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
    // Hence the smallest element is first element. A[0]
    if (nums[right] > nums[0]) {
      return nums[0];
    }
    
    // Binary search way
    while (right >= left) {
      // Find the mid element
      int mid = left + (right - left) / 2;

      // if the mid element is greater than its next element then mid+1 element is the smallest
      // This point would be the point of change. From higher to lower value.
      // 之所以不会越界，是因为无论什么情况下，一定是从左边向右挤过去的。还没等越界，就已经符合条件跳出去了。
      if (nums[mid] > nums[mid + 1]) {
        return nums[mid + 1];
      }

      // if the mid element is lesser than its previous element then mid element is the smallest
      // 这个也是同样的道理，如果查到mid == 0时，其实这种情况早就检查过了，就是上面升序排列的情况。所以
      // mid - 1不可能越界
      if (nums[mid - 1] > nums[mid]) {
        return nums[mid];
      }

      // if the mid elements value is greater than the 0th element this means
      // the least value is still somewhere to the right as we are still dealing with elements
      // greater than nums[0]
      if (nums[mid] > nums[0]) {
        left = mid + 1;
      } else {
        // if nums[0] is greater than the mid value then this means the smallest value is somewhere to
        // the left
        right = mid - 1;
      }
    }
    return -1;
  }
}

还是这个代码比较干净漂亮。

P162. Find Peak Element (Medium)

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

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

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

Solution

public class P162_FindPeakElement {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

这个题最关键的是，没有目标条件。直到循环退出为止。

P209. Minimum Size Subarray Sum (Medium)

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Discuss

class Solution {
    public int minSubArrayLen(int s, int[] a) {
      if (a == null || a.length == 0)
        return 0;

      int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;

      while (j < a.length) {
        sum += a[j++];

        while (sum >= s) {
          min = Math.min(min, j - i);
          sum -= a[i++];
        }
      }

      return min == Integer.MAX_VALUE ? 0 : min;
    }
}

从第一个开始，始终保持一个sum >= s的状态。然后用前后两个pointer，依次加加减减，更新最短的长度。

P222. Count Complete Tree Nodes (Medium)

Given a complete binary tree, count the number of nodes.

Solution

class Solution {
    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes(TreeNode root) {
        int h = height(root);
        return h < 0 ? 0 :
               height(root.right) == h-1 ? (1 << h) + countNodes(root.right)
                                         : (1 << h-1) + countNodes(root.left);
    }
}

这代码写得相当魔幻。暂时理解不了。。。

P230. Kth Smallest Element in a BST (Medium)

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

My Solution

inorder 就是从小到大排列的，找到每k个就停止。

public class P230_KthSmallestElementinaBST {
    int k;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        return inorder(root);
    }

    private int inorder(TreeNode node){
        if (node == null) {
            return -1;
        }
        int left = inorder(node.left);
        if (left != -1) {
            return left;
        }
        k--;
        if (k == 0) {
            return node.val;
        }
        int right = inorder(node.right);
        if (right != -1) {
            return right;
        }
        return -1;
    }
}

虽然过了，不过感觉写得非常啰嗦，而且搞成-1也不严谨。

Solution

Recursion:

class Solution {
  public ArrayList<Integer> inorder(TreeNode root, ArrayList<Integer> arr) {
    if (root == null) return arr;
    inorder(root.left, arr);
    arr.add(root.val);
    inorder(root.right, arr);
    return arr;
  }

  public int kthSmallest(TreeNode root, int k) {
    ArrayList<Integer> nums = inorder(root, new ArrayList<Integer>());
    return nums.get(k - 1);
  }
}

我觉得可以设置一个变量，不需要所有节点都遍历。

Iteration:

class Solution {
  public int kthSmallest(TreeNode root, int k) {
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();

    while (true) {
      while (root != null) {
        stack.add(root);
        root = root.left;
      }
      root = stack.removeLast();
      if (--k == 0) return root.val;
      root = root.right;
    }
  }
}