代码随想录三刷

数组

704.二分查找

 public int search(int[] nums, int target) {
		  int left=0;
		  int right=nums.length-1;
		  int mid=0;
	        while(left<=right) {
	        	mid=left+(right-left)>>1;
	            if(nums[mid]==target) {
	            	return mid;
	            }else if(nums[mid]>target) {
	            	right=mid-1;
	            }else if(nums[mid]<target) {
	            	left=mid+1;
	            }
	        }
	        return -1;
	    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

35. 搜索插入位置

//最后是左区间有问题。

  public int searchInsert(int[] nums, int target) {
		   int left=0;
		   int right=nums.length-1;
		   int mid=0;
		   while(left<=right) {
			   mid=left+(right-left)/2;
	            if(nums[mid]==target) {
	            	return mid;
	            }else if(nums[mid]>target) {
	            	right=mid-1;
	            }else if(nums[mid]<target) {
	            	left=mid+1;
	            }
		   }
		   return left;

	    }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

34. 在排序数组中查找元素的第一个和最后一个位置

  /*
	    * 需要有两个二分查找，分别去查找左边界和右边界
	    * 分三种情况：
	    * 1.target在数组范围外，直接返回-1。
	    * 2.target在数组范围里，但在数组中没有找到这个target
	    * 3.target在数组范围里边，且有这两个目标值
	    */
	   public int[] searchRange(int[] nums, int target) {
		   
		  
		   int left=findLeftBorder(nums,target);
		   int right=findRightBorder(nums,target);
		   if(left==-1&&right==-1) {
			   return new int[] {-1,-1};
		   }
		   if(target<nums[0]||target>nums[nums.length-1]) {
			   return new int[] {-1,-1};
		   }
		   if(right-left>1) {
			   return new int[] {left+1,right-1};
		   }
		   return new int[] {-1,-1};

	    }
	   public int findRightBorder(int []nums,int target) {
		   int resultRight=-1;
		   int left=0;
		   int right=nums.length-1;
		   int mid=0;
		   while(left<=right) {
			   mid=left+(right-left)/2;
			   if(nums[mid]>target) {
				   right=mid-1;
			   }else {//当nums[mid]==target的时候，更新左边界,但等于的时候不能直接返回，因为右边还可能有相同的数字，所以要找到最右边的节点
				   
				   left=mid+1;
				   resultRight=left;
				   
			   }
		   }
		   return resultRight;
	   }
      
	   
	   public int findLeftBorder(int []nums,int target) {
		   int resultLeft=-1;
		   int left=0;
		   int right=nums.length-1;
		   int mid=0;
		   while(left<=right) {
			   mid=left+(right-left)/2;
			   if(nums[mid]<target) {
				   left=mid+1;
			   }else {//当nums[mid]==taregt的时候，更新右边界，然后获取到左边界的内容
				   right=mid-1;
				   resultLeft=right;
				   
			   }
		   }
		   return resultLeft;
		   
	   }
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

69. x 的平方根

/*
	    * 用二分查找[0,x]之间的目标值
	    */
	   public int mySqrt(int x) {
		   int left=0;
		   int right=x;
		   int mid=1;
		   while(left<=right) {
			   mid=left+((right-left)>>1);
			   if((long)mid*mid>x) {
				   right=mid-1;
			   }else if((long)mid*mid<x) {
				   left=mid+1;
			   }else if((long)mid*mid==x){
				   return  mid;
			   }
		   }
		   return right;
		   

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

367. 有效的完全平方数

  public boolean isPerfectSquare(int num) {
		   long left=0;
		   long right=num;
		   long mid=1;
		   while(left<=right) {
			   mid=left+((right-left)>>1);
			   if(mid*mid>num) {
				   right=mid-1;
			   }else if(mid*mid<num) {
				   left=mid+1;
			   }else if(mid*mid==num){
				   return  true;
			   }
		   }
		   return false;
		   

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

977. 有序数组的平方

/*
	    * 双指针排序,两个指针分别在起始位置和终止位置，然后依次放在新数组里边
	    */
	   public int[] sortedSquares(int[] nums) {
		  int[] newsum=new int[nums.length];
		  int start=0;
		  int last=nums.length-1;
		  for(int i=newsum.length-1;i>=0;i--) {
			  if(nums[start]*nums[start]>nums[last]*nums[last]) {
				  newsum[i]=nums[start]*nums[start];
				  start++;
			  }else {
				  newsum[i]=nums[last]*nums[last];
				  last--;
			  }
		  }
		  
		  return newsum;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

27.移除元素

 /*
	    * 快慢指针，快指针向前遍历来筛选数据，然后慢指针向后遍历
	    */
	   public int removeElement(int[] nums, int val) {
		   int slow=0;
		   for(int fast=0;fast<nums.length;fast++) {
			   if(nums[fast]==val) {
				   continue;
			   }else {
				   nums[slow++]=nums[fast];
			   }
		   }
		   return slow;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

26. 删除有序数组中的重复项

 public int removeDuplicates(int[] nums) {
		   int slow=1;
           int fast=1;
           while(fast<nums.length) {
        	   if(nums[fast]!=nums[fast-1]) {
        		   nums[slow]=nums[fast];
        		   slow++;
        	   }
        	   fast++;
           }
           return slow;
	    }
1
2
3
4
5
6
7
8
9
10
11
12

283.移动零

 /*快慢指针：
	    * 如果遇到0的话就跳过，然后再在后边补0
	    */
	    public void moveZeroes(int[] nums) {
	    	int slow=0;
	    	for(int i=0;i<nums.length;i++) {
	    		if(nums[i]!=0) {
	    			nums[slow]=nums[i];
	    			slow++;
	    		}
	    	}
	    	for(int i=slow+1;i<nums.length;i++) {
	    		nums[i]=0;
	    	}
	    	

	    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

844. 比较含退格的字符串

public static boolean backspaceCompare(String s, String t) {
           Stack a=new Stack();
           Stack b=new Stack();
           for(int i=0;i<s.length();i++) {
        	   if(s.charAt(i)=='#') {
        		   if(!a.isEmpty()){
        		   a.pop();
        		   }
        		   
        	   }else {
        		   a.push(s.charAt(i));
        	   }
  
           }
           for(int i=0;i<t.length();i++) {
        	   if(t.charAt(i)=='#') {
        		   if(!b.isEmpty()){
            		   b.pop();
            		  }
        	   }else {
        		   b.push(t.charAt(i));
        	   }
        	 
           }

           return a.equals(b);
           
	  }

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

209. 长度最小的子数组

/*
	     * 找到满足和大于target，且长度最小的连续子数组,
	     * 当右指针找到目标值后，然后左指针一直往右走
	     */
	    public int minSubArrayLen(int target, int[] nums) {
	    	int result= Integer.MAX_VALUE;//存储结果
	    	int right=0;//右指针
	    	int left=0;//左指针
	    	int sum=0;
	    	for( right=0;right<nums.length;right++) {
	    		sum+=nums[right];
	    		while(sum>=target) {
	    			result=Math.min(result, right-left+1);
	    			sum-=nums[left];
	    			left++;
	    		}
	    	}
	    	return result==Integer.MAX_VALUE?0:result;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

904.水果成栏

 /*
	     * 也是滑动窗口的思路，用Map来代表果篮里的水果数量，当果篮里的数量到达2种时，就开始移除果篮里的水果
	     * map,以种类为键，以数量为值,因为果树是连续的，所以只能一颗一颗的采摘
	     */
	    public int totalFruit(int[] fruits) {
	    	int right=0;//右指针
	    	int left=0;//左指针
	    	int result=0;//存储结果
	    	Map<Integer,Integer> pack=new HashMap<Integer,Integer>();//代表背包
	    	for(right=0;right<fruits.length;right++) {
	    		pack.put(fruits[right],pack.getOrDefault(fruits[right], 0)+1);
	    		while(pack.size()>2) {//当包裹的水果种类大于2时
	    			pack.put(fruits[left],pack.get(fruits[left])-1);
	    			if(pack.get(fruits[left])==0) {//
	    				pack.remove(fruits[left]);
	    				
	    			}
	    			left++;
	    		}
	    		result=Math.max(result, right-left+1);
	    	}
	    	return result;
	    	

	    }
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

59. 螺旋矩阵 II

 /*
	     * 万能解：定义好矩阵的上下左右边界，如果越界的话，直接break;
	     */
	    public int[][] generateMatrix(int n) {
	    	int index=1;
	    	int [][]result=new int[n][n];
	    	int left=0;
	    	int right=n-1;
	    	int top=0;
	    	int bottom=n-1;
	    	while(true) {
	    		for(int i=left;i<=right;i++) {//从左到右
	    			result[top][i]= index++;
	    		}
	    		top++;
	    		if(top>bottom) {
	    			break;
	    		}
	    		for(int i=top;i<=bottom;i++) {//从上到下
	    			result[i][right]= index++;
	    		}
	    		right--;
	    		if(right<left) {
	    			break;
	    		}
	    		
	    		for(int i=right;i>=left;i--) {//从右到左
	    			result[bottom][i]= index++;
	    		}
	    		bottom--;
	    		if(bottom<top) {
	    			break;
	    		}
	    		for(int i=bottom;i>=top;i--) {//从下到上
	    			result[i][left]= index++;
	    		}
	    		left++;
	    		if(left>right) {
	    			break;
	    		}
	    	}
	    	return result;

	    }
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

54. 螺旋矩阵

   /**
	     * 
	     * 万能解：
	     */
	    public List<Integer> spiralOrder(int[][] matrix) {
	    	List<Integer> result=new ArrayList<Integer>();
	    	int m=matrix.length;//m行
	    	int n=matrix[0].length;//n列
	    	int top=0;
	    	int left=0;
	    	int bottom=m-1;
	    	int right=n-1;
	    	while(true) {
	    		for(int i=left;i<=right;i++) {//从左到右
	    			result.add(matrix[top][i]);
	    		}
	    		top++;
	    		if(top>bottom) {
	    			break;
	    		}
	    		for(int i=top;i<=bottom;i++) {//从上到下
	    			result.add(matrix[i][right]);
	    			
	    		}
	    		right--;
	    		if(right<left) {
	    			break;
	    		}
	    		for(int i=right;i>=left;i--) {//从右到左
	    			result.add(matrix[bottom][i]);
	    		}
	    		bottom--;
	    		if(bottom<top) {
	    			break;
	    		}
	    		for(int i=bottom;i>=top;i--) {//从下到上
	    			result.add(matrix[i][left]);
	    			
	    		}
	    		left++;
	    		if(left>right) {
	    			break;
	    		}
	    			
	    	}
	    	return result;
		    

	    }
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

剑指 Offer 29. 顺时针打印矩阵

 public int[] spiralOrder(int[][] matrix) {
		 	if(matrix.length==0) {
	    		return new int[] {};
	    	}
	    	List<Integer> result=new ArrayList<Integer>();
	    	int m=matrix.length;//m行
	    	int n=matrix[0].length;//n列
	    	int top=0;
	    	int left=0;
	    	int bottom=m-1;
	    	int right=n-1;
	    	while(true) {
	    		for(int i=left;i<=right;i++) {//从左到右
	    			result.add(matrix[top][i]);
	    		}
	    		top++;
	    		if(top>bottom) {
	    			break;
	    		}
	    		for(int i=top;i<=bottom;i++) {//从上到下
	    			result.add(matrix[i][right]);
	    			
	    		}
	    		right--;
	    		if(right<left) {
	    			break;
	    		}
	    		for(int i=right;i>=left;i--) {//从右到左
	    			result.add(matrix[bottom][i]);
	    		}
	    		bottom--;
	    		if(bottom<top) {
	    			break;
	    		}
	    		for(int i=bottom;i>=top;i--) {//从下到上
	    			result.add(matrix[i][left]);
	    			
	    		}
	    		left++;
	    		if(left>right) {
	    			break;
	    		}
	    			
	    	}
	    	return result.stream().mapToInt(x->x).toArray();

	    }
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

链表

203. 移除链表元素

  /*
	       * 设置一个虚拟头节点，遇到目标值的节点就跳过
	   */
	  public ListNode removeElements(ListNode head, int val) {
		  
		  ListNode dummy=new ListNode(-1,head);
		  ListNode pre=dummy;//指向上一个节点
		  ListNode cur=head;
		  while(cur!=null) {
			  if (cur.val==val) {
				  pre.next=cur.next;
			  }else {
				  pre=cur;
			  }
			  cur=cur.next;
		  }
		  return dummy.next;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

206. 反转链表

  /*
	   * 反转链表,需要两个指针，一个指向指针的下一个节点，下一个节点指向之前的节点
	   */
	   public ListNode reverseList(ListNode head) {
		   ListNode pre=null;
		   ListNode next=null;
		   while(head!=null) {
			   next=head.next;
			   head.next=pre;
			   pre=head;
			   head=next;
		   }
		   return pre;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

92. 反转链表 II

 /*
	       * 反转指定区域的链表,需要三个指针，一个永远指向反转区域的前一个节点，一个指向要操作的节点，一个指向要操作节点的下一个节点
	    */
	    public ListNode reverseBetween(ListNode head, int left, int right) {
	    	ListNode dummy=new ListNode(-1,head);
	    	ListNode pre=dummy;
	    	for(int i=0;i<left-1;i++) {
	    		pre=pre.next;
	    	}
	    	ListNode cur=pre.next;
	    	ListNode next=null;
	    	for(int i=0;i<right-left;i++) {
	    		next=cur.next;
	    		cur.next=next.next;
	    		next.next=pre.next;
	    		pre.next=next;
	    	}
	    	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

24. 两两交换链表中的节点

    /*
	     * 用两个节点来分别模拟就可以了 ,cur要保证指向交换两个节点的前一个节点
	     */
	    public ListNode swapPairs(ListNode head) {
	    	ListNode dummy=new ListNode(-1,head);
	    	ListNode cur=dummy;
	    	ListNode temp1;
	    	ListNode temp2;
	    	while(cur.next!=null&&cur.next.next!=null) {
	    		temp1=cur.next;
	    		temp2=cur.next.next;
	    		temp1.next=temp2.next;
	    		temp2.next=cur.next;
	    		cur.next=temp2;
	    		cur=temp1;
	    		
	    	}
	    	return dummy.next;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

19. 删除链表的倒数第 N 个结点

    /*
	     * 快指针先走n步，然后快慢指针同时走，快指针指向空的时候，慢指针就删除节点就可以了
	     */
	    public ListNode removeNthFromEnd(ListNode head, int n) {
	    	ListNode dummy=new ListNode(-1,head);
	    	n++;//因为设置了虚拟节点，所以快指针多走一步
	    	ListNode fast=dummy;
	    	ListNode slow=dummy;
	    	while(n-->0&&fast!=null) {
	    		fast=fast.next;
	    	}
	    	while(fast!=null) {
	    		fast=fast.next;
	    		slow=slow.next;
	    	}
	    	slow.next=slow.next.next;
	    	return dummy.next;
	    	

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

160. 相交链表

  /*
                  * 用两个指针，一个链表走到头的时候走第二个链表的起点
         */
	    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	    	
	    	if(headA==null||headB==null) {
	    		return null;
	    	}
	    	ListNode p1=headA;
	    	ListNode p2=headB;
	    	while(p1!=p2) {
	    		p1=p1==null?headB:p1.next;
	    		p2=p2==null?headA:p2.next;
	    	}
	        return p1;
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

141. 环形链表

 /*
	          *  用快慢指针，一个走一步，一个走两步，如果两个指针能相遇，就证明有环
	     */
	    public boolean hasCycle(ListNode head) {
	        ListNode fast=head;
	        ListNode slow=head;
	        if(head==null) {
	        	return false;
	        }
	        if(fast.next!=null) {
	        	fast=fast.next;
	        }
	        while(fast.next!=null&&fast.next.next!=null) {
	        	if(fast==slow) {
	        		return true;
	        	}
	        	fast=fast.next.next;
	        	slow=slow.next;
	        	
	        }
	        return false;
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

142. 环形链表 II

   
	    /*
	          * 用两个快慢指针，找到相遇位置，然后再设两个指针，从相遇位置和开头位置一起走，走到相遇的时候就是链表的入环节点
	     */
	    public ListNode detectCycle(ListNode head) {
	    	if(head==null) {
	    		return null;
	    	}
	    	ListNode slow=head;
	    	ListNode fast=head;
	    	while(fast.next!=null&&fast.next.next!=null) {
	    		slow=slow.next;
	    		fast=fast.next.next;
	    		if(slow==fast) {
	    			ListNode index1=slow;
	    			ListNode index2=head;
	    			while(index1!=index2) {
	    				index1=index1.next;
	    				index2=index2.next;
	    				
	    			}
	    			return index1;
	    		}
	    	}
	    	return 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

242. 有效的字母异位词

 /*
	          * 将s中出现的单词存在一个数组里边，然后t中出现的单词再减去
	     */
	    public boolean isAnagram(String s, String t) {
	    	char []arr=new char[27];
	    	for(int i=0;i<s.length();i++) {
	    		arr[s.charAt(i)-'a']++;
	    	}
	    	for(int i=0;i<t.length();i++) {
	    		arr[t.charAt(i)-'a']--;
	    	}
	    	for(int i:arr) {
	    		if(i!=0) {
	    			return false;
	    		}
	    	}
	    	return true;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

49. 字母异位词分组

 /*
	          *  以排序后的单词作为键，单词作为值,把它拿出来再放进去即可
	     */
	    public List<List<String>> groupAnagrams(String[] strs) {
	    	Map<String,List<String>> map=new HashMap<String,List<String>>();
	    	for(String str:strs) {
	    		char []arr=str.toCharArray();
	    		Arrays.sort(arr);
	    		String key=new String(arr);
	    		List<String> list=map.getOrDefault(key, new ArrayList<String>());
	    		list.add(str);
	    		map.put(key,list);
	    		
	    		
	    	}
	    	
	    	return new ArrayList<List<String>>(map.values());

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

349. 两个数组的交集

   /*
         * 将一个数组存到set里边，然后遍历另一个数组，把重复的存到result里边
         */
	    public int[] intersection(int[] nums1, int[] nums2) {
	    	Set<Integer> set=new HashSet<Integer>();
	    	Set<Integer> result=new HashSet<Integer>();
	    	for(int i:nums1) {
	    		set.add(i);
	    	}
	    	for(int i:nums2) {
	    		if(set.contains(i)) {
	    			result.add(i);
	    		}
	    	}
	    	
	    	return result.stream().mapToInt(x->x).toArray();
 
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

202.快乐数

  /*
	     * 用set将每次出现的数都存起来，如果出现的话就返回false
	     */
	    public boolean isHappy(int n) {
	    	Set<Integer> res=new HashSet<Integer>();
	    	while(n!=1&&!res.contains(n)) {
	    		res.add(n);
	    		n=nextHappy(n);
	    	}
	    	return n==1;

	    }
	    /*
	     * 求出这个数字的下一个快乐数
	     */
	    public int nextHappy(int n) {
	    	int result=0;
	    	while(n>0) {
	    		int index=n%10;
	    		result+=index*index;
	    		n/=10;
	    	}
	    	return result;
	    }

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

1. 两数之和

  /*
	     * 用数组的值作为键，数组的下标作为值，然后只遍历一次就能遍历出来。
	     */
	    public int[] twoSum(int[] nums, int target) {
	    	Map<Integer,Integer> map=new HashMap<Integer,Integer>();
	    	for(int i=0;i<nums.length;i++) {
	    		if(map.containsKey(target-nums[i])) {
	    			return new int[] {i,map.get(target-nums[i])};
	    		}
	    		map.put(nums[i],i);
	    	}
	    	return new int[] {0};

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

454. 四数相加 II

  /*
	     * 先遍历一遍数组1和数组2，把他们存到map中，以nums[i]+nums[j]作为键，出现的次数作为值
	     */
	    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
	    	Map<Integer,Integer> map=new HashMap<Integer,Integer>();
	    	int result=0;
	    	for(int i:nums1) {
	    		for(int j:nums2) {
	    			map.put(i+j,map.getOrDefault(i+j, 0)+1);
	    		}
	    	}
	    	for(int i:nums3) {
	    		for(int j:nums4) {
	    			if(map.containsKey(0-i-j)) {
	    				result+=map.get(0-i-j);
	    			}
	    		}
	    	}
	    	return result;
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

15. 三数之和

  /*
	     * 先把数组排好序，然后遍历，找第一个数字，然后用两个指针，首尾开始走，直到找出结果
	     */
	    public List<List<Integer>> threeSum(int[] nums) {
	    	List<List<Integer>> result= new ArrayList<List<Integer>>();
	    	Arrays.sort(nums);
	    	for(int i=0;i<nums.length;i++) {
	    		if(i>0&&nums[i]==nums[i-1]) {//去重逻辑
	    			continue;
	    			
	    		}
	    		int left=i+1;
	    		int right=nums.length-1;
	    		while(left<right) {
	    			if((nums[i]+nums[left]+nums[right])==0) {
	    				result.add(Arrays.asList(nums[i],nums[left],nums[right]));
	    				while(left<right&&nums[left]==nums[left+1]) {//找到节点后也要去重
	    					left++;
	    				}
	    				while(left<right&&nums[right]==nums[right-1]) {//找到节点后也要去重
	    					right--;
	    				}
	    				left++;
	    				right--;
	    			}else if((nums[i]+nums[left]+nums[right])<0) {
	    				left++;
	    			}else if((nums[i]+nums[left]+nums[right])>0) {
	    				right--;
	    			}
	    		}
	    	}
	    	
	    	return result;
	    	

	    }
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

18. 四数之和

   /*
	          * 先把数组排好序，外边套两层循环
	            然后注意去重操作
	     */
	    public List<List<Integer>> fourSum(int[] nums, int target) {
	    	List<List<Integer>> result=new ArrayList<List<Integer>>();
	    	Arrays.sort(nums);
	    	for(int i=0;i<nums.length;i++) {
	    		if(i>0&&nums[i]==nums[i-1]) {//去重操作
	    			continue;
	    		}
	    		// 剪枝操作，如果nums[k]大于0,并且nums[k]大于target的话，可以直接return了。为啥要target大于0呢，因为如果是负数的情况，会出现两个数相加越来越小的情况
				if (nums[i] > 0 && nums[i]>target) {
					return result;
				}
	    		for(int j=i+1;j<nums.length;j++) {
	    			if(j>i+1&&nums[j]==nums[j-1]) {
	    				continue;//去重操作
	    			}
	    			int left=j+1;
	    			int right=nums.length-1;
	    			while(left<right) {
	    				if((nums[i]+nums[j]+nums[left]+nums[right])==target){
	    					result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
	    					while(left<right&&nums[left]==nums[left+1]) {//去重操作
	    						left++;
	    					}
	    					while(left<right&&nums[right]==nums[right-1]) {//去重操作
	    						right--;
	    					}
	    					left++;
	    					right--;
	    				}else if((nums[i]+nums[j]+nums[left]+nums[right])>target) {
	    					right--;
	    					
	    				}else if((nums[i]+nums[j]+nums[left]+nums[right])<target) {
	    					left++;
	    				}
	    			}
	    		}
	    	}
	    	return result;

	    }
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

字符串

344. 反转字符串

   /*
	         * 从左到右来交换字符串的位置即可
	     */
	    public void reverseString(char[] s) {
	    	
	    	for(int left=0, right=s.length-1;left<right;left++,right--) {
	    		swap(s,left,right);
	    	}

	    }
	    public void swap(char []s,int i,int j) {
	    	char temp=s[i];
	    	s[i]=s[j];
	    	s[j]=temp;
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

541. 反转字符串 II

  /*
	         * 从左到右来交换字符串的位置即可
	     */
	    public void reverseString(char[] s,int i,int j) {
	    	
	    	for(int left=i, right=j-1;left<right;left++,right--) {
	    		swap(s,left,right);
	    	}

	    }
	    public void swap(char []s,int i,int j) {
	    	char temp=s[i];
	    	s[i]=s[j];
	    	s[j]=temp;
	    }
	    /*
	           * 给出一个函数可以反转(i,k)区间里的字符串
	     */
	    public String reverseStr(String s, int k) {
	    	char []array=s.toCharArray();
	    	for(int i=0;i<s.length();i+=2*k) {
	    		if(i+k<s.length()) {
	    			reverseString(array,i,i+k);
	    			continue;//跳过本次循环，不再执行下边的语句
	    		}
	    		reverseString(array,i,array.length);
	    	}
	    	return new String(array);

	    }
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

剑指 Offer 05. 替换空格

class Solution {
      public String replaceSpace(String s) {
		   StringBuffer result=new StringBuffer();
		   for(int i=0;i<s.length();i++) {
			   if(s.charAt(i)==' ') {
				   result.append("%20");
			   }else {
				   result.append(s.charAt(i));
			   }
		   }
		   return new String(result);

	    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

151.反转字符串中的单词

  
	    /*
            * 从左到右来交换字符串的位置即可
     */
    public void reverseString(char[] s,int i,int j) {
    	
    	for(int left=i, right=j-1;left<right;left++,right--) {
    		swap(s,left,right);
    	}

    }
    public void swap(char []s,int i,int j) {
    	char temp=s[i];
    	s[i]=s[j];
    	s[j]=temp;
    }
    /*
        /*
                  * 先翻转整体的单词，然后再翻转每个单词，
                  * 先用快慢指针遍历一遍字符串，去除多余的空格
         */
	    public String reverseWords(String s) {
            char []array=s.toCharArray();
            int fast=0;
            int slow=0;
            for(fast=0;fast<array.length;fast++) {
                if(array[fast]!=' ') {
                	if(slow!=0) {
                		array[slow++]=' ';
                	}
                	while(fast<array.length&&array[fast]!=' ') {
                		array[slow++]=array[fast++];
                	}
                }
            }
            //翻转每个单词
            //2.反转整个字符串
  		  reverseString(array, 0, slow);
            int start=0;
            for(int i=0;i<=slow;i++) {
            	if(i==slow||array[i]==' ') {
            		reverseString(array,start,i);
            		start=i+1;
            	}
            }
            return new String(array).substring(0,slow);
            
	    }
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

剑指 Offer 58 - II. 左旋转字符串

 /*
            * 从左到右来交换字符串的位置即可
     */
    public void reverseString(char[] s,int i,int j) {
    	
    	for(int left=i, right=j-1;left<right;left++,right--) {
    		swap(s,left,right);
    	}

    }
    public void swap(char []s,int i,int j) {
    	char temp=s[i];
    	s[i]=s[j];
    	s[j]=temp;
    }
   public String reverseLeftWords(String s, int n) {
	    	char[]array=s.toCharArray();
	    	reverseString(array,0,n);
	    	reverseString(array,n,array.length);
	    	//进行整体的翻转
	    	reverseString(array,0,array.length);
	    	return new String(array);
   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

28. 找出字符串中第一个匹配项的下标

/*
	     * kmp算法，先得到next数组
	     */
	    public int strStr(String haystack, String needle) {
	    	  if(needle.length()==0) {
				  return 0;
			  }
	    	
	    	int []next=new int[needle.length()];
	    	getNext(next,needle);
	    	int j=0;
	    	for(int i=0;i<haystack.length();i++) {
	    		while(j>0&&haystack.charAt(i)!=needle.charAt(j)) {
	    			j=next[j-1];//回退指针
	    		}
	    		if(haystack.charAt(i)==needle.charAt(j)) {
	    			j++;
	    		}
	    		if(j==needle.length()) {
	    			return i-needle.length()+1;
	    		}
	    	}
	    	return -1;

	    }
	    public void getNext(int []next,String needle) {
	    	next[0]=0;
	    	int j=0;//j指向前缀末尾，i指向后缀末尾，用来填充next数组
	    	for(int i=1;i<needle.length();i++) {
	    		while(j>0&&needle.charAt(i)!=needle.charAt(j)) {//进行回退操作
	    			j=next[j-1];
	    		}
	    		if(needle.charAt(i)==needle.charAt(j)) {
	    			j++;
	    			next[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
27
28
29
30
31
32
33
34
35
36
37
38

459. 重复的子字符串

 /*
	     * 将字符串拼接一下，然后去掉首字符和末尾字符，看拼接的字符串是不是包含原字符串
	     */
	    public boolean repeatedSubstringPattern(String s) {
	    	String index=s+s;
	    	return .substring(1, index.length()-1).contains(s);

	    }
	    
1
2
3
4
5
6
7
8
9

栈与队列

232.用栈实现队列

   /*
	     * 一个入栈一个出栈，入栈之间进入入栈就行,出栈的时候需要把入栈的元素全都放到出栈里，如果不放全部，就会出现问题
	     */
	    class MyQueue {
	    	Stack<Integer> inStack;
	    	Stack<Integer> outStack;

	        public MyQueue() {
	        	inStack=new Stack<Integer>();
	        	outStack=new Stack<Integer>();

	        }
	        
	        public void push(int x) {
                inStack.push(x);
	        }
	        
	        public int pop() {
                dummyInstack();
                return outStack.pop();
	        }
	        
	        public int peek() {
	        	dummyInstack();
	        	return outStack.peek();

	        }
	        
	        public boolean empty() {
               return inStack.isEmpty()&&outStack.isEmpty();
	        }
	        /*
	         * 清空入栈
	         */
	        public void dummyInstack() {
	        	if(!outStack.isEmpty()) {//如果出栈中还有元素，之间返回即可，因为出队的时候直接让它出就可以了
	        		return ;
	        	}
	        	while(!inStack.isEmpty()) {
	        		outStack.push(inStack.pop());
	        	}
	        	
	        }
	    }
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

225. 用队列实现栈

  /*
	          * 每次pop的时候都要去移动元素，top的时候只需要top队列的最后一个即可
	     */
	    class MyStack {
	    	Deque<Integer> deque;

	        public MyStack() {
               deque= new ArrayDeque<Integer>();
	        }
	        
	        public void push(int x) {
                 deque.addLast(x);
	        }
	        /*
	                  * 移动size-1个元素去队尾
	         */
	        public int pop() {
	        	int size =deque.size();
	        	size--;
	        	while(size-->0) {
	        		deque.addLast(deque.pollFirst());
	        	}
	        	return deque.pollFirst();

	        }
	        
	        public int top() {
                return deque.peekLast();
	        }
	        
	        public boolean empty() {
               return deque.isEmpty();
	        }
	    }
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

20. 有效的括号

 /*
	     * 1.括号不匹配的情况
	     * 2.左括号多的情况  （放完之后栈空了）
	     * 3.右括号多的情况（栈为空了）
	     */
	    public boolean isValid(String s) {
	    	Stack<Character> stack=new Stack<Character>();
	    	for(int i=0;i<s.length();i++) {
	    		if(s.charAt(i)=='(') {
	    			stack.push(')');
	    		}else if(s.charAt(i)=='[') {
	    			stack.push(']');
	    		}else if(s.charAt(i)=='{') {
	    			stack.push('}');
	    		}else if(stack.isEmpty()||s.charAt(i)!=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
20
21
22
23
24

1047. 删除字符串中的所有相邻重复项

  /*
	           * 用栈来操作，如果栈顶和栈底不相同，就入栈操作
	     */
	    public String removeDuplicates(String s) {
	    	
	    	Stack<Character> stack=new Stack<Character>();
	    	for(int i=0;i<s.length();i++) {
	    		if(stack.isEmpty()||s.charAt(i)!=stack.peek()) {
	    			stack.push(s.charAt(i));
	    		}else {
	    			stack.pop();
	    		}
	    		
	    	}
	    	return stack.toString().substring(1,stack.toString().length()-1).replace(",", "").replace(" ", "");

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

150. 逆波兰表达式求值

 /*
	          * 用栈，如果遇到数字就放进去，如果遇到操作符号的话，就把栈顶的两个元素拿出来，做一下运算再放进去。
	     */
	    public int evalRPN(String[] tokens) {
	    	Stack<Integer> stack= new Stack<Integer>();
	    	for(String str:tokens) {
	    		if(str.equals("+")) {
	    			Integer number1=stack.pop();
	    			Integer number2=stack.pop();
	    			stack.add(number1+number2);
	    		}else if(str.equals("-")) {
	    			Integer number1=stack.pop();
	    			Integer number2=stack.pop();
	    			stack.add(number2-number1);
	    		}else if(str.equals("*")) {
	    			Integer number1=stack.pop();
	    			Integer number2=stack.pop();
	    			stack.add(number2*number1);
	    		}else if(str.equals("/")) {
	    			Integer number1=stack.pop();
	    			Integer number2=stack.pop();
	    			stack.add(number2/number1);
	    		}else {
	    			stack.add(Integer.valueOf(str));
	    		}
	    	}
	    	return stack.pop();

	    }
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

239. 滑动窗口最大值

 /*
	     * 自己定义一个优先级队列,里边有三个方法,pop(),push(),getMaxValue。保证队首的元素一直是最大值
	     */
	    class MyQueue1{
	    	public Deque<Integer> deque;
	    	public MyQueue1(){
	    		deque =new LinkedList<Integer>();
	    	}
	    	/*
	    	 * 从队列里边弹出一个元素，当这个元素等于队首元素时再弹出，如果不等于时,前边push的时候自然会删掉前边的元素
	    	 */
	    	public void poll(int val) {
	    		if(!deque.isEmpty()&&deque.peekFirst()==val) {
	    			deque.pollFirst();
	    		}
	    		
	    	}
	    	/*
	    	 * 当加进这个元素的时候，要保证删除前边比它小的元素
	    	 */
	    	public void push(int val) {
	    		while(!deque.isEmpty()&&val>deque.getLast()) {
	    			deque.removeLast();
	    		}
	    		deque.addLast(val);
	    	}
	    	/*
	    	 *得到队列里的最大值，队首的元素就是最大值
	    	 */
	    	public int getMaxValue() {
	    		return deque.getFirst();
	    	}
	    }
	    public int[] maxSlidingWindow(int[] nums, int k) {
	    	List<Integer> result=new ArrayList<Integer>();
	    	MyQueue1 mydeque=new MyQueue1();
	    	for(int i=0;i<k;i++) {
	    		mydeque.push(nums[i]);
	    	}
	    	result.add(mydeque.getMaxValue());
	    	//当这个队列走了一步之后再收集结果，也就是加入一个元素再弹出一个元素
	    	for(int i=k;i<nums.length;i++) {
	    		mydeque.push(nums[i]);//加入一个元素
	    		mydeque.poll(nums[i-k]);//弹出一个元素
	    		result.add(mydeque.getMaxValue());//收集结果集
	    	
	    	}
	    	return result.stream().mapToInt(x->x).toArray();

	    }
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

347. 前 K 个高频元素

 /*
	     * 将数组中出现的数字和次数用Map来统计一遍，然后再用大顶堆这个结构来进行一个排序，就不用排全部的了
	     */
	    public int[] topKFrequent(int[] nums, int k) {
	    	Map<Integer,Integer> map=new HashMap<Integer,Integer>();
	    	for(int i:nums) {
	    		map.put(i,map.getOrDefault(i, 0)+1);
	    	}
	    	PriorityQueue<int []>queue=new PriorityQueue<int[]>((x1,x2)->(x2[1]-x1[1]));//按数字出现的频率从大到小排序
	    	for(Map.Entry<Integer, Integer> entry:map.entrySet()) {
	    		queue.add(new int[] {entry.getKey(),entry.getValue()});
	    	}
	    	int []result=new int[k];//存结果
	    	for(int i=0;i<k;i++) {
	    		result[i]=queue.poll()[0];
	    	}
	    	return result;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二叉树

144. 二叉树的前序遍历

  /*
	    * 递归遍历
	    */
	   public List<Integer> preorderTraversal(TreeNode root) {
		   List<Integer> result=new ArrayList<Integer>();
		   pre(result,root);
		   return result;

	    }
	   
	   public void pre(List<Integer> result,TreeNode root) {
		   //终止条件
		   if(root==null) {
			   return ;
		   }
		   result.add(root.val);
		   pre(result,root.left);
		   pre(result,root.right);
		   
	   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

145. 二叉树的后序遍历

/*
	    * 后序递归遍历
	    */
	   public List<Integer> postorderTraversal(TreeNode root) {
		   List<Integer> result=new ArrayList<Integer> ();
		   post(result,root);
		   return result;

	    }
	   
	   public void post(List<Integer> result,TreeNode root) {
		   //终止条件
		   if(root==null) {
			   return ;
		   }
		   post(result,root.left);
		   post(result,root.right);
		   result.add(root.val);
		  
	   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

94. 二叉树的中序遍历

/*
	    * 中序递归遍历，把结果当成一个参数传过去，然后左中右的次序去遍历即可
	    */
	   public List<Integer> inorderTraversal(TreeNode root) {
		   List<Integer> result=new ArrayList<Integer> ();
		   inorder(result,root);
		   return result;

	    }
	   public void inorder(List<Integer> result,TreeNode root) {
		   //终止条件
		   if(root==null) {
			   return ;
		   }
		   inorder(result,root.left);
		   result.add(root.val);
		   inorder(result,root.right);
	   }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

144.二叉树的前序遍历（迭代）

 /*
	        * 迭代先序遍历，先处理根节点，然后放右子树，然后放左子树，因为先序是中，左，右的顺序，所以要先放右子树，要访问的节点和要处理的节点是一样的。
	    */
	   public List<Integer> preorderTraversal(TreeNode root) {
		   List<Integer> result=new ArrayList<Integer>();
		   Stack<TreeNode> stack=new Stack<TreeNode>();
		   if(root==null) {
			   return result;
		   }
		   stack.add(root);
		   while(!stack.isEmpty()) {
			   TreeNode node=stack.pop();
			   result.add(node.val);
			   if(node.right!=null) {
				   stack.add(node.right);
			   }
			   if(node.left!=null) {
				   stack.add(node.left);
			   }
		   }
		   return result;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

145.二叉树的后序遍历（迭代）

  /*
	        * 迭代法二叉树的后序遍历，后序遍历的顺序是左，右，中。所以按照中，右，左的顺序排列出来，最后把结果反转了就可以
	    */
	   public List<Integer> postorderTraversal(TreeNode root) {
		   List<Integer> result=new ArrayList<Integer>();
		   Stack<TreeNode> stack=new Stack<TreeNode>();
		   if(root==null) {
			   return result;
		   }
		   stack.push(root);
		   while(!stack.isEmpty()) {
			   TreeNode node=stack.pop();
			   result.add(node.val);
			   //因为现在要保证出栈顺序为中，右，左，所以先让左子树进去
			   if(node.left!=null) {
				   stack.push(node.left);
			   }
			   if(node.right!=null) {
				   stack.push(node.right);
			   }
		   }
		   
		  Collections.reverse(result);
		  return result;
		   

	    }
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

94. 二叉树的中序遍历 (迭代)

 /*
	        *  迭代中序遍历，因为顺序是左，右，中了，所以先让左节点进去。
	          先访问的节点是中间的节点，要一步步访问到最左边的节点，再开始处理节点，
	          所以需要指针的遍历来帮助访问节点，栈用来处理节点，所以要先一步步让左节点进去，然后再pop出来，然后接着处理右节点
	    */
	   public List<Integer> inorderTraversal(TreeNode root) {
		   List<Integer> result=new ArrayList<Integer>();
		   Stack<TreeNode> stack=new Stack<TreeNode>();
		   TreeNode cur=root;
		   while(cur!=null||!stack.isEmpty()) {
			   if(cur!=null) {
				   stack.push(cur);
				   cur=cur.left;
			   }else {
				   //开始处理节点了，cur指向从栈里pop出来的节点
				   cur=stack.pop();
				   result.add(cur.val);
				   cur=cur.right;
			   }
		   }
		   return result;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

102. 二叉树的层序遍历

  /*
	        * 层序遍历要借助队列来实现,先把根节点放进去，然后统计当前层数的元素个数，然后再把每个节点拿出来，操作每个节点的适合把它们对应的左右
	        * 孩子放进去
	    */
	   public List<List<Integer>> levelOrder(TreeNode root) {
		   List<List<Integer>> result=new ArrayList<List<Integer>>();
		   Deque<TreeNode> deque=new LinkedList<TreeNode> ();
		   if(root==null) {
			   return result;
		   }
		   deque.offer(root);
		   while(!deque.isEmpty()) {
			   int len=deque.size();
			   List<Integer> index=new ArrayList<Integer>();
			   while(len-->0) {
				   TreeNode node=deque.poll();
				   index.add(node.val);
				   if(node.left!=null) {
					   deque.add(node.left);
				   }
				   if(node.right!=null) {
					   deque.add(node.right);
				   }
			   }
			   result.add(index);
		   }
		   return result;
 
	    }
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

107.二叉树的层序遍历II

 /*
	         * 按照层序遍历就行，最后把层序遍历的结果反转掉即可。
	    */
	   public List<List<Integer>> levelOrderBottom(TreeNode root) {
		   List<List<Integer>> result=new ArrayList<List<Integer>>();
		   Deque<TreeNode> deque=new LinkedList<TreeNode> ();
		   if(root==null) {
			   return result;
		   }
		   deque.offer(root);
		   while(!deque.isEmpty()) {
			   int len=deque.size();
			   List<Integer> index=new ArrayList<Integer>();
			   while(len-->0) {
				   TreeNode node=deque.poll();
				   index.add(node.val);
				   if(node.left!=null) {
					   deque.add(node.left);
				   }
				   if(node.right!=null) {
					   deque.add(node.right);
				   }
			   }
			   result.add(index);
		   }
		   Collections.reverse(result);
		   return result;

	    }
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

199.二叉树的右视图

/*
		 * 在层序遍历的过程中，直接加入最右侧的节点就可以了,当
		 */
		public List<Integer> rightSideView(TreeNode root) {
			Deque<TreeNode> deque=new LinkedList<TreeNode>();
			List<Integer> result=new ArrayList<Integer>();
			if(root==null) {
				return result;
			}
			deque.offer(root);
			while(!deque.isEmpty()) {
				int len=deque.size();
				while(len-->0) {
					TreeNode node=deque.pop();
					if(len==0) {//当长度为0时再加入数值，因为最后一个节点的时候，走到这长度肯定为0了
						result.add(node.val);
					}
					if(node.left!=null) {
						deque.add(node.left);
					}
					if(node.right!=null) {
						deque.add(node.right);
					}
				}
	    }
			return result;
	}
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

637. 二叉树的层平均值

	/*
		 * 把每层的个数记录下来，然后用sum/个数即可
		 */
		 public List<Double> averageOfLevels(TreeNode root) {
			 List<Double> result=new ArrayList<Double>();
			 Deque<TreeNode> deque=new LinkedList<TreeNode> ();
			 if(root==null) {
				 return result;
			 }
			 deque.offer(root);
			 while(!deque.isEmpty()) {
				 int len=deque.size();
				 double geshu=deque.size();
				double sum=0;
				while(len-->0) {
					TreeNode node=deque.pop();
					sum+=node.val;
					if(node.left!=null) {
						deque.add(node.left);
					}
					if(node.right!=null) {
						deque.add(node.right);
					}
				}
				result.add(sum/geshu);
			 }
			 
			 
			 return result;

		 }
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

429. N 叉树的层序遍历

 public List<List<Integer>> levelOrder(Node root) {
		    List<List<Integer>> result=new ArrayList<List<Integer>>();
		    Deque<Node> deque=new LinkedList<Node>();
		    if(root==null) {
		    	return result;
		    }
		    deque.offer(root);
		    while(!deque.isEmpty()) {
		    	int len=deque.size();
		    	List<Integer> index=new ArrayList<Integer>();
		    	while(len-->0) {
		    		Node node=deque.poll();
		    		//当前出来的节点才是本层的节点，然后下面的节点再添加进去就属于孩子节点了。
		    		index.add(node.val);
		    		List<Node> children=node.children;
		    		for(Node de:children) {
		    			if(de!=null) {
		    				deque.add(de);
		    			}
		    		}
		    		
		    	}
		    	result.add(new ArrayList<>(index));
		    }
		    
		    return result;
		
			        
	 }
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

515. 在每个树行中找最大值

public List<Integer> largestValues(TreeNode root) {
             List<Integer> result=new ArrayList<Integer>();
             Deque<TreeNode> deque=new LinkedList<TreeNode>();
             if(root==null) {
            	 return result;
             }
             deque.offer(root);
             while(!deque.isEmpty()) {
            	 int len=deque.size();
            	 int index=Integer.MIN_VALUE;//记录每层的最大值
            	 while(len-->0) {
            		 TreeNode node=deque.pop();
            		 index=Math.max(index, node.val);
            		 if(node.left!=null) {
            			 deque.add(node.left);
            		 }
            		 if(node.right!=null) {
            			 deque.add(node.right);
            		 }
            	 }
            	 result.add(index);
             }
             return result;
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

116. 填充每个节点的下一个右侧节点指针

/*
	    * 遍历每一层的节点时，先把第一层的节点拿出来保留住，然后依次连接下边的节点即可
	    */
	   public Node connect(Node root) {
		   Deque<Node> deque=new LinkedList<Node>();
		   if(root!=null) {
			   deque.offer(root);
		   }
		   while(!deque.isEmpty()) {
			   int len=deque.size();
			   //拿出每层的第一个节点
			   Node first=deque.poll();
			   if(first.left!=null) {
				   deque.add(first.left);
				   
			   }
			   if(first.right!=null) {
				   deque.add(first.right);
			   }
			   while(len-->1) {
				   Node node=deque.poll();
				   if(node.left!=null) {
					   deque.add(node.left);
				   }
				   if(node.right!=null) {
					   deque.add(node.right);
				   }
				   first.next=node;
				   first=node;
			   }
		   }
		   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
27
28
29
30
31
32
33
34

117.填充每个节点的下一个右侧节点指针 II

  * 遍历每层的时候先把第一个节点拿出来，然后记录下来，剩下的再遍历同层的其他节点
	    */
	   public Node connect(Node root) {
		   
		   Deque<Node> deque=new LinkedList<Node>();
		   if(root==null) {
			   return root;
		   }
		   deque.offer(root);
		   while(!deque.isEmpty()) {
			   int len=deque.size();
			   //拿出第一个节点
			   Node first=deque.poll();
			   if(first.left!=null) {
				   deque.add(first.left);
			   }
			   if(first.right!=null) {
				   deque.add(first.right);
			   }
			   while(len-->1) {
				   Node node=deque.poll();
				   if(node.left!=null) {
					   deque.add(node.left);
				   }
				   if(node.right!=null) {
					   deque.add(node.right);
				   }
				   first.next=node;
				   first=node;
			   }
		   }
		  
		   
		   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
27
28
29
30
31
32
33
34
35
36

104.二叉树的最大深度

 /*
	    * 最大深度，当层序遍历的时候，遍历了几层，这个二叉树的最大深度就是几
	    */
	    public int maxDepth(TreeNode root) {
	    	Deque<TreeNode> deque=new LinkedList<TreeNode> ();
	    	if(root==null) {
	    		return 0;
	    	}
	    	deque.offer(root);
	    	int dept=0;
	    	while(!deque.isEmpty()) {
	    		int len=deque.size();//求每层的节点有多少个
	    		dept++;
	    		while(len-->0) {
	    			TreeNode  node=deque.poll();
	    			if(node.left!=null) {
	    				deque.add(node.left);
	    			}
	    			if(node.right!=null) {
	    				deque.add(node.right);
	    			}
	    		}
	    		
	    	}
	    	return dept;

	    }
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

111. 二叉树的最小深度

public int minDepth(TreeNode root) {
	    	Deque<TreeNode> deque=new LinkedList<TreeNode>();
	    	if(root==null) {
	    		return 0;
	    	}
	    	deque.offer(root);
	    	int minDepth=0;
	    	while(!deque.isEmpty()) {
	    		minDepth++;
	    		int len=deque.size();
	    		while(len-->0) {
	    			TreeNode node=deque.poll();
	    			if(node.left!=null) {
	    				deque.add(node.left);
	    			}
	    			if(node.right!=null) {
	    				deque.add(node.right);
	    			}
	    			if(node.left==null&&node.right==null) {
	    				return minDepth;
	    			}
	    		}
	    	}
	    	return minDepth;

	    }
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

226. 翻转二叉树

 public TreeNode invertTree(TreeNode root) {
	    	   if(root==null) {
	    		   return null;
	    	   }
	    	   reverse(root);
	    	   invertTree(root.left);
	    	   invertTree(root.right);
	    	   return root;

	    
	    }
	    
	    public void reverse(TreeNode node) {
	    	TreeNode temp=node.left;
	    	node.left=node.right;
	    	node.right=temp;
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

101. 对称二叉树

 /*
	     * 判断是不是对称二叉树，要判断它的左右子树想不想等，递归的去判断，先序遍历即可。
	     */
	    public boolean isSymmetric(TreeNode root) {
	    	return compare(root.left,root.right);

	    }
	    public boolean compare(TreeNode left,TreeNode right) {
	    	if(left!=null&&right==null) {
	    		return false;
	    	}else if(left==null&&right!=null) {
	    		return false;
	    	}else if(left==null&&right==null) {
	    		return true;
	    	}else if(left.val!=right.val) {
	    		return false;
	    	}
	    	//让内测的节点去比较
	    	boolean inside=compare(left.right,right.left);
	    	boolean outside=compare(left.left,right.right);
	    	return inside&&outside;
	    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

572. 另一棵树的子树

 /*
	     * 判断者两棵树是不是相等的
	     */
	    public boolean compare1(TreeNode left,TreeNode right) {
	    	if(left!=null&&right==null) {
	    		return false;
	    	}else if(left==null&&right!=null) {
	    		return false;
	    	}else if(left==null&&right==null){
	    		return true;
	    	}else if(left.val!=right.val) {
	    		return false;
	    	}
	    	boolean leftResult=compare1(left.left,right.left);
	    	boolean rightResult=compare1(left.right,right.right);
	    	return leftResult&&rightResult;
	    	
	    }

	    /*
	     * 判断一棵树是不是另一棵的子树
	     */
	    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
	    	//如果右边的子树等于null了，那么肯定是true
	    	if(subRoot==null) {
	    		return true;
	    	}
	    	if(root==null) {
	    		return false;
	    	}
	    	return isSubtree(root.left,subRoot)||isSubtree(root.right,subRoot)||compare1(root,subRoot);

	    }
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

104.二叉树的最大深度（递归）

 /*
	     * 二叉树最大深度，用递归来求，写上终止条件，然后每遍历一层的时候就+1即可
	     */
	    public int maxDepth(TreeNode root) {
	    	if(root==null) {
	    		return 0;
	    	}
	    	return 1+Math.max(maxDepth(root.left), maxDepth(root.right));

	    }
1
2
3
4
5
6
7
8
9
10

559. N 叉树的最大深度(递归)

 /*
	     * 用递归来求，写上终止条件，然后用max记录最大孩子的深度，最后return 1+这个深度即可
	     */
	    public int maxDepth(Node root) {
	    	if(root==null) {
	    		return 0;
	    	}
	    	List<Node> children=root.children;
	    	int max=0;
	    	for(Node node:children) {
	    		max=Math.max(max,maxDepth(node) );
	    	}
	    	return 1+max;
	        
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

111. 二叉树的最小深度(递归)

    public int minDepth(TreeNode root) {
	    	if(root==null) {
	    		return 0;
	    	}
	    	int leftDepth=minDepth(root.left);
	    	int rightDepth=minDepth(root.right);
	    	//中序遍历
	    	if(root.left==null&&root.right!=null) {
	    		return 1+rightDepth;
	    	}
	    	if(root.left!=null&&root.right==null) {
	    		return 1+leftDepth;
	    	}else {
	    		return 1+Math.min(leftDepth, rightDepth);
	    	}

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

222. 完全二叉树的节点个数

 /*
	          * 求二叉树节点的个数，运用递归求解,左边节点的数量加上右边节点的数量
	     */
	    public int countNodes(TreeNode root) {
	    	if(root==null) {
	    		return 0;
	    	}
	    	return 1+countNodes(root.left)+countNodes(root.right);

	    }
1
2
3
4
5
6
7
8
9
10

110. 平衡二叉树

   /*
	           * 求出左右子树的深度，如果不是平衡二叉树就返回-1，如果是，就返回两个子树最深的深度,
	             要用后序遍历
	     */
	    public boolean isBalanced(TreeNode root) {
	    	if(isbalance(root)==-1) {
	    		return false;
	    	}
	    	return true;

	    }
	    public int isbalance(TreeNode root) {
	    	if(root==null) {
	    		return 0;
	    	}
	    	int leftdepth=isbalance(root.left);
	    	if(leftdepth==-1) {
	    		return -1;
	    	}
	    	int rightdepth=isbalance(root.right);
	    	if(rightdepth==-1) {
	    		return -1;
	    	}
	    	
	    	if(Math.abs(leftdepth-rightdepth)>1) {//如果当前层不是平衡二叉树了，就返回-1
	    		return -1;
	    	}else {
	    		return 1+Math.max(leftdepth, rightdepth);
	    	}
	    }
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

257. 二叉树的所有路径

 /*
	          * 用回溯法去找，因为路径是从根节点开始的，所以采用先序遍历的方式
	     */
	    public List<String> binaryTreePaths(TreeNode root) {
	    	List<String> result=new ArrayList<String>();
	    	List<Integer> path=new ArrayList<Integer>();
	    	if(root==null) {
	    		return result;
	    	}
	    	traval(root,path,result);
	    	return result;

	    }
	    public void traval(TreeNode root,List<Integer> path,List<String> result) {
	    	path.add(root.val);
	    	//先序遍历，先遍历到中间的节点
	    	if(root.left==null&&root.right==null) {
	    		StringBuffer str=new StringBuffer();
	    		for(int i=0;i<path.size()-1;i++) {
	    			str.append(path.get(i)).append("->");
	    		}
	    		//加上最后一个节点
	    		str.append(path.get(path.size()-1));
	    		result.add(str.toString());
	    	}
	    	//如果左子树不为空，去遍历左子树
	    	if(root.left!=null) {
	    		traval(root.left,path,result);
	    		//进行回溯操作
	    		path.remove(path.size()-1);
	    	}
	    	//如果右子树不为空，去遍历右子树
	    	if(root.right!=null) {
	    		traval(root.right,path,result);
	    		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
28
29
30
31
32
33
34
35
36
37
38

404. 左叶子之和

 /*
	           * 因为是找左叶子之和，所以采用后序遍历，左右中的方式
	     */
	    public int sumOfLeftLeaves(TreeNode root) {
	    	if(root==null) {
	    		return 0;
	    	}
	    	int left=sumOfLeftLeaves(root.left);
	    	int right=sumOfLeftLeaves(root.right);
	    	int middle=0;
	    	//判断这个节点是不是左叶子，要从它的父级节点开始判断，如果不是的话就没法判断它是左叶子
	    	if(root.left!=null&&root.left.left==null&&root.left.right==null) {
	    		middle+=root.left.val;
	    	}
	    	return middle+left+right;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

513. 找树左下角的值

/*
	          * 用层序遍历去找树结构最左侧的值
	     */
	    public int findBottomLeftValue(TreeNode root) {
	    	Deque<TreeNode> deque=new LinkedList<TreeNode>();
	    	int result=0;
	    	if(root==null) {
	    		return 0;
	    	}
	    	deque.offer(root);
	    	while(!deque.isEmpty()) {
	    		int len=deque.size();
	    		for(int i=0;i<len;i++) {
	    			TreeNode node=deque.poll();
	    			if(i==0) {//要保存第一个节点的结果
	    				result=node.val;
	    			}
	    			if(node.left!=null) {
	    				deque.add(node.left);
	    			}
	    			if(node.right!=null) {
	    				deque.add(node.right);
	    			}
	    		}
	    	}
	    	return result;

	    }
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

112.路径总和

  /*
	          * 判断路径总和有没有目标值，要达到的话，就返回true,如果没有目标值，则返回false。
	          采用先序遍历的方式，先遍历根节点，再遍历左右叶子
	      
	     */
	    public boolean hasPathSum(TreeNode root, int targetSum) {
	    	if(root==null) {
	    		return false;
	    	}
	    	targetSum-=root.val;
	    	//当碰到叶子节点的时候，判断此时target是不是0即可
	    	if(root.left==null&&root.right==null) {
	    		return targetSum==0;
	    	}
	    	//如果左子树不是目标树的话，是不需要返回值的，而是让它继续递归，而如果是true的话，那么就需要立马返回了
	    	if(root.left!=null) {
	    		boolean left=hasPathSum(root.left,targetSum);
	    		if(left) {
	    			return true;
	    		}
	    	}
	    	if(root.right!=null) {
	    		boolean right=hasPathSum(root.right,targetSum);
	    		if(right) {
	    			return true;
	    		}
	    	}
	    	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

113.路径总和II

/*
	          * 用回溯来求，如果满足了目标路径的值，并且到了叶子节点，就把它放入结果集中
	     */
	    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
	    	List<List<Integer>> result=new ArrayList<List<Integer>>();
	    	if(root==null) {
	    		return result;
	    	}
	    	List<Integer>path=new ArrayList<Integer>();
	    	travel(root,targetSum,path,result);
	    	return result;

	    }
	    public void travel(TreeNode root,int targetSum,List<Integer>path,List<List<Integer>> result) {
	    	targetSum-=root.val;
	    	path.add(root.val);
	    	//当遇到了叶子节点
	    	if(root.left==null&&root.right==null) {
	    		if(targetSum==0) {
	    			result.add(new ArrayList<>(path));
	    		}
	    	}
	    	//然后去找左边的子树
	    	if(root.left!=null) {
	    		travel(root.left,targetSum,path,result);
	    		//进行回溯
	    		path.remove(path.size()-1);
	    	}
	    	//去找右边的子树
	    	if(root.right!=null) {
	    		travel(root.right,targetSum,path,result);
	    		//进行回溯
	    		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
28
29
30
31
32
33
34
35
36

106. 从中序与后序遍历序列构造二叉树

/*
	          * 从后序遍历与中序遍历构造二叉树，
	            首先找到后序遍历的最后一个节点，这个节点就是根节点，然后去切割中序遍历的左右子树，这样的递归去求，每层都返回当前层的节点,
	            采用左闭右开区间，左闭右闭掌握不了
	     */
	    public Map<Integer,Integer>  hashmap;
	    public TreeNode buildTree(int[] inorder, int[] postorder) {
	    	//用map来存每个数字的下标
	    	hashmap=new HashMap<Integer,Integer>();
	    	for(int i=0;i<inorder.length;i++) {
	    		hashmap.put(inorder[i],i);
	    	}
	    	return buildTreehelp(inorder,0,inorder.length,postorder,0,postorder.length);
	    	

	    }
	    public TreeNode buildTreehelp(int []inorder,int instart,int inend,int []postorder,int poststart,int postend) {
	    	//确定终止条件
	    	if(instart>=inend||poststart>=postend) {
	    		return null;
	    	}
	    	//找到中序遍历中的下标
	    	int rootIndex=hashmap.get(postorder[postend-1]);
	    	TreeNode root=new TreeNode(inorder[rootIndex]);
	    	//左子树的长度
	    	int lengthOfLeft=rootIndex-instart;
	    	root.left=buildTreehelp(inorder,instart,rootIndex,postorder,poststart,poststart+lengthOfLeft);
	    	root.right=buildTreehelp(inorder,rootIndex+1,inend,postorder,poststart+lengthOfLeft,postend-1);
	    	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
27
28
29
30

105. 从前序与中序遍历序列构造二叉树

 /*
	          * 先序和中序遍历构造二叉树，同样先找到先序遍历的第一个节点，就是中序遍历的节点，然后再根据中序分割的左右子树去分割
	     */
	    Map<Integer,Integer> map; 
	    public TreeNode buildTree(int[] preorder, int[] inorder) {
	    	map=new HashMap<Integer,Integer>();
           for(int i=0;i<inorder.length;i++) {
        	   map.put(inorder[i],i);
           }
           return buildTreeHelp(preorder,0,preorder.length,inorder,0,inorder.length);
	    }
	    public TreeNode buildTreeHelp(int []preorder,int prebegin,int preend,int []inorder,int inbegin,int inend) {
	    	if(prebegin>=preend||inbegin>=inend) {
	    		return null;
	    	}
	    	int rootIndex=map.get(preorder[prebegin]);//找到中序遍历的下标
	    	TreeNode root=new TreeNode(inorder[rootIndex]);
	    	int leftofLength=rootIndex-inbegin;//左子树的长度
	    	root.left=buildTreeHelp(preorder,prebegin+1,prebegin+leftofLength+1,inorder,inbegin,inbegin+leftofLength);
	    	root.right=buildTreeHelp(preorder,prebegin+leftofLength+1,preend,inorder,rootIndex+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

654.最大二叉树

  /*
	          * 根据题意去模拟即可，找到区间里的最大值和最大值的下标，然后根据这个下标去构建根节点，递归的去构造即可。
	            采用的是左闭右开区间
	     */
	    public TreeNode constructMaximumBinaryTree(int[] nums) {
	    	return constructMaximumBinaryTreehelp(nums,0,nums.length);

	    }
	    public TreeNode constructMaximumBinaryTreehelp(int []nums,int left,int right) {
	    	if(left>=right) {
	    		return null;
	    	}
	    	//如果区间里边只剩一个元素，那么直接返回这个元素即可
	    	if((right-left)==1) {
	    		return new TreeNode(nums[left]);
	    	}
	    	int maxValue=nums[left];
	    	int maxIndex=left;
	    	for(int i=maxIndex+1;i<right;i++) {
	    		if(nums[i]>maxValue) {
	    			maxValue=nums[i];
	    			maxIndex=i;
	    		}
	    	}
	    	TreeNode root=new TreeNode(maxValue);
	    	root.left=constructMaximumBinaryTreehelp(nums,left,maxIndex);
	    	root.right=constructMaximumBinaryTreehelp(nums,maxIndex+1,right);
	    	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
27
28
29

617.合并二叉树

/*
	          * 递归，采用先序遍历
	     */
	    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
             //确定终止条件
	    	if(root1==null) {
	    		return root2;
	    	}
	    	if(root2==null) {
	    		return root1;
	    	}
	    	root1.val=root1.val+root2.val;
	    	root1.left=mergeTrees(root1.left,root2.left);
	    	root1.right=mergeTrees(root1.right,root2.right);
	    	return root1;
	    			
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

700.二叉搜索树中的搜索

 /*
	     * 二叉搜索树，如果节点比目标值小，从右边搜索，如果节点比目标值大，往左边搜索
	     */
	    public TreeNode searchBST(TreeNode root, int val) {
	    	if(root==null||root.val==val) {
	    		return root;
	    	}
	    	if(root.val>val) {
	    		return searchBST(root.left,val);
	    	}
	    	if(root.val<val) {
	    		return searchBST(root.right,val);
	    	}
            return null;
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

98. 验证二叉搜索树

  /*
	     * 用单独一个指针记录之前的指针
	     */
	    TreeNode pre;
	    public boolean isValidBST(TreeNode root) {
	    	if(root==null) {//当指针节点为空时，return true；
	    		return true;
	    	}
	    	//判断左边是不是二叉搜索树
	    	boolean left=isValidBST(root.left);
	    	if(!left) {
	    		return false;
	    	}
	    	//中间的逻辑
	    	if(pre!=null&&pre.val>=root.val) {
	    		return false;
	    	}
	    	pre=root;
	    	boolean right=isValidBST(root.right);
	    	if(!right) {
	    		return false;
	    	}
	    	return left&&right;

	    }
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

530. 二叉搜索树的最小绝对差

 TreeNode pre1;
	    int result1=Integer.MAX_VALUE;
	    /*
	     * 因为是二叉搜索树，所以两个节点之间差的数值最小
	     */
	    public int getMinimumDifference(TreeNode root) {
	    	
           if(root==null) {
        	   return 0;
           }
           getmin(root);
           return result1;
	    }
	    /*
	     * 采用中序遍历的方式
	     */
	    public void getmin(TreeNode root) {
	    	if(root==null) {
	    		return ;
	    	}
	    	getmin(root.left);
	       if(pre1!=null) {
	    	   result1=(root.val-pre1.val)<result1?root.val-pre1.val:result1;
	       }
	       pre1=root;
	       getmin(root.right);
	    	
	    }
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

501.二叉搜索树中的众数

/*
	          * 二叉搜索树中的众数,因为是二叉搜索树，所以肯定两个节点之间是差值最小的，所以按次遍历即可。
	     */
	    TreeNode pre3=null;
	    int count=0;
	    int maxCount=0;//记录当前出现最大数字的次数
	    List<Integer> result=new ArrayList<Integer>();
	    public int[] findMode(TreeNode root) {
	    	if(root==null) {
	    		return result.stream().mapToInt(x->x).toArray();
	    	}
	    	//采用中序遍历的方式
	    	findMode(root.left);
	    	if(pre3!=null&&pre3.val!=root.val) {
	    		count=1;
	    	}else {
	    		count++;
	    	}
	    	//如果当前数字的计数大于最大值的时候
	    	if(count>maxCount) {
	    		result.clear();
	    		result.add(root.val);
	    		maxCount=count;
	    	}else if(count==maxCount) {
	    		result.add(root.val);
	    	}
	    	pre3=root;
	    	findMode(root.right);
	    	return result.stream().mapToInt(x->x).toArray();

	    }

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

236. 二叉树的最近公共祖先

 /*
	         * 终止条件,采用后序遍历的方式
	     */
	    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	    	//终止条件
	    	if(root==null||root==p||root==q) {
	    		return root;
	    	}
	    	TreeNode left=lowestCommonAncestor(root.left,p,q);
	    	TreeNode right=lowestCommonAncestor(root.right,p,q);
	    	if(left!=null&&right==null) {
	    		return left;
	    	}else if(left==null&&right!=null) {
	    		return right;
	    	}else if(left==null&&right==null) {
	        	return null;
	        }else {
	        	return root;
	        }
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

235. 二叉搜索树的最近公共祖先

 /*
	           * 二叉搜索树的最近公共祖先，因为有顺序了，所以只需要按顺序去搜即可
	     */
	    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
	    	if(root==null||root==p||root==q) {
	    		return root;
	    	}
	    	if(root.val<p.val&&root.val<q.val) {
	    		TreeNode right=lowestCommonAncestor(root.right,p,q);
	    		if(right!=null) {
	    			return right;
	    		}
	    	}
	    	if(root.val>p.val&&root.val>q.val) {
	    		TreeNode left=lowestCommonAncestor(root.left,p,q);
	    		if(left!=null) {
	    			return left;
	    		}
	    	}
	    	return root;
	        
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

701. 二叉搜索树中的插入操作

   /*
	     * 二叉搜索树的插入，当遇到空节点时，直接生成节点然后返回这个节点即可。
	     * 如果数字的节点小于当前的节点数，就去左子树插，反之，则去右子树插
	     */
	    public TreeNode insertIntoBST(TreeNode root, int val) {
	    	if(root==null) {
	    		TreeNode node=new TreeNode(val);
	    		return node;
	    	}
	    	if(root.val<val) {
	    		root.right=insertIntoBST(root.right,val);
	    	}
	    	if(root.val>val) {
	    		root.left=insertIntoBST(root.left,val);
	    	}
	    	return root;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

450. 删除二叉搜索树中的节点

  /*
	          * 采用先序遍历的方式
	      分为5种情况
	      1.没有找到该节点
	      2.找到该节点，并且节点是叶子节点
	      3.找到该节点，该节点有左子树
	      4.找到该节点，该节点有右子树
	      5.找到该节点，该节点左右子树都有
	     */
	    public TreeNode deleteNode(TreeNode root, int key) {
             if(root==null) {
            	 return null;
             }
             if(root.val==key) {
            	 if(root.left==null&&root.right==null) {
            		 return null;
            	 }else if(root.left!=null&&root.right==null) {
            		 return root.left;
            	 }else if(root.left==null&&root.right!=null) {
            		 return root.right;
            	 }else if(root.left!=null&&root.right!=null) {
            		 TreeNode cur=root.right;
            		 while(cur.left!=null) {
            			 cur=cur.left;
            		 }
            		 cur.left=root.left;
            		 return root.right;
            	 }
             }
             
             root.left=deleteNode(root.left,key);
             root.right=deleteNode(root.right,key);
             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
27
28
29
30
31
32
33
34

669.修剪二叉树

/*
	          * 修剪二叉搜索树，因为是二叉搜索树，所以是有顺序的，
	     */
	    public TreeNode trimBST(TreeNode root, int low, int high) {
	    	//终止条件
	    	if(root==null) {
	    		return null;
	    	}
	    	
	    	//如果当前节点的值小于最小边界，返回修剪后的右子树，因为这个节点的左子树肯定是不满足条件的
	    	if(root.val<low) {
	    		return trimBST(root.right,low,high);
	    	}
	    	
	    	//如果当前节点的值大于最大边界，返回修剪后的左子树，因为这个节点的右子树肯定是不满足条件的
	    	if(root.val>high) {
	    		return trimBST(root.left,low,high);
	    	}
	    	
	    	//如果节点的值在区间之中，那么就分别修剪左右子树
	    	root.left=trimBST(root.left,low,high);
	    	root.right=trimBST(root.right,low,high);
	    	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

108.将有序数组转换为二叉搜索树

  /*
	     * 因为是有序数组，所以找到中间的节点就可以作为根节点了
	     */
	    public TreeNode sortedArrayToBST(int[] nums) {
	    	if(nums.length==0) {
	    		return null;
	    	}
	    	return sort(nums,0,nums.length-1);
	    	

	    }
	    public TreeNode sort(int []nums,int left,int right) {//采用左闭右闭区间
	    	//判断终止条件
	    	if(left>right) {
	    		return null;
	    	}
	    	int mid=(left+right)/2;
	    	TreeNode root=new TreeNode(nums[mid]);
	    	root.left=sort(nums,left,mid-1);
	    	root.right=sort(nums,mid+1,right);
	    	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

538. 把二叉搜索树转换为累加树

  /*
	          * 采用 右，中，左的遍历方式，然后每个节点的值累加上即可
	     */
	    int pre4=0;
	    public TreeNode convertBST(TreeNode root) {
	    	if(root==null) {
	    		return null;
	    	}
	    	convertBST(root.right);
	    	root.val+=pre4;
	    	pre4=root.val;
	    	convertBST(root.left);
	    	return root;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

回溯

77. 组合

/*
	 * 递归中有一个startindex，来标识走到哪了，然后再从后边的挑选一个，注意回溯
	 */
	List<List<Integer>> result=new ArrayList<List<Integer>>();
	List<Integer>path=new ArrayList<Integer>();
	   public List<List<Integer>> combine(int n, int k) {
		   combinehelper(n,k,1);
		   return result;

	    }
	   public void combinehelper(int n,int k,int start) {
		   if(path.size()==k) {
			   result.add(new ArrayList<>(path));
			   return ;
		   }
		   for(int i=start;i<=n;i++) {
			   path.add(i);
			   combinehelper(n,k,i+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
21
22
23
24
25

216. 组合总和 III

List<List<Integer>> result=new ArrayList<List<Integer>>();
		List<Integer>path=new ArrayList<Integer>();
	   /*
	    * 组合总和3，找到目标值相加等于n的数,还要求是k个数
	    */
	   public List<List<Integer>> combinationSum3(int k, int n) {
		   combinationSum3help(k,n,1);
		   return result;

	    }
	   public void combinationSum3help(int k,int n,int start) {
		   if(path.size()==k) {
			   if(n==0) {
				   result.add(new ArrayList<>(path));
			   }
		   }
		for(int i=start;i<=9;i++) {
			path.add(i);
			combinationSum3help(k,n-i,i+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
21
22
23

17. 电话号码的字母组合

 /*
	        * 这道题是不同数字里的集合，然后每次只选取一个
	    */
	   String []number= {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	   List<String> result=new ArrayList<String>();
	   public List<String> letterCombinations(String digits) {
		   if(digits==null||digits.length()==0) {
			   return result;
		   }
		   letterCombinationshelp(digits,0);
		   return result;

	    }
	   /*
	    * index代表遍历到第几个字母了
	    */
	   StringBuffer path=new StringBuffer();
	   public void letterCombinationshelp(String digits,int index) {
		   if(path.length()==digits.length()) {//目标达到可以收集结果了
			   result.add(path.toString());
			   return ;
			   
		   }
		   //找到每个下标对应的字母
		   String str=number[digits.charAt(index)-'0'];
		   for(int i=0;i<str.length();i++) {
			   path.append(str.charAt(i));
			   letterCombinationshelp(digits,index+1);
			   path.deleteCharAt(path.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
27
28
29
30
31
32

39. 组合总和

  /*
	        * 这道题的区别就是数字可以重复使用
	    */
	   List<Integer> path=new ArrayList<Integer>();
	   List<List<Integer>> result=new ArrayList<List<Integer>>();
	   public List<List<Integer>> combinationSum(int[] candidates, int target) {
		   
             combinationSum(candidates,target,0);
             return result;
	    }
	   
	   public void combinationSum(int[] candidates, int target,int start) {
		   if(target==0) {//收集结果
			   result.add(new ArrayList<>(path));
			   return ;
		   }
		   for(int i=start;i<candidates.length;i++) {
			   if(target<0) {//进行剪枝操作
				   return ;
			   }
			   path.add(candidates[i]);
			   combinationSum(candidates,target-candidates[i],i);//要从i开始，如果从0开始就是排列了
			   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

40. 组合总和 II

  
	   /*
	        * 这里需要去重，要求是不同的组合，比如目标和为3的话，1，1，2，这个数组，只能找出1，2这一个组合，而不能有两个组合
	    */
	   List<Integer>path=new ArrayList<Integer>();
	   List<List<Integer>> result=new ArrayList<List<Integer>>();
	   boolean []used;
	   public List<List<Integer>> combinationSum2(int[] candidates, int target) {
             used=new boolean[candidates.length];//标识这个数组有没有被用过
             Arrays.sort(candidates);
             combinationSum2(candidates,target,0,used);
             return result;
	    }
	   public void combinationSum2(int []candidates,int target, int start,boolean []used) {
		   if(target==0) {//收集结果了
			   result.add(new ArrayList<>(path));
			   return ;
		   }
		   for(int i=start;i<candidates.length;i++) {
			   
			   if(target<0) {
				   return ;
			   }
			   //去重逻辑
			   if(i>0&&candidates[i]==candidates[i-1]&&!used[i-1]) {//去重的逻辑，表示这个数字已经在数层上了,used[i-1]表示前一个没有用过的时候，因为已经
				   //回溯到树枝上了，没用过也就是用过的情况。
				   continue;
				   
			   }
			   path.add(candidates[i]);
			   used[i]=true;
			   combinationSum2(candidates,target-candidates[i],i+1,used);
			   //回溯
			   used[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
28
29
30
31
32
33
34
35
36
37
38

131. 分割回文串

 List<String> path=new ArrayList<String>();
	   List<List<String>> result=new ArrayList<List<String>>();
	   /*
	        * 从起始位置到i判断是不是回文串，如果是的话，就把它加入到path中
	    */
	   public List<List<String>> partition(String s) {
		   partition(s,0);
		   return result;
		   

	    }
	   
	   public void partition(String s,int start) {
		   //判断终止条件
		   if(start>=s.length()) {//收集结果
			   result.add(new ArrayList<>(path));
			   return ;
			   
		   }
		   for(int i=start;i<s.length();i++) {
			   if(isPalindrome(s,start,i)) {
				   path.add(s.substring(start,i+1));
			   }else {//如果不是，进入下一层循环
				   continue;
			   }
			   partition(s,i+1);
			   path.remove(path.size()-1);
			   
		   }
	   }
	   
	 //判断是否是回文串
	    private boolean isPalindrome(String s, int startIndex, int end) {
	        for (int i = startIndex, j = end; 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
35
36
37
38
39
40
41

78.子集

  /*
	          * 找到所有的子集，区别就是不一定要达到条件才收集结果，而是每次都得收集
	     */
	   List<Integer> path=new ArrayList<Integer>();
	   List<List<Integer>>result=new ArrayList<List<Integer>>();
	    public List<List<Integer>> subsets(int[] nums) {
                subsets(nums,0);
                return result;
	    }
	    public void subsets(int []nums,int start) {
	    	result.add(new ArrayList<>(path));
	    	if(start>=nums.length) {
	    		return ;
	    	}
	    	for(int i=start;i<nums.length;i++) {
	    		path.add(nums[i]);
	    		subsets(nums,i+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
21
22

90.子集II

 /*
	        * 这里要进行组合去重了，所以需要used数组来判断数组有没有被用过
	      
	    */
	   List<Integer> path=new ArrayList<Integer>();
	   List<List<Integer>> result=new ArrayList<List<Integer>>();
	   boolean used[];
	    public List<List<Integer>> subsetsWithDup(int[] nums) {
	    	used=new boolean[nums.length];
	    	Arrays.sort(nums);
	    	subsetsWithDup(nums,used,0);
	    	return result;

	    }
	    public void subsetsWithDup(int []nums,boolean []used,int start) {
	    	result.add(new ArrayList<>(path));
	    	//终止条件
	    	if(start>=nums.length) {
	    		return ;
	    	}
	    	for(int i=start;i<nums.length;i++) {
	    		if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) {
	    			continue;
	    		}
	    		path.add(nums[i]);
	    		used[i]=true;
	    		subsetsWithDup(nums,used,i+1);
	    		used[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
28
29
30
31
32

491. 递增子序列

  /*
                * 去重逻辑，是前边只要用过了这个数，就把这里砍掉。加入节点的时候，加入的节点要比path的最后一个元素大才加入
	    */
	   List<Integer> path=new ArrayList<Integer>();
	   List<List<Integer>> result=new ArrayList<List<Integer>>();
	   boolean used[];
	   public List<List<Integer>> findSubsequences(int[] nums) {
		   
		   findSubsequences(nums,used,0);
		   return result;

	    }
	   public void findSubsequences(int []nums,boolean []used,int start) {
		   if(path.size()>=2) {
			   result.add(new ArrayList<>(path));
			 
		   }
		   used=new boolean[201];
		   for(int i=start;i<nums.length;i++) {
			   if(!path.isEmpty()&&nums[i]<path.get(path.size()-1)||used[nums[i]+100]==true) {
				   continue;
			   }
			
			   used[nums[i]+100]=true;
			   path.add(nums[i]);
			   findSubsequences(nums,used,i+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
21
22
23
24
25
26
27
28
29
30
31

46. 全排列

 /*
	        * 这次是排列了，所以不需要从start之后开始了，而是每次都从0开始，但是还需要一个used数组，当再次遍历到自己的时候直接跳过就行
	    * 
	    */
	   List<Integer> path=new ArrayList<Integer>();
	   List<List<Integer>> result=new ArrayList<List<Integer>>();
	   boolean used[];
	   public List<List<Integer>> permute(int[] nums) {
		   used=new boolean [nums.length];
		   permute(nums,used);
		   return result;

	    }
	   public void permute(int []nums,boolean used[]) {
		   if(path.size()==nums.length) {
			   //收集结果
			   result.add(new ArrayList<>(path));
			   return ;
		   }
		   for(int i=0;i<nums.length;i++) {
			   if(used[i]==true) {
				   continue;
			   }
			   path.add(nums[i]);
			   used[i]=true;
			   permute(nums,used);
			   used[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
28
29
30
31
32

47.全排列II

 /*
	        * 这道题的的数字有重复数字了，所以在循环里还要进行一个去重操作
	    */
	   List<Integer> path=new ArrayList<Integer>();
	   List<List<Integer>> result=new ArrayList<List<Integer>>();
	   boolean []used;
	   public List<List<Integer>> permuteUnique(int[] nums) {
		   Arrays.sort(nums);
		   used=new boolean [nums.length];
		   permuteUnique(nums,used);
		   return result;

	    }
	   public void permuteUnique(int []nums,boolean []used) {
		   if(path.size()==nums.length) {
			   result.add(new ArrayList<>(path));
			   return ;
		   }
		   for(int i=0;i<nums.length;i++) {
			   if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) {//去重的逻辑
				   continue;
				   
			   }
			   if(used[i]==true) {
				   continue;
			   }
			   used[i]=true;
			   path.add(nums[i]);
			   permuteUnique(nums,used);
			   used[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
28
29
30
31
32
33
34
35

动态规划

509. 斐波那契数

  public int fib(int n) {
		  //dp[i]表示第i个斐波那契数列的树枝
		  if(n==0) {
			  return 0;
		  }
		  if(n==1) {
			  return 1;
		  }
		  int dp[]=new int[n+1];
		  //初始化
		  dp[0]=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
11
12
13
14
15
16
17
18
19

70. 爬楼梯

 public int climbStairs(int n) {
		  if(n==1) {
			  return 1;
		  }
		  if(n==2) {
			  return 2;
		  }
		  int []dp=new int[n+1];
		  //初始化
		  dp[1]=1;
		  dp[2]=2;
		  for(int i=3;i<=n;i++) {
			  dp[i]=dp[i-1]+dp[i-2];
		  }
		  return dp[n];

	    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

746. 使用最小花费爬楼梯

 public int minCostClimbingStairs(int[] cost) {
		  int []dp=new int[cost.length+1];//定义dp数组，dp[i]表示到达第i阶台阶耗费的最小经历
		  //初始化
		  dp[0]=0;
		  dp[1]=0;
		  for(int i=2;i<=cost.length;i++) {//这样每次递推下来，每步都是最小的花费次数
			  dp[i]=Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
		  }
		  return dp[cost.length];

	    }
1
2
3
4
5
6
7
8
9
10
11

62. 不同路径

 /*
	        * 每个的位置可以从左边走过来，也可以从上边走过来
	    */
	    public int uniquePaths(int m, int n) {
	    	int [][]dp=new int[m][n];//dp[i][j],到达i,j的路径
	    	//初始化
	    	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
16
17
18
19
20

63. 不同路径 II

 /*
	          * 如果有障碍物的话就代表此路不通了
	     */
	    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
	    	int m=obstacleGrid.length;
	    	int n=obstacleGrid[0].length;
	    	if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1) {//起始位置和终止位置有,代表此路不通了
	    		return 0;
	    		
	    	}
	    	int [][]dp=new int[m][n];
	    	for(int i=0;i<m;i++) {
	    		if(obstacleGrid[i][0]==0) {
	    			dp[i][0]=1;
	    		}else {//遇到障碍物时，直接break
	    			break;
	    		}
	    	}
	    	for(int j=0;j<n;j++) {
	    		if(obstacleGrid[0][j]==0) {
	    			dp[0][j]=1;
	    		}else {//遇到障碍物时，直接break;
	    			break;
	    		}
	    	}
	    	for(int i=1;i<m;i++) {
	    		for(int j=1;j<n;j++) {
	    			if(obstacleGrid[i][j]==0) {
	    				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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

343.整数拆分

public int integerBreak(int n) {
	    	int dp[]=new int[n+1];//dp[i]表示i能拆分数组的最大值
	    	if(n==1) {
	    		return 0;
	    	}
	    	if(n==2) {
	    		return 1;
	    	}
	    	//初始化
	    	dp[1]=1;
	    	dp[2]=1;
	    	for(int i=3;i<=n;i++) {
	    		//从这开始拆分i
	    		for(int j=1;j<i;j++) {
	    			dp[i]=Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));//(6)可以拆成1*5  还可以拆成1*dp[5]，dp[5]就包含了后边的拆分情况。
	    			
	    		}
	    	}
	    	return dp[n];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

96. 不同的二叉搜索树

 public int numTrees(int n) {
	    	int[]dp=new int[n+1];//dp[i]代表第i个节点能组成多少种二叉搜索树
	    	//初始化
	    	dp[0]=1;
	    	dp[1]=1;
	    	for(int i=2;i<=n;i++) {
	    		for(int j=1;j<=i;j++) {//让每个节点都做一次根节点，这样才有不同的种类
	    			dp[i]+=dp[j-1]*dp[i-j];//左子树有j-1个节点，右子树右i-j个节点
	    			
	    		}
	    	}
	    	return dp[n];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

背包问题：
如果是二维数组，那么先遍历背包还是先遍历物品都可以。

dp[i][j]:[0,i]的物品任意存放，容量为j的背包
放还是不放物品i
不放物品i:dp[i-1][j]
放物品i:dp[i-1][j-weight[i]]+value[i]

一维dp数组的话：
dp[j]:容量为j的背包的最大价值为dp[j]

递推公式：不放物品i dp[j-weight[i]], 放物品i,dp[j],dp[j-weight[i]]+value[i]

一维dp，要倒序，保证物品只放了一次。必须先物品，再背包，反过来却不行。

416. 分割等和子集

  /*
	     * 判断这些物品是不是正好能装满sum/2总数的背包
	     */
	    public boolean canPartition(int[] nums) {
	    	int sum=0;
	    	for(int i:nums) {
	    		sum+=i;
	    	}
	    	if(sum%2==1) {
	    		return false;
	    	}
	    	int dp[]=new int[sum/2+1];
	    	for(int i=0;i<nums.length;i++) {//先遍历物品
	    		for(int j=sum/2;j>=nums[i];j--) {//再遍历背包
	    			dp[j]=Math.max(dp[j], dp[j-nums[i]]+nums[i]);
	    		}
	    		
	    	}
	    	return dp[sum/2]==sum/2;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1049. 最后一块石头的重量 II

  /*
	     * 用一个石头重量1半的背包尽量装，装满之后再用两者相减
	     */
	    public int lastStoneWeightII(int[] stones) {
	    	int sum=0;
	    	for(int i:stones) {
	    		sum+=i;
	    	}
	    	int target=sum/2;
	    	int dp[]=new int[target+1];
	    	for(int i=0;i<stones.length;i++) {//先遍历物品
	    		for(int j=target;j>=stones[i];j--) {//再遍历背包
	    			dp[j]=Math.max(dp[j], dp[j-stones[i]]+stones[i]);
	    			
	    		}
	    		
	    	}
	    	return sum-dp[target]-dp[target];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

494.目标和

class Solution {
  public int findTargetSumWays(int[] nums, int target) {
	    	int sum=0;
	    	for(int i:nums) {
	    		sum+=i;
	    	}
	    	int temp=(sum+target)/2;
	    	if((target+sum)%2!=0) {//不能凑出整数的情况
	    		return 0;
	    	}
	    	if(target<0&&sum<-target) {
	    		return 0;
	    	}
	    	int dp[]=new int[temp+1];//dp[i]的含义，装满i的容量的背包有多少种方法
	    	//初始化
	    	dp[0]=1;
	    	for(int i=0;i<nums.length;i++) {
	    		for(int j=temp;j>=nums[i];j--) {//先遍历物品，再遍历背包
	    			dp[j]+=dp[j-nums[i]];
	    		}
	    	}
	    	return dp[temp];
		}
	    

}
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

474. 一和零

  /*
	            * 每个字符串的0，1个数是物品。m，n是背包的含量。先遍历物品，再遍历背包
	     */
	    public int findMaxForm(String[] strs, int m, int n) {
	    	int [][]dp=new int [m+1][n+1];//dp[i][j]的含义是当前背包的容量最多能放i个0，j个的最大子集长度
	    	for(String str:strs) {
	    		int zeronum=0;
	    		int onenum=0;//统计这个物品中0和1的个数
	    		for(char c:str.toCharArray()) {
	    			if(c=='0') {
	    				zeronum++;
	    			}else if(c=='1') {
	    				onenum++;
	    			}
	    		}
	    		//再遍历背包
	    		for(int i=m;i>=zeronum;i--) {
	    			for(int j=n;j>=onenum;j--) {
	    				dp[i][j]=Math.max(dp[i-zeronum][j-onenum]+1, dp[i][j]);
	    			}
	    		}
	    	}
	    	return dp[m][n];

	    }
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

518. 零钱兑换 II

/*
	     * 完全背包问题，先遍历物品，再遍历背包，背包容量要从小到大开始遍历
	     */
	    public int change(int amount, int[] coins) {
	    	int dp[]=new int[amount+1];
	    	dp[0]=1;
	    	for(int i=0;i<coins.length;i++) {
	    		for(int j=coins[i];j<=amount;j++) {
	    			dp[j]+=dp[j-coins[i]];
	    		}
	    	}
	    	return dp[amount];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

377. 组合总和 Ⅳ

  /*
	     * 这题要强调组合的顺序了，顺序不同结果也不一样，所以要先遍历背包，再遍历物品
	     */
	    public int combinationSum4(int[] nums, int target) {
	    	int []dp=new int[target+1];
	    	dp[0]=1;
	    	for(int i=0;i<=target;i++) {
	    		for(int j=0;j<nums.length;j++) {
	    			if(i>=nums[j]) {
	    				dp[i]+=dp[i-nums[j]];
	    			}
	    		}
	    	}
	    	return dp[target];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

322. 零钱兑换

 /*
	     * 这题要求组合最小的数目
	     */
	    public int coinChange(int[] coins, int amount) {
	    	int []dp=new int[amount+1];
	    	dp[0]=0;
	    	//将数组填充成最大的数
	    	for(int i=1;i<amount+1;i++) {
	    		dp[i]=Integer.MAX_VALUE;
	    	}
	    	for(int i=0;i<coins.length;i++) {
	    		for(int j=coins[i];j<=amount;j++) {
	    			if(dp[j-coins[i]]!=Integer.MAX_VALUE) {
	    				dp[j]=Math.min(dp[j], dp[j-coins[i]]+1);
	    			}
	    		}
	    	}
	    	return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];

	    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

279. 完全平方数

/*
	     * 这道题也是求最小数量
	     */
	    public int numSquares(int n) {
	    	int []dp=new int[n+1];
	    	//初始化
	    	dp[0]=0;
	    	for(int i=1;i<=n;i++) {
	    		dp[i]=Integer.MAX_VALUE;
	    	}
	    	for(int i=1;i*i<=n;i++) {//先遍历物品
	    		 for(int j=i*i;j<=n;j++) {
	    			 if(dp[j-(i*i)]!=Integer.MAX_VALUE) {
	    				 dp[j]=Math.min(dp[j], dp[j-(i*i)]+1);
	    			 }
	    		 }
	    	}
	    	return dp[n];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

139.单词拆分

  /*
	     * 因为单词有顺序问题，要强调单词之间的顺序，所以这里使用排列
	     */
	    public boolean wordBreak(String s, List<String> wordDict) {
	    	boolean []dp=new boolean [s.length()+1];//dp[i]表示字符串的长度为i能否被下边的单词所组成，所以返回值为dp[s.length]
	    	// j, ... i。如果dp[j]能被单词所构成并且[j,i]之间的字符串也在字典里，那么就证明dp[j]能构成这个字典
	    	Set<String> set=new HashSet<String>(wordDict);
	    	//初始化
	    	dp[0]=true;
	    	for(int i=1;i<=s.length();i++) {//先遍历背包
	    		for(int j=0;j<i;j++) {//再遍历物品
	    			String word=s.substring(j,i);//物品
	    			if(set.contains(word)&&dp[j]) {
	    				dp[i]=true;
	    			}
	    			
	    		}
	    		
	    	}
	    	return dp[s.length()];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

198. 打家劫舍

 /*
	         *  打家劫舍，不能偷相邻的房间
	     */
	    public int rob(int[] nums) {
	    	int []dp=new int[nums.length];//dp[i]表示从0到下标i，包含下标i能偷取的最大值
	    	if(nums.length==1) {
	    		return nums[0];
	    	}
	    	//初始化
	    	dp[0]=nums[0];
	    	dp[1]=Math.max(nums[0], nums[1]);
	    	for(int i=2;i<nums.length;i++) {
	    		dp[i]=Math.max(dp[i-2]+nums[i], dp[i-1]);
	    	}
	    	return dp[nums.length-1];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

213. 打家劫舍 II

 /*
	          * 因为房子是成环的，所以要分别考虑第一个元素和最后一个元素的情况
	     */
	    public int rob(int[] nums) {
	    	if(nums.length==1) {
	    		return nums[0];
	    	}
	    	if(nums.length==2) {
	    		return Math.max(nums[0], nums[1]);
	    	}
	    	return Math.max(robhelp(nums,0,nums.length-2), robhelp(nums,1,nums.length-1));

	    }
	    
	    public int robhelp(int []nums,int start,int end) {//左闭右闭区间
	    	int []dp=new int[nums.length];
	    	dp[start]=nums[start];
	    	dp[start+1]=Math.max(nums[start], nums[start+1]);
	    	for(int i=start+2;i<=end;i++) {
	    		dp[i]=Math.max(dp[i-2]+nums[i], dp[i-1]);
	    	}
	    	return dp[end];
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

121. 买卖股票的最佳时机

/*
	          * 定义好dp数组的状态然后依次递推即可
	     */
	    public int maxProfit(int[] prices) {
	    	int [][]dp=new int[prices.length][2];//dp[i][0]表示在第i天持有股票的金钱，dp[i][1]表示第i天不持有股票的金钱
	    	dp[0][0]=-prices[0];
	    	dp[0][1]=0;
	    	for(int i=1;i<prices.length;i++) {
	    		dp[i][0]=Math.max(dp[i-1][0], -prices[i]);
	    		dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]+prices[i]);
	    	}
	    	return dp[prices.length-1][1];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

122. 买卖股票的最佳时机 II

 /*
	          * 这次是可以买卖多次了
	     */
	    public int maxProfit(int[] prices) {
			  int [][]dp=new int[prices.length][2];//dp[i][0]表示第i天持有股票的余额，dp[i][1]表示第i天不持有股票的余额
			  dp[0][0]=-prices[0];
			  dp[0][1]=0;
			  for(int i=1;i<prices.length;i++) {
				  dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]-prices[i]);//这里的余额不是0了
				  dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]+prices[i]);
			  }
			  return dp[prices.length-1][1];

		    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

123. 买卖股票的最佳时机 III

  /*
	     * 这次是可以买卖两次了，所以定义好四个状态然后分别去模拟即可
	     */
	    public int maxProfit3(int[] prices) {
	    	int [][]dp=new int[prices.length][5];
	    	dp[0][0]=0;//什么都不操作的状态
	    	dp[0][1]=-prices[0];//第1次持有的状态
	    	dp[0][2]=0;//第1次不持有的状态
	    	dp[0][3]=-prices[0];//第2次持有的状态
	    	dp[0][4]=0;//第2次不持有的状态
	    	for(int i=1;i<prices.length;i++) {
	    		dp[i][1]=Math.max(dp[i-1][1], -prices[i]);
	    		dp[i][2]=Math.max(dp[i-1][2], dp[i-1][1]+prices[i]);
	    		dp[i][3]=Math.max(dp[i-1][3], dp[i-1][2]-prices[i]);
	    		dp[i][4]=Math.max(dp[i-1][4], dp[i-1][3]+prices[i]);
	    	}
	    	return dp[prices.length-1][4];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

188. 买卖股票的最佳时机 IV

 /*
         * 因为有k笔交易，所以会有2k个状态，定义当奇数的时候是持有的状态，为偶数的时候是不持有的状态
         */
	    public int maxProfit(int k, int[] prices) {
	    	int [][]dp=new int[prices.length][2*k+1];
	    	dp[0][0]=0;//什么都不做的状态
	    	for(int i=1;i<2*k+1;i+=2) {
	    		dp[0][i]=-prices[0];
	    	}
	    	for(int i=1;i<prices.length;i++) {
	    		for(int j=0;j<2*k+1;j+=2) {
	    			dp[i][j+1]=Math.max(dp[i-1][j+1], dp[i-1][j]-prices[i]);//持有的状态
	    			dp[i][j+2]=Math.max(dp[i-1][j+2], dp[i-1][j+1]+prices[i]);//不持有的状态
	    			
	    		}
	    	}
	    	return dp[prices.length-1][2*k];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

309. 买卖股票的最佳时机含冷冻期

//把每个状态都列举出来，每个状态要区分清楚。

 public int maxProfit(int[] prices) {
		  int [][]dp=new int[prices.length][4];
		  /**
		   * dp数组含义
		   * dp[i][0]持有股票的状态
		   * dp[i][1]保持卖出股票的状态,在冷冻期之后，每天都是保持卖出股票的状态
		   * dp[i][2]当天卖出股票的状态
		   * dp[i][3]冷冻期
		   */
		  //初始化
		  dp[0][0]=-prices[0];
		  dp[0][1]=0;
		  //递推公式
		  for(int i=1;i<prices.length;i++) {
			  dp[i][0]=Math.max(dp[i-1][0], Math.max(dp[i-1][3]-prices[i], dp[i-1][1]-prices[i]));
			  dp[i][1]=Math.max(dp[i-1][1], dp[i-1][3]);//冷冻期的下一天也是保持卖出股票的状态
			  dp[i][2]=dp[i-1][0]+prices[i];
			  dp[i][3]=dp[i-1][2];
			  
		  }
		  
		  return Math.max(dp[prices.length-1][1], Math.max(dp[prices.length-1][2], dp[prices.length-1][3]));

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

714. 买卖股票的最佳时机含手续费

 /*
	     * 每次交易完一笔之后把手续费减去即可
	     */
	    public int maxProfit(int[] prices, int fee) {
	    	int [][]dp=new int[prices.length][2];
	    	dp[0][0]=-prices[0];//持有股票的状态
	    	dp[0][1]=0;//不持有股票的状态
	    	for(int i=1;i<prices.length;i++) {
	    		dp[i][0]=Math.max(dp[i-1][0], dp[i-1][1]-prices[i]);
	    		dp[i][1]=Math.max(dp[i-1][1], dp[i-1][0]+prices[i]-fee);
	    	}
	    	return dp[prices.length-1][1];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

300. 最长递增子序列

 public static int lengthOfLIS(int[] nums) {
	    	int []dp=new int[nums.length];//dp[i]表示以i为结尾的最长递增子序列的长度，i代表的是下标
	    	//初始化
	    	for(int i=0;i<nums.length;i++) {
	    		Arrays.fill(dp, 1);
	    	}
	    	for(int i=1;i<nums.length;i++) {
	    		for(int j=0;j<i;j++) {//从第二层开始再找比j大的数组
	    			if(nums[i]>nums[j]) {
	    				dp[i]=Math.max(dp[i], dp[j]+1);
	    			}
	    		}
	    	}
	    	//从dp数组中找到一个最大值
	    	int result=0;
	    	for(int i=0;i<nums.length;i++) {
	    		result=Math.max(result, dp[i]);
	    	}
	    	return result;
			  
	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

674. 最长连续递增序列

  public int findLengthOfLCIS(int[] nums) {
	    	int []dp=new int[nums.length];//dp[i]表示以i结尾的最长连续递增子序列
	    	//初始化
	    	dp[0]=1;
	    	for(int i=1;i<nums.length;i++) {
	    		if(nums[i]>nums[i-1]) {
	    			dp[i]=dp[i-1]+1;
	    		}else {
	    			dp[i]=1;
	    		}
	    	}
	    	//找到数组里的最大值
	    	//从dp数组中找到一个最大值
	    	int result=0;
	    	for(int i=0;i<nums.length;i++) {
	    		result=Math.max(result, dp[i]);
	    	}
	    	return result;

	    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

718. 最长重复子数组

  public int findLength(int[] nums1, int[] nums2) {
			   int [][]dp=new int[nums1.length+1][nums2.length+1];
			   //dp数组的定义是dp[i][j]表示数组1以i-1为结尾的数组2以j-1为结尾的最长公共子序列的长度，如果代表以i为结尾的话，初始化就不好初始化了
			   //初始化,第一行第一列初始为0
			   int result=0;
			   for(int i=1;i<nums1.length+1;i++) {
				   for(int j=1;j<nums2.length+1;j++) {
					   if(nums1[i-1]==nums2[j-1]) {
						   dp[i][j]=dp[i-1][j-1]+1;
						  
					   }
					   result=Math.max(result,  dp[i][j]);
					
				   }
			   }
			   return result;
		    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1143. 最长公共子序列

 /*
	     * 最长公共子序列，这道题是不要求子序列连续了
	     */
	    public int longestCommonSubsequence(String text1, String text2) {
	    	int dp[][]=new int[text1.length()+1][text2.length()+1];
	    	//dp[i][j]的含义是 text1从[0,i-1]的子序列与text2从[0,i-1]的最长共子序列的长度
	    	for(int i=1;i<=text1.length();i++) {
	    		for(int j=1;j<=text2.length();j++) {
	    			if(text1.charAt(i-1)==text2.charAt(j-1)) {
	    				dp[i][j]=dp[i-1][j-1]+1;//如果两个字符相等的话，数值就加上一个
	    			}else {
	    				dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
	    			}
	    		}
	    	}
	    	return dp[text1.length()][text2.length()];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1035. 不相交的线

 /*
	     * 就是求两者的最长公共子序列
	     */
	    public int maxUncrossedLines(int[] nums1, int[] nums2) {
	    	int dp[][]=new int[nums1.length+1][nums2.length+1];
	    	//dp[i][j]的含义是 text1从[0,i-1]的子序列与text2从[0,i-1]的最长共子序列的长度
	    	for(int i=1;i<=nums1.length;i++) {
	    		for(int j=1;j<=nums2.length;j++) {
	    			if(nums1[i-1]==nums2[j-1]) {
	    				dp[i][j]=dp[i-1][j-1]+1;//如果两个字符相等的话，数值就加上一个
	    			}else {
	    				dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
	    			}
	    		}
	    	}
	    	return dp[nums1.length][nums2.length];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

53. 最大子数组和

  public int maxSubArray(int[] nums) {
	    	int []dp=new int[nums.length];//dp[i]表示以i结尾的数组最大子数组和的值
	    	
	    	dp[0]=nums[0];
	    	int result=dp[0];
	    	for(int i=1;i<nums.length;i++) {
	    		dp[i]=Math.max(dp[i-1]+nums[i], nums[i]);
	    		result=Math.max(result, dp[i]);
	    	}
	    	return result;

	    }
1
2
3
4
5
6
7
8
9
10
11
12

392. 判断子序列

 /*
	         * 这道题求出最长公共子序列的长度，然后比较和t的长度即可
	     */
	    public boolean isSubsequence(String s, String t) {
	    	int [][]dp=new int[s.length()+1][t.length()+1];
	    	for(int i=1;i<=s.length();i++) {
	    		for(int j=1;j<=t.length();j++) {
	    			if(s.charAt(i-1)==t.charAt(j-1)) {
	    				dp[i][j]=dp[i-1][j-1]+1;
	    			}else {
	    				dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
	    			}
	    		}
	    	}
	    	return dp[s.length()][t.length()]==s.length();

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

115. 不同的子序列

public int numDistinct(String s, String t) {
	    	int [][]dp=new int[s.length()+1][t.length()+1];
	    	//dp[i][j]表示以i-1为结尾的s中有多少个以j-1为结尾的t
	    	//初始化
	    	dp[0][0]=1;
	    	dp[0][1]=0;
	    	dp[0][0]=1;
	    	for(int i=0;i<=s.length();i++) {
	    		dp[i][0]=1;
	    	}
	    	//递推公式
	    	for(int i=1;i<=s.length();i++) {
	    		for(int j=1;j<=t.length();j++) {
	    			if(s.charAt(i-1)==t.charAt(j-1)) {//如果这两个元素相等的话，就不用考虑这两个元素了,或者不用i这个元素了
	    				dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
	    				
	    			}else {//如果不相等的话，只需要删除上边的元素即可
	    				dp[i][j]=dp[i-1][j];
	    			}
	    		}
	    	}
	    	return dp[s.length()][t.length()];

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

583. 两个字符串的删除操作

 /*
	          * 如果不相等，删上一个、删下一个、还是都删了从这里边选个最小的
	     */
	    public int minDistance(String word1, String word2) {
	    	int [][]dp=new int[word1.length()+1][word2.length()+1];
	    	//dp[i][j]的含义以i-1为结尾的word1要和word2以j-1为结尾变成相同的字符串最少需要多少步
	    	//初始化
	    	for(int i=0;i<=word1.length();i++) {
	    		dp[i][0]=i;
	    	}
	    	for(int j=0;j<=word2.length();j++) {
	    		dp[0][j]=j;
	    	}
	    	for(int i=1;i<=word1.length();i++) {
	    		for(int j=1;j<=word2.length();j++) {
	    			if(word1.charAt(i-1)==word2.charAt(j-1)) {
	    				dp[i][j]=dp[i-1][j-1];
	    			}else {
	    				dp[i][j]=Math.min(dp[i-1][j]+1, Math.min(dp[i][j-1]+1, dp[i-1][j-1]+2));
	    			}
	    		}
	    	}
	    	return dp[word1.length()][word2.length()];

	    }
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

72. 编辑距离

/*
	          * 是删一个还是更改一个
	     */
	    public int minDistance(String word1, String word2) {
	    	int [][]dp=new int[word1.length()+1][word2.length()+1];
	    	//dp[i][j]的含义以i-1为结尾的word1要和word2以j-1为结尾变成相同的字符串最少需要多少步
	    	//初始化
	    	for(int i=0;i<=word1.length();i++) {
	    		dp[i][0]=i;
	    	}
	    	for(int j=0;j<=word2.length();j++) {
	    		dp[0][j]=j;
	    	}
	    	for(int i=1;i<=word1.length();i++) {
	    		for(int j=1;j<=word2.length();j++) {
	    			if(word1.charAt(i-1)==word2.charAt(j-1)) {
	    				dp[i][j]=dp[i-1][j-1];
	    			}else {
	    				dp[i][j]=Math.min(dp[i-1][j]+1, Math.min(dp[i][j-1]+1, dp[i-1][j-1]+1));
	    			}
	    		}
	    	}
	    	return dp[word1.length()][word2.length()];


	    }
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

647. 回文子串

 /*
	     * 因为递推公式要用到左下角的值，所以遍历顺序应该是从下到上，从左到右去遍历
	     */
	    public int countSubstrings(String s) {
	    	boolean [][]dp=new boolean[s.length()][s.length()];
	    	//dp[i][j]表示[i,j]这个区间的字符串是不是回文字符串
	    	int result=0;
	    	for(int i=s.length()-1;i>=0;i--) {
	    		for(int j=i;j<s.length();j++) {
	    			if(s.charAt(i)==s.charAt(j)) {//如果这两个字符相等
	    				if(j-i<=1) {
	    					dp[i][j]= true;
	    					result++;
	    				}else if(dp[i+1][j-1]){//如果它里边是回文字符串
	    					dp[i][j]=true;
	    					result++;
	    				}
	    			}
	    		}
	    	}
	    	return result;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

516.最长回文子序列

class Solution {
    public int longestPalindromeSubseq(String s) {
	    	int [][]dp=new int[s.length()][s.length()];
	    	//dp[i][j]表示[i,j]这个区间的回文子串长度。
	    	//初始化
	    	for(int i=0;i<s.length();i++) {
	    		dp[i][i]=1;
	    	}
	    	for(int i=s.length()-1 ;i>=0;i--) {
	    		for(int j=i+1;j<s.length();j++) {
	    			if(s.charAt(i)==s.charAt(j)) {//如果两个字符相同的话
	    				dp[i][j]=dp[i+1][j-1]+2;
	    			}else {
	    				dp[i][j]=Math.max(dp[i+1][j], dp[i][j-1]);
	    			}
	    		}
	    		
	    	}
	    	return dp[0][s.length()-1];

	    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

图论

LeetCode100

128. 最长连续序列

/*
	 * 用哈希表存下这些数字，然后如果这个数字有前缀，则直接跳过，如果没有的化，再从当前的位置进行遍历
	 */
    public int longestConsecutive(int[] nums) {
    	Set<Integer> set=new HashSet<Integer>();
    	for(int i:nums) {
    		set.add(i);
    	}
    	int maxResult=0;
    	
    	for(int i=0;i<nums.length;i++) {
    		if(set.contains(nums[i]-1)) {
    			continue;
    		}else {
    			int curnum=nums[i];
    			int result=1;
    			while(set.contains(curnum+1)) {
    				curnum+=1;
    				result+=1;
    			}
    			maxResult=Math.max(result, maxResult);
    		}
    	}
    	return maxResult;

    }
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

11.盛水最多的容器

  /*
     * 两个指针分别指向首尾位置，每次去收缩身高短的指针，因为如果伸缩身高高的指针，它的面积也只会越来越小
     */
    public int maxArea(int[] height) {
    	int left=0;
    	int right=height.length-1;
    	int result=0;
    	while(left<=right) {
    		result=Math.max(result, Math.min(height[left], height[right])*(right-left));
    		if(height[left]<height[right]) {
    			left++;
    		}else {
    			right--;
    		}
    		
    	}
    	return result;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

42. 接雨水

  /*
     * 单调栈来解决，栈里存的是从小到大的元素，如果遍历的元素大于栈顶的元素，就证明出现凹槽了，然后就开始计算雨水面积
     */
    public int trap(int[] height) {
    	int size=height.length;
    	Stack<Integer> stack=new Stack<Integer>();
    	//先把第一个元素放进去,存的元素是下标
    	stack.push(0);
    	int sum=0;
    	for(int i=1;i<height.length;i++) {//分为三种情况
    		if(height[i]<height[stack.peek()]) {//如果遍历的元素小于栈顶元素，直接放进去即可
    	       stack.push(i);
    			
    		}else if(height[i]==height[stack.peek()]) {//如果遍历的元素等于栈顶元素，直接更新当前的，因为相等的相邻墙，左边是不可能存放雨水的
    			
    			stack.pop();
    			stack.push(i);
    			
    		}else {//遍历的元素大于栈顶元素，这里要开始计算雨水面积了
    			
    		     int heightAtIdx=height[i];//当前遍历到的高度
    		     while(!stack.isEmpty()&&(heightAtIdx>height[stack.peek()])) {//当前遍历的元素大于栈口元素的时候
    		    	 
    		    	 int mid=stack.pop();//栈顶的下标
    		    	 if(!stack.isEmpty()) {
    		    		 int left=stack.peek();//凹槽左边的下标
    		    		 int h=Math.min(height[left], height[i])-height[mid];
    		    		 int w=i-left-1;
    		    		 int area=h*w;
    		    		 if(area>0) {
    		    			 sum+=area;
    		    		 }
    		    		 
    		    	 }
    		    	 stack.push(i);
    		    	 
    		     }
    			
    			
    		}
    		
    	}
    	return sum;
    	

    }
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

3. 无重复字符的最长子串

  /*
          * 最长无重复子串，我们用滑动窗口来解决，当右指针往右移动时，我们只需要每次移动左指针，然后依次的去更新右指针即可
     */
    public int lengthOfLongestSubstring(String s) {
    	Set<Character> set=new HashSet<Character>();
    	int right=0;
    	int result=0;
    	for(int left=0;left<s.length();left++) {
    		if(left!=0) {
    			set.remove(s.charAt(left-1));
    		}
    		while(right<s.length()&&!set.contains(s.charAt(right))) {//当右指针指向的字符不在set里
    			set.add(s.charAt(right));
    			right++;
    			
    		}
    		result=Math.max(result, right-left);
    	}
    	return result;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

560.和为k的子数组

这道题我们采用前缀和+哈希表的方式。

前缀和就是 1 2 3这个数组的每个数字的前缀和是多少 这个数组的前缀和就是 1 3 6。
我们求[i,j]里边的子数组和就可以表示为pre[j]-pre[i-1]；
我们求数组里边有多少个pre[j]-pre[i-1]=k,所以有pre[j]

56.合并区间

 /*
	  * 讲数组以左边界排好序，然后比较右边界的关系
	  */
	  public int[][] merge(int[][] intervals) {
		  List<int []>result=new ArrayList<int []>();
		  Arrays.sort(intervals,(x,y)->Integer.compare(x[0], y[0]));
		  int start=intervals[0][0];
		  int right=intervals[0][1];
		  for(int i=1;i<intervals.length;i++) {
			  if(intervals[i][0]>right) {//如果左边界大于右边界
				  result.add(new int[] {start,right});
				  start=intervals[i][0];
				  right=intervals[i][1];
				  
				  
			  }else {
				  //更新最右边界
				  right=Math.max(right, intervals[i][1]);
			  }
		  }
		  result.add(new int[] {start,right});
		  return result.toArray(new int[result.size()][]);

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

189. 轮转数组

 /*
	   * 直接声明一个新数组，将旧数组的元素放到它该放的位置
	   */
	   public void rotate(int[] nums, int k) {
		   int []newArray=new int[nums.length];
		   for(int i=0;i<nums.length;i++) {
			   newArray[(i+k)%nums.length]=nums[i];
		   }
		   System.arraycopy(newArray, 0, nums, 0, nums.length);

	    }
1
2
3
4
5
6
7
8
9
10
11

238. 除自身以外数组的乘积

 /*
	    * 将这个索引的左侧乘积索引和右侧乘积索引分别求出来，然后answer[i]=L[i]*R[i]
	    */
	   public int[] productExceptSelf(int[] nums) {
		   int []L=new int[nums.length];
		   int []R=new int[nums.length];
		   L[0]=1;
		   for(int i=1;i<nums.length;i++) {
			   L[i]=L[i-1]*nums[i-1];
		   }
		   R[nums.length-1]=1;
		   for(int i=nums.length-2;i>=0;i--) {
			   R[i]=R[i+1]*nums[i+1];
		   }
		   int []answer=new int[nums.length];
		   for(int i=0;i<nums.length;i++) {
			   answer[i]=L[i]*R[i];
		   }
		   return answer;

	    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

200.岛屿数量

class Solution {
      public int numIslands(char[][] grid) {
	    	if(grid==null||grid.length==0) {
	    		return 0;
	    	}
	    	int result=0;
	    	for(int i=0;i<grid.length;i++) {
	    		for(int j=0;j<grid[0].length;j++) {
	    			if(grid[i][j]=='1') {
	    				result++;
	    				dfs(grid,i,j);
	    			}
	    		}
	    	}
	    	return result;
	        
	    }
	    public void dfs(char [][]grid,int i,int j) {
	    	int m=grid.length;
	    	int n=grid[0].length;
	    	if(i<0||j<0 ||i>=m||j>=n||grid[i][j]=='0') {
	    		return ;
	    	}
	    	grid[i][j]='0';
	    	dfs(grid,i-1,j);
	    	dfs(grid,i+1,j);
	    	dfs(grid,i,j-1);
	    	dfs(grid,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
29
30