153. Find Minimum in Rotated Sorted Array
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.
题目： 找出旋转数组中的最小值。 思路： 二分查找，若中间值大于左侧的值，说明旋转后的头部在中间值右侧；反之在左侧。找到left和right相邻之后，返回right。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
if(right == 1) return Math.min(nums[left], nums[right]);
while(left < right - 1){
if(nums[left] < nums[right]) return nums[left];
int mid = (left + right) / 2;
if(nums[mid] > nums[left]) left = mid;
else right = mid;
}
return nums[right];
}
}
46. Permutaions
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
题目： 找出全排列。 思路： 长度位n的数组中，将第一个元素与包括自身的每个元素交换，得到n个新的数组，将后面n-1长度的数组继续之前的操作，直到头尾重合。这组交换过后的数组就是一个排列。利用递归可以快速实现。
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
import java.util.ArrayList;
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
public void swap(int[] array, int i, int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public void generatePermute(int[] nums, int i){
if(i == nums.length - 1) {
List<Integer> current = new ArrayList<Integer>();
for (int a : nums) {
current.add(a);
}
res.add(current);
}
for(int j = i; j < nums.length; j++){
if(j == i || nums[j]!=nums[i]){
swap(nums, i, j);
generatePermute(nums, i+1);
swap(nums, i, j);
}
}
}
public List<List<Integer>> permute(int[] nums) {
if(nums.length == 0) return res;
generatePermute(nums, 0);
return res;
}
}
623. Add One Row to Tree
Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1.
The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root’s left subtree.
Example 1:
Input:
A binary tree as following:
4
/ \
2 6
/ \ /
3 1 5
v = 1
d = 2
Output:
4
/ \
1 1
/ \
2 6
/ \ /
3 1 5
题目：在二叉树的第d层插入值为v的节点，若d=1，则插入节点为根节点，原先根节点变成左孩子。
思路：利用队列存储每一层，并使用计数器判断是否到达n层。若到达，则新建值为v的节点，原先d+1层的左孩子成为新建左侧节点的左孩子，右孩子成为新建节点的右孩子，再令原先父节点的左孩子和右孩子分别为这两个新建的节点。
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
import java.util.ArrayList;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode addOneRow(TreeNode root, int v, int d) {
if(d == 1){
TreeNode newRoot = new TreeNode(v);
newRoot.left = root;
return newRoot;
}
ArrayList<TreeNode> layer = new ArrayList<TreeNode>();
layer.add(root);
int count = 1;
while(!layer.isEmpty()){
int len = layer.size();
count++;
for(int i = 0; i < len; i++){
TreeNode tmp = layer.remove(0);
if(tmp.right != null) layer.add(tmp.right);
if(tmp.left != null) layer.add(tmp.left);
if(count == d){
TreeNode node1 = new TreeNode(v);
TreeNode node2 = new TreeNode(v);
if(tmp.left != null) node1.left = tmp.left;
if(tmp.right != null) node2.right = tmp.right;
tmp.left = node1;
tmp.right = node2;
}
}
}
return root;
}
}