3. 無重復字符的最長子串

核心代碼模式

class Solution {public int lengthOfLongestSubstring(String s) {int len=s.length();int []num=new int[300];int ans=0;for(int i=0,j=0;i<len;i++){num[s.charAt(i)]++;while(num[s.charAt(i)]>1){num[s.charAt(j)]--;j++;}ans=Math.max(ans,i-j+1);}return ans;}
}

手寫輸入輸出模式?

import java.util.*;public class Javaacm
{public static void main(String []args){
//輸入：abadsadasScanner scan=new Scanner(System.in);String s=scan.next();int len=s.length();int ans=0;int num[]=new int[300];for(int i=0,j=0;i<len;i++){num[s.charAt(i)]++;while(num[s.charAt(i)]>1){num[s.charAt(j)]--;j++;}ans=Math.max(ans,i-j+1);}System.out.println(ans);}
}

146. LRU 緩存

核心代碼模式

class LRUCache {int capacity;   Map<Integer,Node> m=new HashMap<>();Node dummy=new Node(0,0);class Node{int key,value;Node pre ,ne;Node(int k,int v){key=k;value=v;}}public LRUCache(int capacity) {this.capacity=capacity;dummy.pre=dummy;dummy.ne=dummy;}public int get(int key) {Node cur=getNode(key);return cur==null?-1:cur.value;}Node getNode(int key){if(!m.containsKey(key))return null;Node cur=m.get(key);remove(cur);pushFront(cur);return cur;}void remove(Node node){node.pre.ne=node.ne;node.ne.pre=node.pre;}void pushFront(Node node){node.ne=dummy.ne;node.pre=dummy;node.pre.ne=node;node.ne.pre=node;}//邏輯最復雜public void put(int key, int value) {Node cur=getNode(key);if(cur!=null){cur.value=value;return ;}    cur=new Node(key,value);m.put(key,cur);pushFront(cur);if(capacity<m.size()){m.remove(dummy.pre.key);remove(dummy.pre);}}
}

手寫輸入輸出模式?

import java.util.*;
class lrucache
{//雙向鏈表+HashMapprivate final int capacity;//容量private final Node dummy=new Node(0,0);//雙向鏈表頭結點Map<Integer,Node> m=new HashMap<>();//哈希表public static class Node{ //node類，構造節點int key ,value;Node pre,ne;Node(int k,int v){key=k;value=v;}}public lrucache(int capacity)  //初始化，設定容量{this.capacity=capacity;dummy.pre=dummy;dummy.ne=dummy;}//get，獲取節點的value，沒有則為-1public int get(int key){Node node=getNode(key);   //獲取節點并更新到最近使用return node!=null?node.value:-1;}//獲取節點病更新到最近使用private Node getNode(int key){if(!m.containsKey(key))return null;  //沒有則返回nullNode node=m.get(key);     //獲取該節點linkRemove(node);        //雙向鏈表中刪除該結點linkPushFront(node);      //插入到頭部return node;}void linkRemove(Node x){//刪除某節點x.ne.pre=x.pre;x.pre.ne=x.ne;}
void linkPushFront(Node x)
{//從頭部插入節點x.pre=dummy;x.ne=dummy.ne;x.ne.pre=x;x.pre.ne=x;
}public void put(int key,int value)
{  //先獲取節點，順便更新到最近使用Node node=getNode(key);if(node!=null){node.value=value;   return ;       //存在則更新值并返回}node=new Node(key,value);m.put(key,node);      //哈希表插入linkPushFront(node);    //雙向鏈表插入if(m.size()>capacity){    //容量超過上限m.remove(dummy.pre.key);    //哈希表刪除最久使用linkRemove(dummy.pre);          //雙向鏈表移除該節點}
}
}
public class Javaacm
{public static void main(String []args){lrucache lru=new lrucache(2);lru.put(1,1);lru.put(2,2);System.out.println(lru.get(2));  //2lru.put(3,3); System.out.println(lru.get(1));  //-1System.out.println(lru.get(3));  //3}
}

206. 反轉鏈表

核心代碼模式

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode pre=null,cur=head;//雙指針while(cur!=null){ListNode ne=cur.next;//留存剩余節點的頭部cur.next=pre;   //雙指針更新pre=cur;cur=ne;}return pre;//最后cur為null,pre為新的頭節點}
}

手寫輸入輸出模式?

import java.util.*;
class ListNode
{int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next;}
}
public class Javaacm
{public static void main(String []args){
//輸入3,2,1,4,5Scanner scanner=new Scanner(System.in);String inner[]=scanner.next().split(",");   //輸入ListNode  head=new ListNode(Integer.valueOf(inner[0])); //創建第一個節點，這里默認不會傳空ListNode pre=null,cur=head;for(int i=1;i<inner.length;i++){    //循環構造鏈表ListNode curNode =new ListNode(Integer.valueOf(inner[i]));cur.next=curNode;cur=curNode;}//開始反轉鏈表cur=head;while(cur!=null){ListNode ne=cur.next;cur.next=pre;pre=cur;cur=ne;}//輸出即可while(pre!=null){System.out.print(pre.val+"->");pre=pre.next;}System.out.print("null");//5->4->3->2->1->null}
}

215. 數組中的第K個最大元素

PriorityQueue寫法

核心代碼模式

class Solution {public int findKthLargest(int[] nums, int k) {Queue<Integer> q=new PriorityQueue<>();for(int i=0;i<nums.length;i++){q.add(nums[i]);if(q.size()>k){q.poll();}}return q.poll();}
}

手寫輸入輸出

import java.util.*;public class Javaacm
{public static void main(String []args){
//輸入：
//[3,2,1,5,6,4]
//3Scanner scanner=new Scanner(System.in);String s=scanner.next();int k=scanner.nextInt();String str[]=s.substring(1,s.length()-1).split(",");Queue<Integer> q=new PriorityQueue<>();for(int i=0;i<str.length;i++){int cur=Integer.valueOf(str[i]);q.add(cur);if(q.size()>k){q.poll();}}System.out.print(q.poll());}
}

快速選擇算法

核心代碼模式

class Solution {int nums[];public int findKthLargest(int[] num, int k) {nums=num;int n=nums.length;return f(0,n-1,n-k);}void swap(int i,int j){int t=nums[i];nums[i]=nums[j];nums[j]=t;}int f(int l,int r,int k){if(l>=r)return nums[k];int x=nums[l],i=l-1,j=r+1;while(i<j){do i++;while(nums[i]<x);do j--;while(nums[j]>x);if(i<j)swap(i,j);}if(k<=j)return f(l,j,k);return f(j+1,r,k);}
}

手寫輸入輸出

import java.util.*;public class Javaacm
{static int nums[];public static void main(String []args){
//輸入：
//[3,2,1,5,6,4]
//3Scanner scanner=new Scanner(System.in);String s=scanner.next();int k=scanner.nextInt();String str[]=s.substring(1,s.length()-1).split(",");nums=new int[str.length];for(int i=0;i<str.length;i++)nums[i]=Integer.valueOf(str[i]);System.out.print(quickselect(0,nums.length-1,nums.length-k));}static int quickselect(int l,int r,int k){if(l>=r)return nums[k];int x=nums[l],i=l-1,j=r+1;while(i<j){do i++;while(nums[i]<x);do j--;while(nums[j]>x);if(i<j)swap(i,j);}if(k<=j)return quickselect(l,j,k);return quickselect(j+1,r,k);}static void swap(int a,int b){int t=nums[a];nums[a]=nums[b];nums[b]=t;}
}

25. K 個一組翻轉鏈表

核心代碼模式

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode pre=null,cur=head,hh=new ListNode(0,head);ListNode before=hh;int len=0;while(cur!=null){len++;cur=cur.next;}cur=head;for(int i=len;i>=k;i-=k){for(int j=0;j<k;j++){ListNode ne=cur.next;cur.next=pre;pre=cur;cur=ne;}ListNode ne=before.next;before.next=pre;before=ne;ne.next=cur;}return hh.next;}
}

手寫輸入輸出

import java.util.*;class ListNode
{int val;ListNode next;ListNode(){}ListNode(String v){val=Integer.valueOf(v);}ListNode(int v,ListNode ne){val=v;next=ne;}
}
public class Javaacm
{
//輸入格式
// [3,2,1,5,6,4]
// 3public static void main(String []args){Scanner scanner=new Scanner(System.in);String s=scanner.next();int k=scanner.nextInt();String str[]=s.substring(1,s.length()-1).split(",");int len=str.length;ListNode head=new ListNode(str[0]);ListNode pre=head;for(int i=1;i<len;i++){ListNode cur=new ListNode(str[i]);pre.next=cur;pre=cur;}ListNode cur=head;ListNode hh=new ListNode(0,head);ListNode before=hh;for(int l=len;l>=k;l-=k){for(int i=0;i<k;i++){ListNode ne=cur.next;cur.next=pre;pre=cur;cur=ne;}ListNode ne=before.next;  before.next=pre;  //改頭部before=ne;        //換指針ne.next=cur;      //銜尾部}ListNode p=hh.next;for(int i=0;i<len;i++){System.out.print(p.val+"->");p=p.next;}System.out.print("null");}
}