[[441765]]

大家好，我是bigsai，好久不見，天天想念。

最近不少小伙伴跟我交流刷題腫么刷，我給的建議就是先劍指offer和力扣hot100，在這些題中還有些重要程度和出現(xiàn)頻率是非常非常高的，今天給大家分享當(dāng)今出現(xiàn)頻率最高的10道算法題，最近鋪天蓋地的出現(xiàn)，學(xué)到就是賺到。

本篇主要內(nèi)容為：

0X01翻轉(zhuǎn)鏈表

力扣206和劍指offer24原題，題意為：

給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

分析：

翻轉(zhuǎn)鏈表，本意是不創(chuàng)建新的鏈表節(jié)點(diǎn)然后在原鏈表上實(shí)現(xiàn)翻轉(zhuǎn)，但是這個(gè)圖有點(diǎn)會(huì)誤導(dǎo)人的思維，其實(shí)更好的理解你可以看下面這幅圖：

具體實(shí)現(xiàn)上兩個(gè)思路，非遞歸和遞歸的實(shí)現(xiàn)方式，非遞歸的實(shí)現(xiàn)方式比較簡(jiǎn)單，利用一個(gè)pre節(jié)點(diǎn)記錄前驅(qū)節(jié)點(diǎn)，向下枚舉的時(shí)候改變指針指向就可以，實(shí)現(xiàn)代碼為：

class Solution { 
    public ListNode reverseList(ListNode head) { 
       if(head==null||head.next==null)//如果節(jié)點(diǎn)為NULL或者單個(gè)節(jié)點(diǎn)直接返回 
            return head; 
        ListNode pre=head;//前驅(qū)節(jié)點(diǎn) 
        ListNode cur=head.next;//當(dāng)前節(jié)點(diǎn)用來枚舉 
        while (cur!=null) 
        { 
            ListNode next=cur.next; 
            //改變指向 
            cur.next=pre; 
            pre=cur; 
            cur=next; 
        } 
        head.next=null;//將原先的head節(jié)點(diǎn)next置null防止最后成環(huán) 
        return pre; 
    } 
} 

而遞歸的方式比較巧妙，借助遞歸歸來的過程巧妙改變指針指向和返回值傳遞，代碼雖然精簡(jiǎn)但是理解起來有一定難度的，這里用一張圖幫助大家理解：

具體代碼為：

class Solution { 
    public ListNode reverseList(ListNode head) { 
        if(head==null||head.next==null)//如果最后一個(gè)節(jié)點(diǎn)不操作 
            return  head; 
        ListNode node =reverseList(head.next);//先遞歸 到最底層 然后返回 
        head.next.next=head;//后面一個(gè)節(jié)點(diǎn)指向自己 
        head.next=null;//自己本來指向的next置為null 
        return node;//返回最后一個(gè)節(jié)點(diǎn)(一直被遞歸傳遞) 
    } 
} 

0X02設(shè)計(jì)LRU

對(duì)應(yīng)力扣146LRU緩存機(jī)制,題目要求為：

運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU 緩存機(jī)制 。實(shí)現(xiàn) LRUCache 類：

LRUCache(int capacity) 以正整數(shù)作為容量 capacity 初始化 LRU 緩存

int get(int key) 如果關(guān)鍵字 key 存在于緩存中，則返回關(guān)鍵字的值，否則返回 -1 。

void put(int key, int value) 如果關(guān)鍵字已經(jīng)存在，則變更其數(shù)據(jù)值;如果關(guān)鍵字不存在，則插入該組「關(guān)鍵字-值」。當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最久未使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

進(jìn)階：在 O(1) 時(shí)間復(fù)雜度內(nèi)完成這兩種操作

詳細(xì)分析：一次倒在LRU上的經(jīng)歷

LRU的核心就是借助哈希+雙鏈表，哈希用于查詢，雙鏈表實(shí)現(xiàn)刪除只知道當(dāng)前節(jié)點(diǎn)也能O(1)的復(fù)雜度刪除，不過雙鏈表需要考慮的頭尾指針特殊情況。

具體實(shí)現(xiàn)的代碼為：

class LRUCache { 
    class Node { 
        int key; 
        int value; 
        Node pre; 
        Node next; 
        public Node() { 
        } 
        public Node( int key,int value) { 
            this.key = key; 
            this.value=value; 
        } 
    } 
    class DoubleList{ 
        private Node head;// 頭節(jié)點(diǎn) 
        private Node tail;// 尾節(jié)點(diǎn) 
        private int length; 
        public DoubleList() { 
            head = new Node(-1,-1); 
            tail = head; 
            length = 0; 
        } 
        void add(Node teamNode)// 默認(rèn)尾節(jié)點(diǎn)插入 
        { 
            tail.next = teamNode; 
            teamNode.pre=tail; 
            tail = teamNode; 
            length++; 
        } 
        void deleteFirst(){ 
            if(head.next==null) 
                return; 
            if(head.next==tail)//如果刪除的那個(gè)剛好是tail  注意啦 tail指針前面移動(dòng) 
                tail=head; 
            head.next=head.next.next; 
 
            if(head.next!=null) 
                head.next.pre=head; 
            length--; 
        } 
        void deleteNode(Node team){ 
 
            team.pre.next=team.next; 
            if(team.next!=null) 
                team.next.pre=team.pre; 
            if(team==tail) 
                tail=tail.pre; 
           team.pre=null; 
           team.next=null; 
            length--; 
        } 
    } 
    Map<Integer,Node> map=new HashMap<>(); 
    DoubleList doubleList;//存儲(chǔ)順序 
    int maxSize; 
    LinkedList<Integer>list2=new LinkedList<>(); 
 
    public   LRUCache(int capacity) { 
        doubleList=new DoubleList(); 
        maxSize=capacity; 
    } 
    public int get(int key) { 
        int val; 
        if(!map.containsKey(key)) 
            return  -1; 
        val=map.get(key).value; 
        Node team=map.get(key); 
        doubleList.deleteNode(team); 
        doubleList.add(team); 
        return  val; 
    } 
 
    public void put(int key, int value) { 
        if(map.containsKey(key)){// 已經(jīng)有這個(gè)key 不考慮長(zhǎng)短直接刪除然后更新 
           Node deleteNode=map.get(key); 
            doubleList.deleteNode(deleteNode); 
        } 
        else if(doubleList.length==maxSize){//不包含并且長(zhǎng)度小于 
            Node first=doubleList.head.next; 
            map.remove(first.key); 
            doubleList.deleteFirst(); 
        } 
       Node node=new Node(key,value); 
        doubleList.add(node); 
        map.put(key,node); 
 
    } 
} 

0X03環(huán)形鏈表

對(duì)應(yīng)力扣141和力扣142，力扣141環(huán)形鏈表要求為：

給定一個(gè)鏈表，判斷鏈表中是否有環(huán)，用O(1)內(nèi)存解決。

詳細(xì)分析：環(huán)形鏈表找入口，真的太妙了

這個(gè)問題利用快慢雙指針比較高效，快指針fast每次走2步，slow每次走1步，慢指針走n步到尾時(shí)候快指針走了2n步，而環(huán)的大小一定小于等于n所以一定會(huì)相遇，如果相遇那么說明有環(huán)，如果不相遇fast先為null說明無環(huán)。

具體代碼為：

public class Solution { 
    public boolean hasCycle(ListNode head) { 
        ListNode fast=head; 
        ListNode slow=fast; 
        while (fast!=null&&fast.next!=null) { 
            slow=slow.next; 
            fast=fast.next.next; 
            if(fast==slow) 
                return true; 
        } 
        return false;     
    } 
} 

力扣142是在力扣141拓展，如有有環(huán)，返回入環(huán)的那個(gè)節(jié)點(diǎn)，就想下圖環(huán)形鏈表返回節(jié)點(diǎn)2。

這個(gè)問題是需要數(shù)學(xué)轉(zhuǎn)換的，具體的分析可以看上面的詳細(xì)分析，這里面提一下大題的步驟。

如果找到第一個(gè)交匯點(diǎn)，其中一個(gè)停止，另一個(gè)繼續(xù)走，下一次交匯時(shí)候剛好走一圈，可以算出循環(huán)部分長(zhǎng)度為y。

所以我們知道的東西有：交匯時(shí)候fast走2x步，slow走x步，環(huán)長(zhǎng)為y。并且快指針和慢指針交匯時(shí)候，多走的步數(shù)剛好是換長(zhǎng)y的整數(shù)倍(它兩此刻在同一個(gè)位置，快指針剛好多繞整數(shù)倍圈數(shù)才能在同一個(gè)位置相聚)，可以得到2x=x+ny(x=ny)。其中所以說慢指針走的x和快指針多走的x是圈長(zhǎng)y的整數(shù)倍。

也就是說，從開頭走到這個(gè)點(diǎn)共計(jì)x步，從這個(gè)點(diǎn)走x步也就是繞了幾圈也回到這個(gè)點(diǎn)。如果說slow從起點(diǎn)出發(fā)，fast從這個(gè)點(diǎn)出發(fā)(每次走一步，相當(dāng)于之前兩步抵消slow走的路程)，那么走x步還會(huì)到達(dá)這個(gè)點(diǎn)，但是這兩個(gè)指針這次都是每次走一步，所以一旦slow到達(dá)循環(huán)圈內(nèi)，兩個(gè)指針就開始匯合了。

實(shí)現(xiàn)代碼為：

public class Solution { 
    public ListNode detectCycle(ListNode head) { 
        boolean isloop=false; 
        ListNode fast=new ListNode(0);//頭指針 
        ListNode slow=fast; 
        fast.next=head; 
        if(fast.next==null||fast.next.next==null) 
            return null; 
        while (fast!=null&&fast.next!=null) { 
            fast=fast.next.next; 
            slow=slow.next; 
            if(fast==slow) 
            { 
                isloop=true; 
                break; 
            } 
        } 
        if(!isloop)//如果沒有環(huán)返回 
            return null; 
        ListNode team=new ListNode(-1);//頭指針 下一個(gè)才是head 
        team.next=head; 
        while (team!=fast) {//slow 和fast 分別從起點(diǎn)和當(dāng)前點(diǎn)出發(fā) 
            team=team.next; 
            fast=fast.next; 
        } 
        return team; 
    } 
} 

0X04兩個(gè)棧實(shí)現(xiàn)隊(duì)列對(duì)

應(yīng)劍指offer09，題意為：

用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列。隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù) appendTail 和 deleteHead ，分別完成在隊(duì)列尾部插入整數(shù)和在隊(duì)列頭部刪除整數(shù)的功能。(若隊(duì)列中沒有元素，deleteHead 操作返回 -1 )

分析：

解決這個(gè)問題，要知道棧是什么，隊(duì)列是什么，兩種常見數(shù)據(jù)結(jié)構(gòu)格式很簡(jiǎn)單，棧的特點(diǎn)就是：后進(jìn)先出，隊(duì)列的特點(diǎn)就是：先進(jìn)先出，?？梢韵胂蟪梢欢褧?，越在上面的取的越早，上面來上面出(比喻一下);隊(duì)列就是想象成排隊(duì)買東西，只能后面進(jìn)前面出，所以兩者數(shù)據(jù)結(jié)構(gòu)還是有區(qū)別的，雖然都是單個(gè)入口進(jìn)出，但是棧進(jìn)出口相同，而隊(duì)列不同。

上面描述的是一個(gè)普通棧和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，這里面讓我們用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列的操作，這里比較容易想的方案就是其中一個(gè)棧stack1用作數(shù)據(jù)存儲(chǔ)，插入尾時(shí)候直接插入stack1，而刪除頭的時(shí)候?qū)?shù)據(jù)先加入到另一個(gè)棧stack2中，返回并刪除棧頂元素，將stack2順序加入stack1中實(shí)現(xiàn)一個(gè)復(fù)原，但是這樣操作插入時(shí)間復(fù)雜度為O(1),刪除時(shí)間復(fù)雜度為O(n)比較高。

實(shí)現(xiàn)方式也給大家看下：

class CQueue { 
 
    Stack<Integer>stack1=new Stack<>(); 
    Stack<Integer>stack2=new Stack<>(); 
    public CQueue() { 
    } 
    public void appendTail(int value) { 
       stack1.push(value); 
    } 
    public int deleteHead() { 
        if(stack1.isEmpty()) 
            return -1; 
 
        while (!stack1.isEmpty()) 
        { 
            stack2.push(stack1.pop()); 
        } 
       int value= stack2.pop(); 
        while (!stack2.isEmpty()) 
        { 
            stack1.push(stack2.pop()); 
        } 
        return  value; 
    } 
} 

這樣的時(shí)間復(fù)雜度是不被喜歡的，因?yàn)閯h除太雞兒耗時(shí)了，每次都要折騰一番，有沒有什么好的方法能夠讓刪除也方便一點(diǎn)呢?

有啊，stack1可以順序保證順序插入，stack1數(shù)據(jù)放到stack2中可以保證順序刪除，所以用stack1作插入，stack2作刪除，因?yàn)轭}目也沒要求數(shù)據(jù)必須放到一個(gè)容器中，所以就這樣組合使用，完美perfect!

具體實(shí)現(xiàn)的時(shí)候，插入直接插入到stack1中，如果需要?jiǎng)h除從stack2中棧頂刪除，如果stack2棧為空那么將stack1中數(shù)據(jù)全部添加進(jìn)來(這樣又能保證stack2中所有數(shù)據(jù)是可以順序刪除的了)，下面列舉幾個(gè)刪除的例子

其實(shí)就是將數(shù)據(jù)分成兩個(gè)部分，一部分用來插入，一部分用來刪除，刪除的那個(gè)棧stack2空了添加所有stack1中的數(shù)據(jù)繼續(xù)操作。這個(gè)操作插入刪除的時(shí)間復(fù)雜度是O(1),具體實(shí)現(xiàn)的代碼為：

class CQueue { 
    Deque<Integer> stack1; 
    Deque<Integer> stack2; 
 
    public CQueue() { 
        stack1 = new LinkedList<Integer>(); 
        stack2 = new LinkedList<Integer>(); 
    } 
 
    public void appendTail(int value) { 
        stack1.push(value); 
    } 
 
    public int deleteHead() { 
        // 如果第二個(gè)棧為空 將stack1數(shù)據(jù)加入stack2 
        if (stack2.isEmpty()) { 
            while (!stack1.isEmpty()) { 
                stack2.push(stack1.pop()); 
            } 
        } //如果stack2依然為空 說明沒有數(shù)據(jù) 
        if (stack2.isEmpty()) { 
            return -1; 
        } else {//否則刪除 
            int deleteItem = stack2.pop(); 
            return deleteItem; 
        } 
    } 
} 

0X05二叉樹層序(鋸齒)遍歷

二叉樹的遍歷，對(duì)應(yīng)力扣102，107，103.

詳細(xì)分析：一次面試，被二叉樹層序遍歷打爆了

如果普通二叉樹層序遍歷，也不是什么困難的問題，但是它會(huì)有個(gè)分層返回結(jié)果的操作，就需要你詳細(xì)考慮了。

很多人會(huì)用兩個(gè)容器(隊(duì)列)進(jìn)行分層的操作，這里其實(shí)可以直接使用一個(gè)隊(duì)列，我們首先記錄枚舉前隊(duì)列大小len，然后根據(jù)這個(gè)大小len去枚舉遍歷就可以得到完整的該層數(shù)據(jù)了。

還有一個(gè)難點(diǎn)就是二叉樹的鋸齒層序(也叫之字形打印)，第一趟是從左往右，第二趟是從右往左，只需要記錄一個(gè)奇偶層數(shù)進(jìn)行對(duì)應(yīng)的操作就可以了。

這里就拿力扣103二叉樹的鋸齒形層序遍歷作為題板給大家分享一下代碼：

public List<List<Integer>> levelOrder(TreeNode root) { 
  List<List<Integer>> value=new ArrayList<>();//存儲(chǔ)到的最終結(jié)果 
  if(root==null) 
    return value; 
  int index=0;//判斷 
  Queue<TreeNode>queue=new ArrayDeque<>(); 
  queue.add(root); 
  while (!queue.isEmpty()){ 
    List<Integer>va=new ArrayList<>();//臨時(shí) 用于存儲(chǔ)到value中 
    int len=queue.size();//當(dāng)前層節(jié)點(diǎn)的數(shù)量 
    for(int i=0;i<len;i++){ 
      TreeNode node=queue.poll(); 
      if(index%2==0)//根據(jù)奇偶 選擇添加策略 
        va.add(node.val); 
      else 
        va.add(0,node.val); 
      if(node.left!=null) 
        queue.add(node.left); 
      if(node.right!=null) 
        queue.add(node.right); 
    } 
    value.add(va); 
    index++; 
  } 
  return value; 
} 

0X06 二叉樹中后序遍歷(非遞歸)

二叉樹的非遞歸遍歷也是考察的重點(diǎn)，對(duì)于中序后序遍歷遞歸實(shí)現(xiàn)很簡(jiǎn)單，非遞歸實(shí)現(xiàn)起來還是要點(diǎn)技巧的哦。

詳細(xì)分析：二叉樹的各種遍歷(遞歸、非遞歸)

對(duì)于二叉樹的中序遍歷，其實(shí)就是正常情況第二次訪問該節(jié)點(diǎn)的時(shí)候才拋出輸出(第一次數(shù)前序)，這樣我們枚舉每個(gè)節(jié)點(diǎn)第一次不能刪除，需要先將它存到棧中，當(dāng)左子節(jié)點(diǎn)處理完成的時(shí)候在拋出訪問該節(jié)點(diǎn)。

核心也就兩步，葉子節(jié)點(diǎn)左右都為null，也可滿足下列條件：

枚舉當(dāng)前節(jié)點(diǎn)(不存儲(chǔ)輸出)并用棧存儲(chǔ)，節(jié)點(diǎn)指向左節(jié)點(diǎn)，直到左孩子為null。

拋出棧頂訪問。如果有右節(jié)點(diǎn)，訪問其右節(jié)點(diǎn)重復(fù)步驟1，如有沒右節(jié)點(diǎn)，繼續(xù)重復(fù)步驟2拋出。

實(shí)現(xiàn)代碼為：

class Solution { 
   public List<Integer> inorderTraversal(TreeNode root) { 
    List<Integer>value=new ArrayList<Integer>(); 
    Stack<TreeNode> q1 = new Stack();     
    while(!q1.isEmpty()||root!=null) 
    { 
        while (root!=null) { 
            q1.push(root);                 
            root=root.left; 
        } 
        root=q1.pop();//拋出 
        value.add(root.val); 
        root=root.right;//準(zhǔn)備訪問其右節(jié)點(diǎn) 
 
    } 
    return value; 
  } 
} 

而后序遍歷按照遞歸的思路其實(shí)一般是第三次訪問該節(jié)點(diǎn)是從右子節(jié)點(diǎn)回來才拋出輸出，這個(gè)實(shí)現(xiàn)起來確實(shí)有難度。但是具體的實(shí)現(xiàn)，我們使用一個(gè)pre節(jié)點(diǎn)記錄上一次被拋出訪問的點(diǎn)，如果當(dāng)前被拋出的右孩子是pre或者當(dāng)前節(jié)點(diǎn)右為null，那么就將這個(gè)點(diǎn)拋出，否則說明它的右側(cè)還未被訪問需要將它"回爐重造"，后面再用!如果不理解可以看前面的詳細(xì)介紹。

具體實(shí)現(xiàn)的代碼為：

class Solution { 
    public List<Integer> postorderTraversal(TreeNode root) { 
        TreeNode temp=root;//枚舉的臨時(shí)節(jié)點(diǎn) 
        List<Integer>value=new ArrayList<>(); 
        TreeNode pre=null;//前置節(jié)點(diǎn) 
        Stack<TreeNode>stack=new Stack<>(); 
 
        while (!stack.isEmpty()||temp!=null){ 
 
            while(temp!=null){ 
                stack.push(temp); 
                temp=temp.left; 
            } 
            temp=stack.pop(); 
            if(temp.right==pre||temp.right==null)//需要彈出 
            { 
                value.add(temp.val); 
                pre=temp; 
                temp=null;//需要重新從棧中拋出 
            }else{ 
                stack.push(temp); 
                temp=temp.right; 
            } 
 
        } 
        return value; 
    } 
} 

當(dāng)然，后序遍歷也有用前序(根右左)的前序遍歷結(jié)果最后翻轉(zhuǎn)一下的，但面試官更想考察的還是上面提到的方法。

0X07 跳臺(tái)階(斐波那契、爬樓梯)

爬樓梯、跳臺(tái)階是一個(gè)經(jīng)典問題，對(duì)應(yīng)劍指offer10和力扣70題，題目的要求為：

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢?注意：給定 n 是一個(gè)正整數(shù)。

分析：

這個(gè)問題入門級(jí)別dp，分析當(dāng)前第k階的結(jié)果，每個(gè)人可以爬1個(gè)或者2個(gè)臺(tái)階，那么說明它可能是由k-1或者k-2來的，所以就是兩個(gè)子情況的疊加(需要特殊考慮一下初始情況)，這個(gè)思路有人會(huì)想到遞歸，沒錯(cuò)用遞歸確實(shí)可以解決但是用遞歸效率較低(因?yàn)檫@個(gè)是個(gè)發(fā)散的遞歸一個(gè)拆成兩個(gè))，使用記憶化搜索會(huì)稍微好一些。

但是dp是比較好的方法，核心狀態(tài)轉(zhuǎn)移方程為：dp[i]=dp[i-1]+dp[i-2]，有些空間優(yōu)化的那就更好了，因?yàn)橹挥玫角皟蓚€(gè)值，所以完全可以用三個(gè)值重復(fù)使用節(jié)省空間。

class Solution { 
    public int climbStairs(int n) { 
        if(n<3)return n; 
         int dp[]=new int[n+1]; 
         dp[1]=1; 
         dp[2]=2; 
         for(int i=3;i<n+1;i++) 
         { 
             dp[i]=dp[i-1]+dp[i-2]; 
         } 
         return dp[n]; 
    } 
 
  public int climbStairs(int n) { 
        int a = 0, b = 0, c = 1; 
        for (int i = 1; i <= n; i++) { 
            a = b;  
            b = c;  
            c = a + b; 
        } 
        return c; 
    } 
} 

當(dāng)然，有的數(shù)據(jù)很大求余的跳臺(tái)階，可以用矩陣快速冪解決，但是這里就不介紹啦，有興趣可以詳細(xì)看看。

0X08 TOPK問題

TOPK問題真的非常經(jīng)典，通常問的有最小的K個(gè)數(shù)，尋找第K大都是TOPK這種問題，這里就用力扣215尋找數(shù)組第K大元素作為板子。

詳細(xì)分析：一文拿捏TOPK

TOPK的問題解決思路有很多，如果優(yōu)化的冒泡或者簡(jiǎn)單選擇排序，時(shí)間復(fù)雜度為O(nk),使用優(yōu)化的堆排序?yàn)镺(n+klogn)，不過掌握快排的變形就可以應(yīng)付大體上的所有問題了(面試官要是讓你手寫堆排序那真是有點(diǎn)難為你了)。

快排每次確定一個(gè)數(shù)pivot位置，將數(shù)分成兩部分：左面的都比這個(gè)數(shù)pivot小，右面的都比這個(gè)數(shù)pivot大，這樣就可以根據(jù)這個(gè)k去判斷剛好在pivot位置，還是左側(cè)還是右側(cè)?可以壓縮空間迭代去調(diào)用遞歸最終求出結(jié)果。

很多人為了更快過測(cè)試樣例將這個(gè)pivot不選第一個(gè)隨機(jī)選擇(為了和刁鉆的測(cè)試樣例作斗爭(zhēng))，不過這里我就選第一個(gè)作為pivot了，代碼可以參考：

class Solution { 
    public int findKthLargest(int[] nums, int k) { 
        quickSort(nums,0,nums.length-1,k); 
        return nums[nums.length-k]; 
    } 
    private void quickSort(int[] nums,int start,int end,int k) { 
        if(start>end) 
            return; 
        int left=start; 
        int right=end; 
        int number=nums[start]; 
        while (left<right){ 
            while (number<=nums[right]&&left<right){ 
                right--; 
            } 
            nums[left]=nums[right]; 
            while (number>=nums[left]&&left<right){ 
                left++; 
            } 
            nums[right]=nums[left]; 
        } 
        nums[left]=number; 
        int num=end-left+1; 
        if(num==k)//找到k就終止 
            return; 
        if(num>k){ 
            quickSort(nums,left+1,end,k); 
        }else { 
            quickSort(nums,start,left-1,k-num); 
        } 
    } 
} 

0X09 無重復(fù)的最長(zhǎng)子串(數(shù)組)

這個(gè)問題可能是個(gè)字符串也可能是數(shù)組，但是道理一致，無重復(fù)字符的最長(zhǎng)子串和最長(zhǎng)無重復(fù)子數(shù)組本質(zhì)一致。

題目要求為：給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

分析：

此題就是給一個(gè)字符串讓你找出最長(zhǎng)沒有重復(fù)的一個(gè)子串。要搞清子串和子序列的區(qū)別：

子串：是連續(xù)的，可以看成原串的一部分截取。

子序列：不一定是連續(xù)的，但是要保證各個(gè)元素之間相對(duì)位置不變。

那么我們?nèi)绾翁幚砟?

暴力查找，暴力查找當(dāng)然是可以的，但是復(fù)雜度過高這里就不進(jìn)行講解了。這里選擇的思路是滑動(dòng)窗口，滑動(dòng)窗口，就是用一個(gè)區(qū)間從左往右，右側(cè)先進(jìn)行試探，找到區(qū)間無重復(fù)最大值，當(dāng)有重復(fù)時(shí)左側(cè)再往右側(cè)移動(dòng)一直到?jīng)]重復(fù)，然后重復(fù)進(jìn)行到最后。在整個(gè)過程中找到最大子串即可。

具體實(shí)現(xiàn)時(shí)候可以用數(shù)組替代哈希表會(huì)快很多：

class Solution { 
    public int lengthOfLongestSubstring(String s) { 
         int a[]=new int[128]; 
         int max=0;//記錄最大 
         int l=0;//left 用i 當(dāng)成right，當(dāng)有重復(fù)左就往右 
         for(int i=0;i<s.length();i++) 
         { 
             a[s.charAt(i)]++; 
             while (a[s.charAt(i)]>1) { 
                a[s.charAt(l++)]--; 
            } 
             if(i-l+1>max) 
                 max=i-l+1; 
         } 
         return max; 
    } 
} 

0X10 排序

不會(huì)真的有人以為用個(gè)Arrays.sort()就完事了吧，手寫排序還是很高頻的，像冒泡、插入這些簡(jiǎn)單的大家相比都會(huì)，像堆排序、希爾、基數(shù)排序等考察也不多，比較高頻的就是快排了，這里額外獎(jiǎng)勵(lì)一個(gè)也很高頻的歸并排序，兩個(gè)都是典型分治算法，也可以將快排和前面的TOPK問題比較一番。

排序詳細(xì)的十大排序都有詳細(xì)講過，大家可以自行參考：程序員必知必會(huì)十大排序

快排：

具體實(shí)現(xiàn)：

public void quicksort(int [] a,int left,int right) 
{ 
  int low=left; 
  int high=right; 
  //下面兩句的順序一定不能混，否則會(huì)產(chǎn)生數(shù)組越界?。?！very important！??！ 
  if(low>high)//作為判斷是否截止條件 
    return; 
  int k=a[low];//額外空間k，取最左側(cè)的一個(gè)作為衡量，最后要求左側(cè)都比它小，右側(cè)都比它大。 
  while(low<high)//這一輪要求把左側(cè)小于a[low],右側(cè)大于a[low]。 
  { 
    while(low<high&&a[high]>=k)//右側(cè)找到第一個(gè)小于k的停止 
    { 
      high--; 
    } 
    //這樣就找到第一個(gè)比它小的了 
    a[low]=a[high];//放到low位置 
    while(low<high&&a[low]<=k)//在low往右找到第一個(gè)大于k的，放到右側(cè)a[high]位置 
    { 
      low++; 
    } 
    a[high]=a[low];             
  } 
  a[low]=k;//賦值然后左右遞歸分治求之 
  quicksort(a, left, low-1); 
  quicksort(a, low+1, right);         
} 

歸并排序:

實(shí)現(xiàn)代碼為：

private static void mergesort(int[] array, int left, int right) { 
  int mid=(left+right)/2; 
  if(left<right) 
  { 
    mergesort(array, left, mid); 
    mergesort(array, mid+1, right); 
    merge(array, left,mid, right); 
  } 
} 
 
private static void merge(int[] array, int l, int mid, int r) { 
  int lindex=l;int rindex=mid+1; 
  int team[]=new int[r-l+1]; 
  int teamindex=0; 
  while (lindex<=mid&&rindex<=r) {//先左右比較合并 
    if(array[lindex]<=array[rindex]) 
    { 
      team[teamindex++]=array[lindex++]; 
    } 
    else {                 
      team[teamindex++]=array[rindex++]; 
    } 
  } 
  while(lindex<=mid)//當(dāng)一個(gè)越界后剩余按序列添加即可 
  { 
    team[teamindex++]=array[lindex++]; 
 
  } 
  while(rindex<=r) 
  { 
    team[teamindex++]=array[rindex++]; 
  }     
  for(int i=0;i<teamindex;i++) 
  { 
    array[l+i]=team[i]; 
  } 
} 

結(jié)語(yǔ)

好了，今天給大家分享的10個(gè)問題，是真的在面試中非常非常高頻，我敢說平均每?jī)纱蚊嬖嚲偷糜龅竭@里面的其中一個(gè)題(毫不夸張)!

雖說題海很深學(xué)不完，但是學(xué)過緩存的都知道要把熱點(diǎn)數(shù)據(jù)放緩存，考過試的都知道要把必考點(diǎn)掌握……這十個(gè)問題已經(jīng)送到嘴邊。