面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集

本文涉及的产品
云解析DNS,个人版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
全局流量管理 GTM,标准版 1个月
简介: 面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集

本文将覆盖 二分 + 哈希表 + + 优先队列 方面的面试算法题,文中我将给出:

  1. 面试中的题目
  2. 解题的思路
  3. 特定问题的技巧和注意事项
  4. 考察的知识点及其概念
  5. 详细的代码和解析
    在开始之前,我们先看下会有哪些重点内容:

现在就让我们开始吧!


二分

  • 概念:
    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
  • 基本思路:
  1. 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较
  2. 如果两者相等,则查找成功
  3. 否则利用中间位置记录将表分成前、后两个子表
  4. 如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表
  5. 否则进一步查找后一子表
  6. 重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

二分搜索

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

技巧:

分析二分查找的一个技巧是:

  • 不要出现 else,而是把所有情况用 if / else if 写清楚
  • 这样可以清楚地展现所有细节。

这里我们以递归非递归方式,解决面试中的二分搜索题

递归

思路很简单:

  • 判断起始点是否大于终止点
  • 比较 nums[mid]与目标值大小
  • 如果 nums[mid]大,说明目标值 target 在前面
  • 反之如果 nums[mid]小,说明目标值 target 在前面后面
  • 如果既不大也不小,说明相等,则返回当前位置
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;
    }
}
非递归

这个场景是最简单的:

  • 搜索一个数
  • 如果存在, 返回其索引
  • 否则返回 -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;
}
相关视频

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


X的平方根

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 2:

输入: 8

输出: 2

说明: 8 的平方根是 2.82842...,

由于返回类型是整数,小数部分将被舍去。

解题思路

使用二分法搜索平方根的思想很简单:

  • 就类似于小时候我们看的电视节目中的“猜价格”游戏
  • 高了就往低了猜
  • 低了就往高了猜
  • 范围越来越小。

注:一个数的平方根最多不会超过它的一半,例如 8 的平方根,8 的一半是 4,如果这个数越大越是如此

注意:

对于判断条件:

  • 比如说:我们很容易想当然觉得
  • mid == x / midmid * mid == x 是等价的,实际却不然
  • 比如 mid = 2,x = 5
  • 对于 mid == x / mid 就是:2 == 2 返回 true
  • 而对于 mid * mid == x 就是:4 == 5 返回 false

对于边界条件有个坑:

  • 要注意此处耍了一下小技巧,在二分左值和右值相差为1的时候就停止查找;因为在这里,有个对中值取整数的操作,在取整后始终有 start == mid == end则会死循环。

取整操作的误差为1,故而在这里限制条件改成包含1在内的范围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;
    // 直接对答案可能存在的区间进行二分 => 二分答案
    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,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
  • 数据结构
    给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。

两数之和

给一个整数数组,找到两个数使得他们的和等于一个给定的数 target。需要实现的函数 twoSum 需要返回这两个数的下标。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

解题思路
  • 用一个hashmap来记录
  • key记录target - numbers[i]的值,value记录numbers[i]i的值
  • 如果碰到一个 numbers[j]hashmap中存在
  • 那么说明前面的某个numbers[i]numbers[j]的和为target
  • 那么当前的ij即为答案
public int[] twoSum(int[] numbers, int target) {
 
    HashMap<Integer,Integer> map = new HashMap<>();
 
    for (int i = 0; i < numbers.length; i++) {
        // 判断 map 中是否有需要该值的项
        if (map.containsKey(numbers[i])) {
            return new int[]{map.get(numbers[i]), i};
        }
        // 意思可理解为第 i 项,需要 target - numbers[i]
        map.put(target - numbers[i], i);
    }
 
    return new int[]{};
}

连续数组

给一个二进制数组,找到 0 和 1 数量相等的子数组的最大长度

示例 2:

输入: [0,1,0]

输出: 2

说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

步骤
  1. 使用一个数字sum维护到i为止1的数量与0的数量的差值
  2. loop i的同时维护sum并将其插入hashmap
  3. 对于某一个sum值,若hashmap中已有这个值
  4. 则当前的isum上一次出现的位置之间的序列0的数量与1的数量相同
public int findMaxLength(int[] nums) {
    Map<Integer, Integer> prefix = new HashMap<>();
    int sum = 0;
    int max = 0;
    // 因为在开始时 0 、 1 的数量都为 0 ,所以必须先存 0 
    // 否则第一次为 0 的时候,<- i - prefix.get(sum) -> 找不到 prefix.get(0)
    prefix.put(0, -1); 
    // 当第一个 0 1 数量相等的情况出现时,数组下标减去-1得到正确的长度
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (num == 0) {
            sum--;
        } else {
            sum++;
        }
        // 判断是否已存在 sum 值
        // 存在则说明之前存过
        if (prefix.containsKey(sum)) {
            // 只做判断,不做存储
            max = Math.max(max, i - prefix.get(sum));
        } else {
            prefix.put(sum, i);
        }
    }
    
    return max;
}

最长无重复字符的子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

解题思路

HashMap记录每一个字母出现的位置:

  1. 设定一个左边界,到当前枚举到的位置之间的字符串为不含重复字符的子串。
  2. 若新碰到的字符的上一次的位置在左边界右边, 则需要向右移动左边界。
视频

大圣算法- 最长无重复字符的子串

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    HashMap<Character, Integer> map = new HashMap<>();
    int max = Integer.MIN_VALUE;
    // 计算无重复字符子串开始的位置
    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));
            // 上一次的位置在左边界右边, 则需要向右移动左边界
            if (tmp >= start) { 
                start = tmp;
            }
        } 
        
        map.put(s.charAt(i), i);
        max = Math.max(max, i - start);
    }
    return max;
}

最多点在一条直线上

给出二维平面上的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
解题思路

提示:我们会发现,其实只需要考虑当前点之后出现的点i + 1 .. N - 1即可,因为通过点 i-2 的直线已经在搜索点 i-2 的过程中考虑过了。

  • 画一条通过点 i 和之后出现的点的直线,在哈希表中存储这条边并计数为2 = 当前这条直线上有两个点。
  • 存储时,以斜率来区分线与线之间的关系
  • 假设现在 i < i + k < i + l 这三个点在同一条直线上,当画出一条通过 i 和 i+l 的直线会发现已经记录过了,因此对更新这条边对应的计数:count++

通过 HashMap 记录下两个点之间的斜率相同出现的次数,注意考虑点重合的情况

    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];
                // 两个点重合的情况记录下来
                if (dy == 0 && dx == 0) {
                    overlap++;
                    continue;
                }
                // 防止 x 相同 y 不同,但 rate 都为 0 
                // 防止 y 相同 x 不同,但 rate 都为 0 
                // 以及超大数约等于 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; 
    }

堆 / 优先队列

  • (英语:heap)是计算机科学中一类特殊的数据结构的统称。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:

  1. 堆中某个节点的值总是不大于或不小于其父节点的值;
  2. 堆总是一棵完全二叉树。

如下图这是一个最大堆,,因为每一个父节点的值都比其子节点要大。10 比 7 和 2 都大。7 比 5 和 1都大。

  • 优先队列(priority queue)
    优先队列是一种抽象数据类型,它是一种排序的机制,它有两个核心操作:找出键值最大(优先级最高)的元素、插入新的元素,效果就是他在维护一个动态的队列。可以收集一些元素,并快速取出键值最大的元素,对其操作后移出队列,然后再收集更多的元素,再处理当前键值最大的元素,如此这般。
  • 例如,我们有一台能够运行多个程序的计算机。计算机通过给每个应用一个优先级属性,将应用根据优先级进行排列,计算机总是处理下一个优先级最高的元素。

前K大的数

PriorityQueue 优先队列:Java 的优先队列,保证了每次取最小元素

// 维护一个 PriorityQueue,以返回前K大的数
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() 方法用于检索或获取和删除队列的第一个元素或队列头部的元素
            pq.poll();
        }
    }
    
    for (int i = k - 1; i >= 0; i--) {
        result[i] = pq.poll(); 
    }
    
    return result;
}

前K大的数II

实现一个数据结构,提供下面两个接口:

  1. add(number) 添加一个元素
  2. topk() 返回前K大的数
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)的语义相同,都是向优先队列中插入元素
            // 只是Queue接口规定二者对插入失败时的处理不同
            // 前者在插入失败时抛出异常,后则则会返回false
            minheap.offer(num);
            return;
        }
        
        if (num > minheap.peek()) {
            minheap.poll();
            minheap.offer(num);
        }
    }
 
    public List<Integer> topk() {
        // 将队列中的数存到数组中
        Iterator it = minheap.iterator();
        List<Integer> result = new ArrayList<Integer>();
        while (it.hasNext()) {
            result.add((Integer) it.next());
        }
        // 调用数组排序法后返回
        Collections.sort(result, Collections.reverseOrder());
        return result;
    }
}

数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 2:

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

输出: 4

我的第一个想法:暴力法

    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();
    }
这里举个无关的算法:

使用快速排序,思路极其简单:

  1. 首先对数组进行快速排序
  2. 最后返回第 k 个数即可

具体实现:

    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

为了提高文章质量,防止冗长乏味

下一部分算法题

  • 本片文章篇幅总结越长。我一直觉得,一片过长的文章,就像一场超长的 会议/课堂,体验很不好,所以打算再开一篇文章来总结其余的考点
  • 在后续文章中,我将继续针对链表 队列 动态规划 矩阵 位运算 等近百种,面试高频算法题,及其图文解析 + 教学视频 + 范例代码,进行深入剖析有兴趣可以继续关注 _yuanhao 的编程世界

相关文章


? 面试必备:高频算法题汇总「图文解析 + 教学视频 + 范例代码」必问之 链表 + 栈 + 队列 部分!?

?面试必备:高频算法题汇总「图文解析 + 教学视频 + 范例代码」必知必会 排序 + 二叉树 部分!?

每个人都要学的图片压缩终极奥义,有效解决 Android 程序 OOM

Android 让你的 Room 搭上 RxJava 的顺风车 从重复的代码中解脱出来

ViewModel 和 ViewModelProvider.Factory:ViewModel 的创建者

单例模式-全局可用的 context 对象,这一篇就够了

缩放手势 ScaleGestureDetector 源码解析,这一篇就够了

Android 属性动画框架 ObjectAnimator、ValueAnimator ,这一篇就够了

看完这篇再不会 View 的动画框架,我跪搓衣板

看完这篇还不会 GestureDetector 手势检测,我跪搓衣板!


相关文章
|
13天前
|
算法 Python
算法不再难!Python分治法、贪心、动态规划实战解析,轻松应对各种算法挑战!
【7月更文挑战第8天】掌握Python算法三剑客:分治、贪心、动态规划。分治如归并排序,将大问题拆解递归解决;贪心策略在每步选最优解,如高效找零;动态规划利用子问题解,避免重复计算,解决最长公共子序列问题。实例展示,助你轻松驾驭算法!**
25 3
|
3天前
|
存储 分布式计算 DataWorks
MaxCompute产品使用合集之如何在代码中解析File类型的文件内容
MaxCompute作为一款全面的大数据处理平台,广泛应用于各类大数据分析、数据挖掘、BI及机器学习场景。掌握其核心功能、熟练操作流程、遵循最佳实践,可以帮助用户高效、安全地管理和利用海量数据。以下是一个关于MaxCompute产品使用的合集,涵盖了其核心功能、应用场景、操作流程以及最佳实践等内容。
28 11
|
17天前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
184 1
|
8天前
|
机器学习/深度学习 存储 数据采集
强化学习系列:A3C算法解析
【7月更文挑战第13天】A3C算法作为一种高效且广泛应用的强化学习算法,通过结合Actor-Critic结构和异步训练的思想,实现了在复杂环境下的高效学习和优化策略的能力。其并行化的训练方式和优势函数的引入,使得A3C算法在解决大规模连续动作空间和高维状态空间的问题上表现优异。未来,随着技术的不断发展,A3C算法有望在更多领域发挥重要作用,推动强化学习技术的进一步发展。
|
4天前
|
并行计算 算法 Python
Dantzig-Wolfe分解算法解释与Python代码示例
Dantzig-Wolfe分解算法解释与Python代码示例
|
12天前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。
|
17天前
|
存储 数据管理 数据库
CRUD操作实战:从理论到代码实现的全面解析
【7月更文挑战第4天】在软件开发领域,CRUD代表了数据管理的四个基本操作:创建(Create)、读取(Read)、更新(Update)和删除(Delete)。这四个操作构成了大多数应用程序数据交互的核心。本文将深入讲解CRUD概念,并通过一个简单的代码示例,展示如何在实际项目中实现这些操作。我们将使用Python语言结合SQLite数据库来演示,因为它们的轻量级特性和易用性非常适合教学目的。
37 2
|
18天前
|
文字识别 Java Python
文本,文识08图片保存()上,最方便在于整体生成代码,serivce及实体类,base64编码保存图片文件,调用flask实现内部ocr接口,通过paddleocr识别,解析结果,base64转图片
文本,文识08图片保存()上,最方便在于整体生成代码,serivce及实体类,base64编码保存图片文件,调用flask实现内部ocr接口,通过paddleocr识别,解析结果,base64转图片
|
11天前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
11 0
|
11天前
|
存储 算法 Java
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
Java面试题:解释JVM的内存结构,并描述堆、栈、方法区在内存结构中的角色和作用,Java中的多线程是如何实现的,Java垃圾回收机制的基本原理,并讨论常见的垃圾回收算法
10 0

推荐镜像

更多