面試

本文將覆蓋 二分 + 哈希表 + 堆 + 優(yōu)先隊(duì)列 方面的面試算法題镶奉，文中我將給出：

1. 面試中的題目
2. 解題的思路
3. 特定問(wèn)題的技巧和注意事項(xiàng)
4. 考察的知識(shí)點(diǎn)及其概念
5. 詳細(xì)的代碼和解析
   在開始之前窘行，我們先看下會(huì)有哪些重點(diǎn)內(nèi)容：

本文

現(xiàn)在就讓我們開始吧！

二分

• **概# 二分

• 概念：
  二分查找也稱折半查找（Binary Search）纲刀，它是一種效率較高的查找方法。但是担平，折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)示绊，而且表中元素按關(guān)鍵字有序排列。

• 基本思路：

1. 首先暂论，假設(shè)表中元素是按升序排列耻台，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較
2. 如果兩者相等，則查找成功
3. 否則利用中間位置記錄將表分成前空另、后兩個(gè)子表
4. 如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字盆耽，則進(jìn)一步查找前一子表
5. 否則進(jìn)一步查找后一子表
6. 重復(fù)以上過(guò)程，直到找到滿足條件的記錄扼菠，使查找成功摄杂，或直到子表不存在為止，此時(shí)查找不成功循榆。

在這里插入圖片描述

二分搜索

給定一個(gè) n 個(gè)元素有序的（升序）整型數(shù)組 nums 和一個(gè)目標(biāo)值 target 析恢，寫一個(gè)函數(shù)搜索 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)秧饮，否則返回 -1映挂。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4

技巧：

分析二分查找的一個(gè)技巧是：

• 不要出現(xiàn) else，而是把所有情況用 if / else if 寫清楚
• 這樣可以清楚地展現(xiàn)所有細(xì)節(jié)盗尸。

這里我們以遞歸和非遞歸方式柑船，解決面試中的二分搜索題

在這里插入圖片描述

遞歸

思路很簡(jiǎn)單：

• 判斷起始點(diǎn)是否大于終止點(diǎn)
• 比較 nums[mid]與目標(biāo)值大小
• 如果 nums[mid]大，說(shuō)明目標(biāo)值 target 在前面
• 反之如果 nums[mid]小泼各，說(shuō)明目標(biāo)值 target 在前面后面
• 如果既不大也不小鞍时，說(shuō)明相等，則返回當(dāng)前位置

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, 0, nums.length - 1, target);
    }

    private int binarySearch(int[] nums, int start, int end, int target) {
        if(start > end) {
            return -1;
        }
        int mid = (end + start) / 2;
        if(nums[mid] < target) {
            return binarySearch(nums, mid + 1, end, target);
        }
        if(nums[mid] > target) {
            return binarySearch(nums, start, mid - 1, target);
        }
        return mid;
    }
}

非遞歸

這個(gè)場(chǎng)景是最簡(jiǎn)單的:

• 搜索一個(gè)數(shù)
• 如果存在, 返回其索引
• 否則返回 -1

int binarySearch(int[] nums, int target) {
    int left = 0; 
    // 注意減 1
    int right = nums.length - 1; 

    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

相關(guān)視頻

分鐘教你二分查找(python版)

X的平方根

計(jì)算并返回 x 的平方根，其中 x 是非負(fù)整數(shù)逆巍。

由于返回類型是整數(shù)及塘，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去锐极。

示例 2:

輸入: 8
輸出: 2
說(shuō)明: 8 的平方根是 2.82842...,
由于返回類型是整數(shù)笙僚，小數(shù)部分將被舍去。

解題思路

使用二分法搜索平方根的思想很簡(jiǎn)單：

• 就類似于小時(shí)候我們看的電視節(jié)目中的“猜價(jià)格”游戲
• 高了就往低了猜
• 低了就往高了猜
• 范圍越來(lái)越小灵再。

注：一個(gè)數(shù)的平方根最多不會(huì)超過(guò)它的一半味咳，例如 8 的平方根，8 的一半是 4檬嘀，如果這個(gè)數(shù)越大越是如此

注意：

對(duì)于判斷條件：

• 比如說(shuō)：我們很容易想當(dāng)然覺(jué)得
• mid == x / mid 和 mid * mid == x 是等價(jià)的槽驶，實(shí)際卻不然
• 比如 mid = 2，x = 5
• 對(duì)于 mid == x / mid 就是：2 == 2 返回 true
• 而對(duì)于 mid * mid == x 就是：4 == 5 返回 false

對(duì)于邊界條件有個(gè)坑:

• 要注意此處耍了一下小技巧鸳兽，在二分左值和右值相差為1的時(shí)候就停止查找掂铐；因?yàn)樵谶@里，有個(gè)對(duì)中值取整數(shù)的操作揍异，在取整后始終有 start == mid == end則會(huì)死循環(huán)全陨。

取整操作的誤差為1，故而在這里限制條件改成包含1在內(nèi)的范圍start + 1 < end ; 這里減一很精髓

public int sqrt(int x) {
    if (x < 0)  {
        throw new IllegalArgumentException();
    } else if (x <= 1) {
        return x;
    }

    int start = 1, end = x;
    // 直接對(duì)答案可能存在的區(qū)間進(jìn)行二分 => 二分答案
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (mid == x / mid) {
            return mid;
        }  else if (mid < x / mid) {
            start = mid;
        } else {
            end = mid;
        }  
    }
    
    if (end > x / end) {
        return start;
    }
    return end;
}

哈希表

• 概念
  散列表（Hash table衷掷，也叫哈希表）辱姨，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)戚嗅，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄雨涛，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)懦胞，存放記錄的數(shù)組叫做散列表替久。

• 數(shù)據(jù)結(jié)構(gòu)
  給定表M，存在函數(shù)f(key)躏尉，對(duì)任意給定的關(guān)鍵字值key蚯根，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表胀糜，函數(shù)f(key)為哈希(Hash) 函數(shù)颅拦。

在這里插入圖片描述

兩數(shù)之和

給一個(gè)整數(shù)數(shù)組，找到兩個(gè)數(shù)使得他們的和等于一個(gè)給定的數(shù) target教藻。需要實(shí)現(xiàn)的函數(shù) twoSum 需要返回這兩個(gè)數(shù)的下標(biāo)距帅。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解題思路

• 用一個(gè)hashmap來(lái)記錄
• key記錄target - numbers[i]的值，value記錄numbers[i]的i的值
• 如果碰到一個(gè) numbers[j]在hashmap中存在
• 那么說(shuō)明前面的某個(gè)numbers[i]和numbers[j]的和為target
• 那么當(dāng)前的i和j即為答案

public int[] twoSum(int[] numbers, int target) {

    HashMap<Integer,Integer> map = new HashMap<>();

    for (int i = 0; i < numbers.length; i++) {
        // 判斷 map 中是否有需要該值的項(xiàng)
        if (map.containsKey(numbers[i])) {
            return new int[]{map.get(numbers[i]), i};
        }
        // 意思可理解為第 i 項(xiàng)怖竭，需要 target - numbers[i]
        map.put(target - numbers[i], i);
    }

    return new int[]{};
}

連續(xù)數(shù)組

給一個(gè)二進(jìn)制數(shù)組锥债，找到 0 和 1 數(shù)量相等的子數(shù)組的最大長(zhǎng)度

示例 2:

輸入: [0,1,0]
輸出: 2
說(shuō)明: [0, 1] (或 [1, 0]) 是具有相同數(shù)量0和1的最長(zhǎng)連續(xù)子數(shù)組陡蝇。

步驟

1. 使用一個(gè)數(shù)字sum維護(hù)到i為止1的數(shù)量與0的數(shù)量的差值

2. 在loop i的同時(shí)維護(hù)sum并將其插入hashmap中

3. 對(duì)于某一個(gè)sum值痊臭，若hashmap中已有這個(gè)值

4. 則當(dāng)前的i與sum上一次出現(xiàn)的位置之間的序列0的數(shù)量與1的數(shù)量相同

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> prefix = new HashMap<>();
    int sum = 0;
    int max = 0;
    // 因?yàn)樵陂_始時(shí) 0 哮肚、 1 的數(shù)量都為 0 ，所以必須先存 0 
    // 否則第一次為 0 的時(shí)候广匙，<- i - prefix.get(sum) -> 找不到 prefix.get(0)
    prefix.put(0, -1); 
    // 當(dāng)?shù)谝粋€(gè) 0 1 數(shù)量相等的情況出現(xiàn)時(shí)允趟，數(shù)組下標(biāo)減去-1得到正確的長(zhǎng)度
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (num == 0) {
            sum--;
        } else {
            sum++;
        }
        // 判斷是否已存在 sum 值
        // 存在則說(shuō)明之前存過(guò)
        if (prefix.containsKey(sum)) {
            // 只做判斷，不做存儲(chǔ)
            max = Math.max(max, i - prefix.get(sum));
        } else {
            prefix.put(sum, i);
        }
    }
    
    return max;
}

最長(zhǎng)無(wú)重復(fù)字符的子串

給定一個(gè)字符串鸦致，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度潮剪。

輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3分唾。

解題思路

用HashMap記錄每一個(gè)字母出現(xiàn)的位置：

1. 設(shè)定一個(gè)左邊界抗碰，到當(dāng)前枚舉到的位置之間的字符串為不含重復(fù)字符的子串。
2. 若新碰到的字符的上一次的位置在左邊界右邊, 則需要向右移動(dòng)左邊界绽乔。

最長(zhǎng)無(wú)重復(fù)字符的子串

視頻

大圣算法- 最長(zhǎng)無(wú)重復(fù)字符的子串

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    HashMap<Character, Integer> map = new HashMap<>();
    int max = Integer.MIN_VALUE;
    // 計(jì)算無(wú)重復(fù)字符子串開始的位置
    int start = -1; 
    int current = 0;
    for (int i = 0; i < s.length(); i++) {
        if (map.containsKey(s.charAt(i))) {
            int tmp = map.get(s.charAt(i));
            // 上一次的位置在左邊界右邊, 則需要向右移動(dòng)左邊界
            if (tmp >= start) { 
                start = tmp;
            }
        } 
        
        map.put(s.charAt(i), i);
        max = Math.max(max, i - start);
    }
    return max;
}

最多點(diǎn)在一條直線上

給出二維平面上的n個(gè)點(diǎn)弧蝇，求最多有多少點(diǎn)在同一條直線上

首先點(diǎn)的定義如下

class Point {
    int x;
    int y;
    Point() { 
        x = 0; y = 0; 
    }
    Point(int a, int b) { 
        x = a; y = b; 
    }
}

示例 :

輸入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
輸出: 4
解釋:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6

解題思路

提示：我們會(huì)發(fā)現(xiàn)，其實(shí)只需要考慮當(dāng)前點(diǎn)之后出現(xiàn)的點(diǎn)i + 1 .. N - 1即可折砸，因?yàn)橥ㄟ^(guò)點(diǎn) i-2 的直線已經(jīng)在搜索點(diǎn) i-2 的過(guò)程中考慮過(guò)了看疗。

• 畫一條通過(guò)點(diǎn) i 和之后出現(xiàn)的點(diǎn)的直線，在哈希表中存儲(chǔ)這條邊并計(jì)數(shù)為2 = 當(dāng)前這條直線上有兩個(gè)點(diǎn)睦授。

• 存儲(chǔ)時(shí)两芳，以斜率來(lái)區(qū)分線與線之間的關(guān)系

• 假設(shè)現(xiàn)在 i < i + k < i + l 這三個(gè)點(diǎn)在同一條直線上，當(dāng)畫出一條通過(guò) i 和 i+l 的直線會(huì)發(fā)現(xiàn)已經(jīng)記錄過(guò)了去枷，因此對(duì)更新這條邊對(duì)應(yīng)的計(jì)數(shù)：count++怖辆。

在這里插入圖片描述

通過(guò) HashMap 記錄下兩個(gè)點(diǎn)之間的斜率相同出現(xiàn)的次數(shù)，注意考慮點(diǎn)重合的情況

    public int maxPoints(int[][] points) {
        if (points == null) {
            return 0;
        }
        
        int max = 0;
        for (int i = 0; i < points.length; i++) {
            Map<String, Integer> map = new HashMap<>();
            int maxPoints = 0;
            int overlap = 0;
            for (int j = i + 1; j < points.length; j++) {
                int dy = points[i][1] - points[j][1];
                int dx = points[i][0] - points[j][0];
                // 兩個(gè)點(diǎn)重合的情況記錄下來(lái)
                if (dy == 0 && dx == 0) {
                    overlap++;
                    continue;
                }
                // 防止 x 相同 y 不同删顶，但 rate 都為 0 
                // 防止 y 相同 x 不同疗隶，但 rate 都為 0 
                // 以及超大數(shù)約等于 0 的情況：[[0,0],[94911151,94911150],[94911152,94911151]]
                String rate = "";
                if(dy == 0)
                    rate = "yy";
                else if (dx == 0)
                    rate = "xx";
                else
                    rate = ((dy * 1.0) / dx) + "";
                
                map.put(rate, map.getOrDefault(rate, 0) + 1);
                maxPoints = Math.max(maxPoints, map.get(rate));
            }
            max = Math.max(max, overlap + maxPoints + 1);
        }
        return max; 
    }

堆 / 優(yōu)先隊(duì)列

• 堆（英語(yǔ)：heap)是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆翼闹，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆斑鼻。

堆通常是一個(gè)可以被看做一棵樹的數(shù)組對(duì)象。堆總是滿足下列性質(zhì)：

1. 堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值猎荠；
2. 堆總是一棵完全二叉樹坚弱。

如下圖這是一個(gè)最大堆，关摇，因?yàn)槊恳粋€(gè)父節(jié)點(diǎn)的值都比其子節(jié)點(diǎn)要大荒叶。10 比 7 和 2 都大。7 比 5 和 1都大输虱。

在這里插入圖片描述

• 優(yōu)先隊(duì)列(priority queue)
  優(yōu)先隊(duì)列是一種抽象數(shù)據(jù)類型些楣，它是一種排序的機(jī)制，它有兩個(gè)核心操作：找出鍵值最大(優(yōu)先級(jí)最高)的元素、插入新的元素愁茁，效果就是他在維護(hù)一個(gè)動(dòng)態(tài)的隊(duì)列蚕钦。可以收集一些元素鹅很，并快速取出鍵值最大的元素嘶居，對(duì)其操作后移出隊(duì)列，然后再收集更多的元素促煮，再處理當(dāng)前鍵值最大的元素邮屁，如此這般。
• 例如菠齿，我們有一臺(tái)能夠運(yùn)行多個(gè)程序的計(jì)算機(jī)佑吝。計(jì)算機(jī)通過(guò)給每個(gè)應(yīng)用一個(gè)優(yōu)先級(jí)屬性，將應(yīng)用根據(jù)優(yōu)先級(jí)進(jìn)行排列绳匀，計(jì)算機(jī)總是處理下一個(gè)優(yōu)先級(jí)最高的元素迹蛤。

前K大的數(shù)

PriorityQueue 優(yōu)先隊(duì)列：Java 的優(yōu)先隊(duì)列，保證了每次取最小元素

// 維護(hù)一個(gè) PriorityQueue襟士，以返回前K大的數(shù)
public int[] topk(int[] nums, int k) {
    int[] result = new int[k];
    if (nums == null || nums.length < k) {
        return result;
    }
    
    Queue<Integer> pq = new PriorityQueue<>();
    for (int num : nums) {
        pq.add(num);
        if (pq.size() > k) {
            // poll() 方法用于檢索或獲取和刪除隊(duì)列的第一個(gè)元素或隊(duì)列頭部的元素
            pq.poll();
        }
    }
    
    for (int i = k - 1; i >= 0; i--) {
        result[i] = pq.poll(); 
    }
    
    return result;
}

前K大的數(shù)II

實(shí)現(xiàn)一個(gè)數(shù)據(jù)結(jié)構(gòu)盗飒，提供下面兩個(gè)接口：

1. add(number) 添加一個(gè)元素
2. topk() 返回前K大的數(shù)

public class Solution {
    private int maxSize;
    private Queue<Integer> minheap;
    public Solution(int k) {
        minheap = new PriorityQueue<>();
        maxSize = k;
    }

    public void add(int num) {
        if (minheap.size() < maxSize) {
            // add(E e)和offer(E e)的語(yǔ)義相同，都是向優(yōu)先隊(duì)列中插入元素
            // 只是Queue接口規(guī)定二者對(duì)插入失敗時(shí)的處理不同
            // 前者在插入失敗時(shí)拋出異常陋桂，后則則會(huì)返回false
            minheap.offer(num);
            return;
        }
        
        if (num > minheap.peek()) {
            minheap.poll();
            minheap.offer(num);
        }
    }

    public List<Integer> topk() {
        // 將隊(duì)列中的數(shù)存到數(shù)組中
        Iterator it = minheap.iterator();
        List<Integer> result = new ArrayList<Integer>();
        while (it.hasNext()) {
            result.add((Integer) it.next());
        }
        // 調(diào)用數(shù)組排序法后返回
        Collections.sort(result, Collections.reverseOrder());
        return result;
    }
}

數(shù)組中的第K個(gè)最大元素

在未排序的數(shù)組中找到第 k 個(gè)最大的元素逆趣。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素嗜历，而不是第 k 個(gè)不同的元素宣渗。

示例 2:

輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4

我的第一個(gè)想法：暴力法

    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> que = new PriorityQueue<>();
        for(int num : nums) {
            if(que.size() < k) {
                que.offer(num);
            } else {
                if(que.peek() < num) {
                    que.poll();
                    que.offer(num);
                }
            }
        }
        return que.peek();
    }

這里舉個(gè)無(wú)關(guān)的算法：

使用快速排序，思路極其簡(jiǎn)單：

1. 首先對(duì)數(shù)組進(jìn)行快速排序
2. 最后返回第 k 個(gè)數(shù)即可

快速排序

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

    public int kthLargestElement(int k, int[] nums) {
        if (nums == null || nums.length == 0 || k < 1 || k > nums.length){
            return -1;
        }
        return partition(nums, 0, nums.length - 1, nums.length - k);
    }

    private int partition(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[k];
        }
        
        int left = start, right = end;
        int pivot = nums[(start + end) / 2];
        
        while (left <= right) {
            while (left <= right && nums[left] < pivot) {
                left++;
            }
            while (left <= right && nums[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
        
        if (k <= right) {
            return partition(nums, start, right, k);
        }
        if (k >= left) {
            return partition(nums, left, end, k);
        }
        return nums[k];
    }    
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

Attention

為了提高文章質(zhì)量梨州，防止冗長(zhǎng)乏味

下一部分算法題

• 本片文章篇幅總結(jié)越長(zhǎng)痕囱。我一直覺(jué)得，一片過(guò)長(zhǎng)的文章暴匠，就像一場(chǎng)超長(zhǎng)的 會(huì)議/課堂鞍恢，體驗(yàn)很不好，所以打算再開一篇文章來(lái)總結(jié)其余的考點(diǎn)

• 在后續(xù)文章中每窖，我將繼續(xù)針對(duì)鏈表 棧 隊(duì)列 堆 動(dòng)態(tài)規(guī)劃 矩陣 位運(yùn)算 等近百種帮掉，面試高頻算法題，及其圖文解析 + 教學(xué)視頻 + 范例代碼窒典，進(jìn)行深入剖析有興趣可以繼續(xù)關(guān)注 _yuanhao 的編程世界

• 不求快蟆炊，只求優(yōu)質(zhì)，每篇文章將以 2 ～ 3 天的周期進(jìn)行更新瀑志，力求保持高質(zhì)量輸出

相關(guān)文章

?? 面試必備：高頻算法題匯總「圖文解析 + 教學(xué)視頻 + 范例代碼」必問(wèn)之 鏈表 + 棧 + 隊(duì)列 部分涩搓！??
?? 面試必備：高頻算法題匯總「圖文解析 + 教學(xué)視頻 + 范例代碼」排序 + 二叉樹 部分污秆！??
Android 圖片壓縮策略詳解，有效解決 Android 程序 OOM
Android 讓你的 Room 搭上 RxJava 的順風(fēng)車 從重復(fù)的代碼中解脫出來(lái)
ViewModel 和 ViewModelProvider.Factory：ViewModel 的創(chuàng)建者

歡迎關(guān)注_yuanhao的簡(jiǎn)書昧甘！

為了方便大家跟進(jìn)學(xué)習(xí)良拼，我在 GitHub 建立了一個(gè)倉(cāng)庫(kù)

倉(cāng)庫(kù)地址：超級(jí)干貨！精心歸納視頻疾层、歸類将饺、總結(jié)贡避，各位路過(guò)的老鐵支持一下痛黎！給個(gè) Star ！

請(qǐng)點(diǎn)贊刮吧！因?yàn)槟愕墓膭?lì)是我寫作的最大動(dòng)力湖饱！

學(xué)Android