39. Combination Sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
题目：给定一个数组和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
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums.length < 4) return res;
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
if(i > 0 && nums[i] == nums[i - 1]) continue;
for(int j = i + 1; j < nums.length; j++){
if(j > i + 1 && nums[j] == nums[j -1]) continue;
int k = j + 1, l = nums.length - 1;
while(k < l){
int sum = nums[i] + nums[j] + nums[k] + nums[l];
if(sum == target){
res.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
while(k < l && nums[k] == nums[k + 1]) k++;
while(k < l && nums[l] == nums[l - 1]) l--;
k++;
l--;
}
else if(sum > target) l--;
else if(sum < target) k++;
}
}
}
return res;
}
}
56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.
题目：给定一组区间，将有重叠的区间合并。
思路：前一个区间的end如果大于等于后一个区间的start，则说明有重叠，如果后一个区间的end要大于前一个区间的end，那么就令后一个区间的end覆盖前一个区间的end，并删除后一个区间；反之，前一个区间完全包含了后一个区间，那么直接删除后一个区间。但是这个思路有一个前提是各个区间是按区间的start升序排序的，因此需要先重写sort方法，给区间排序。
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
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> merge(List<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval i1, Interval i2){
return i1.start - i2.start;
}
});
for(int i = 0; i < intervals.size() - 1; i++){
if(intervals.get(i).end >= intervals.get(i + 1).start){
if(intervals.get(i).end < intervals.get(i + 1).end){
intervals.get(i).end = intervals.get(i + 1).end;
}
intervals.remove(i + 1);
i -= 1;
}
}
return intervals;
}
}
74. Search a 2D matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
Example 1:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
题目：在一个矩阵中找出target。矩阵满足横向递增，，且每一行的第一个数字都比前一行的最后一个数字大，即纵向也是递增的。
思路：以右下角为起始搜索点，若此处比target大，则网上搜索；若比target小，则往右搜索。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length == 0 || matrix == null) return false;
int rlen = matrix.length, clen = matrix[0].length;
int i = rlen - 1, j = 0;
while(i >= 0 && j <= clen - 1){
if(matrix[i][j] > target) i--;
else if(matrix[i][j] < target) j++;
else return true;
}
return false;
}
}
34. Search for a Range
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
题目：在排序数组中找出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
34
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums == null || nums.length == 0) return new int[]{-1, -1};
return new int[]{findStart(nums, target), findEnd(nums, target)};
}
public int findStart(int[] nums, int target){
int start = 0, end = nums.length - 1;
while(start <= end){
int mid = (start + end) / 2;
if(nums[mid] < target) start = mid + 1;
else if(nums[mid] > target) end = mid - 1;
else if(nums[mid] == target && mid > 0){
while(mid > 0 && nums[mid - 1] == nums[mid] ) mid--;
return mid;
}
else return mid;
}
return -1;
}
public int findEnd(int[] nums, int target){
int start = 0, end = nums.length - 1;
while(start <= end){
int mid = (start + end) / 2;
if(nums[mid] < target) start = mid + 1;
else if(nums[mid] > target) end = mid - 1;
else if(nums[mid] == target && mid < nums.length - 1){
while(mid < nums.length - 1 && nums[mid + 1] == nums[mid]) mid++;
return mid;
}
else return mid;
}
return -1;
}
}
35. Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5
Output: 2
Example 2:
Input: [1,3,5,6], 2
Output: 1
Example 3:
Input: [1,3,5,6], 7
Output: 4
Example 4:
Input: [1,3,5,6], 0
Output: 0
题目：在数组中找出target的位置，若 target不在数组中，返回插入位置。
思路：排序数组，用二分查找，若不存在，则返回start位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int searchInsert(int[] nums, int target) {
if(nums.length == 0 || nums == null) return 0;
int start = 0, end = nums.length - 1;
while(start <= end){
int mid = (start + end) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) start = mid + 1;
else if(nums[mid] > target) end = mid - 1;
}
return start;
}
}