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];
}
}

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);
}
}

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);
}
}

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;
}
}

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;
}
}