九、哈希表

  1. 哈希表不一定是标准库提供的容器，也可以是通过位图、整形数组的方式代替，尤其是只有小写字母或者数据范围固定的情况下

  2. 哈希表的最主要目的就是映射（优化遍历查找）

9.1 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> rets = new ArrayList<>();
        HashMap<String, List<String>> hash = new HashMap<>();
        for(int i = 0; i < strs.length; i++){
            char[] tmp = strs[i].toCharArray();
            Arrays.sort(tmp);
            String s = new String(tmp);
            if(hash.containsKey(s)){
                hash.get(s).add(strs[i]);
            }
            else{
                List<String> item = new ArrayList<>();
                hash.put(s, item);
                item.add(strs[i]);
            }
        }
        rets.addAll(hash.values());
        return rets;
    }
}

把这道题选进来，就是这里对于异位词的处理：对于异位词而言，其所含字母的种类和数量都是相同的，所以排序之后得到的字符串也是相同的，因此他们可以被映射到同一个String数组中

十、字符串

这里其实没有什么固定的思想或者说套路，大多通过类似模拟的方式就可以解决了（但模拟的对象是自己的解法）

10.1 最长回文子串

给你一个字符串 s，找到 s 中最长的 回文 子串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String ret = "";
        for(int i = 0; i < n; i++){
            int left = i;
            int right = left;
            while(left >= 0 && right <= n - 1 && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            int tmp = right - left - 1;
            if(tmp > ret.length()){
                ret = s.substring(left + 1, right);
            }
            if(i == n - 1){
                break;
            }
            right = i + 1;
            left = i;
            while(left >= 0 && right <= n - 1 && s.charAt(left) == s.charAt(right)){
                left--;
                right++;
            }
            if(left + 1 == right && s.charAt(left) != s.charAt(right)){
                continue;
            }
            tmp = right - left - 1;
            if(tmp > ret.length()){
                ret = s.substring(left + 1, right);
            }
        }
        return ret;
    }
}

选这道题主要是为了介绍“中心拓展算法”。回文串具有一个中心（奇数长度是一个字符，偶数长度是两个相同字符），基于此我们就可以去遍历每一个中心，并记录得到的最长得回文串

10.2 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")){
            return "0";
        }
        int m = num1.length(),  n = num2.length();
        int[] arr = new int[m + n - 1];
        StringBuilder sb1 = new StringBuilder(num1);
        StringBuilder sb2 = new StringBuilder(num2);
        num1 = sb1.reverse().toString();
        num2 = sb2.reverse().toString();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int val1 = num1.charAt(i) - '0';
                int val2 = num2.charAt(j) - '0';
                arr[i + j] += val1 * val2;
            }
        }
        StringBuilder ret = new StringBuilder();
        int tmp = 0;
        for(int i = 0; i < arr.length; i++){
            int val = arr[i] + tmp;
            int num = val % 10;
            tmp = val / 10;
            ret.append(num + "");
        }
        if(tmp != 0){
            ret.append(tmp + "");
        }
        return ret.reverse().toString();
    }
}

首先肯定是可以模拟竖式运算来完成的，但是太麻烦。对于乘法，我们可以使用无进制相乘，具体过程为：和竖式运算一样，每一位对应相乘，但是每一位上不写个位数字，而是直接写这个运算结果，每一位上也不进位

123 * 456
      1 2 3
      4 5 6
    --------
      6 12 18
    5 10 15
  4 8 12
    ---------
  5 6 0 8 8

十一、栈

11.1 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

class Solution {
    private int i = 0;
    public int calculate(String s) {
        int n = s.length();
        int ret = 0;
        char op = '+';
        Stack<Integer> st = new Stack<>();
        for(; i < n;){
            char ch = s.charAt(i);
            if(ch == ' '){
                i++;
                continue;
            }
            if(ch >= '0' && ch <= '9'){
                int val = getNum(s);
                if(op == '+'){
                    st.add(val);
                }
                else if(op == '-'){
                    st.add(0 - val);
                }
                else if(op == '*'){
                    int val2 = st.peek();
                    st.pop();
                    st.add(val2 * val);
                }
                else{
                    int val2 = st.peek();
                    st.pop();
                    st.add(val2 / val);
                }
            }
            else{
                if(ch == '+'){
                    op = '+';
                }
                else if(ch == '-'){
                    op = '-';
                }
                else if(ch == '*'){
                    op = '*';
                }
                else{
                    op = '/';
                }
                i++;
            }
        }
        while(!st.isEmpty()){
            int val = st.peek();
            st.pop();
            ret += val;
        }
        return ret;
    }

    public int getNum(String s){
        //1234
        int ret = 0;
        while(i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9'){
            ret *= 10;
            ret += s.charAt(i) - '0';
            i++;
        }
        return ret;
    }
}

这道题我们的处理思路是：把所有乘除法、减法都处理为结果，最后通过加法的方式获得最终结果。这时，栈的作用就出现了：栈可以让我们始终取到最近的若干个元素，而我们每次要进行乘法、除法的时候需要获取的都是最前面的一个数。

11.2 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

测试用例保证输出的长度不会超过 105。

示例 1：

输入：s = “3[a]2[bc]”
输出：“aaabcbc”
示例 2：

输入：s = “3[a2[c]]”
输出：“accaccacc”
示例 3：

输入：s = “2[abc]3[cd]ef”
输出：“abcabccdcdcdef”

class Solution {
    int index = 0;
    String s = "";
    int n = 0;
    String ret = "";
    public String decodeString(String str) {
        s = str;
        n = str.length();
        Stack<Integer> st_num = new Stack<>();
        Stack<String> st_str = new Stack<>();
        st_str.add("");
        while(index < n){
            char ch = str.charAt(index);
            if(ch == '['){
                index++;
                String tmp = getStr();
                st_str.add(tmp);
            }
            else if(ch == ']'){
                int cnt = st_num.peek();
                st_num.pop();
                String tmp = st_str.peek();
                st_str.pop();
                StringBuilder sb = new StringBuilder(st_str.peek());
                st_str.pop();
                while(cnt-- != 0){
                    sb.append(tmp);
                }
                st_str.add(sb.toString());
                index++;
            }
            else if(ch >= '0' && ch <= '9'){
                st_num.add(getNum());
            }
            else{
                String tmp = getStr();
                StringBuilder sb = new StringBuilder(st_str.peek());
                st_str.pop();
                sb.append(tmp);
                st_str.add(sb.toString());
            }
        }
        return st_str.peek();
    }

    private int getNum(){
        int ret = 0;
        while(index < n && s.charAt(index) >= '0' && s.charAt(index) <= '9'){
            ret *= 10;
            ret += s.charAt(index) - '0';
            index++;
        }
        return ret;
    }

    private String getStr(){
        StringBuilder sb = new StringBuilder();
        while(index < n && s.charAt(index) >= 'a' && s.charAt(index) <= 'z'){
            sb.append(s.charAt(index));
            index++;
        }
        return sb.toString();
    }
}

这个题算是栈的题目里很复杂的题目了，我们的思路是：从内到外完成解析（这一部分通过栈来保证），如果遇到数字那么就保存到数字的栈里；如果遇到了[，那么接下来跟的一定是准备开始解析的新的一段字符串（放到栈顶的），如果是]，就说明当前栈顶的字符串的解析已经完成了一部分（具备了解析字段的重复部分和次数），就需要把内容追加到站定元素后面；如果是直接遇到了字符串，那么这部分是对于当前栈顶字符串来说不需要重复的部分，直接添加的栈顶字符串中（因为另一种出现字符，即遇到 [ 的下一个位置，已经被我们在 [ 的地方处理了）

另外在我们的方法里，当前解析的内容最后都放到了栈顶字符串的下一个中，所有在开始解析字符串以前首先往栈里添加一个空串，用来存放最终结果

十二、二叉树的层序遍历

12.1 二叉树的最大宽度

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

class Solution {
    public class Pair{
        TreeNode node;
        int index;
        Pair(TreeNode node, int index){
            this.node = node;
            this.index = index;
        }
    }
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        long ret = 0;
        List<Pair> queue = new ArrayList<>();
        Pair pair = new Pair(root, 0);
        queue.add(pair);
        while(!queue.isEmpty()){
            int cnt = queue.size();
            int leftI = queue.get(0).index;
            int rightI = queue.get(cnt - 1).index;
            ret = Math.max(ret, rightI - leftI + 1);

            List<Pair> tmp = new ArrayList<>();
            for(Pair p: queue){
                TreeNode node = p.node;
                int index = p.index;
                if(node.left != null){
                    tmp.add(new Pair(node.left, index * 2 + 1));
                }
                if(node.right != null){
                    tmp.add(new Pair(node.right, index * 2 + 2));
                }
            }
            queue = tmp;
        }
        return (int)ret;
    }
}

选这道题更多是为了展现 Java 算法题中数据结构的使用思路。在 Java 中，使用各种数据结构作为存储数据的容器时，C++中的容器适配器的思想就更加明显。比如我们这里通过把节点和下标绑定（C++中我们可以直接使用 std::pair，但是Java中我们只能手搓了），同时我们又需要随机访问“队列”每一层的起止 Pair，所以我们使用ArrayList来代替队列；同时我们又需要把“队列”提供给下一层的遍历，所以我们采取临时容器的方式，完成一层的“入队列”操作后，就用临时队列代替原队列

十三、堆

13.1 关于大小根堆的自定义比较器

13.1.1 Java

Java 中，堆的自定义比较器规则和排序算法的一样，都是返回 e1 - e2，则排升序（或者是等价写法 e1.compareTo(e2)），对于堆来说，就是排小根堆（Java默认）；返回 e2 - e1，则排降序（或者是等价写法 e2.compareTo(e1)），对于堆来说，就是排大根堆

13.1.2 C++

C++ 中，堆的自定义比较器规则和排序算法的相反。

对于排序算法，可以简记：看大小于号的上半部分，如果是上升的，例如 return e1 < e2;，那么就是排升序；如果是下降的，例如 return e1 > e2，那么就是排降序

对于堆来说，规则正好相反，依然看大小于号的上半部分：如果是上升的，例如 return e1 < e2，那么排的就是层与层之间的降序关系，也就是大根堆（C++默认），如果是下降的，例如 return e1 > e2，那么排的就是层级之间的升序关系，也就是小根堆

另外，对于 stl 中提供的两个比较器，std::greater<> 和 std::less<> ，分别对应 return e1 > e2 和 return e1 < e2，如果没有自定义比较器的需求（如实现结构体之间的比较规则），可以等价使用

13.2 前 k 个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。

class Solution {
    private class Pair {
        String word;
        int cnt;

        Pair(String word, int cnt) {
            this.word = word;
            this.cnt = cnt;
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        int n = words.length;
        List<String> rets = new ArrayList<>();
        PriorityQueue<Pair> pq = new PriorityQueue<>((Pair p1, Pair p2) -> {
            if (p1.cnt == p2.cnt) {
                return p2.word.compareTo(p1.word);
            } else {
                return p1.cnt - p2.cnt;
            }
        });

        HashMap<String, Pair> hash = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (hash.containsKey(words[i])) {
                hash.get(words[i]).cnt++;
            } else {
                hash.put(words[i], new Pair(words[i], 1));
            }
        }

        for (Pair p : hash.values()) {
            pq.add(p);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        while (!pq.isEmpty()) {
            rets.add(pq.poll().word);
        }
        Collections.reverse(rets);
        return rets;
    }
}

堆的算法题里，主要涉及两种知识点：

  1. 自定义比较器的设计
  2. 堆的设计

在这道题中，选出前 k 个大元素，最简单的做法就是让我们的堆是一个小根堆，并且大小始终不超过 k，只要超过了k，就把堆顶的元素删除（堆顶的元素在小根堆中是最小的，这样不断筛选出堆中的最小元素，最后，所有元素都进入过堆之后，堆中剩下的元素就是前 k 大的元素）

13.3 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。

void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

class MedianFinder {
    private PriorityQueue<Integer> pq_br;
    private PriorityQueue<Integer> pq_sr;
    //1 6 4 2 6 2
    public MedianFinder() {
        pq_br = new PriorityQueue<>(Collections.reverseOrder());
        pq_sr = new PriorityQueue<>();
    }

    public void addNum(int num) {
        int m = pq_br.size();
        int n = pq_sr.size();
        if(m == n){
            if(m == 0 || pq_br.peek() >= num){
                pq_br.add(num);
            }
            else{
                pq_sr.add(num);
                pq_br.add(pq_sr.peek());
                pq_sr.poll();
            }
        }
        else{ //m == n + 1
            if(pq_br.peek() >= num){
                pq_br.add(num);
                pq_sr.add(pq_br.peek());
                pq_br.poll();

            }
            else{
                pq_sr.add(num);
            }
        }
    }

    public double findMedian() {
        int m = pq_br.size();
        int n = pq_sr.size();
        if(m == n){
            return (pq_br.peek() + pq_sr.peek()) / 2.0;
        }
        else{
            return pq_br.peek();
        }
    }
}

这道题我们采取两个堆结合的方式来寻找中位数。一个是大根堆，用来存中位数及比它小的元素；一个是小根堆，用来存比中位数大的元素

十四、BFS

14.1 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ 组成，捕获 所有 被围绕的区域：

连接：一个单元格与水平或垂直方向上相邻的单元格连接。
区域：连接所有 ‘O’ 的单元格来形成一个区域。
围绕：如果一个区域中的所有 ‘O’ 单元格都不在棋盘的边缘，则该区域被包围。这样的区域 完全 被 ‘X’ 单元格包围。
通过 原地 将输入矩阵中的所有 ‘O’ 替换为 ‘X’ 来 捕获被围绕的区域。你不需要返回任何值。

这道题就不写代码了，选这道题的主要原因是强调正难则反的思路。如果直接找整个区域中的 O 并判断区域是否全部在非边界上的话，写的比较麻烦，需要用额外的数据结构保存每个区域中的位置，并判断是否需要反转。

更好的做法是直接遍历边界，把所有在边界上能通过 bfs 遍历到的 O 都设置为其他符号（比如 .），最后再恢复就好了

十五、BFS解决最短路问题

通过bfs解决最短路问题，就是通过类似落到水面的水滴激起的波纹一样，向四周暴力查找，最先找到的路径就是最短路径

15.1 为高尔夫比赛砍树

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：

0 表示障碍，无法触碰
1 表示地面，可以行走
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。

你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。

你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。

可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

class Solution {
    private int m = 0, n = 0;
    private static int[] dx = {1, -1, 0, 0};
    private static int[] dy = {0, 0, 1, -1};
    public int cutOffTree(List<List<Integer>> forest) {
        m = forest.size(); n = forest.get(0).size();
        List<int[]> trees = new ArrayList<>();

        for(int x = 0; x < m; x++){
            for(int y = 0; y < n; y++){
                if(forest.get(x).get(y) != 0){
                    int[] t1 = {x, y};
                    trees.add(t1);
                }
            }
        }

        trees.sort((int[] i1, int[] i2)->{
            return forest.get(i1[0]).get(i1[1]) - forest.get(i2[0]).get(i2[1]);
        });
        int ret = 0;
        int[] prev = {0, 0};

        for(int i = 0; i < trees.size(); i++){
            if(forest.get(trees.get(i)[0]).get(trees.get(i)[1]) == 1){
                continue;
            }
            int tmp = bfs(forest, prev, trees.get(i));
            prev = trees.get(i);
            if(tmp == -1){
                return -1;
            }
            ret += tmp;
        }

        return ret;
    }

    public int bfs(List<List<Integer>> forest, int[] start, int[] end){
        Queue<int[]> q = new LinkedList<>();
        if(start[0] == end[0] && start[1] == end[1]){
            return 0;
        }
        boolean[][] vis = new boolean[m][n];
        q.add(start);
        int ret = 0;
        while(!q.isEmpty()){
            ret++;
            int sz = q.size();
            while(sz-- != 0){
                int[] t1 = q.poll();
                if(vis[t1[0]][t1[1]] == true){
                    continue;
                }
                vis[t1[0]][t1[1]] = true;
                for(int k = 0; k < 4; k++){
                    int a = t1[0] + dx[k], b = t1[1] + dy[k];
                    if(a >= 0 && a < m && b >= 0 && b < n && forest.get(a).get(b) != 0 && !vis[a][b]){
                        if(forest.get(a).get(b) == forest.get(end[0]).get(end[1])){
                            return ret;
                        }
                        int[] t2 = {a, b};
                        q.add(t2);
                    }
                }
            }
        }
        return -1;
    }
}

这道题主要有两点需要注意

  1. 自定义比较器的使用。

  2. 题中已经说明，每棵树高度不会重复，并且要从低到高砍树，那么我们砍树的顺序其实就是固定的。这意味着，这个问题可以转化为若干个最短路径问题

# 算法 # 散列表 # 宽度优先
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

【世界杯中的AI】（2026-07-04）三场生死战，AI成了预言家？揭晓“首届AI世界杯”最疯狂的24小时！

avatar 亚马逊云科技技术品牌专区
cover

4-20mA/0-10V 通用模拟量采集电路

avatar 亚马逊云科技技术品牌专区

云原生模型服务 SLO：别只承诺平均延迟

云原生模型服务 SLO 要关注可用性、首 token、尾延迟、错误分类和阶段拆解，并连接扩缩容和回滚动作。别只承诺平均延迟。用户不会被平均值安慰，生产系统也不该被平均值误导。

avatar 亚马逊云科技技术品牌专区