这里不对每道题都做记录。
- 904题, Fruit Into Baskets,中等难度,题目比较难读懂,其实简单来说就是找出数组中长度最大的连续由2种元素构成的子数组,返回这个子数组的长度。HashMap+滑动窗口。
1 | class Solution { |
- 41题,First Missing Positive,找出给出的数组中没有出现的最小正整数。重点是要求时间复杂度O(n),另外空间复杂度O(1),那么只能覆盖原有数组
1 | class Solution { |
152,Maximum Product Subarray,寻找最大乘积的子数组。DP,保留一个到某一位来看的最大值和最小值。因为在数组中有负数的出现,所以到这一位为止的能得到的最大值,可能是由之前的最大值和这个数相乘得到,也可能是最小值和这个数相乘得到的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public int maxProduct(int[] nums) {
int global = nums[0]; //全局最优
int max = nums[0]; //记录局部最大值
int min = nums[0]; //记录局部最小值
for(int i = 1;i < nums.length; i++) { //注意从1开始
// 最大值一定在max*nums[i], min*nums[i]), nums[i]三个数之间
// 更新max,min
int maxTemp = Math.max(max * nums[i], min * nums[i]); //Math的max方法只能比较两个数的大小
int minTemp = Math.min(max * nums[i], min * nums[i]);
max = Math.max(maxTemp, nums[i]);
min = Math.min(minTemp, nums[i]);
global = Math.max(global, max);
}
return global;
}
}142,Linked List Cycle II,环形链表。置快指针每次走两步、慢指针每次走一步,当它们相遇时,表示该链表有环。然后再将slow指针指向头结点,slow和fast同时向前走,下一个相遇的点即是入环节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
fast = head; //fast指向头,同时变慢
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
}Spiral Matrix,螺旋矩阵,下边给个高票答案。
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
37class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if(matrix == null || matrix.length == 0) return res;
int rowBegin = 0;
int rowEnd = matrix.length - 1;
int colBegin = 0;
int colEnd = matrix[0].length - 1;
while(rowBegin <= rowEnd && colBegin <= colEnd) {
// Traverse Right
for(int i = colBegin; i <= colEnd; ++i) {
res.add(matrix[rowBegin][i]);
}
rowBegin++;
// Traverse Down
for(int i = rowBegin; i <= rowEnd; ++i) {
res.add(matrix[i][colEnd]);
}
colEnd--;
// Traverse Left
if(rowBegin <= rowEnd) {
for(int i = colEnd; i >= colBegin; i--) {
res.add(matrix[rowEnd][i]);
}
rowEnd--;
}
// Traver Up
if(colBegin <= colEnd) {
for(int i = rowEnd; i >= rowBegin; i--) {
res.add(matrix[i][colBegin]);
}
colBegin++;
}
}
return res;
}
}
39题,combination Sum,在给出的数中找到和为target的组合,回溯递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// 组合得到target
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
dfs(res,temp,target,candidates,0);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> temp, int target,int[] candidates, int j) {
if(target == 0) { //target为0,说明已找到合适的结果,将中间集加入结果集
res.add(new ArrayList<>(temp));
}
for (int i = j; i < candidates.length && target > candidates[i]; i++) {
temp.add(candidates[i]);
dfs(res, temp, target - candidates[i], candidates, i);
temp.remove(temp.size() - 1);
}
}
}63题. Unique Paths II,DP
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
36class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int row = obstacleGrid.length;
int col = obstacleGrid[0].length;
if(obstacleGrid[0][0] == 1){
return 0;
} else {
obstacleGrid[0][0] = 1; //左上开始计数为1
}
// 填充第一列和第一行
for (int i = 1; i < row; i++) { // 如果当前块无阻碍且前一块可走到当前块,当前块计数为1
if (obstacleGrid[i][0] == 0 && obstacleGrid[i-1][0] == 1) {
obstacleGrid[i][0] = 1;
}else {
obstacleGrid[i][0] = 0;
}
}
for (int i = 1; i < col; i++) {
if (obstacleGrid[0][i] == 0 && obstacleGrid[0][i-1] == 1) {
obstacleGrid[0][i] = 1;
}else {
obstacleGrid[0][i] = 0;
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (obstacleGrid[i][j] == 0) {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
}else {
obstacleGrid[i][j] = 0;
}
}
}
return obstacleGrid[row-1][col-1];
}
}56题,区间合并。这道题目分析之前先了解一下Arrays.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
31
32
33
34
35package test;
import java.util.Arrays;
import java.util.Comparator;
public class Solution28 {
public static void main(String[] args) {
//注意,要想改变默认的排列顺序,不能使用基本类型(int,double, char)
//而要使用它们对应的类
Integer[] a = {9, 8, 7, 2, 3, 4, 1, 0, 6, 5};
//定义一个自定义类MyComparator的对象
Comparator cmp = new MyComparator();
Arrays.sort(a, cmp);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
//Comparator是一个接口,所以这里我们自己定义的类MyComparator要implents该接口
//而不是extends Comparator
class MyComparator implements Comparator<Integer> {
public int compare(Integer o1, Integer o2) {
//如果o1小于o2,我们就返回正值,如果o1大于o2我们就返回负值,
//这样颠倒一下,就可以实现反向排序了
if (o1 < o2) {
return 1;
} else if (o1 > o2) {
return -1;
} else {
return 0;
}
}
}解法:
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
31import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
// 钉钉面试,数组合并
class Solution27 {
public int[][] merge(int[][] arr) {
Arrays.parallelSort(arr, Comparator.comparingInt(x -> x[0])); //lambda表达式,按照数组左端点排序
//匿名内部类写法
/* Arrays.sort(arr, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});*/
LinkedList<int[]> list = new LinkedList<>();
for (int i = 0; i < arr.length; i++) {
if (list.size() == 0 || list.getLast()[1] < arr[i][0]) {
list.add(arr[i]);//集合为空,或不满足条件,向后新增
} else {//满足条件,集合最后元素的end=最大值
list.getLast()[1] = Math.max(list.getLast()[1], arr[i][1]);
}
}
int[][] res = new int[list.size()][2];//生成结果数组
int index = 0;
while (!list.isEmpty()) {//遍历集合
res[index++] = list.removeFirst();//删除集合首元素
}
return res;
}
}
注:转载文章请注明出处,谢谢~