718. 最长重复子数组
53. 最大子序和
54. 螺旋矩阵
55. 跳跃游戏
56. 合并区间
---------------------------------分割线-----------------------------------------
718. 最长重复子数组
Difficulty: 中等
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 1:
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。
说明:
1 <= len(A), len(B) <= 10000 <= A[i], B[i] < 100
Solution:动态规划
（关键地方）定义状态：dp[i][j]是以A[i]和B[j] 结尾 的字母的最长子数组的长度，这样才需要更新状态
class Solution {
public int findLength(int[] A
, int[] B
) {
int[][] dp
= new int[A
.length
+1][B
.length
+1];
int res
= 0;
for(int i
=1; i
<=A
.length
; i
++){
for(int j
=1; j
<=B
.length
; j
++){
if(A
[i
-1] == B
[j
-1]) dp
[i
][j
] = dp
[i
-1][j
-1]+1;
else dp
[i
][j
] = 0;
res
= Math
.max(dp
[i
][j
], res
);
}
}
return res
;
}
}
53. 最大子序和
Difficulty: 简单
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
Solution：num[i] 之前的还要不要
class Solution {
public int maxSubArray(int[] nums
) {
int count
= nums
[0], sum
= nums
[0];
for(int i
=1; i
<nums
.length
; i
++){
if(count
> 0){
count
+= nums
[i
];
}
else{
count
= nums
[i
];
}
sum
= Math
.max(sum
, count
);
}
sum
= Math
.max(sum
, count
);
return sum
;
}
}
54. 螺旋矩阵
Difficulty: 中等
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
Solution：确定四个角，这样方便遍历，注意：下 可能和 上 重复， 左 可能和 右 重复
class Solution {
public List
<Integer> spiralOrder(int[][] matrix
) {
List
<Integer> res
= new ArrayList<>();
int top
, bottom
, left
, right
, m
, n
;
m
= matrix
.length
;
if(m
<= 0) return res
;
n
= matrix
[0].length
;
if(n
<= 0) return res
;
top
= 0;
left
= 0;
bottom
= m
-1;
right
= n
-1;
while(top
<= bottom
&& left
<= right
){
for(int i
=left
; i
<=right
; i
++){
res
.add(matrix
[top
][i
]);
}
for(int i
=top
+1; i
<=bottom
; i
++){
res
.add(matrix
[i
][right
]);
}
if(top
!= bottom
){
for(int i
=right
-1; i
>=left
; i
--){
res
.add(matrix
[bottom
][i
]);
}
}
if(left
!= right
){
for(int i
=bottom
-1; i
>top
; i
--){
res
.add(matrix
[i
][left
]);
}
}
top
++;
bottom
--;
left
++;
right
--;
}
return res
;
}
}
55. 跳跃游戏
Difficulty: 中等
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
Solution：贪心算法，从右到左寻找最大的跳数
class Solution {
public boolean canJump(int[] nums
) {
int len
= nums
.length
, index
;
if(len
<= 0) return false;
index
= len
-1;
while(index
> 0){
int flag
= index
;
for(int i
=index
-1; i
>=0; i
--){
if(index
-i
<= nums
[i
]){
index
= i
;
}
}
if(flag
== index
) return false;
}
return true;
}
}
56. 合并区间
Difficulty: 中等
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
Solution：先对区间的第一维进行排序，然后找每个小区间的最大值和最小值
import java
.util
.ArrayList
;
import java
.util
.HashMap
;
import java
.util
.List
;
import java
.util
.Random
;
class Solution {
public int[][] merge(int[][] intervals
) {
List
<int[]> res
= new ArrayList<>();
int len
= intervals
.length
;
if(len
<= 0) return new int[0][2];
quickSort(intervals
);
int low
= intervals
[0][0], high
= intervals
[0][1];
for(int i
=1; i
<len
; i
++){
if(high
< intervals
[i
][0]){
int[] temp
= new int[2];
temp
[0] = low
;
temp
[1] = high
;
res
.add(temp
);
low
= intervals
[i
][0];
high
= intervals
[i
][1];
}
else{
high
= Math
.max(high
, intervals
[i
][1]);
}
}
int[] temp
= new int[2];
temp
[0] = low
;
temp
[1] = high
;
res
.add(temp
);
int[][] val
= new int[res
.size()][2];
for(int i
=0; i
<res
.size(); i
++){
val
[i
] = res
.get(i
);
}
return val
;
}
public void quickSort(int[][] intervals
){
sortHelp(intervals
, 0, intervals
.length
-1);
}
Random random
= new Random();
public void sortHelp(int[][] intervals
, int low
, int high
){
if(low
> high
) return;
int flag
= random
.nextInt(high
-low
+1)+low
;
int partition
= intervals
[flag
][0];
swap(intervals
, low
, flag
);
int l
= low
, h
= high
;
while(l
< h
){
while(l
<h
&& intervals
[h
][0]>=partition
){
h
--;
}
if(l
<h
){
swap(intervals
, l
, h
);
}
while(l
<h
&& intervals
[l
][0]<=partition
){
l
++;
}
if(l
<h
){
swap(intervals
, l
, h
);
}
}
sortHelp(intervals
, low
, l
-1);
sortHelp(intervals
, l
+1, high
);
}
public void swap(int[][] intervals
, int i
, int j
){
int[] temp
= intervals
[i
];
intervals
[i
] = intervals
[j
];
intervals
[j
] = temp
;
}
}
