算法强基计划
快速排序
快速排序就是选择一个作为基准元素，左边的元素放比基准元素小的，右边放比基准元素大的，然后分别对左右两个区间进行递归。
我的这个方法是以最左边的元素为基准，遍历区间，然后找到比当前元素大的元素就交换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
53
|
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;
}
}
|