hot100
# 哈希
# 1. 两数之和 (opens new window)
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] ret = new int[2];
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
int tmp = target-nums[i];
if(map.containsKey(tmp)){
ret[0] = map.get(tmp);
ret[1] = i;
}
map.put(nums[i],i);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 49. 字母异位词分组 (opens new window)
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(String str:strs){
char[] ch = str.toCharArray();
Arrays.sort(ch);
String key = new String(ch);
map.computeIfAbsent(key,e->new ArrayList<>()).add(str);
}
return new ArrayList<>(map.values());
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 128. 最长连续序列 (opens new window)
方法一：滑动窗口
如果是左边界，寻找其连续序列的右边界；
class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for(int num:nums){
map.put(num,num);
}
int ret = 0;
for(int l:nums){
if(!map.containsKey(l-1)){ //寻找其左边界
int r = l;
while(map.containsKey(r+1))
r++;
ret = Math.max(ret,r-l+1);
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
方法二：排序
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length==0)
return 0;
Arrays.sort(nums);
int ret = 1;
int cal = 1;
for(int i=1;i<nums.length;i++){
if(nums[i]==nums[i-1]+1){
cal++;
ret = Math.max(ret,cal);
}else if(nums[i]==nums[i-1])
continue ;
else
cal = 1;
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 双指针
# 283. 移动零 (opens new window)
循环不变量
方法一：
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length;
if(n<2) return ;
// 循环不变量：nums[0...j)!=0
// nums[j...i]==0
int j=0; // j 指向下一个非零元素的位置
for(int i=0;i<n;i++){
if(nums[i]!=0){
nums[j] = nums[i];
j++;
}
}
for(int i=j;i<n;i++){
nums[i] = 0;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
方法二：
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length;
if(n<2) return ;
int j=-1; // j 指向马上要赋值的元素
for(int i=0;i<n;i++){
if(nums[i]!=0){
j++;
nums[j] = nums[i];
}
}
for(int i=j+1;i<n;i++){
nums[i] = 0;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 11. 盛最多水的容器 (opens new window)
class Solution {
public int maxArea(int[] height) {
int ret = 0;
int l=0,r=height.length-1;
int area = 0;
while(l<r){
area = (r-l)*Math.min(height[l],height[r]);
ret = Math.max(ret,area);
if(height[l]<height[r])
l++;
else
r--;
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 15. 三数之和 (opens new window)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ret = new ArrayList<>();
for(int i=0;i<nums.length;i++){
if(nums[i]>0)
return ret;
if(i>0 && nums[i]==nums[i-1])
continue;
int l=i+1,r=nums.length-1;
while(l<r){
int sum = nums[i]+nums[l]+nums[r];
if(sum>0)
r--;
else if(sum<0)
l++;
else{
ret.add(Arrays.asList(nums[i],nums[l],nums[r]));
while(r>l && nums[r]==nums[r-1])
r--;
while(r>l && nums[l]==nums[l+1])
l++;
l++;r--;
}
}
}
return ret;
}
}
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
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
# 42. 接雨水 (opens new window)
方法一：前后缀数组
class Solution {
public int trap(int[] height) {
int n = height.length;
int[] preMax = new int[n];
int[] sufMax = new int[n];
preMax[0] = height[0];
for(int i=1;i<n;i++){
preMax[i] = Math.max(preMax[i-1],height[i]);
}
sufMax[n-1] = height[n-1];
for(int i=n-2;i>=0;i--){
sufMax[i] = Math.max(sufMax[i+1],height[i]);
}
int ret = 0;
for(int i=0;i<n;i++){
ret += Math.min(preMax[i],sufMax[i])-height[i];
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
方法二：双指针
class Solution {
public int trap(int[] height) {
int l=0,r=height.length-1;
int ret = 0;
int preMax = 0;
int sufMax = 0;
while(l<=r){
preMax = Math.max(preMax,height[l]);
sufMax = Math.max(sufMax,height[r]);
if(preMax<sufMax)
ret += preMax-height[l++];
else
ret += sufMax-height[r--];
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 滑动窗口
# 3. 无重复字符的最长子串 (opens new window)
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] window = new int[256];
int l=0,r=0;
int ret = 0;
while(r<s.length()){
char c1 = s.charAt(r++);
window[c1]++;
while(window[c1]>1){
char c2 = s.charAt(l++);
window[c2]--;
}
ret = Math.max(ret,r-l);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 438. 找到字符串中所有字母异位词 (opens new window)
class Solution {
public List<Integer> findAnagrams(String s, String p) {
Map<Character,Integer> window = new HashMap<>();
Map<Character,Integer> need = new HashMap<>();
for(Character c:p.toCharArray()){
need.put(c,need.getOrDefault(c,0)+1);
}
int l=0,r=0;
int cnt = 0;
List<Integer> ret = new ArrayList<>();
while(r<s.length()){
char c1 = s.charAt(r++);
if(need.containsKey(c1)){
window.put(c1,window.getOrDefault(c1,0)+1);
if(window.get(c1).equals(need.get(c1))){
cnt++;
}
}
while(r-l==p.length()){
if(cnt==need.size()){
ret.add(l);
}
char c2 = s.charAt(l++);
if(need.containsKey(c2)){
if(window.get(c2).equals(need.get(c2))){
cnt--;
}
window.put(c2,window.get(c2)-1);
}
}
}
return ret;
}
}
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
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
# 子串
# 560. 和为 K 的子数组 (opens new window)
前缀和
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int ret = 0;
int preSum = 0;
for(int num:nums){
preSum+=num;
if(map.containsKey(preSum-k)){
ret += map.get(preSum-k);
}
map.put(preSum,map.getOrDefault(preSum,0)+1);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 239. 滑动窗口最大值 (opens new window)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums==null || nums.length<k)
return null;
LinkedList<Integer> que = new LinkedList<>();
int[] ret = new int[nums.length-k+1];
// 单调减队列
for(int i=0;i<nums.length;i++){
while(!que.isEmpty() && nums[que.peekLast()]<=nums[i])
que.pollLast();
que.addLast(i);
// 超出窗口左边界
if(que.peek()<=i-k)
que.poll();
// 满足窗口条件
if(i-k+1>=0)
ret[i-k+1] = nums[que.peek()];
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 76. 最小覆盖子串 (opens new window)
class Solution {
public String minWindow(String s, String t) {
Map<Character,Integer> window = new HashMap<>();
Map<Character,Integer> need = new HashMap<>();
for(char c:t.toCharArray())
need.put(c,need.getOrDefault(c,0)+1);
int l=0,r=0;
int minLen = Integer.MAX_VALUE;
int retStart = 0;
int cnt = 0;
while(r<s.length()){
char c1 = s.charAt(r++);
if(need.containsKey(c1)){
window.put(c1,window.getOrDefault(c1,0)+1);
if(window.get(c1).equals(need.get(c1))){
cnt++;
}
}
while(cnt == need.size()){
if(r-l<minLen){
retStart = l;
minLen = r-l;
}
char c2 = s.charAt(l++);
if(need.containsKey(c2)){
if(window.get(c2).equals(need.get(c2))){
cnt--;
}
window.put(c2,window.get(c2)-1);
}
}
}
return minLen==Integer.MAX_VALUE?"":s.substring(retStart,retStart+minLen);
}
}
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
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
# 数组
# 53. 最大子数组和 (opens new window)
无后效性：状态定义为以nums[i]结尾的连续子数组的最大和是多少；
若定义为经过nums[i]的连续子数组最大和则有后效性；
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
// nums[i] 一定会被选
for(int i=1;i<n;i++){
if(dp[i-1]>0)
dp[i] = dp[i-1]+nums[i];
else
dp[i] = nums[i];
}
int ret = dp[0];
for(int i=1;i<n;i++)
ret = Math.max(ret,dp[i]);
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 56. 合并区间 (opens new window)
class Solution {
public int[][] merge(int[][] intervals) {
LinkedList<int[]> ret = new LinkedList<>();
Arrays.sort(intervals,(a,b)->{
return a[0]-b[0];
});
ret.add(intervals[0]);
for(int i=1;i<intervals.length;i++){
int[] pre = ret.getLast();
int[] cur = intervals[i];
if(cur[0]<=pre[1])
pre[1] = Math.max(pre[1],cur[1]);
else
ret.add(cur);
}
return ret.toArray(new int[0][0]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 189. 轮转数组 (opens new window)
nums = "----->-->"; k =3 result = "-->----->";
reverse "----->-->" we can get "<--<-----" reverse "<--" we can get "--><-----" reverse "<-----" we can get "-->----->"
class Solution {
public void rotate(int[] nums, int k) {
k=k%nums.length;
reverse(nums,0,nums.length-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.length-1);
}
void reverse(int[] nums,int a,int b){
int i=a,j=b;
while(i<j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i++;
j--;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 238. 除自身以外数组的乘积 (opens new window)
class Solution {
public int[] productExceptSelf(int[] nums) {
int l=1,r=1;
int[] ret = new int[nums.length];
for(int i=0;i<nums.length;i++){
ret[i] = l;
l *= nums[i];
}
for(int j=nums.length-1;j>=0;j--){
ret[j] *= r;
r *= nums[j];
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 41. 缺失的第一个正数 (opens new window)
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for(int i=0;i<n;i++){
while(nums[i]>0 && nums[i]<=n && nums[nums[i]-1]!=nums[i])
swap(nums,nums[i]-1,i);
}
for(int i=0;i<n;i++){
if(nums[i]!=i+1)
return i+1;
}
return n+1;
}
void swap(int[] nums,int i,int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 矩阵
# 73. 矩阵置零 (opens new window)
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[] row = new boolean[m];
boolean[] col = new boolean[n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]==0)
row[i] = col[j] = true;
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(row[i] || col[j])
matrix[i][j] = 0;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 54. 螺旋矩阵 (opens new window)
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int l=0,r=n-1;
int u=0,b=m-1;
List<Integer> ret = new ArrayList<>();
while(ret.size()<m*n){
if(u<=b){
for(int i=l;i<=r;i++){
ret.add(matrix[u][i]);
}
u++;
}
if(l<=r){
for(int j=u;j<=b;j++){
ret.add(matrix[j][r]);
}
r--;
}
if(b>=u){
for(int i=r;i>=l;i--){
ret.add(matrix[b][i]);
}
b--;
}
if(r>=l){
for(int j=b;j>=u;j--){
ret.add(matrix[j][l]);
}
l++;
}
}
return ret;
}
}
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
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
# 48. 旋转图像 (opens new window)
class Solution {
public void rotate(int[][] matrix) {
int m = matrix.length;
for(int i=0;i<m;i++){
for(int j=i;j<m;j++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for(int[] row:matrix){
reverseRow(row);
}
}
void reverseRow(int[] arr){
int i=0,j=arr.length-1;
while(i<j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;j--;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 240. 搜索二维矩阵 II (opens new window)
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int i=0,j=n-1;
while(i<m && j>=0){
if(target==matrix[i][j])
return true;
else if(target<matrix[i][j])
j--;
else
i++;
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 链表
# 160. 相交链表 (opens new window)
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
while(p!=q){
if(p!=null) p=p.next;
else p = headB;
if(q!=null) q=q.next;
else q = headA;
}
return p;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 206. 反转链表 (opens new window)
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null)
return head;
ListNode tail = reverseList(head.next);
head.next.next = head;
head.next = null;
return tail;
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 234. 回文链表 (opens new window)
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head,slow = head;
ListNode p = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
// 节点数为奇数
if(fast!=null)
slow = slow.next;
ListNode tailRev = reverse(slow);
while(tailRev!=null){
if(p.val!=tailRev.val)
return false;
p = p.next;
tailRev = tailRev.next;
}
return true;
}
ListNode reverse(ListNode head){
if(head==null || head.next==null)
return head;
ListNode tail = reverse(head.next);
head.next.next = head;
head.next = null;
return tail;
}
}
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
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
# 141. 环形链表 (opens new window)
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow)
return true;
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 142. 环形链表 II (opens new window)
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head,slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow)
break;
}
if(fast==null || fast.next==null)
return null;
slow = head;
while(slow!=fast){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 21. 合并两个有序链表 (opens new window)
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null)
return l2;
if(l2==null)
return l1;
if(l1.val<l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 2. 两数相加 (opens new window)
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
int carry = 0;
while(l1!=null || l2!=null){
int x = (l1==null?0:l1.val);
int y = (l2==null?0:l2.val);
int sum = x+y+carry;
carry = sum/10;
sum %= 10;
p.next = new ListNode(sum);
p = p.next;
if(l1!=null) l1=l1.next;
if(l2!=null) l2=l2.next;
}
if(carry==1)
p.next = new ListNode(1);
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 19. 删除链表的倒数第 N 个结点 (opens new window)
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1,head);
// 设置虚拟节点 是防止删除的节点是头节点，find函数寻找的节点为空
ListNode node = find(dummy,n+1);
node.next = node.next.next;
return dummy.next;
}
ListNode find(ListNode p,int n){
ListNode fast = p;
ListNode slow = p;
for(int i=0;i<n;i++){
fast = fast.next;
}
while(fast!=null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 24. 两两交换链表中的节点 (opens new window)
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null || head.next==null)
return head;
ListNode p1 = head;
ListNode p2 = head.next;
ListNode p3 = head.next.next;
p2.next = p1;
p1.next = swapPairs(p3);
return p2;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 25. K 个一组翻转链表 (opens new window)
用临时变量tmp = p.next，最后更新p = tmp，开启下一轮循环；
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int n = 0;
for(ListNode cur=head;cur!=null;cur=cur.next)
n++;
ListNode dummy = new ListNode(0,head);
ListNode p = dummy;
ListNode pre = p,cur = head;
for(;n>=k;n-=k){
for(int i=0;i<k;i++){
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
p.next.next = cur;
ListNode tmp = p.next;
p.next = pre; // 断开链表
p = tmp;
}
return dummy.next;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 138. 随机链表的复制 (opens new window)
class Solution {
public Node copyRandomList(Node head) {
Map<Node,Node> map = new HashMap<>();
Node cur = head;
while(cur!=null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur = head;
while(cur!=null){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 148. 排序链表 (opens new window)
class Solution {
public ListNode sortList(ListNode head) {
if(head==null || head.next==null)
return head;
ListNode midNode = getMid(head);
ListNode rightHead = midNode.next;
midNode.next = null;
ListNode l = sortList(head);
ListNode r = sortList(rightHead);
return merge(l,r);
}
ListNode getMid(ListNode head){
if(head.next==null || head.next.next==null)
return head;
ListNode fast=head,slow=head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
ListNode merge(ListNode l1,ListNode l2){
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val>l2.val){
l2.next = merge(l1,l2.next);
return l2;
}else{
l1.next = merge(l1.next,l2);
return l1;
}
}
}
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
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
# 23. 合并 K 个升序链表 (opens new window)
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0)
return null;
return sort(lists,0,lists.length-1);
}
ListNode sort(ListNode[] lists,int l,int r){
if(l==r)
return lists[l];
int mid = (l+r)>>>1;
ListNode l1 = sort(lists,l,mid);
ListNode l2 = sort(lists,mid+1,r);
return merge(l1,l2);
}
ListNode merge(ListNode l1,ListNode l2){
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val<l2.val){
l1.next = merge(l1.next,l2);
return l1;
}else{
l2.next = merge(l1,l2.next);
return l2;
}
}
}
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
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
# 146. LRU 缓存 (opens new window)
方法一：LinkedHashMap
class LRUCache {
int cap;
LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if(!cache.containsKey(key))
return -1;
makeRecent(key);
return cache.get(key);
}
public void put(int key, int value) {
if(cache.containsKey(key)){
cache.put(key,value);
makeRecent(key);
return ;
}
if(cache.size()>=this.cap){
int oldKey = cache.keySet().iterator().next();
cache.remove(oldKey);
}
// 无key且cap<size
cache.put(key,value);
}
void makeRecent(int key){
int val = cache.get(key);
cache.remove(key);
cache.put(key,val);
}
}
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
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
方法二：不基于LinkedHashMap
class ListNode{
int key;
int val;
ListNode next;
ListNode pre;
ListNode(int key, int val){
this.key = key;
this.val = val;
}
}
class LRUCache {
Map<Integer, ListNode> map;
ListNode head;
ListNode tail;
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<Integer,ListNode>(capacity);
head = new ListNode(0, 0);
tail = new ListNode(0, 0);
head.next = tail;
tail.pre = head;
}
public int get(int key) {
ListNode p = map.get(key);
if(p == null){
return -1;
}else{
remove(p);
addLast(p);
return p.val;
}
}
public void put(int key, int value) {
ListNode p = map.get(key);
if(p == null){
if(map.size() >= capacity){
map.remove(head.next.key);
remove(head.next);
}
ListNode cur = new ListNode(key, value);
addLast(cur);
map.put(key, cur);
}else{
p.val = value;
remove(p);
addLast(p);
}
}
private void addLast(ListNode node){
node.pre = tail.pre;
node.next = tail;
tail.pre.next = node;
tail.pre = node;
}
private void remove(ListNode node){
node.pre.next = node.next;
node.next.pre = node.pre;
node.pre = null;
node.next = 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# 二叉树
# 94. 二叉树的中序遍历 (opens new window)
方法一：递归
class Solution {
List<Integer> ret = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
dfs(root);
return ret;
}
void dfs(TreeNode root){
if(root==null)
return ;
dfs(root.left);
ret.add(root.val);
dfs(root.right);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
方法二：迭代
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack= new Stack<>();
if(root==null)
return ret;
TreeNode cur = root;
while(cur!=null || !stack.isEmpty()){
if(cur!=null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
ret.add(cur.val);
cur = cur.right;
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 104. 二叉树的最大深度 (opens new window)
class Solution {
public int maxDepth(TreeNode root) {
if(root==null)
return 0;
int lson = maxDepth(root.left);
int rson = maxDepth(root.right);
return Math.max(lson,rson)+1;
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 226. 翻转二叉树 (opens new window)
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
TreeNode lson = invertTree(root.left);
TreeNode rson = invertTree(root.right);
root.left = rson;
root.right = lson;
return root;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 101. 对称二叉树 (opens new window)
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null)
return true;
return dfs(root.left,root.right);
}
boolean dfs(TreeNode lson,TreeNode rson){
if(lson==null && rson==null)
return true;
if(lson!=null&&rson==null || lson==null&&rson!=null)
return false;
if(lson.val!=rson.val)
return false;
boolean outSide = dfs(lson.left,rson.right);
boolean inSide = dfs(lson.right,rson.left);
return outSide&&inSide;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 543. 二叉树的直径 (opens new window)
class Solution {
int ret = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return ret;
}
int dfs(TreeNode root){
if(root==null)
return 0;
int l = dfs(root.left);
int r = dfs(root.right);
ret = Math.max(l+r,ret);
return Math.max(l,r)+1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 102. 二叉树的层序遍历 (opens new window)
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root==null)
return ret;
que.offer(root);
while(!que.isEmpty()){
List<Integer> level = new ArrayList<>();
int size = que.size();
while(size>0){
TreeNode node = que.poll();
level.add(node.val);
if(node.left!=null)
que.offer(node.left);
if(node.right!=null)
que.offer(node.right);
size--;
}
ret.add(level);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 108. 将有序数组转换为二叉搜索树 (opens new window)
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums,0,nums.length-1);
}
TreeNode dfs(int[] nums,int l,int r){
if(r<l)
return null;
int mid = (l+r)>>>1;
TreeNode root = new TreeNode(nums[mid]);
root.left = dfs(nums,l,mid-1);
root.right = dfs(nums,mid+1,r);
return root;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 98. 验证二叉搜索树 (opens new window)
class Solution {
Integer pre; // 初始化为中序序列中第一个节点值
public boolean isValidBST(TreeNode root) {
if(root==null)
return true;
boolean left = isValidBST(root.left);
if(pre!=null && root.val<=pre)
return false;
pre = root.val; // 如果当前节点小于中序序列上一个值，更新
boolean right = isValidBST(root.right);
return left&&right;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 230. 二叉搜索树中第K小的元素 (opens new window)
class Solution {
int ret,rank;
public int kthSmallest(TreeNode root, int k) {
dfs(root,k);
return ret;
}
void dfs(TreeNode root,int k){
if(root==null)
return ;
dfs(root.left,k);
rank++;
if(rank==k){
ret = root.val;
return ;
}
dfs(root.right,k);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 199. 二叉树的右视图 (opens new window)
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList<>();
if(root==null)
return ret;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int size = que.size();
while(size>0){
TreeNode node = que.poll();
if(size==1)
ret.add(node.val);
if(node.left!=null)
que.add(node.left);
if(node.right!=null)
que.add(node.right);
size--;
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 114. 二叉树展开为链表 (opens new window)
class Solution {
public void flatten(TreeNode root) {
if(root==null)
return ;
flatten(root.left);
flatten(root.right);
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
root.right = left;
TreeNode p = root;
while(p.right!=null){
p = p.right;
}
p.right = right;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 105. 从前序与中序遍历序列构造二叉树 (opens new window)
class Solution {
int[] preorder;
int[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
return dfs(0,preorder.length-1,0,inorder.length-1);
}
TreeNode dfs(int preStart,int preEnd,int inStart,int inEnd){
if(preStart>preEnd)
return null;
int rootVal = preorder[preStart];
int anchor = 0;
for(int i=inStart;i<=inEnd;i++){
if(inorder[i]==rootVal){
anchor = i;
break;
}
}
int leftSize = anchor-inStart;
TreeNode root = new TreeNode(rootVal);
root.left = dfs(preStart+1,preStart+leftSize,inStart,anchor-1);
root.right = dfs(preStart+1+leftSize,preEnd,anchor+1,inEnd);
return root;
}
}
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
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
# 437. 路径总和 III (opens new window)
class Solution {
int ret;
public int pathSum(TreeNode root, int targetSum) {
if(root==null)
return 0;
dfs(root,targetSum);
pathSum(root.left,targetSum);
pathSum(root.right,targetSum);
return ret;
}
void dfs(TreeNode root,long targetSum){
if(root==null)
return ;
targetSum-=root.val;
if(targetSum==0)
ret++;
dfs(root.left,targetSum);
dfs(root.right,targetSum);
targetSum+=root.val;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 236. 二叉树的最近公共祖先 (opens new window)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root==p || root==q)
return root;
TreeNode l = lowestCommonAncestor(root.left,p,q);
TreeNode r = lowestCommonAncestor(root.right,p,q);
if(l==null && r==null)
return null;
if(l==null)
return r;
if(r==null)
return l;
return root;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 124. 二叉树中的最大路径和 (opens new window)
class Solution {
int ret = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if(root==null)
return 0;
dfs(root);
return ret;
}
int dfs(TreeNode root){
if(root==null)
return 0;
int left = Math.max(0,dfs(root.left));
int right = Math.max(0,dfs(root.right));
ret = Math.max(ret,root.val+left+right);
return root.val+Math.max(left,right);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 图论
# 200. 岛屿数量 (opens new window)
class Solution {
char[][] grid;
int m,n;
public int numIslands(char[][] grid) {
this.grid = grid;
this.m = grid.length;
this.n = grid[0].length;
int ret = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='1'){
ret++;
dfs(i,j);
}
}
}
return ret;
}
void dfs(int i,int j){
if(i<0||i>=m||j<0||j>=n||grid[i][j]!='1')
return ;
grid[i][j] = '0';
dfs(i+1,j);
dfs(i-1,j);
dfs(i,j+1);
dfs(i,j-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
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
# 994. 腐烂的橘子 (opens new window)
class Solution {
int[][] dirs = new int[][]{{1,0},{-1,0},{0,-1},{0,1}};
public int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Queue<int[]> que = new LinkedList<>();
int cnt = 0;//新鲜橘子
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]==1)
cnt++;
if(grid[i][j]==2)
que.add(new int[]{i,j});
}
}
int ret = 0;
while(cnt>0 && !que.isEmpty()){
ret++;
int size = que.size();
for(int k=0;k<size;k++){
int[] node = que.poll();
int x = node[0];
int y = node[1];
for(int[] dir:dirs){
int dx = x+dir[0];
int dy = y+dir[1];
if(dx>=0&&dx<m&&dy>=0&&dy<n && grid[dx][dy]==1){
grid[dx][dy] = 2;
cnt--;
que.add(new int[]{dx,dy});
}
}
}
}
return cnt>0?-1:ret;
}
}
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
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
# 207. 课程表 (opens new window)
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegrees = new int[numCourses];
List<List<Integer>> adjacency = new ArrayList<>();
for(int i=0;i<numCourses;i++){
adjacency.add(new ArrayList());
}
Queue<Integer> que = new LinkedList<>();
// 入度表 与 邻接表 赋值
for(int[] e:prerequisites){
indegrees[e[0]]++;
adjacency.get(e[1]).add(e[0]);
}
// 入度为0 入队列
for(int i=0;i<numCourses;i++){
if(indegrees[i]==0)
que.add(i);
}
while(!que.isEmpty()){
int pre = que.poll();
numCourses--;
for(int cur:adjacency.get(pre)){
if(--indegrees[cur]==0){
que.add(cur);
}
}
}
return numCourses==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
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
# 208. 实现 Trie (前缀树) (opens new window)
只在最后一个节点将isWord设置为true;
class Trie {
class TrieNode{
boolean isWord;
TrieNode[] children;
public TrieNode(){
this.isWord = false;
this.children = new TrieNode[26];
}
}
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode cur = root;
for(int i=0;i<word.length();i++){
int c = word.charAt(i)-'a';
if(cur.children[c]==null)
cur.children[c] = new TrieNode();
cur = cur.children[c];
}
cur.isWord = true;
}
public boolean search(String word) {
TrieNode cur = root;
for(int i=0;i<word.length();i++){
int c = word.charAt(i)-'a';
if(cur.children[c]==null)
return false;
cur = cur.children[c];
}
return cur.isWord;
}
public boolean startsWith(String prefix) {
TrieNode cur = root;
for(int i=0;i<prefix.length();i++){
int c = prefix.charAt(i)-'a';
if(cur.children[c]==null)
return false;
cur = cur.children[c];
}
return true;
}
}
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
42
43
44
45
46
47
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
42
43
44
45
46
47
# 回溯
# 46. 全排列 (opens new window)
class Solution {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] nums;
boolean[] vis;
public List<List<Integer>> permute(int[] nums) {
this.nums = nums;
this.vis = new boolean[nums.length];
dfs();
return ret;
}
void dfs(){
if(nums.length==path.size()){
ret.add(new ArrayList<>(path));
return ;
}
for(int i=0;i<nums.length;i++){
if(vis[i])
continue;
vis[i] = true;
path.add(nums[i]);
dfs();
vis[i] = false;
path.remove(path.size()-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
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
# 78. 子集 (opens new window)
方法一：选哪个
class Solution {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
dfs(0);
return ret;
}
void dfs(int i){
ret.add(new ArrayList<>(path));
if(i==nums.length)
return ;
for(int j=i;j<nums.length;j++){
path.add(nums[j]);
dfs(j+1);
path.remove(path.size()-1);
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
方法二：选或不选
[类似题型](#22. 括号生成 (opens new window))
1
# 17. 电话号码的字母组合 (opens new window)
class Solution {
List<String> ret = new ArrayList<>();
String[] arr;
String digits;
public List<String> letterCombinations(String digits) {
this.arr = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
this.digits = digits;
if(digits==null || digits.length()==0){
return ret;
}
dfs(0,new StringBuilder());
return ret;
}
void dfs(int i,StringBuilder cur){
if(i==digits.length()){
ret.add(cur.toString());
return ;
}
String str = arr[digits.charAt(i)-'0'];
for(int j=0;j<str.length();j++){
cur.append(str.charAt(j));
dfs(i+1,cur);
cur.deleteCharAt(cur.length()-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
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
# 39. 组合总和 (opens new window)
class Solution {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> path = new ArrayList();
int[] candidates;
int target;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.candidates = candidates;
this.target = target;
dfs(0,target);
return ret;
}
void dfs(int i,int target){
if(target<0)
return ;
if(i<candidates.length && target==0){
ret.add(new ArrayList<>(path));
return ;
}
for(int j=i;j<candidates.length;j++){
path.add(candidates[j]);
dfs(j,target-candidates[j]);
path.remove(path.size()-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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 22. 括号生成 (opens new window)
class Solution {
List<String> ret = new ArrayList<>();
public List<String> generateParenthesis(int n) {
dfs(new StringBuilder(),n,n);
return ret;
}
void dfs(StringBuilder cur,int l,int r){
if(l==0 && r==0){
ret.add(cur.toString());
return ;
}
if(l<0 || r<0)
return ;
if(l>r)
return ;
cur.append('(');
dfs(cur,l-1,r);
cur.deleteCharAt(cur.length()-1);
cur.append(')');
dfs(cur,l,r-1);
cur.deleteCharAt(cur.length()-1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 79. 单词搜索 (opens new window)
class Solution {
char[][] board;
String word;
int n;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
public boolean exist(char[][] board, String word) {
this.board = board;
this.word = word;
this.n = word.length();
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(dfs(0,i,j))
return true;
}
}
return false;
}
boolean dfs(int idx,int x,int y){
if(word.charAt(idx)!=board[x][y])
return false;
if(idx==n-1)
return true;
char ch = board[x][y];
board[x][y] = '.';
for(int[] dir:dirs){
int dx = x+dir[0];
int dy = y+dir[1];
if(dx<0||dx>=board.length||dy<0||dy>=board[0].length
|| board[dx][dy]=='.'){
continue;
}
if(dfs(idx+1,dx,dy))
return true;
}
board[x][y] = ch;
return false;
}
}
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
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
# 131. 分割回文串 (opens new window)
class Solution {
List<List<String>> ret = new ArrayList<>();
List<String> path = new ArrayList<>();
String s;
public List<List<String>> partition(String s) {
this.s = s;
dfs(0);
return ret;
}
void dfs(int i){
if(i==s.length()){
ret.add(new ArrayList<>(path));
return ;
}
for(int j=i;j<s.length();j++){
if(f(s,i,j)){
String str = s.substring(i,j+1);
path.add(str);
}else{
continue;
}
dfs(j+1);
path.remove(path.size()-1);
}
}
boolean f(String s,int l,int r){
for(int i=l,j=r;i<=j;i++,j--){
if(s.charAt(i)!=s.charAt(j)){
return false;
}
}
return true;
}
}
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
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
# 51. N 皇后 (opens new window)
class Solution {
int[] cols;
int n;
List<List<String>> ret = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
this.n = n;
this.cols = new int[n];
dfs(0);
return ret;
}
void dfs(int i){
if(i==n){
List<String> method = new ArrayList<>();
for(int col:cols){
char[] row = new char[n];
Arrays.fill(row,'.');
row[col] = 'Q';
method.add(new String(row));
}
ret.add(method);
return ;
}
for(int j=0;j<cols.length;j++){
if(f(i,j)){
cols[i] = j;
dfs(i+1);
}
}
}
boolean f(int r,int c){
for(int i=0;i<r;i++){
int j = cols[i];
if(c==j || (i+j)==(r+c) || (i-j)==(r-c))
return false;
}
return true;
}
}
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
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
# 二分查找
# 35. 搜索插入位置 (opens new window)
class Solution {
public int searchInsert(int[] nums, int target) {
int l=0,r=nums.length-1;
while(l<=r){
int mid = (l+r)>>>1;
if(target>nums[mid])
l = mid+1;
else
r = mid-1;
}
return r+1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 74. 搜索二维矩阵 (opens new window)
class Solution {
int[][] matrix;
int m;
int n;
public boolean searchMatrix(int[][] matrix, int target) {
this.matrix = matrix;
this.m = matrix.length;
this.n = matrix[0].length;
int l=0,r=m*n-1;
while(l<=r){
int mid = (l+r)>>>1;
if(f(mid)<target)
l = mid+1;
else if(f(mid)>target)
r = mid-1;
else
return true;
}
return false;
}
int f(int k){
int i = k/n;
int j = k%n;
return matrix[i][j];
}
}
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
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
# 34. 在排序数组中查找元素的第一个和最后一个位置 (opens new window)
class Solution {
public int[] searchRange(int[] nums, int target) {
int l = bound(nums,target);
if(l==nums.length || nums[l]!=target){
return new int[]{-1,-1};
}
int r = bound(nums,target+1)-1;
return new int[]{l,r};
}
int bound(int[] nums,int target){
int l=0,r=nums.length-1;
while(l<=r){
int mid = (l+r)>>>1;
if(nums[mid]<target){
l = mid+1;
}else{
r = mid-1;
}
}
return l;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 33. 搜索旋转排序数组 (opens new window)
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int i = findMin(nums);
if(target>nums[n-1]){
return bound(nums,0,i-1,target);
}
return bound(nums,i,n-1,target);
}
// 寻找最小值索引
int findMin(int[] nums){
int l=0,r=nums.length-2;
int target = nums[nums.length-1];
while(l<=r){
int mid = (l+r)>>>1;
if(nums[mid]<target){
r = mid-1;
}else{
l = mid+1;
}
}
return l;
}
// 寻找target的左边界
int bound(int[] nums,int l,int r,int target){
while(l<=r){
int mid = (l+r)>>>1;
if(nums[mid]<target){
l = mid+1;
}else{
r = mid-1;
}
}
return nums[l]==target?l:-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
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
# 153. 寻找旋转排序数组中的最小值 (opens new window)
class Solution {
public int findMin(int[] nums) {
int l=0,r=nums.length-2;
int target = nums[nums.length-1];
while(l<=r){
int mid = (l+r)>>>1;
if(nums[mid]<target)
r = mid-1;
else
l = mid+1;
}
return nums[l];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 4. 寻找两个正序数组的中位数 (opens new window)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length,n = nums2.length;
int[] nums = new int[m+n];
int i=0,j=0,k=0;
while(i<m && j<n)
nums[k++] = nums1[i]<=nums2[j]?nums1[i++]:nums2[j++];
while(i<m)
nums[k++] = nums1[i++];
while(j<n)
nums[k++] = nums2[j++];
if(k%2==0)
return (nums[k/2-1]+nums[k/2])/2.0;
else
return nums[k/2];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 栈
# 20. 有效的括号 (opens new window)
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
if(c=='(')
stack.push(')');
else if(c=='[')
stack.push(']');
else if(c=='{')
stack.push('}');
else if(stack.isEmpty() || c!=stack.peek())
return false;
else
stack.pop();
}
return stack.isEmpty();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 155. 最小栈 (opens new window)
class MinStack {
// 当前值，之前最小值
Deque<int[]> stack = new ArrayDeque<>();
public MinStack() {
}
public void push(int val) {
if(stack.isEmpty())
stack.push(new int[]{val,val});
else
stack.push(new int[]{val,Math.min(val,stack.peek()[1])});
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[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
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
# 394. 字符串解码 (opens new window)
方法一：递归
class Solution {
public String decodeString(String s) {
return dfs(s,0)[0];
}
// 返回值p1:]的索引i,p2:sb
String[] dfs(String s,int i){
StringBuilder sb = new StringBuilder();
int mul = 0;
while(i<s.length()){
if(s.charAt(i)>='0' && s.charAt(i)<='9'){
mul = mul*10 + s.charAt(i)-'0';
}else if(s.charAt(i)=='['){
// 记录[...]内字符串tmp 和 递归后最新索引i
String[] tmp = dfs(s,i+1);
i = Integer.parseInt(tmp[0]);
while(mul>0){
sb.append(tmp[1]);
mul--;
}
}else if(s.charAt(i)==']'){
// ']'的索引i位置，括号内的sb
return new String[]{String.valueOf(i),sb.toString()};
}else{
sb.append(s.charAt(i));
}
i++;
}
return new String[]{sb.toString()};
}
}
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
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
# 739. 每日温度 (opens new window)
更小的值入栈
class Solution {
public int[] dailyTemperatures(int[] t) {
Deque<Integer> stack = new ArrayDeque<>();
int n = t.length;
int[] ret = new int[n];
for(int i=0;i<n;i++){
while(!stack.isEmpty() && t[i]>t[stack.peek()]){
int pre = stack.pop();
ret[pre] = i-pre;
}
stack.push(i);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 84. 柱状图中最大的矩形 (opens new window)
class Solution {
int[] heights;
public int largestRectangleArea(int[] heights) {
this.heights = heights;
int ret = 0;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(-1);
for(int i=0;i<=heights.length;i++){
// 更大的元素入栈
while(getHeight(i)<getHeight(stack.peek())){
int x = stack.pop();
// [1,5,6,2],i=3时，第一轮循环ret=6，第二轮循环ret=10
ret = Math.max(ret,getHeight(x)*(i-stack.peek()-1));
}
stack.push(i);
}
return ret;
}
int getHeight(int i){
if(i==-1)
return -1;
else if(i==heights.length)
return -1;
else
return heights[i];
}
}
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
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
# 堆
# 215. 数组中的第K个最大元素 (opens new window)
方法一：优先级队列
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int num:nums){
pq.offer(num);
if(pq.size()>k){
pq.poll();
}
}
return pq.peek();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
方法二：快排
class Solution {
public int findKthLargest(int[] nums, int k) {
shuffle(nums);
int l=0,r=nums.length-1;
k = nums.length-k;
while(l<=r){
int p = partition(nums,l,r);
if(p<k) l=p+1;
else if(p>k) r=p-1;
else return nums[p];
}
return -1;
}
int partition(int[] nums,int l,int r){
int i = l;
int base = nums[r];
// 让i正好在第一个>base的地方
for(int j=l;j<r;j++){
if(nums[j]<base){
swap(nums,i,j);
i++;
}
}
swap(nums,i,r);
return i;
}
void shuffle(int[] nums){
Random random = new Random();
int n = nums.length;
for(int i=0;i<n;i++){
int r = i+random.nextInt(n-i);
swap(nums,i,r);
}
}
void swap(int[] nums,int l,int r){
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
}
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
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
方法三：堆排序
1
# 347. 前 K 个高频元素 (opens new window)
方法一：优先级队列
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
PriorityQueue<Map.Entry<Integer,Integer>> pq = new PriorityQueue<>((o1,o2)->{
return o1.getValue().compareTo(o2.getValue());
});
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
pq.offer(entry);
if(pq.size()>k)
pq.poll();
}
int[] ret = new int[k];
for(int i=0;i<=k-1;i++)
ret[i] = pq.poll().getKey();
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
方法二：计数排序
1
# 295. 数据流的中位数 (opens new window)
class MedianFinder {
PriorityQueue<Integer> large;
PriorityQueue<Integer> small;
public MedianFinder() {
this.large = new PriorityQueue<>();// 小根堆
this.small = new PriorityQueue<>((a,b)->{
return b-a;
});
}
public void addNum(int num) {
// 优先加入小根堆
if(large.isEmpty() || num>=large.peek())
large.add(num);
else
small.add(num);
modify();
}
void modify(){
if(large.size() == small.size()+2)
small.offer(large.poll());
if(small.size() == large.size()+2)
large.offer(small.poll());
}
public double findMedian() {
int largeSize = large.size();
int smallSize = small.size();
Integer largeHead = large.peek();
Integer smallHead = small.peek();
if(((largeSize+smallSize)&1)==0)
return (largeHead+smallHead)/2.0;
return largeSize>smallSize?largeHead:smallHead;
}
}
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
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
# 贪心算法
# 121. 买卖股票的最佳时机 (opens new window)
class Solution {
public int maxProfit(int[] prices) {
int ret = 0;
int min = Integer.MAX_VALUE;
for(int i=0;i<prices.length;i++){
min = Math.min(min,prices[i]);
ret = Math.max(prices[i]-min,ret);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 55. 跳跃游戏 (opens new window)
方法一：贪心
class Solution {
public boolean canJump(int[] nums) {
int max = 0;
for(int i=0;i<=max;i++){
max = Math.max(max,i+nums[i]);
if(max>=nums.length-1)
return true;
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
方法二：动态规划
状态定义：能否跳到第i个位置；
class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
boolean[] dp = new boolean[n];
dp[0] = true;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(dp[j] && (i-j)<=nums[j]){
dp[i] = true;
break;
}
}
}
return dp[n-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
重新定义：i点之前能跳的最远距离；
class Solution { public boolean canJump(int[] nums) { int n = nums.length; if(n==1) return true; if(nums[0]==0) return false; // i点之前能跳的最远距离 int[] dp = new int[n]; dp[0] = nums[0]; for(int i=1;i<n-1;i++){ dp[i] = Math.max(dp[i-1],nums[i]+i); if(dp[i]>=n-1) return true; if(dp[i]==i) return false; } return true; } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 45. 跳跃游戏 II (opens new window)
方法一：贪心
class Solution {
public int jump(int[] nums) {
int end = 0;
int max = 0;
int ret = 0;
int n = nums.length;
for(int i=0;i<n-1;i++){
max = Math.max(max,i+nums[i]);
if(i==end){
end = max;
ret++;
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
方法二：动态规划
状态定义为跳到i的最少步数；
class Solution {
public int jump(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp,Integer.MAX_VALUE/2);
dp[0] = 0;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(i-j<=nums[j])
dp[i] = Math.min(dp[j]+1,dp[i]);
}
}
return dp[n-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 763. 划分字母区间 (opens new window)
i==end这一步与跳跃游戏很像；
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> ret = new ArrayList<>();
int[] map = new int[26];
char[] cs = s.toCharArray();
// 记录每个字母最后一次出现的位置
for(int i=0;i<cs.length;i++)
map[cs[i]-'a'] = i;
int start=-1,end=0;
for(int i=0;i<cs.length;i++){
end = Math.max(end,map[cs[i]-'a']);
if(i==end){
ret.add(i-start);
start = i;
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 动态规划
# 70. 爬楼梯 (opens new window)
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n+1];
dp[0] = dp[1] = 1;
for(int i=2;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 118. 杨辉三角 (opens new window)
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<>();
for(int i=0;i<numRows;i++){
List<Integer> row = new ArrayList<>();
for(int j=0;j<=i;j++){
if(j==0 || j==i){
row.add(1);
}else{
row.add(ret.get(i-1).get(j-1) + ret.get(i-1).get(j));
}
}
ret.add(row);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 198. 打家劫舍 (opens new window)
状态定义：前i个房子偷到的最大值；
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n+2];
for(int i=0;i<n;i++)
dp[i+2] = Math.max(dp[i+1],dp[i]+nums[i]);
return dp[n+1];
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 279. 完全平方数 (opens new window)
方法一：记忆化搜索
class Solution {
int ret = 10000;
int[] memo;
public int numSquares(int n) {
if(n==1)
return 1;
this.memo = new int[n+1];
Arrays.fill(memo,-1);
dfs(n);
return ret;
}
int dfs(int n){
if(n==0)
return 0;
if(memo[n]!=-1)
return memo[n];
int c = (int)Math.sqrt(n);
for(int i=1;i<=c;i++){
ret = Math.min(ret,1+dfs(n-i*i));
}
return memo[n] = ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
方法二：动态规划
class Solution {
public int numSquares(int n) {
int m = (int)Math.sqrt(n);
int[][] dp = new int[m+1][n+1];
Arrays.fill(dp[0],10000);
dp[0][0] = 0;
for(int i=0;i<m;i++){
for(int c=0;c<=n;c++){
if(c<(i+1)*(i+1))
dp[i+1][c] = dp[i][c];
else
dp[i+1][c] = Math.min(dp[i][c],dp[i+1][c-(i+1)*(i+1)]+1);
}
}
return dp[m][n];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 322. 零钱兑换 (opens new window)
方法一：记忆化搜索
class Solution {
int[] coins;
int[][] memo;
public int coinChange(int[] coins, int amount) {
this.coins = coins;
int n = coins.length;
this.memo = new int[n][amount+1];
for(int[] row:memo)
Arrays.fill(row,-1);
int ret = dfs(n-1,amount);
return ret<Integer.MAX_VALUE/2?ret:-1;
}
int dfs(int i,int c){
if(i<0)
return c==0?0:Integer.MAX_VALUE/2;
if(memo[i][c]!=-1)
return memo[i][c];
if(c<coins[i])
return memo[i][c] = dfs(i-1,c);
else
return memo[i][c] = Math.min(dfs(i-1,c),dfs(i,c-coins[i])+1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
方法二：动态规划
class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[][] dp = new int[n+1][amount+1];
Arrays.fill(dp[0],Integer.MAX_VALUE/2);
dp[0][0] = 0;
for(int i=0;i<n;i++){
for(int c=0;c<=amount;c++){
if(c<coins[i]){
dp[i+1][c] = dp[i][c];
}else{
dp[i+1][c] = Math.min(dp[i][c],dp[i+1][c-coins[i]]+1);
}
}
}
int ret = dp[n][amount];
return ret<Integer.MAX_VALUE/2?ret:-1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 139. 单词拆分 (opens new window)
方法一：记忆化搜索
class Solution {
int[] memo;
String s;
List<String> wordDict;
public boolean wordBreak(String s, List<String> wordDict) {
this.memo = new int[s.length()];
this.s = s;
this.wordDict = wordDict;
Arrays.fill(memo,-1);
return dfs(0);
}
boolean dfs(int i){
if(i==s.length())
return true;
if(memo[i]!=-1)
return memo[i]==1?true:false;
for(String word:wordDict){
int len = word.length();
if(i+len>s.length())
continue;
String subStr = s.substring(i,i+len);
if(!subStr.equals(word))
continue;
// 能匹配，子问题压栈
if(dfs(i+len)){
memo[i] = 1;
return true;
}
}
// 不能匹配
memo[i] = 0;
return false;
}
}
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
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 boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n+1];// i之前的都能匹配
dp[0] = true;
for(int i=0;i<n;i++){
for(String word:wordDict){
int len =word.length();
if(i-len+1>=0 && dp[i-len+1] && word.equals(s.substring(i-len+1,i+1))){
dp[i+1] = true;
break;
}
}
}
return dp[n];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 300. 最长递增子序列 (opens new window)
方法一：记忆化搜索
class Solution {
int[] nums;
int[] memo;
public int lengthOfLIS(int[] nums) {
int ret = 0;
int n = nums.length;
this.nums = nums;
this.memo = new int[n];
for(int i=0;i<n;i++)
ret = Math.max(ret,dfs(i));
return ret;
}
int dfs(int i){
if(memo[i]!=0)
return memo[i];
for(int j=0;j<i;j++){
if(nums[j]<nums[i])
memo[i] = Math.max(memo[i],dfs(j));
}
return ++memo[i];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
方法二：动态规划
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int ret = 0;
int[] dp = new int[n];
Arrays.fill(dp,1);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
ret = Math.max(ret,dp[i]);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 152. 乘积最大子数组 (opens new window)
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
if(n==0)
return 0;
// dp[i][1] 以索引i结尾的连续子序列乘积的最大值
int[][] dp = new int[n][2];
dp[0][0] = nums[0];
dp[0][1] = nums[0];
for(int i=1;i<n;i++){
if(nums[i]>0){
dp[i][1] = Math.max(nums[i],dp[i-1][1]*nums[i]);
dp[i][0] = Math.min(nums[i],dp[i-1][0]*nums[i]);
}else{
dp[i][1] = Math.max(nums[i],dp[i-1][0]*nums[i]);
dp[i][0] = Math.min(nums[i],dp[i-1][1]*nums[i]);
}
}
int ret = dp[0][1];
for(int i=1;i<n;i++){
ret = Math.max(ret,dp[i][1]);
}
return ret;
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
优化：
class Solution { public int maxProduct(int[] nums) { int n = nums.length; if(n==0) return 0; int[] maxDp = new int[n]; int[] minDp = new int[n]; maxDp[0] = nums[0]; minDp[0] = nums[0]; for(int i=1;i<n;i++){ if(nums[i]>=0){ maxDp[i] = Math.max(nums[i],maxDp[i-1]*nums[i]); minDp[i] = Math.min(nums[i],minDp[i-1]*nums[i]); }else{ maxDp[i] = Math.max(nums[i],minDp[i-1]*nums[i]); minDp[i] = Math.min(nums[i],maxDp[i-1]*nums[i]); } } int ret = maxDp[0]; for(int i=1;i<n;i++){ ret = Math.max(ret,maxDp[i]); } return ret; } }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
# 416. 分割等和子集 (opens new window)
方法一：记忆化搜索
class Solution {
int[] nums;
int[][] memo;
public boolean canPartition(int[] nums) {
this.nums = nums;
int n = nums.length;
int sum = Arrays.stream(nums).sum();
if(sum%2!=0)
return false;
int target = sum/2;
this.memo = new int[n][target+1];
for(int[] row:memo){
Arrays.fill(row,-1);
}
return dfs(n-1,target);
}
boolean dfs(int i,int c){
if(i<0)
return c==0?true:false;
if(memo[i][c]!=-1)
return memo[i][c]==1?true:false;
if(c<nums[i])
return dfs(i-1,c);
if(dfs(i-1,c)||dfs(i-1,c-nums[i])){
memo[i][c] = 1;
return true;
}
memo[i][c] = 0;
return false;
}
}
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
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
方法二：动态规划
class Solution {
public boolean canPartition(int[] nums) {
int sum = Arrays.stream(nums).sum();
if(sum%2!=0)
return false;
int target = sum/2;
int n = nums.length;
boolean[][] dp = new boolean[n+1][target+1];
dp[0][0] = true;
for(int i=0;i<n;i++){
for(int c=0;c<=target;c++){
if(c<nums[i])
dp[i+1][c] = dp[i][c];
else
dp[i+1][c] = dp[i][c] || dp[i][c-nums[i]];
}
}
return dp[n][target];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 32. 最长有效括号 (opens new window)
class Solution {
public int longestValidParentheses(String s) {
int ret = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='(')
stack.push(i);
else{
stack.pop();
// )))()
if(stack.isEmpty()){
stack.push(i);
}else{
ret = Math.max(ret,i-stack.peek());
}
}
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 多维动态规划
# 62. 不同路径 (opens new window)
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i=0;i<m;i++)
dp[i][0] = 1;
for(int j=0;j<n;j++)
dp[0][j] = 1;
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 64. 最小路径和 (opens new window)
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for(int i=1;i<m;i++)
dp[i][0] = dp[i-1][0]+grid[i][0];
for(int j=1;j<n;j++)
dp[0][j] = dp[0][j-1]+grid[0][j];
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 5. 最长回文子串 (opens new window)
方法一：动态规划
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
int[] res = new int[2];
boolean[][] dp = new boolean[n][n];
for(int i=0;i<n;i++)
dp[i][i] = true;
for(int i=n-2;i>=0;i--){
for(int j=i+1;j<n;j++){
if(s.charAt(i)==s.charAt(j)){
if(j-i==1)
dp[i][j] = true;
else
dp[i][j] = dp[i+1][j-1];
}else{
dp[i][j] = false;
}
if(dp[i][j]){
if(res[1]-res[0]<=j-i){
res[0] = i;
res[1] = j;
}
}
}
}
return s.substring(res[0],res[1]+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
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 String longestPalindrome(String s) {
String res = "";
for(int i =0;i<s.length();i++){
String s1 = palindrome(s,i,i);
String s2 = palindrome(s,i,i+1);
res = res.length()>s1.length()?res:s1;
res = res.length()>s2.length()?res:s2;
}
return res;
}
//从[l,r]向两边扩展寻找回文
public String palindrome(String s,int l,int r){
while(l>=0 && r<s.length()&&s.charAt(l)==s.charAt(r)){
l--;
r++;
}
return s.substring(l+1,r);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 1143. 最长公共子序列 (opens new window)
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m+1][n+1];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(text1.charAt(i)==text2.charAt(j))
dp[i+1][j+1] = dp[i][j]+1;
else
dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j]);
}
}
return dp[m][n];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 72. 编辑距离 (opens new window)
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++)
dp[i][0] = i;
for(int j=1;j<=n;j++)
dp[0][j] = j;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
dp[i+1][j+1] = word1.charAt(i)==word2.charAt(j)?dp[i][j]:Math.min(Math.min(dp[i+1][j],dp[i][j+1]),dp[i][j])+1;
}
}
return dp[m][n];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 技巧
# 136. 只出现一次的数字 (opens new window)
class Solution {
public int singleNumber(int[] nums) {
int ret = 0;
for(int num:nums){
ret ^= num;
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 169. 多数元素 (opens new window)
方法一：摩尔投票法
将多数元素与其它元素两两抵消，最后还剩至少一个"多数元素"；
- 将cand_num初始化为nums[0]，票数cnt初始化为1；
- 当遇到与cand_num相同的数，则cnt+1，否则-1；
- 当票数为0，更换cand_num，将cnt置为1
class Solution {
public int majorityElement(int[] nums) {
int cand_num = nums[0];
int cnt = 1;
for(int i=1;i<nums.length;i++){
if(cand_num == nums[i])
cnt++;
else if(--cnt==0){
cand_num = nums[i];
cnt = 1;
}
}
return cand_num;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
方法二：分治
class Solution {
public int majorityElement(int[] nums) {
return rec(nums,0,nums.length-1);
}
// 返回众数
int rec(int[] nums,int l,int r){
// size为1的数组，该元素就是众数
if(l==r)
return nums[l];
int mid = (l+r)>>>1;
int leftHalf = rec(nums,l,mid);
int rightHalf = rec(nums,mid+1,r);
if(leftHalf == rightHalf)
return leftHalf;
int leftCount = countInRange(nums,leftHalf,l,r);
int rightCount = countInRange(nums,rightHalf,l,r);
return leftCount>rightCount?leftHalf:rightHalf;
}
int countInRange(int[] nums,int num,int l,int r){
int cnt = 0;
for(int i=l;i<=r;i++){
if(nums[i]==num){
cnt++;
}
}
return cnt;
}
}
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
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
# 75. 颜色分类 (opens new window)
循环不变量
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
if(n<2)
return ;
int l=0,r=n;
int i=0;
while(i<r){
if(nums[i]==0){
swap(nums,i,l);
l++;i++;
}else if(nums[i]==1){
i++;
}else{
r--;
swap(nums,i,r);
}
}
}
void swap(int[] nums,int l,int r){
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 31. 下一个排列 (opens new window)
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n-2;
while(i>=0){
if(nums[i]<nums[i+1])
break;
i--;
}
if(i>=0){
int j = n-1;
while(j>=0){
if(nums[j]>nums[i]){
break;
}
j--;
}
swap(nums,i,j);
}
rev(nums,i+1,n-1);
}
void rev(int[] nums,int l,int r){
while(l<r){
swap(nums,l,r);
l++;r--;
}
}
void swap(int[] nums,int l,int r){
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
}
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
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
# 287. 寻找重复数 (opens new window)
方法一：二分
class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length;
// 在[1..n-1]中查找重复元素
int l=1,r=n-1;
// 开区间，最后l,r重合
while(l<r){
int mid = (l+r)>>>1;
// 记录nums中<=mid的元素个数
int cnt = 0;
for(int num:nums){
if(num<=mid)
cnt++;
}
if(cnt>mid)
// 代表重复元素在[l..mid]中
r = mid;
else
l = mid+1;
}
return l;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
方法二：快慢指针
class Solution {
public int findDuplicate(int[] nums) {
int slow=0,fast=0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = 0;
while(fast != slow){
fast = nums[fast];
slow = nums[slow];
}
return fast;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17