算法强基计划
快速排序
快速排序就是选择一个作为基准元素，左边的元素放比基准元素小的，右边放比基准元素大的，然后分别对左右两个区间进行递归。
我的这个方法是以最左边的元素为基准，遍历区间，然后找到比当前元素大的元素就交换i和j对应的元素，然后i++，最后把i-1位置的元素和low位置的元素进行交换，最终实现排序。
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
|
package com.lucius.interviewproject.SortTest;
import java.util.Scanner;
public class QuickSortTest {
public static void quickSort(int[] arr,int low,int high){
if(low<high){
//采用分治法的思想，将数组分为左右两个子数组
int pivotIndex=partition(arr,low,high);
quickSort(arr,low,pivotIndex-1);
quickSort(arr,pivotIndex+1,high);
}
}
public static int partition(int[] arr,int low,int high){
//将数组分为左右两个子数组，并返回中间位置
int pivot=arr[low];
int i=low+1;
for(int j=low+1;j<=high;j++){
//将小于pivot的元素移到左边，大于pivot的元素移到右边
if(pivot>arr[j]){
int temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
i++;
}
}
//将pivot放到中间位置
int temp=arr[i-1];
arr[i-1]=pivot;
arr[low]=temp;
return i-1;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
for(int a:arr){
System.out.print(a+" ");
}
System.out.println();
quickSort(arr,0,n-1);
for(int a:arr){
System.out.print(a+" ");
}
}
}
|
直接逃课打法，哈希表查重
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public class Solution {
public ListNode detectCycle(ListNode head) {
HashSet<ListNode> set=new HashSet<>();
while(head!=null){
if(set.contains(head)){
return head;
}
set.add(head);
head=head.next;
}
return null;
}
}
|
这题有点难搞，第n次做感觉都不一定能做出来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy=new ListNode();
dummy.next=head;
ListNode cur=dummy;
while(cur.next!=null&&cur.next.next!=null){
ListNode node1=cur.next;
ListNode node2=cur.next.next;
ListNode node3=cur.next.next.next;
node2.next=node1;
node1.next=node3;
//让当前的虚拟头节点的next指向正确的节点
cur.next=node2;
//更新当前虚拟头节点的位置，继续进行下一轮交换
cur=node1;
}
return dummy.next;
}
}
|
简单题，先遍历n次节点，然后再用一个新的节点遍历剩余次数，然后进行节点删除即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy=new ListNode();
dummy.next=head;
ListNode cur=dummy;
for(int i=0;i<n;i++){
cur=cur.next;
}
ListNode node=dummy;
while(cur.next!=null){
cur=cur.next;
node=node.next;
}
node.next=node.next.next;
return dummy.next;
}
}
|
依旧简单题，找到两个链表的相同节点即可，记得用.equals()
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
|
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int aLen=0;
int bLen=0;
ListNode node1=headA;
ListNode node2=headB;
while(node1!=null){
node1=node1.next;
aLen++;
}
while(node2!=null){
node2=node2.next;
bLen++;
}
node1=headA;
node2=headB;
int count=Math.abs(aLen-bLen);
if(aLen>bLen){
while(count>0){
node1=node1.next;
count--;
}
}else{
while(count>0){
node2=node2.next;
count--;
}
}
for(int i=0;i<Math.min(aLen,bLen);i++){
if(node1.equals(node2)){
return node1;
}
node1=node1.next;
node2=node2.next;
}
return null;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public int search(int[] nums, int target) {
int left=0;
int right=nums.length-1;
while(left<=right){
int mid=(right-left)/2+left;
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
left=mid+1;
}else{
right=mid-1;
}
}
return -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public int removeElement(int[] nums, int val) {
int fast=0;
int slow=0;
for(;fast<nums.length;fast++){
if(nums[fast]!=val){
nums[slow]=nums[fast];
slow++;
}
}
return slow;
}
}
|
最作弊的写法
1
2
3
4
5
6
7
8
9
|
class Solution {
public int[] sortedSquares(int[] nums) {
for(int i=0;i<nums.length;i++){
nums[i]*=nums[i];
}
Arrays.sort(nums);
return nums;
}
}
|
因为数组已经排好序了，可以直接用双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public int[] sortedSquares(int[] nums) {
int n=nums.length;
int[] arr=new int[n];
int slow=0;
int fast=n-1;
n-=1;
while(n>=0){
int nFast=nums[fast]*nums[fast];
int nSlow=nums[slow]*nums[slow];
if(nFast<nSlow){
arr[n--]=nSlow;
slow++;
}else{
arr[n--]=nFast;
fast--;
}
}
return arr;
}
}
|
非常简单的一个哈希表，字母可以考虑int[26]还有char c，arr[c-‘a’]++;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public boolean isAnagram(String s, String t) {
int[] hash=new int[26];
if(s.length()!=t.length()){
return false;
}
for(int i=0;i<s.length();i++){
hash[s.charAt(i)-'a']++;
}
for(int i=0;i<t.length();i++){
hash[t.charAt(i)-'a']--;
}
for(int i=0;i<26;i++){
if(hash[i]!=0){
return false;
}
}
return true;
}
}
|
感觉写复杂了，其中遍历set集合中的元素方法应该记牢,还有遍历map的
1
2
3
4
5
6
7
8
9
10
|
HashSet<Integer> set=new HashSet<>();
...
for(int a:setResult){
result[index++]=a;
}
HashMap<Integer,Integer> map=new HashMap<>();
...
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
System.out.println(entry.getValue());
}
|
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
|
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int len1=nums1.length;
int len2=nums2.length;
if(len1>len2){
HashSet<Integer> set=new HashSet<>();
HashSet<Integer> setResult=new HashSet<>();
for(int i=0;i<len1;i++){
set.add(nums1[i]);
}
for(int i=0;i<len2;i++){
if(set.contains(nums2[i])){
setResult.add(nums2[i]);
}
}
int[] result=new int[setResult.size()];
int index=0;
for(int a:setResult){
result[index++]=a;
}
return result;
}else{
HashSet<Integer> set=new HashSet<>();
HashSet<Integer> setResult=new HashSet<>();
for(int i=0;i<len2;i++){
set.add(nums2[i]);
}
for(int i=0;i<len1;i++){
if(set.contains(nums1[i])){
setResult.add(nums1[i]);
}
}
int[] result=new int[setResult.size()];
int index=0;
for(int a:setResult){
result[index++]=a;
}
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
|
class Solution {
public boolean isHappy(int n) {
HashSet<Integer> set=new HashSet<>();
while(true){
int result=func(n);
n=result;
if(result==1){
return true;
}
if(set.contains(result)){
return false;
}else{
set.add(result);
}
}
}
public int func(int n){
List<Integer> list=new ArrayList<>();
while(n!=0){
list.add(n%10);
n/=10;
}
int [] arr=new int[list.size()];
int sum=0;
for(int i=0;i<list.size();i++){
sum+=list.get(i)*list.get(i);
}
return sum;
}
}
|
非常简单的哈希表，但是注意不能自己加自己
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
int a=target-nums[i];
if(map.containsKey(a)&&map.get(a)!=i){
int [] arr=new int[2];
arr[0]=i;
arr[1]=map.get(a);
return arr;
}
}
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
|
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int n=nums1.length;
int count=0;
HashMap<Integer,Integer> map1=new HashMap<>();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int sum=nums1[i]+nums2[j];
if(map1.containsKey(sum)){
map1.put(sum,map1.get(sum)+1);
}else{
map1.put(sum,1);
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int sum=nums3[i]+nums4[j];
if(map1.containsKey(-sum)){
count+=map1.get(-sum);
}
}
}
return count;
}
}
|
这道题就是26字母的哈希表问题，很简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] arr=new int [26];
for(int i=0;i<ransomNote.length();i++){
arr[ransomNote.charAt(i)-'a']++;
}
for(int i=0;i<magazine.length();i++){
if(arr[magazine.charAt(i)-'a']>0){
arr[magazine.charAt(i)-'a']--;
}
}
for(int i=0;i<26;i++){
if(arr[i]!=0){
return false;
}
}
return true;
}
}
|
三数之和老朋友了，遍历+双指针，然后考虑去重，要用while，还有就是别忘了排序
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
|
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result=new ArrayList<>();
int a=Integer.MAX_VALUE;
int n=nums.length;
Arrays.sort(nums);
for(int i=0;i<n-2;i++){
if(nums[i]==a){
continue;
}
a=nums[i];
int left=i+1;
int right=n-1;
while(left<right){
int sum=nums[i]+nums[right]+nums[left];
if(sum==0){
List<Integer> list=new ArrayList<>();
list.add(nums[i]);
list.add(nums[right]);
list.add(nums[left]);
result.add(list);
while(left+1<right&&nums[left]==nums[left+1]){
left++;
}
while(right-1>left&&nums[right]==nums[right-1]){
right--;
}
left++;
right--;
}else if(sum>0){
right--;
}else {
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
|
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result=new ArrayList<>();
int n=nums.length;
Arrays.sort(nums);
for(int i=0;i<n-3;i++){
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for(int j=i+1;j<n-2;j++){
if(j>i+1&&nums[j]==nums[j-1]){
continue;
}
int left=j+1;
int right=n-1;
while(left<right){
long sum=(long)nums[i]+nums[j]+nums[left]+nums[right];
if(sum==target){
List<Integer> list=new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);
result.add(list);
while(left+1<right&&nums[left+1]==nums[left]){
left++;
}
while(right-1>left&&nums[right-1]==nums[right]){
right--;
}
left++;
right--;
}else if(sum<target){
left++;
}else{
right--;
}
}
}
}
return result;
}
}
|
最简单的字符串问题，直接用双指针做
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public void reverseString(char[] s) {
int left=0;
int right=s.length-1;
while(left<right){
char temp=s[left];
s[left]=s[right];
s[right]=temp;
left++;
right--;
}
}
}
|
这道题有点复杂，我一开始用的方法写的很长，而且有些情况做不出来，并且通过这道题了解到不少String相关的api
1
2
|
char[] arr = s.toCharArray
return new Strin
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public String reverseStr(String s, int k) {
int n = s.length();
char[] arr = s.toCharArray();
for (int i = 0; i < n; i += 2 * k) {
reverse(arr, i, Math.min(i + k, n) - 1);
}
return new String(arr);
}
public void reverse(char[] arr, int left, int right) {
while (left < right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
|
第一次做这种题，直接傻了，一开始导包都错了，还有Scanner sc=new Scanner(System.in);都写错了
还有一个常用的api
1
2
|
//判断字符是否是数字
Character.isDigit(a);
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String s=sc.nextLine();
StringBuilder sb=new StringBuilder();
for(int i=0;i<s.length();i++){
if(Character.isDigit(s.charAt(i))){
sb.append("number");
}else{
sb.append(s.charAt(i));
}
}
System.out.println(sb.toString());
}
}
|
这题有点复杂，先要对字符串进行头尾空格删除，然后要删除字符串中多余的空格，然后要整体反转字符串，再进行局部反转字符串。
StringBuilder的api
1
2
|
StringBuilder sb=new StringBuilder();
sb.setCharAt(start,sb.charAt(end));
|
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
|
class Solution {
public String reverseWords(String s) {
StringBuilder sb=delete(s);
sb=reserve(sb,0,sb.length()-1);
sb=result(sb);
return sb.toString();
}
public StringBuilder result(StringBuilder sb){
int index=0;
for(int i=0;i<sb.length();i++){
if(sb.charAt(i)==' '){
sb=reserve(sb,index,i-1);
index=i+1;
}else if(i==sb.length()-1){
sb=reserve(sb,index,i);
}
}
return sb;
}
public StringBuilder reserve(StringBuilder sb,int start,int end){
while(start<end){
char ch=sb.charAt(start);
sb.setCharAt(start,sb.charAt(end));
sb.setCharAt(end,ch);
start++;
end--;
}
return sb;
}
public StringBuilder delete(String s){
int start=0;
int end=s.length()-1;
while(s.charAt(start)==' '){
start++;
}
while(s.charAt(end)==' '){
end--;
}
StringBuilder sb=new StringBuilder();
for(int i=start;i<end+1;i++){
char ch=s.charAt(start);
if(ch!=' '||sb.charAt(sb.length()-1)!=' '){
sb.append(ch);
}
start++;
}
return sb;
}
}
|
这道题直接做很简单，把字符串拼在一起，然后切除两边的字符，这样就让重复子串数减少了两个，如果中间的两个仍然能拼成s，那么就是重复子字符串
String的api
1
2
3
|
String s="abab";
Boolean b=s.contains("a");
int a=s.indexOf("a");
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public boolean repeatedSubstringPattern(String s) {
StringBuilder sb=new StringBuilder();
sb.append(s);
sb.append(s);
String s1=sb.substring(1,sb.length()-1);
if(s1.contains(s)){
return true;
}else {
return false;
}
}
}
|
最简单的做法就是新开一个空间
1
2
3
4
5
6
|
//Scanner的使用方式
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
//注意，这里有个回车
sc.nextLine();
String s=sc.nextLine();
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import java.util.*;
public class Main{
public static char[] func(char[] arr,int k){
char [] charArray=new char[arr.length];
int k1=k%arr.length;
for(int i=0;i<arr.length;i++){
charArray[(i+k1)%arr.length]=arr[i];
}
return charArray;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k=sc.nextInt();
sc.nextLine();
String s=sc.nextLine();
char[] arr = s.toCharArray();
char[] charArray = func(arr, k);
System.out.println(new String(charArray));
sc.close();
}
}
|
两个栈实现队列，栈1用来压入数据，栈2充当队列，如果要出队列或者查看队首元素，可以通过查看栈2，如果栈2没有元素就要把栈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
39
40
41
42
43
44
45
46
47
|
class MyQueue {
Stack<Integer> st1;
Stack<Integer> st2;
public MyQueue() {
st1=new Stack<>();
st2=new Stack<>();
}
public void push(int x) {
st1.push(x);
}
public int pop() {
if(st2.isEmpty()){
while(!st1.isEmpty()){
st2.push(st1.pop());
}
}
return st2.pop();
}
public int peek() {
if(st2.isEmpty()){
while(!st1.isEmpty()){
st2.push(st1.pop());
}
}
return st2.peek();
}
public boolean empty() {
if(st1.isEmpty()&&st2.isEmpty()){
return true;
}else{
return false;
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
|
如果想查看栈顶元素，就需要把q1中除了最后入队列的元素放入q2辅助队列，查看或者出栈后把所有元素再放进来即可
1
2
3
4
5
6
7
8
|
//队列的api
Queue<Integer> q1=new LinkedList<>();
q1.add(1);
q1.add(2);
//从队列中获取队头数据
q1.peek();
//取出队头元素并且获取其值
q1.poll();
|
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
|
class MyStack {
Queue<Integer> q1;
Queue<Integer> q2;
public MyStack() {
q1=new LinkedList<>();
q2=new LinkedList<>();
}
public void push(int x) {
q1.add(x);
}
public int pop() {
while(q1.size()!=1){
q2.add(q1.poll());
}
int result=q1.poll();
while(!q2.isEmpty()){
q1.add(q2.poll());
}
return result;
}
public int top() {
while(q1.size()!=1){
q2.add(q1.poll());
}
int result=q1.poll();
while(!q2.isEmpty()){
q1.add(q2.poll());
}
q1.add(result);
return result;
}
public boolean empty() {
if(q1.isEmpty()&&q2.isEmpty()){
return true;
}else{
return false;
}
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
|
这个闭眼写，不多做解释。
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
|
class Solution {
public boolean isValid(String s) {
int length=s.length();
Stack<Character> st=new Stack<>();
for(int i=0;i<length;i++){
char ch=s.charAt(i);
if(ch=='('||ch=='['||ch=='{'){
st.push(ch);
}else{
if(st.isEmpty()){
return false;
}else if(ch==')'){
if(st.peek()!='('){
return false;
}else{
st.pop();
}
}else if(ch==']'){
if(st.peek()!='['){
return false;
}else{
st.pop();
}
}else if(ch=='}'){
if(st.peek()!='{'){
return false;
}else{
st.pop();
}
}
}
}
if(!st.isEmpty()){
return false;
}
return true;
}
}
|
这题本身挺简单的，但是有个小问题
1
2
3
4
5
6
7
8
9
|
//这样是对的
int size=st.size();
for(int i=0;i<size;i++){
...
}
//这样是错的
for(int i=0;i<st.size();i++){
...
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public String removeDuplicates(String s) {
Stack<Character> st=new Stack<>();
for(int i=0;i<s.length();i++){
if(st.isEmpty()){
st.push(s.charAt(i));
}else{
if(st.peek()==s.charAt(i)){
st.pop();
}else{
st.push(s.charAt(i));
}
}
}
StringBuilder sb=new StringBuilder();
int size=st.size();
for(int i=0;i<size;i++){
sb.append(st.pop());
}
return sb.reverse().toString();
}
}
|
这题较为简单，就入栈出栈就行，记得校验负号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Solution {
public int evalRPN(String[] tokens) {
int length=tokens.length;
Stack<Integer> st=new Stack<>();
for(int i=0;i<length;i++){
if(!tokens[i].equals("+")&&!tokens[i].equals("/")&&!tokens[i].equals("*")&&!tokens[i].equals("-")){
st.push(func(tokens[i]));
}else{
int a=st.pop();
int b=st.pop();
if(tokens[i].equals("+")){
st.push(a+b);
}else if(tokens[i].equals("-")){
st.push(b-a);
}else if(tokens[i].equals("*")){
st.push(a*b);
}else if(tokens[i].equals("/")){
st.push(b/a);
}
}
}
return st.pop();
}
public int func(String s){
int num=0;
boolean flag=false;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='-'){
flag=true;
continue;
}
num*=10;
num+=(s.charAt(i)-'0');
}
return flag?num*-1:num;
}
}
|
使用堆来做，控制好滑动窗口大小，然后等需要删除滑动窗口值的时候统一删除
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
|
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int length=nums.length;
PriorityQueue<int []> queue=new PriorityQueue<>((o1,o2)->o2[0]-o1[0]);
for(int i=0;i<k;i++){
int[] array=new int[2];
array[0]=nums[i];
array[1]=i;
queue.offer(array);
}
int[] result=new int[length-k+1];
result[0]=queue.peek()[0];
for(int i=1;i<length-k+1;i++){
int[] arr=new int[2];
arr[0]=nums[i+k-1];
arr[1]=i+k-1;
queue.add(arr);
while(queue.peek()[1]<i){
queue.poll();
}
result[i]=queue.peek()[0];
}
return result;
}
}
|
这道题思想不难，但是代码中的API比较多，比如map的entrySet()，PriorityQueue
1
2
3
4
5
6
7
8
|
//这个是map的key-value的数据结构
Map.Entry<Integer,Integer> mapEntry;
int key=mapEntry.getKey();
int value=mapEntry.getValue();
//遍历map中的元素
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
...
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map=new HashMap<>();
PriorityQueue<Map.Entry<Integer,Integer>> queue=new PriorityQueue<>((o1,o2)->o2.getValue()-o1.getValue());
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
map.put(nums[i],map.get(nums[i])+1);
}else{
map.put(nums[i],1);
}
}
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
queue.add(entry);
}
int[] result=new int[k];
for(int i=0;i<k;i++){
result[i]=queue.poll().getKey();
}
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
|
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(int val){
this.val=val;
}
}
public class TreeLevelOrder{
public static List<Integer> func(TreeNode root){
if(root==null){
return new ArrayList<>();
}
LinkedList<TreeNode> ll=new LinkedList<>();
ll.add(root);
List<Integer> list=new ArrayList<>();
while(!ll.isEmpty()){
int size=ll.size();
for(int i=0;i<size;i++){
TreeNode node=ll.pop();
list.add(node.val);
if(node.left!=null){
ll.add(node.left);
}
if(node.right!=null){
ll.add(node.right);
}
}
}
return list;
}
public static void main(String[] args){
List<Integer> list=func(root);
for(int a:list){
System.out.println(a);
}
}
}
|
这道题是二叉树层序遍历的特殊题目，需要知道下一个节点的信息，可以通过LinkedList的peek()方法来获取下一个节点
1
2
3
4
5
6
7
|
LinkedList<Integer> ll=new LinkedList<>();
//添加元素
ll.add(a);
//取出队首元素
ll.pop();
//获取队首元素的值
ll.peek();
|
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
|
class Solution {
public Node connect(Node root) {
LinkedList<Node> ll=new LinkedList<>();
ll.add(root);
if(root==null){
return root;
}
while(!ll.isEmpty()){
int size=ll.size();
for(int i=0;i<size;i++){
Node node=ll.pop();
if(i==size-1){
node.next=null;
}else{
node.next=ll.peek();
}
if(node.left!=null){
ll.add(node.left);
}
if(node.right!=null){
ll.add(node.right);
}
}
}
return root;
}
}
|
这题也是比较简单，依旧层序遍历，然后设一个中间变量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
|
class Solution {
public TreeNode invertTree(TreeNode root) {
LinkedList<TreeNode> ll=new LinkedList<>();
if(root==null){
return root;
}
ll.add(root);
while(!ll.isEmpty()){
int size=ll.size();
for(int i=0;i<size;i++){
TreeNode node=ll.pop();
TreeNode temp=node.left;
node.left=node.right;
node.right=temp;
if(node.left!=null){
ll.add(node.left);
}
if(node.right!=null){
ll.add(node.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
|
class Solution {
public boolean isSymmetric(TreeNode root) {
Boolean result=check(root.left,root.right);
return result;
}
public boolean check(TreeNode left,TreeNode right){
if(left!=null&&right==null){
return false;
}
if(left==null&&right!=null){
return false;
}
if(left==null&&right==null){
return true;
}
if(left.val!=right.val){
return false;
}
//判断外侧是否都相等
boolean resultA=check(left.left,right.right);
//判断内部是否都相等
boolean resultB=check(left.right,right.left);
return resultA&&resultB;
}
}
|
这道题相对来说比较简单，直接搓出来了，查看左右两边的最大值，然后把全局变量赋值为左右两边最大值+1，同时返回当前节点最大深度，当然层序遍历的话更简单
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public int maxDepth(TreeNode root) {
func(root);
return depth;
}
int depth=0;
public int func(TreeNode node){
if(node==null){
return 0;
}
int depthLeft=func(node.left);
int depthRight=func(node.right);
depth=Math.max(depthLeft,depthRight)+1;
return Math.max(depthLeft,depthRight)+1;
}
}
|
这道题层序遍历依旧好解，但是递归就比较麻烦，有点像最近公共祖先的写法，都是在主函数内递归，额外要注意的是，必须得是叶子节点才可以判断层数，如果是链表状的树，最小深度就是最大深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public int minDepth(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 1;
}
int leftDepth=-1;
if(root.left!=null){
leftDepth=minDepth(root.left);
}
int rightDepth=-1;
if(root.right!=null){
rightDepth=minDepth(root.right);
}
return (leftDepth!=-1&&rightDepth!=-1)?Math.min(leftDepth,rightDepth)+1:Math.max(leftDepth,rightDepth)+1;
}
}
|
这道题就是看左右子树的高度差是否大于1，如果大于1就说明不是平衡二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public boolean isBalanced(TreeNode root) {
check(root);
return result;
}
boolean result=true;
public int check(TreeNode node){
if(node==null){
return 0;
}
int leftDepth=check(node.left);
int rightDepth=check(node.right);
if(Math.abs(leftDepth-rightDepth)>1){
result=false;
}
return Math.max(leftDepth,rightDepth)+1;
}
}
|
这道题有点难度，拿回溯算法做了不过有个坑就是得在到叶子节点的时候再去拼接字符串，然后得先把根节点加入path中才行
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
|
class Solution {
List<String> ans=new ArrayList<>();
List<Integer> path=new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
if(root.left==null&&root.right==null){
ans.add(root.val+"");
return ans;
}
if(root==null){
return ans;
}
path.add(root.val);
backTracing(root);
return ans;
}
public void backTracing(TreeNode node){
if(node.left==null&&node.right==null){
StringBuilder sb=new StringBuilder();
for(int i=0;i<path.size()-1;i++){
sb.append(path.get(i)+"->");
}
sb.append(path.get(path.size()-1));
ans.add(sb.toString());
return ;
}
if(node.left!=null){
path.add(node.left.val);
backTracing(node.left);
path.removeLast();
}
if(node.right!=null){
path.add(node.right.val);
backTracing(node.right);
path.removeLast();
}
}
}
|
这题比较简单，就是别看成左节点之和就行，如果node.left==null&&node.right==null就可以加上这个节点的值了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
func(root);
return ans;
}
int ans=0;
public void func(TreeNode node){
if(node==null){
return;
}
if(node.left!=null&&node.left.left==null&&node.left.right==null){
ans+=node.left.val;
}
func(node.left);
func(node.right);
}
}
|
这题可以考虑递归和层序遍历去做
1
2
3
4
5
6
7
8
|
class Solution {
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 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
|
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
TreeNode root1=build(nums,0,nums.length-1);
return root1;
}
public TreeNode build(int[] nums,int left,int right){
if(left<=right){
int[] pivot=findMax(nums,left,right);
TreeNode node=new TreeNode(pivot[0]);
TreeNode leftNode=build(nums,left,pivot[1]-1);
if(leftNode!=null){
node.left=leftNode;
}
TreeNode rightNode=build(nums,pivot[1]+1,right);
if(rightNode!=null){
node.right=rightNode;
}
return node;
}
return null;
}
public int[] findMax(int[] nums,int left,int right){
int max=-1;
int index=-1;
for(int i=left;i<=right;i++){
if(max<nums[i]){
max=Math.max(nums[i],max);
index=i;
}
}
int [] arr=new int[2];
arr[0]=max;
arr[1]=index;
return arr;
}
}
|
这题一开始是是真没思路，逻辑就是先判断节点是否为空，如果都为空就返回，如果都不为空就让两个节点相加，然后分别合并其左右子树
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null) return root2;
if (root2 == null) return root1;
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
|
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null||root.val==val){
return root;
}
if(root.val<val){
return searchBST(root.right,val);
}else{
return searchBST(root.left,val);
}
}
}
|
验证二叉搜索树就利用他中序遍历有序性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public boolean isValidBST(TreeNode root) {
check(root);
for(int i=1;i<list.size();i++){
if(list.get(i)<=list.get(i-1)){
return false;
}
}
return true;
}
List<Integer> list=new ArrayList<>();
public void check(TreeNode node){
if(node==null){
return ;
}
check(node.left);
list.add(node.val);
check(node.right);
}
}
|
直接通过中序遍历去判断最小值是什么，通过全局变量front去存储上一个值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
int minValue=Integer.MAX_VALUE;
int front=Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
check(root);
return minValue;
}
public void check(TreeNode node){
if(node==null){
return;
}
check(node.left);
int abs;
if(front!=Integer.MAX_VALUE){
abs=Math.abs(front-node.val);
front=node.val;
minValue=Math.min(minValue,abs);
}else{
front=node.val;
}
check(node.right);
}
}
|
众数的题其实有点像最小K个数，要对PriorityQueue的API比较熟悉
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
|
class Solution {
public int[] findMode(TreeNode root) {
PriorityQueue<Map.Entry<Integer,Integer>> queue=new PriorityQueue<>((a,b)->b.getValue()-a.getValue());
HashMap<Integer,Integer> map=new HashMap<>();
LinkedList<TreeNode> ll=new LinkedList<>();
ll.add(root);
while(!ll.isEmpty()){
int size=ll.size();
for(int i=0;i<size;i++){
TreeNode node=ll.pop();
if(map.containsKey(node.val)){
map.put(node.val,map.get(node.val)+1);
}else{
map.put(node.val,1);
}
if(node.left!=null){
ll.add(node.left);
}
if(node.right!=null){
ll.add(node.right);
}
}
}
for(Map.Entry entry:map.entrySet()){
queue.offer(entry);
}
int max=-1;
List<Integer> list=new ArrayList<>();
for(Map.Entry<Integer,Integer> entry:queue){
int maxNum=entry.getValue();
if(max==-1){
max=maxNum;
list.add(entry.getKey());
continue;
}
if(maxNum==max){
list.add(entry.getKey());
}
}
int[] ans=new int[list.size()];
for(int i=0;i<list.size();i++){
ans[i]=list.get(i);
}
return ans;
}
}
|
二叉树最大公共祖先，先查询是否是根节点，如果不是的话就遍历左右子树中是否有节点是最大
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null||root==p||root==q){
return root;
}
TreeNode leftNode=lowestCommonAncestor(root.left,p,q);
TreeNode rightNode=lowestCommonAncestor(root.right,p,q);
if(leftNode==null&&rightNode==null){
return null;
}else if(leftNode==null&&rightNode!=null){
return rightNode;
}else if(leftNode!=null&&rightNode==null){
return leftNode;
}else{
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
|
class Solution {
int ans;
int depth=0;
public int findBottomLeftValue(TreeNode root) {
if(root.left==null&&root.right==null){
return root.val;
}
ans=root.val;
check(root,1);
return ans;
}
public void check(TreeNode node,int depthValue){
if(node==null){
return;
}
if(depthValue>depth){
if(node.left!=null){
depth=depthValue;
ans=node.left.val;
}else if(node.right!=null){
depth=depthValue;
ans=node.right.val;
}
}
check(node.left,depthValue+1);
check(node.right,depthValue+1);
}
}
|
这个其实很简单，只是一定要是叶子节点才可以判断是否把target减为0，题目说的是到叶子节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
boolean flag=false;
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null){
return false;
}else if(root.left==null&&root.right==null&&root.val==targetSum){
return true;
}
if(root.left!=null){
check(root.left,targetSum-root.val);
}
if(root.right!=null){
check(root.right,targetSum-root.val);
}
return flag;
}
public void check(TreeNode node,int targetSum){
if(node==null){
return ;
}
if(targetSum-node.val==0&&node.left==null&&node.right==null){
flag=true;
}
check(node.left,targetSum-node.val);
check(node.right,targetSum-node.val);
}
}
|
这道题考虑分治法来做，很像快排，要注意的是，做出节点后才能让后序数组index前移
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
|
class Solution {
HashMap<Integer,Integer> map=new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
index=inorder.length-1;
for(int i=0;i<inorder.length;i++){
map.put(inorder[i],i);
}
return build(0,inorder.length-1,inorder,postorder);
}
int index=0;
public TreeNode build(int left,int right,int[] inorder, int[] postorder){
if (left <= right) {
int pivot = partition(index, inorder, postorder);
TreeNode node = new TreeNode(inorder[pivot]);
index--;
node.right = build(pivot + 1, right, inorder, postorder);
node.left = build(left, pivot - 1, inorder, postorder);
return node;
}
return null;
}
public int partition(int index,int[] inorder, int[] postorder){
return map.get(postorder[index]);
}
}
|
这题也是分治思想，很简单就能做出来，和上面的中序后序构造二叉树不同的在于先获取左边，再获取右边。
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
|
class Solution {
int index;
HashMap<Integer,Integer> map=new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for(int i=0;i<preorder.length;i++){
map.put(inorder[i],i);
}
return build(0,inorder.length-1,preorder,inorder);
}
public TreeNode build(int left,int right,int[] preorder, int[] inorder){
if(left<=right){
int num=preorder[index];
int pivot=partition(num);
index++;
TreeNode node=new TreeNode(num);
TreeNode leftNode=build(left,pivot-1,preorder,inorder);
TreeNode rightNode=build(pivot+1,right,preorder,inorder);
node.left=leftNode;
node.right=rightNode;
return node;
}
return null;
}
public int partition(int num){
return map.get(num);
}
}
|
可以采用撞墙缩减的方法，如果到边界情况判断当前应该缩减哪一块，如果说已经到达上限了就直接break
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int l = 0, r = n - 1, t = 0, b = n - 1;
int num = 1;
int target = n * n;
while (num <= target) {
for (int i = l; i <= r; i++) res[t][i] = num++;
t++;
if (num > target) break;
for (int i = t; i <= b; i++) res[i][r] = num++;
r--;
if (num > target) break;
for (int i = r; i >= l; i--) res[b][i] = num++;
b--;
if (num > target) break;
for (int i = b; i >= t; i--) res[i][l] = num++;
l++;
if (num > target) break;
}
return res;
}
}
|
和上面的差不多，思路是一样的
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
|
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int l=0,r=matrix[0].length-1,t=0,b=matrix.length-1;
int target=(r+1)*(b+1);
int count=0;
List<Integer> list=new ArrayList<>();
while(count<target){
for(int i=l;i<=r;i++){
list.add(matrix[t][i]);
count++;
}
t++;
if(count==target){
break;
}
for(int i=t;i<=b;i++){
list.add(matrix[i][r]);
count++;
}
r--;
if(count==target){
break;
}
for(int i=r;i>=l;i--){
list.add(matrix[b][i]);
count++;
}
b--;
if(count==target){
break;
}
for(int i=b;i>=t;i--){
list.add(matrix[i][l]);
count++;
}
l++;
if(count==target){
break;
}
}
return list;
}
}
|
这道题的最近公共祖先的做法比普通二叉树简单，可以直接看当前节点的大小是否是p和q中间，如果小的话就去右边，大的话就去左边
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int val=root.val;
while(true){
if(root.val>=p.val&&root.val<=q.val||root.val<=p.val&&root.val>=q.val){
return root;
}else if(root.val<p.val){
root=root.right;
}else if(root.val>q.val){
root=root.left;
}
}
}
}
|
就左右查找，找到空的位置把数据插进去就行
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
|
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null){
return new TreeNode(val);
}
boolean flag=true;
TreeNode ans=root;
while(flag){
if(root.val>val){
if(root.left!=null){
root=root.left;
}else{
root.left=new TreeNode(val);
return ans;
}
}else{
if(root.right!=null){
root=root.right;
}else{
root.right=new TreeNode(val);
return ans;
}
}
}
return ans;
}
}
|
先考虑删除方式，如果左节点为空，或者右节点为空，直接拿另一个节点替代当前节点即可，如果左右都不为空就要获取右节点，然后依次向左查找空节点，然后把原来的左节点挂在这个位置，然后根节点变为右节点，返回即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null){
return root;
}else if(root.val==key){
if(root.left==null){
return root.right;
}else if(root.right==null){
return root.left;
}else{
TreeNode cur=root.right;
while(cur.left!=null){
cur=cur.left;
}
cur.left=root.left;
root=root.right;
return root;
}
}
if(key<root.val) root.left = deleteNode(root.left,key);
if(key>root.val) root.right = deleteNode(root.right,key);
return root;
}
}
|
如果当前节点是不符合规则的节点，就要尝试删除，在删除前先去尝试删除其左右两边不符合规定的节点，比如现在的情况是val<low，左边节点一定比val还小，直接为null即可，右边的需要进行递归修剪，然后删除当前节点，如果当前节点符合规定，就去递归修剪左右节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root==null){
return null;
}
if(root.val<low||root.val>high){
int val=root.val;
if(val<low){
root.left= null;
root.right=trimBST(root.right,low,high);
}else{
root.right=null;
root.left=trimBST(root.left,low,high);
}
if(root.left==null){
return root.right;
}else if(root.right==null){
return root.left;
}
TreeNode cur=root.right;
while(cur.left!=null){
cur=cur.left;
}
cur.left=root.left;
root=root.right;
return root;
}
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
|
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums,0,nums.length-1);
}
public TreeNode build(int[] nums,int left,int right){
if(left<=right){
int pivot=(right-left)/2+left;
TreeNode node=new TreeNode(nums[pivot]);
node.left=build(nums,left,pivot-1);
node.right=build(nums,pivot+1,right);
return node;
}
return null;
}
}
|
这道题得考虑右中左的遍历顺序，然后对节点进行累加，可以考虑通过全局变量实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public TreeNode convertBST(TreeNode root) {
TreeNode ans=root;
count(root);
return ans;
}
int sum=0;
public void count(TreeNode node){
if(node==null){
return;
}
count(node.right);
int val=node.val;
node.val+=sum;
sum+=val;
count(node.left);
return;
}
}
|
如果想返回答案，一定要ans.add(new ArrayList<>(path));这样才能加入真正的值
这道题中backTracking()里的第一个参数要是当前index的i+1，这样才能让后面添加的值比现在的数组顺序靠后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
List<List<Integer>> ans=new ArrayList<>();
List<Integer> path=new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backTracking(1,k,n);
return ans;
}
public void backTracking(int index,int k,int n){
if(path.size()==k){
ans.add(new ArrayList<>(path));
return;
}
for(int i=index;i<=n;i++){
path.add(i);
backTracking(i+1,k,n);
path.removeLast();
}
}
}
|
这道题就和上一题差不多，就是要维护一个全局变量，来判断当前值是啥
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
List<Integer> path=new ArrayList<>();
int sum=0;
List<List<Integer>> ans=new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTracking(k,n,1);
return ans;
}
public void backTracking(int k,int n,int index){
if(path.size()==k){
if(sum==n){
ans.add(new ArrayList<>(path));
}
return;
}
for(int i=index;i<=9;i++){
path.add(i);
sum+=i;
backTracking(k,n,i+1);
sum-=i;
path.removeLast();
}
}
}
|
String[] 的值不会赋，一定要记住API，是String[] arr={“abc”," “,…};
还有StringBuilder的删除某一个字符的方法是sb.deleteCharAt(sb.length()-1);
这道题的index是电话号码的数字index，先遍历到树的最底下，然后依次回溯加入新的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public List<String> letterCombinations(String digits) {
String[] arr={" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
backTracking(arr,digits,0);
return ans;
}
StringBuilder sb=new StringBuilder();
List<String> ans=new ArrayList<>();
public void backTracking(String[] arr,String digits,int index){
if(index==digits.length()){
ans.add(sb.toString());
return;
}
char digit = digits.charAt(index);
String letters = arr[digit - '0'];
for (int i = 0; i < letters.length(); i++) {
sb.append(letters.charAt(i));
backTracking(arr,digits, index + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
}
|
这道题求组合的时候是可以用当前元素后面的所有元素，所以index为i，也可以起到去重的效果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
List<List<Integer>> ans=new ArrayList<>();
List<Integer> path=new ArrayList<>();
int sum=0;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int[] used=new int[candidates.length];
backTracking(candidates,used,target,0);
return ans;
}
public void backTracking(int[] candidates,int[] used,int target,int index){
if(sum>=target){
if(sum==target){
ans.add(new ArrayList<>(path));
}
return;
}
for(int i=index;i<used.length;i++){
sum+=candidates[i];
path.add(candidates[i]);
backTracking(candidates,used,target,i);
sum-=candidates[i];
path.removeLast();
}
}
}
|