如何学习数据结构和算法。你必须知道的20个解决问题的技巧

基于指针的技术

基于递归的技术

排序和搜索

扩展基本数据结构

杂项

结论

本文最初发表在我的博客www.yourdevopsguy.com上。

这篇文章是我刚开始编程时希望读到的。编程的意义在于解决问题，在这里，我将深入探讨 20 种解决问题的技巧，并提供代码示例、大 O 分析和挑战，以便你能够掌握它们。

在本文中，我概述了准备下一次编程面试的高级策略，以及需要避免的主要错误。在这里，我将深入探讨 20 种你必须掌握的解决问题的技巧，才能在下一次面试中脱颖而出。这些技巧也对我的工作有所帮助，甚至为我正在做的一个业余项目提供了灵感。此外，最后一部分还包含一个分步指南，指导你学习（而不是死记硬背）任何算法或数据结构，并附有 2 个示例。

我将这些技术归类为：

基于指针
基于递归
排序和搜索
扩展基本数据结构
杂项

我将对它们进行每一个解释，展示如何将它们应用于编码问题，并给你留下一些练习，以便你可以自己练习。

这份清单是我申请亚马逊之前做的学习笔记的一部分。希望它们能像对我一样对你有所帮助。

为了方便起见，我把问题描述复制到了这里，但保留了所有练习的链接。你可以复制粘贴我的解决方案并尝试一下。我强烈建议你编写代码，看看它是否通过测试。

有些问题最好用图片或图表来解释。对于这类问题，我留下了一条评论，请大家打开链接查看问题的图形描述。

基于指针的技术

1. 两个指针

这种技术对于已排序的数组和我们想要对其元素进行分组的数组非常有用。

这个想法是使用两个（或更多指针）根据某些条件将数组分成不同的区域或组：

小于、等于和大于某个值的元素
总和过小或过大的元素
ETC。

下面的例子将帮助你理解这个原理。

两笔和

给定一个已按升序排序的整数数组，找出两个数字，使它们的和等于特定的目标数。函数 twoSum 应该返回这两个数字的索引，使它们的和等于目标数，其中 index1 必须小于 index2。

笔记：

您返回的答案（index1 和 index2）不是从零开始的。
您可以假设每个输入只有一个解决方案，并且您可能不会两次使用相同的元素。

例子：

输入：数字 = [2,7,11,15]，目标 = 9
输出：[1,2]
解释：2 加 7 等于 9。因此 index1 = 1，index2 = 2。

解决方案

由于数组a已排序，我们知道：

最大和等于最后 2 个元素之和
最小和等于前两个元素之和
对于[0, a.size() - 1) => a[i + 1] >= a[i] 中的任何索引i

据此，我们可以设计以下算法：

我们保留 2 个指针：l，从数组的第一个元素开始，r，从最后一个元素开始。
如果 a[l] + a[r] 的和小于我们的目标，则将 l 加 1（将加法中的最小操作数更改为在l+1处等于或大于它的另一个操作数）；如果它大于目标，则将 r 减 1（将最大的操作数更改为在r-1处等于或小于它的另一个操作数）。
我们这样做，直到 a[l] + a[r] 等于我们的目标，或者 l 和 r 指向同一个元素（因为我们不能两次使用同一个元素）或者交叉，表明没有解决方案。

这是一个简单的 C++ 实现：

vector<int> twoSum(const vector<int>& a, int target) {
        int l = 0, r = a.size() - 1;
        vector<int> sol;
        while(l < r) {
            const int sum = a[l] + a[r];
            if(target == sum){
                sol.push_back(l + 1); 
                sol.push_back(r + 1); 
                break;
            } else if (target > sum) {
                ++l;
            } else {
                --r;
            }
        }
        return sol;
    }

时间复杂度为 O(N)，因为我们可能需要遍历数组的 N 个元素才能找到解决方案。

空间复杂度为 O(1)，因为我们只需要两个指针，而不管数组包含多少个元素。

还有其他方法可以解决这个问题（例如，使用哈希表），但我只是用它作为双指针技术的一个例子。

挑战

这个练习有两个变体：三和运算和
四和运算。它们可以通过简化为同一个问题来类似地求解。

这是一个非常常见的技巧：将一个你不知道其解决方案的问题转化为一个你可以解决的问题。

从数组中删除重复项

给定一个排序数组 nums，就地删除重复项，使得每个元素只出现一次，并返回新的长度。

不要为另一个数组分配额外的空间，您必须通过使用 O(1) 额外内存就地修改输入数组来实现。

例 1：

给定 nums = [1,1,2]，
输出 = 2

示例 2：

给定 nums = [0,0,1,1,1,2,2,3,3,4]，
输出 = 5

返回的长度之外设置什么值都没有关系。

解决方案

数组已排序，我们希望将重复项移至数组末尾，这听起来很像基于某些条件的分组。如何使用两个指针来解决这个问题？

您将需要一个指针来遍历数组i。
第二个指针n用于定义不包含重复项的区域：[0,n]。

逻辑如下，假设索引i （ i = 0除外）和i-1 处的元素的值为：

同样，我们不做任何事情——这个重复项将被a中的下一个唯一元素覆盖。
不同之处：我们将a[i]添加到数组中不包含重复项的部分（以n分隔），并将 n 增加 1。

int removeDuplicates(vector<int>& nums) {
    if(nums.empty())
        return 0;
    int n = 0;
    for(int i = 0; i < nums.size(); ++i){
        if(i == 0 || nums[i] != nums[i - 1]){
            nums[n++] = nums[i];
        }
    }
    return n;
    }

该问题具有线性时间复杂度和恒定空间复杂度（使用这种技术解决问题通常都是这种情况）。

对颜色进行排序

给定一个包含 n 个红色、白色或蓝色对象的数组，请对它们进行原地排序，使相同颜色的对象相邻，颜色顺序为红、白、蓝。这里，我们将使用整数 0、1 和 2 分别表示红色、白色和蓝色。
注意：本题不应使用库中的排序函数。

例子：

输入：[2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

解决方案

这次的团体是：

小于 1
等于 1
大于 1

我们可以通过三分球实现什么目标。

这个实现有点棘手，所以一定要彻底测试它。

void sortColors(vector<int>& nums) {
    int smaller = 0, eq = 0, larger = nums.size() - 1;
    while(eq <= larger){
        if(nums[eq] == 0){
            swap(nums[smaller], nums[eq]);
            ++smaller; ++eq;
        } else if (nums[eq] == 2) {
            swap(nums[larger], nums[eq]);
            --larger;
        } else {
            eq++;
        }
    }
}

由于需要遍历数组进行排序，时间复杂度为 O(N)。空间复杂度为 O(1)。

出于好奇，这是Dijkstra 描述的荷兰国旗问题的一个例子。

删除链表末尾的第 n 个节点

给定一个链表和一个数字 n，编写一个函数返回链表末尾第 n 个节点的值。

解决方案

这是双指针技术最常见的变体之一：引入偏移量，使得其中一个指针达到某个条件，而另一个指针处于您感兴趣的位置。

在这种情况下，如果我们移动其中一个指针f n 次，然后同时将两个指针前进一个节点，当f到达列表末尾时，另一个指针s将指向我们要删除的节点之前的节点。

确保定义 n = 1 的含义（最后一个元素还是最后一个元素之前的元素？），并避免出现偏差错误。

时间和空间复杂度与前面的问题相同。

2. 指针以不同的速度移动

现在，你将有两个以不同速度移动的指针：每次迭代时，其中一个指针前进一个节点，另一个指针前进两个节点。我们可以利用这种变化来：

获取链表的中间元素
检测链接列表中的循环
ETC

像往常一样，只要我举出一些例子，就会变得更加清楚。

查找未知大小的链表的中间节点

给定一个非空的单链表，其头节点为 head，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。

例 1：

输入：[1,2,3,4,5]
输出：此列表中的节点 3

解决方案

用两遍就能解决这个问题：第一遍我们计算列表的大小L，第二遍我们只前进L/2 个节点来找到列表中间的元素。这种方法在时间上具有线性复杂度，在空间上具有常数复杂度。

我们如何使用两个指针一次性找到中间元素？

如果其中一个指针f的移动速度是另一个指针s 的两倍，那么当f到达末尾时，s将位于列表的中间。

这是我的 C++ 解决方案。测试代码时，请务必考虑一些特殊情况（例如空列表、奇偶大小的列表等）。

ListNode* middleNode(ListNode* head) {
       ListNode* slow = head;
       ListNode* fast = head;

       while (fast != nullptr && fast->next != nullptr) {
           slow = slow->next;
           fast = fast->next->next;
       }
       return slow; 
    }

检测链接列表中的循环

给定一个链表，判断其中是否存在循环。为了表示给定链表中的循环，我们使用一个整数 pos，它表示链表中尾部连接的位置（从 0 开始）。如果 pos 为 -1，则表示链表中不存在循环。

例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个循环，其尾部连接到第二个节点。

解决方案

最简单的解决方案是将所有节点添加到一个哈希集合中。当我们遍历该列表时，如果遇到一个已经添加到集合中的节点，则存在循环。如果到达列表末尾，则不存在循环。

它的时间复杂度为 O(L)，其中L是列表的长度，空间复杂度为 O(L)，因为在最坏的情况下 - 没有循环 - 我们需要将列表中的所有元素添加到哈希集中。

时间复杂度无法提升。然而，空间复杂度可以降低到 O(1)。想一想，如果两个指针以不同的速度移动，如何实现这一点。

我们把这些指针称为快速指针和慢速指针。慢速指针每次访问一个节点，快速指针就会向前移动两个节点。为什么？

如果快速到达列表末尾，则列表不包含任何循环。
如果存在循环，由于快速移动的速度是慢速的两倍，因此快速节点追上慢速节点只是时间问题（更准确地说是迭代），将两者都指向同一个节点，这表明存在循环。

现在，让我们将此解决方案转化为代码：

bool hasCycle(ListNode *head) {
        ListNode* slow = head, *fast = head;
        while(fast){
            slow = slow->next;
            fast = fast->next;
            if(!fast)
                break;
            fast = fast->next;
            if(slow == fast)
                return true;
        }
        return false;
    }

查找重复的数字

给定一个数组 nums，包含 n + 1 个整数，每个整数介于 1 到 n 之间（含 1 和 n）。请证明至少存在一个重复的数字。假设只有一个重复的数字，请找出这个重复的数字。

例 1：

输入：[1,3,4,2,2]
输出：2

解决方案

这与前面的问题/解决方案相同，但针对的是数组而不是链表。

int findDuplicate(const vector<int>& nums) {
    int slow = nums[0], fast = slow; 
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while(slow != fast);

    slow = nums[0];
    while(slow != fast){
        slow = nums[slow];
        fast = nums[fast];            
    }

    return slow;
}

挑战

以下是可以使用此技术解决的更多问题：

3.滑动窗口

滑动窗口技术简化了寻找满足特定条件的最佳连续数据块的任务：

最长的子数组...
包含...的最短子串
ETC

你可以把它看作是双指针技术的另一种变体，其中指针会根据特定条件分别更新。下面是解决此类问题的基本方法（伪代码）：

Create two pointers, l, and r
Create variable to keep track of the result (res)

Iterate until condition A is satisfied:
  Based on condition B:
update l, r or both
Update res
Return res

最长无重复字符的子字符串

给定一个字符串，找出不包含重复字符的最长子字符串的长度。

例 1：

输入：“abcabcbb”
输出：3
解释：答案是“abc”，长度为 3

解决方案

找到不包含重复字符的最长子字符串的长度听起来很像找到满足特定条件的最佳*连续数据块*。

根据我上面描述的食谱，您将需要：

两个指针l和r来定义子字符串s。
变量sol用于存储迄今为止我们看到的最长子字符串的长度。
一种跟踪组成s的字符的方法：一组，如所见，对于这种情况来说将是完美的。

迭代字符串时：

如果当前字符在seen* 中，则必须增加 *l以开始从s的开头删除元素。
否则，将字符添加到seen，将r向前移动并更新sol。

int lengthOfLongestSubstring(const string& s) {
    int sol = 0;
    int l = 0, r = 0;
    unordered_set<int> seen;
    while(r < s.size()) {
        const auto find = seen.find(s[r]);
        if(find == seen.end()) {
            sol = max (sol, r - l + 1);
            seen.insert(s[r]);
            ++r;
        } else {
            seen.erase(s[l++]);
        }
    }
    return sol;
}

挑战

为了进行更多练习，您可以尝试以下问题：

可能有更简单的解决方案，但请专注于使用这项技术来更好地掌握它。

基于递归的技术

4.动态规划

我已经发表了一篇关于这个主题的文章，您可以在这里找到。

5.回溯

回溯背后的理念是以一种智能的方式探索问题的所有潜在解决方案。它会逐步构建候选解决方案，一旦确定某个候选解决方案不可行，就会回溯到先前的状态并尝试下一个候选解决方案。

回溯问题会给你提供一系列选择：

你应该把这块棋子放在这个位置吗？
您应该将此数字添加到集合中吗？
您下一步应该在这个位置尝试这个数字吗？
ETC

在您选择其中一个选项后，它会为您提供一个新的选择列表，直到您达到没有更多选择的状态：要么您找到了解决方案，要么没有解决方案。

直观地看，你每次选择都会从树的根部开始移动，直到到达叶子。回溯算法的基本高级方法（伪代码）如下：

boolean backtracking(Node n){
    if(isLeaf(n) {
        if(isSolution(candidate)){
            sol.add(candidate);
            return true;
        } else {
            return false;
        }
    }

    //Explore all children
    for(child in n) {
        if(backtracking(child))
            return true;
    }

    return false;
}

这当然可以根据问题而改变：

如果您需要所有解决方案，则辅助函数将返回任何内容（void），以避免在我们找到第一个解决方案时停止。
要回溯，你可能必须先将程序恢复到之前的状态，然后才能继续前进
选择一个孩子后，您需要检测候选解决方案是否可行：可行的定义取决于问题
ETC

但核心思想是一样的：以系统的方式检查所有路径，一旦当前路径不再可行，就回溯。

N皇后

n 皇后难题是在 n×n 棋盘上放置 n 个皇后的问题，使得没有两个皇后互相攻击
给定一个整数 n，返回 n 皇后难题的所有不同解决方案。

每个解决方案都包含一个不同的 n 皇后棋盘配置，其中“Q”和“。”分别表示皇后和空白处。

例子：

输入：4
输出：[ [".Q..", // 解决方案 1 "...Q", "Q...", "..Q."],

["..Q.", // 解决方案 2
"Q...",
"...Q",
".Q.."]
]

解释：如上所示，四皇后难题存在两个不同的解决方案。

解决方案

这是一个经典的回溯问题

这里我们需要所有的解决方案，这就是为什么递归函数不返回任何内容，正如我在本节介绍中所解释的那样。
现在先别太担心isViableSolution函数。试试我给你的这个方法（略作修改）。

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> solutions;

        /** 

        This is usually solved with a vector of integers, 
        where each integer represents the position of the queen in that column.
        This particular problem expects strings.
        Each string represents a column
        */
        vector<string> board(n, string(n, '.'));

        solveBoard(solutions, board, 0, n);   

        return solutions;
    }

    void solveBoard(vector<vector<string>>& solutions, vector<string>& board, int col, int n){
        if(col == n){
            solutions.push_back(board);
            return;
        }

        for(int row = 0; row < n; row++){
            if(isViableSolution(board, row, col)){                
                board[row][col] = 'Q';
                solveBoard(solutions, board, col + 1, n);
                //Backtracking - we bring our board to the previous state
                board[row][col] = '.';  
            }
        }        
    }

    bool isViableSolution(vector<string>& board, int row, int col){
        int n = board.size(); 

        for(int x = 1; x <= col; x++){
            if(board[row][col-x] == 'Q')
                return false;
        }

        for(int x = 1; row - x >= 0 && col >= x; x++){
            if(board[row-x][col-x] == 'Q') 
                return false;
        }

        for(int x = 1; row + x < n && col >= x; x++){
            if(board[row+x][col-x] == 'Q') 
                return false;
        } 

        return true;
    }
};

字母组合

给定一个包含 2-9（含）数字的字符串，返回该数字可能代表的所有字母组合（查看链接中的图表）。注意，1 不映射到任何字母。

例子：

输入：“23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。

解决方案

对于输入中的每个数字，你都有多个字母可供选择。如果你能画一棵树（我就是这样做的），树上的枝条源于你做出的不同选择，那么你很可能可以运用回溯法。

注意：在开始解决任何问题之前，请尝试不同的方法：动态规划、贪婪算法、分而治之、算法和数据结构的组合等。编码是最后一步。

我的解决方案（用 C++ 编写）：

vector<string> letterCombinations(const string &digits) {
    if(digits.empty())
        return {};
    const vector<string> letters {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> sol;
    string candidate (digits.size(), ' ');
    h(sol, 0, candidate, letters, digits);
    return sol;
}

void h(vector<string> &sol, int idx, string &candidate, const vector<string> &letters, const string &digits){
    if(idx == digits.size()){
        sol.push_back(candidate);
        return;
    }

    for(const char &c : letters[digits[idx] - '0']) {
        candidate[idx] = c;
        h(sol, idx + 1, candidate, letters, digits);            
    }
}

因为我已经知道解决方案的大小，所以我candidate用这个大小初始化了我的，并且只修改了位置处的字符idx。如果不知道大小，可以这样做：

string candidate; //instead of string candidate (digits.size(), ' ');
…
for(const char &c : letters[digits[idx] - '0']) {
    candidate.push_back(c);
    h(sol, idx + 1, candidate, letters, digits);            
    candidate.pop_back();
}

数独解算器

编写一个程序，通过填充空白单元格来解决数独难题。打开链接即可查看更详细的描述，包括谜题的图片。

解决方案

在面试中，除非你时间充裕，否则你不需要实现isViableSolution，只需画个草图就行。我认识一位同事在现场面试时就遇到过这个问题。

虽然代码很长，但主要是因为isViableSolution的问题。除此之外，它与其他回溯问题并没有太大区别。

void solveSudoku(vector<vector<char>>& board){
        helper(board);
    }

    bool helper(vector<vector<char>>& board, int row = 0, int col = 0) {
        if(col == size){
           col = 0;
           ++row;
            if(row == size){
                return true;
            }
        }

        if(board[row][col] != '.'){
            return helper(board, row, col + 1);
        }

        for(char i = '1'; i <= '9'; ++i){
            if(isViableSolution(board, row, col, i)){
                board[row][col] = i;
                if (helper(board, row, col + 1))
                    return true;
            }
        }
        board[row][col] = '.';
        return false;
    }

    bool isViableSolution(const vector<vector<char>>& board, int row, int col, char c){
        for(const auto& n : board[row]){
            if(n == c)
                return false;
        }

        for(int r = 0; r < size; ++r){
            if(board[r][col] == c)
                return false;
        }

        const int br = row / nsize;
        const int bc = col / nsize;

        for(int i = 0; i < nsize ; ++i){
            for(int j = 0; j < nsize; ++j){
                if(c == board[3 * br + i][3 * bc + j])
                    return false;
            }
        }

        return true;
    }

挑战

6. 子集

我已经创建了一个通用的单独部分：

子集
组合
排列
ETC

因为从概念上讲它们是相似的：获取容器（数组、字符串等）的元素并根据某些规则从中创建子集。

您会注意到其中大多数都是回溯问题或非常相似。

子集

给定一组不同的整数 nums，返回所有可能的子集（幂集）。

注意：解决方案集不能包含重复的子集。

例子：

输入：nums = [1,2,3]
输出：[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

解决方案

对于每个索引i，您需要生成两个解决方案：

包含 a[i]
不包含 a[i] 的

直到到达数组的末尾。

以下是我们所讨论内容的一个简单实现。

vector<vector<int>> subsets(const vector<int>& nums) {
        vector<vector<int>> sol;
        vector<int> partial;
        h(sol, partial, nums);
        return sol;
    }
    void h(vector<vector<int>>& sol, vector<int>& partial, const vector<int>& nums, int idx = 0){
        sol.push_back(partial);
        if(idx == nums.size()){
            return;
        }

        for(int i = idx; i < nums.size(); ++i){
            partial.push_back(nums[i]);
            h(sol, partial, nums, i + 1);
            partial.pop_back();
        }        
    }

子集 - 包含重复项

这是上一个问题的变体。尝试修改我的代码，看看能否满足新的需求。修改内容不得超过 5 行。

祝你好运！

解决方案

vector<vector<int>> subsetsWithDup(vector<int> nums) {
        vector<vector<int>> sol;
        vector<int> partial;
        sort(nums.begin(), nums.end());
        h(sol, partial, nums);
        return sol;
    }
    void h(vector<vector<int>>& sol, vector<int>& partial, const vector<int>& nums, int idx = 0){
        sol.push_back(partial);
        if(idx == nums.size()){
            return;
        }

        for(int i = idx; i < nums.size(); ++i){
            if(i != idx && nums[i] == nums[i - 1])
                continue;
            partial.push_back(nums[i]);
            h(sol, partial, nums, i + 1);
            partial.pop_back();
        }        
    }

排列

给定一组不同的整数，返回所有可能的排列。

例子：

输入：[1,2,3]
输出：[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] #### 解决方案

与上一个问题非常相似，但这次我们需要考虑数组中所有候选元素。移动它们的方法是交换不同位置的元素。

vector<vector<int>> permute(const vector<int>& nums) {
        vector<vector<int>> sol;
        vector<int> p (nums);
        h(nums, sol, p);
        return sol;
    }
    void h(const vector<int> &nums, vector<vector<int>> &sol, vector<int> &p, int idx = 0){
        if(idx == nums.size()){
            sol.push_back(p);
            return;
        }
        for(int i = idx; i < nums.size(); ++i){
            swap(p[idx], p[i]);
            h(nums, sol, p, idx + 1);
            swap(p[idx], p[i]);
        }
    }

重复排列

给定一个可能包含重复项的数字集合，返回所有可能的唯一排列。

例子：

输入：[1,1,2]
输出：[[1,1,2], [1,2,1], [2,1,1] ]

解决方案

我们可以在这里应用与之前组合相同的技巧。如果你想不出这个“技巧”，你可以使用一个集合来存储解决方案，然后根据这个集合创建并返回一个数组。

void helper(vector<vector<int>>& res, int pos, vector<int>& nums) {
        if(pos == nums.size()) {
            res.push_back(nums);
            return;
        }
        for(int i = pos; i < nums.size(); ++i) {
            if(i != pos && nums[i] == nums[pos])
                continue;
            swap(nums[i], nums[pos]);
            helper(res, pos + 1, nums);
        }
        rotate(nums.begin() + pos, nums.begin() + pos + 1, nums.end());
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if(nums.empty())
            return {};

        sort(nums.begin(), nums.end());

        vector<vector<int>> sol;
        helper(sol, 0, nums);

        return sol;
    }

正如你所见，解决大量问题并不需要学习文献中提到的每一个数据结构和算法。真正有价值的、可以训练的是系统地思考问题的能力，以及将想法转化为代码的技能。

挑战

额外练习：

排序和搜索

7. 排序

排序本身并不是一个解决问题的技术，但正如您在前面章节中看到的那样，我们可以通过对输入进行排序或假设它已排序然后应用其他技术之一来解决许多问题。

当你面临一个新问题时，问问自己：

我可以对输入进行排序吗？例如，有时您必须返回索引，因此排序不是一种选择
如果元素已排序，这个问题将如何变化？
排序如何影响整体复杂度？最佳排序算法的复杂度为 O(n log n) - 整数排序可以在 O(n) 内完成。

例如，我们的第一个问题（两个数之和）可以用双指针技术在线性时间内求解，因为输入是排序的。但是，如果必须排序，复杂度就变成了 O(n log n)。

这里有几个问题，在对输入进行排序后可以轻松解决。

其他解决方案以空间换取时间，因此在开始编写任何代码之前值得考虑它们。

有效的字谜

给定两个字符串 s 和 t，编写一个函数来确定 t 是否是 s 的字谜。

例 1：

输入：s =“anagram”，t =“nagaram”
输出：true

示例 2：

输入：s =“rat”，t =“car”
输出：false

解决方案

根据定义，如果两个字符串包含相同的字符，但顺序不同，则它们为字母重排的字符串。因此，我们可以简单地对两个字符串进行排序，然后进行比较。总时间复杂度为 O(n log n)。

bool isAnagram(string s, string t) {
        if(s.size() != t.size())
            return false;

        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return  s == t;
}

两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

解决方案

你可以通过对两个数组进行排序并使用基于双指针的方法来解决此问题。在阅读我的解决方案之前，请先尝试一下。

假设我们有以下数组：

A = [1,2,4,5]
B = [2,3,5,7,9,11]

还有两个指针，l代表 A，r代表 B，每个数组从索引 0 开始。

A[l] = 1
B[r] = 2

我们需要增加l来查看 A 是否有 2：B 不能在r右侧包含 1 ，因为它已排序。

简而言之，我们比较两个元素：

如果它们相同，我们将它们包含到表示两个数组交集的数组中，并推进两个指针
如果它们不同，我们就移动指向两个元素中最小元素的指针。

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> sol;
        int i = 0, j = 0;
        while( i < nums1.size() && j < nums2.size()) {
            if(nums1[i] == nums2[j]) {
                sol.push_back(nums1[i]);
                ++i;
                ++j;
            } else if(nums1[i] > nums2[j]) {
                ++j;
            } else {
                ++i;
            }
        }
        return sol;
    }

这种方法的时间复杂度是 O(n log n) - 即使双指针部分是线性的 - 空间复杂度是 O(1) - 当然不包括存储交集所需的空间，在这种情况下我们可以说它是 O(min(length(A), length(B))。

挑战

K 个距离原点最近的点。在另一部分中，我将提出一个不同的解决方案，速度会稍微快一些。
最大数

8. 间隔

我见过的大多数与间隔相关的问题可以归结为：

将间隔建模为两个元素的数组、一对/元组或自定义类（这是最干净的选项）
对输入进行排序
遍历排序后的数组，并根据间隔的开始/结束决定做什么

您可以将其视为另一种类型的问题，在对输入进行排序后可以简化该问题，这就是我将其包含在本节中的原因。

根据我刚才描述的内容，我在这里分享两个练习的答案。在阅读我的答案之前，请先尝试一下。

合并间隔

给定一个区间集合，合并所有重叠区间。

例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：由于区间 [1,3] 和 [2,6] 重叠，因此将它们合并为 [1,6]。

解决方案

vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto& i1, const auto& i2){
           return i1[0] < i2[0];
        });
        int i = 0;
        vector<vector<int>> sol;
        vector<int> curr(2);
        while(i < intervals.size()){
            curr = intervals[i++];
            while(i < intervals.size() && intervals[i][0] <= curr[1]){
                curr[1] = max(curr[1], intervals[i][1]);
                ++i;
            }
            sol.push_back(curr);
        }
        return sol;
    }

区间列表交叉点

给定两个闭区间列表，每个区间列表都是两两不相交的，并且按排序。返回这两个区间列表的交集。

解决方案

vector<vector<int>> intervalIntersection(const vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> sol;
    int i = 0, j = 0;

    while(i < A.size() && j < B.size()){
        const int lo = max(A[i][0], B[j][0]);
        const int hi = min(A[i][1], B[j][1]);
        if(lo <= hi){
            sol.push_back({lo, hi});
        }
        if(A[i][1] < B[j][1])
            ++i;
        else
            ++j;
    }
    return sol;
}

9.二分查找的变体

二分查找是一种搜索算法，可以应用于已排序的数据结构（如数组或二叉搜索树），时间复杂度为 O(log n)，空间复杂度为 O(1)。

你可能不知道的是它实现中最常见的 bug。假设我们在 [l,r] 范围内的元素中执行二分查找，中间的元素通常计算如下：

const int m = (l + r) / 2;

你能发现这里的问题吗？

此行可能会溢出。计算此中间元素的安全方法是：

const int m = l + (r - l) / 2;

以下是使用 C++ 模板实现的二分查找的基本实现。如果你理解了它的工作原理以及如何正确实现它，那么很多只需对需求稍作调整，或者伪装成二分查找的问题，你就能解决。

template<typename T>
int binary_search(const vector<T>& v, int k) {
    int l = 0, r = v.size() - 1;
    while(l<=r) {
     const int m = l + (r - l) / 2;
     if(k == v[m]) {
         return m;
     } else if (k > v[m]) {
         l = m + 1;
     } else {
         r = m - 1;
     }
    }
    return -1;
}

整数平方根

计算并返回 x 的平方根，其中 x 保证为非负整数。
由于返回类型为整数，因此小数部分将被截断，仅返回结果的整数部分。

例 1：

输入：4
输出：2

解决方案

我们需要在 [0, x] 范围内找到一个已排序的数字。这听起来很像二分查找问题。

了解这一点并不重要，但我们可以进行一些优化：

如果x为 0 或 1，则其平方根为x。这样我们就可以从 2 开始测试数字了。
范围的上限可以降低到 x/2，因为 (x/2)^2 = x^2/4 >= x => x >= 4，这对于 [2,…] 范围内的任何整数都是正确的

这样，我们可以在 [2, x/2] 内搜索并加快速度。

int mySqrt(int x) {
        if(x == 0 || x == 1)
            return x;
        int sol = 1;
        int l = 2, r = x / 2;
        while(l <= r){
            const long m = l + (r - l) / 2;
            if(m * m == x)
                return m;
            else if(m * m > x){
                r = m - 1;
            } else {
                sol = m;
                l = m + 1;
            }
        }
        return sol;
    }

挑战

玩得开心！

10.广度优先搜索

这是探索树和图需要掌握的技巧之一。由于许多问题都可以用图来建模，所以你必须掌握这项技巧。要实现它，我们只需要使用一个队列q ，并将我们处理的q节点的子节点添加到这个队列中。。

在迭代中的任何给定点，BFS 都会访问距离原点相同距离的所有节点。看完这些例子之后，这一点会更加清晰。

字梯

给定两个单词（beginWord 和 endWord）和一个字典的单词列表，找到从 beginWord 到 endWord 的最短转换序列的长度，使得：

每次只能更改一个字母。
每个转换后的单词都必须存在于单词列表中。

笔记：

如果不存在这样的转换序列，则返回 0。
所有单词的长度相同。
所有单词仅包含小写字母。
您可以假设单词列表中没有重复的单词。
您可以假设 beginWord 和 endWord 非空并且不一样。

例 1：

输入：
beginWord =“命中”，
endWord =“ cog”，
wordList = [“热”，“点”，“狗”，“很多”，“对数”，“齿轮”]
输出：5
解释：由于一个最短的变换是“hit” -> “hot” -> “dot” -> “dog” -> “cog”，返回其长度 5。

解决方案

我在亚马逊的现场面试中被问到了这个问题。我们的想法是用一个图来建模这个问题：

节点代表单词
边连接仅相差一个字母的单词

按照这种思路，这个问题等同于在图中寻找两个节点之间的路径，BFS 可以解决这个问题。由于所有边的权重相同 (1)，我们不需要 Dijkstra 或任何其他更复杂的算法。

int ladderLength(const string &beginWord, const string &endWord, const vector<string>& wordList) {
        if(beginWord == endWord)
            return 1;
        unordered_set<string> dict(wordList.begin(), wordList.end());
        queue<string> todo;
        todo.push(beginWord);
        dict.erase(beginWord);
        int ladder = 1;
        while (!todo.empty()) {
            ladder++;
            int n = todo.size();
            for (int i = 0; i < n; i++) {
                string word = todo.front();
                todo.pop();
                for (int j = 0; j < word.size(); j++) {
                    char c = word[j];
                    for (int k = 0; k < 26; k++) {
                        word[j] = 'a' + k;
                        if (dict.find(word) != dict.end()) {
                            if (word == endWord) {
                                return ladder;
                            }
                            todo.push(word);
                            dict.erase(word);
                        }
                     }
                    word[j] = c;
                }
            }
        }
        return 0;
    }

访问DFS部分后：

如果我们改用DFS会发生什么？你觉得有什么好处/坏处吗？

顺序层级树遍历

给定一棵二叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

打开链接查看问题的图形描述。

解决方案

您只需在这里对标准 BFS 算法进行一点调整：您需要知道每个级别需要处理队列中的多少个元素。

这种方法可以应用于许多其他问题。

vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root)
            return {};
        vector<vector<int>> sol;
        queue<TreeNode*> q;
        q.push(root);
        vector<int> partial;
        while(!q.empty()){
            int size = q.size();
            while(size-->0){
                auto n = q.front();
                partial.push_back({n->val});
                q.pop();
                if(n->left)
                    q.push({n->left});
                if(n->right)
                    q.push({n->right});
            }
            sol.push_back(partial);
            partial.clear();
        }
        return sol;
    }

挑战

我来提出一种不同的挑战：构建一些东西，而不是解决抽象的问题。我觉得这更有趣，你可以把它们添加到你的 Github 个人资料中。以下是两个例子：

网络爬虫使用 BFS 探索网站上的所有链接。
扫雷舰

11.深度优先搜索

其目的与广度优先搜索 (BFS) 类似：探索树和图。深度优先搜索 (DFS) 不能保证找到两点之间的最短路径，但它可以找到任何现有的路径。

它通常比 BFS 实现起来更短。有些人觉得它更容易实现。而另一些人，由于递归调用的原因，感觉不太容易。这取决于你。只要确保考虑到堆栈大小变大时可能出现的堆栈溢出问题即可。

有些问题用 DFS/递归来解决会容易得多，值得练习。

岛屿数量

给定一个由“1”（陆地）和“0”（水）组成的二维网格图，计算其中岛屿的数量。岛屿由水平或垂直连接相邻陆地而成，周围环绕着水。你可以假设网格的四条边都被水包围。

例子：

输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"]]
输出：1

解决方案

我在亚马逊的第一次电话面试中遇到了这个问题。

一旦你看到矩阵，就把它想象成一个图。这个问题（及其变体）非常简单：

迭代矩阵
每找到 1 个，计数器就会增加，岛屿就会沉没

为了使岛屿沉没，您需要访问矩阵中所有周围的 1，这相当于访问该节点的所有邻居以及它的所有邻居，这听起来很像一个递归问题。

您也可以尝试使用 BFS 来解决这个问题，但 DFS 要短得多。

int numIslands(vector<vector<char>>& grid) {
        int numIslands = 0;
        for(int r = 0; r < grid.size(); ++r){
            for(int c = 0; c < grid[0].size(); ++c){
                if(grid[r][c] == '1'){
                    ++numIslands;
                    sinkIslands(grid, r, c);
                }
            }
        }
        return numIslands;
    }

    const vector<vector<int>> dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    void sinkIslands(vector<vector<char>> &m, int r, int c){
        m[r][c] = '0';
        for(const auto &d : dirs){
            const int nr = r + d[0];
            const int nc = c + d[1];
            if(isValid(m, nr, nc)){
                sinkIslands(m, nr, nc);
            }
        }
    }

    bool isValid(vector<vector<char>> &m, int r, int c){
        return r >= 0 && r < m.size() && c >= 0 && c < m[0].size() && m[r][c] == '1';
    }

对称树

给定一棵二叉树，检查它是否是其自身的镜像（即，围绕其中心对称）。

解决方案

许多与树相关的问题都有相对简单的递归解决方案。这个问题可以用广度优先搜索 (BFS) 来解决，但深度优先搜索 (DFS) 让它变得更容易。

我把这个留在这里作为练习。如果你遇到困难，就用我的解决方案吧。

bool isSymmetric(TreeNode* root) {
        if(!root)        
            return true;
        return helper(root->left, root->right);
    }
    bool helper(TreeNode* p, TreeNode* q){
        if(!p && !q)
            return true;
        if(!p || !q)
            return false;
        return p->val == q->val && iS(p->left, q->right) && iS(p->right, q->left);
    }

挑战

尝试使用我之前提供的 BFS 挑战和练习，并用 DFS 来实现它们。此外，为了进行更多练习，可以尝试以下练习：

12.拓扑排序

你可以把这个算法看作是 DFS 的一个应用。它的实现只需要对常规 DFS 进行一点小小的改动：处理完一个节点的所有子节点后，将该节点添加到堆栈中。

就这么简单。

直观理解该算法实现的最佳方法是想象一堆任务，其中一些任务依赖于其他任务（任务 1 必须等到任务 2 完成才能开始）。拓扑排序将列出所有这些任务，并保留这种依赖关系结构。

让我们用这个算法解决一个问题。

课程安排二

你总共需要选修 n 门课程，编号从 0 到 n-1。有些课程可能有先修课程，例如，要选修课程 0，你必须先选修课程 1，这可以用一对数来表示：[0,1]

给定课程总数和先修课程对列表，返回完成所有课程所需选修的课程顺序。正确的顺序可能有多个，只需返回其中一个即可。如果无法完成所有课程，则返回一个空数组。

例 1：

输入：2，[[1,0]]
输出：[0,1]
解释：总共有 2 门课程要选。要选修课程 1，你必须先完成课程 0。因此正确的课程顺序是 [0,1]。

示例 2：

输入：4, [[1,0],[2,0],[3,1],[3,2]]
输出：[0,1,2,3] 或 [0,2,1,3]
解释：总共有 4 门课程要选。要选修课程 3，你必须先完成课程 1 和课程 2。课程 1 和课程 2 必须在你完成课程 0 之后选修。因此，一种正确的课程顺序是 [0,1,2,3]。另一种正确的顺序是 [0,2,1,3]。

解决方案

这是经典的拓扑排序问题。有很多课程需要学习，其中一些课程依赖于其他课程。这可以用有向图建模。拓扑排序会返回你需要学习的课程顺序，以便完成所有课程。

应用拓扑排序的先决条件是图是有向且无环的。从问题描述中我们可以看出，该图是有向的。我们可以检测它是否包含任何环，并在同一遍历中计算拓扑排序。

一种更间接但仍然有效的方法是首先检查它是否有循环，并且只有当没有循环时才计算拓扑排序。

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(numCourses, vector<int>(0));

        for(const auto &p : prerequisites){
            int u = p[0];
            int v = p[1];
            adj[u].push_back(v);
        }

        vector<bool> white(numCourses, true),
                     grey(numCourses), 
                     black(numCourses);
        vector<int> sol (0);        
        for(int i = 0; i < numCourses; ++i){
            if(white[i] && hasCycle(adj, i, white, grey, black, sol)){
                return {};
            }
        }
        return sol;
}

    bool hasCycle(const vector<vector<int>>& adj, int i, vector<bool> &white, vector<bool> &grey, vector<bool> &black, vector<int>& sol){
        //We have started exploring this node
        white[i] = false;
        grey[i] = true;

        for(const auto & n : adj[i]){
            if(black[i])
                continue;
            if(grey[n] || hasCycle(adj, n, white, grey, black, sol))
                return true;
        }

        grey[i] = false;
        black[i] = true;
        sol.push_back(i);
        return false;
    }

挑战

这里您可以找到更多问题来练习。

玩得开心！

扩展基本数据结构

13. 出队

我见过数据结构主要用作实现本文前面提到的滑动窗口技术的另一种方式。它与标准 FIFO 队列的唯一区别在于，你可以在队列的两端进行操作（插入和删除元素）。

就是这样。很简单。

让我们看看这种微小的改变如何简化这些问题。

滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口，该窗口从数组的最左侧向最右侧移动。窗口中只能看到这 k 个数字。每次滑动窗口向右移动一位。返回最大的滑动窗口。

*注意：打开链接可以更好地理解问题（有图片）。*

例子：

输入：nums = [1,3,-1,-3,5,3,6,7], 且 k = 3
输出：[3,3,5,5,6,7]

解决方案

我们将使用出队队列来存储索引，而不是值。我们需要它来知道哪些元素仍然是滑动窗口的一部分。每次迭代，有四件事要做。

删除出队中当前滑动窗口之外的元素（每次迭代一个）
删除出队中所有小于当前元素的元素，因为它们不能表示该滑动窗口的最大值
将当前元素添加到双端队列
一旦完成了第一个滑动窗口，我们就可以开始向解决方案中添加元素了。根据设计，出队队列最前面的元素将包含滑动窗口的最大值，这正是我们感兴趣的。

该技术可用于查找数组中连续数据块的最小值或其他属性。

vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    vector<int> sol;

    deque<int> dq;
    for (int i=0; i<nums.size(); i++) {
        // Step 1
        if (!dq.empty() && dq.front() == i-k) 
            dq.pop_front();

        // Step 2
        while (!dq.empty() && nums[dq.back()] < nums[i])
            dq.pop_back();

        // Step 3
        dq.push_back(i);

        // Step 4
        if (i >= k-1) 
            sol.push_back(nums[dq.front()]);
    }
    return sol;
}

挑战

设计您自己的循环出队，以充分掌握此数据结构的内部结构。

14.字典树

理解 trie 的最好方式是将其视为树的扩展，在 trie 的不同分支之间移动时，可以存储形成单词的字符。

有一些变体，其中存储后缀而不是前缀，其中使用压缩来减少 trie 的大小等。但从根本上讲，它是另一种类型的树。

它们随处可见：

自动完成
拼写检查器
IP路由
最长前缀/后缀匹配
ETC

实现 trie

使用插入、搜索和startsWith方法实现trie树。

解决方案

下面是一个简单的字典树实现（当然，是为了面试）。与树相比，你只需要：

一个额外的布尔值，用于指示该节点是否标记单词的结尾
用于存储指向节点子节点的指针的数据结构：哈希表、字符数组等。

class Trie {
private:
    struct Node{
        bool isWord;
        unordered_map<int, Node*> children;
        Node() : isWord(false) {}
    };

    Node* findNode(const string &word){
        Node* curr = root;
        for(int i = 0; i < word.size() && curr; ++i)
            curr = curr->children[word[i] - 'a'];
        return curr;
    }

public:
    Node* root;
    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    void insert(const string &word) {
        Node * curr = root;
        for(int i = 0; i < word.size(); ++i){
            const char c = word[i] - 'a';
            if(!curr->children[c]){
                Node* newChild = new Node();
                curr->children[c] = newChild;
            } 
                curr = curr->children[c];
        }
        curr->isWord = true;
    }

    /** Returns true if the word is in the trie. */
    bool search(const string &word) {
        Node* curr = findNode(word);
        return curr ? curr->isWord : false;
    }

    /** Returns true if there is any word in the trie that starts with the given prefix. */
    bool startsWith(const string &prefix) {
        Node* curr = findNode(prefix);
        return curr ? true : false;
    }
};

单词搜索 II

给定一个二维棋盘和字典中的单词列表，找出棋盘上的所有单词。每个单词必须由相邻单元格的字母构成，“相邻”单元格是指水平或垂直相邻的单元格。同一个字母单元格在一个单词中不能出现超过一次。

例子：

输入：board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words = ["oath","pea","eat","rain"]
输出：[“吃”，“誓言”]

解决方案

这可能不是解决这个问题的最简单的方法，但它是字典树的明显应用。

每一步，你都会构建一些候选字符串，并需要检查它是否属于字典。包含字典中所有单词的哈希集会提供非常好的性能。那么，为什么还要费心使用字典树呢？因为字典树可以告诉你这条路径是否值得探索，从而提高我们解决方案的效率。

在我们前面的例子中，假设我们形成字符串“oa”。

我们可以检查这个前缀（潜在单词）是否存在于我们的字典树中。它存在，因为我们添加了单词“oath”。现在假设我们继续在棋盘上移动，并形成了字符串“oaa”。

在我们的字典树中，没有包含前缀“oaa”的单词，所以我们可以在此时回溯。

对于包含所有单词的哈希集，您无法进行这种类型的前缀匹配，除非您创建两个不同的表：一个用于前缀，另一个用于单词。

这是一个复杂的问题，因为它结合了不同的元素，而且不容易实现，所以如果需要尝试几次（没有双关语）才能解决，也不要气馁。

const vector<vector<int>> dirs {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    struct Trie{
        struct Node{
            bool isWord;
            unordered_map<char, Node*> children;
            Node() : isWord(false){}
        };

        Node* root;

        Trie(){root = new Node();}

        void insert (const string& w){
            Node* cur = root;
            for(const auto &c : w){
                if(cur->children.find(c) == cur->children.end()){
                    cur->children[c] = new Node();
                }
                cur = cur->children[c];
            }
            cur->isWord = true;
        }

        bool hasPrefix(const string &prefix){
            Node* cur = root;
            for(const auto &c : prefix){
                if(cur->children.find(c) == cur->children.end()){
                    return false;
                }
                cur = cur->children[c];
            }
            lastNode = cur;
            return cur != nullptr;
        }

        bool isValidWord(const string &w){
            if(lastNode){
                bool res = lastNode->isWord;
                return res;
            }
            Node* cur = root;
            for(const auto &c : w){
                cur = cur->children[c];
                if(!cur){
                    return false;
                }
            }
            lastNode = cur;
            return lastNode->isWord;
        }

        void deleteWord(){
            lastNode->isWord = false;
            lastNode = nullptr;
        }
        Node* lastNode;
    };    

    Trie t;
public:
    vector<string> findWords(vector<vector<char>>& board, const vector<string>& words) {
        for(const auto& w : words)
            t.insert(w);

        vector<string> sol;
        for(int row = 0; row < board.size(); ++row){
            for(int col = 0; col < board[0].size(); ++col){
                string candidate (1, board[row][col]);
                if(t.hasPrefix(candidate))
                    addWords(board, row, col, sol, candidate);
            }
        }
        return sol;
    }

    void addWords(vector<vector<char>> &board, int row, int col, vector<string> &sol, string &candidate){
        if(t.isValidWord(candidate)){
            sol.push_back(candidate);
            t.deleteWord();
        }

        const char old = board[row][col];
        board[row][col] = '-';
        for(const auto &d : dirs){
            const int nrow = row + d[0];
            const int ncol = col + d[1];
            if(nrow >= 0 && nrow < board.size() 
                && ncol >= 0 && ncol < board[0].size() 
                    && board[nrow][ncol] != '.' 
                        && t.hasPrefix(candidate + board[nrow][ncol])){
                candidate.push_back(board[nrow][ncol]);
                addWords(board, nrow, ncol, sol, candidate);
                candidate.pop_back();
            }
        }
        board[row][col] = old;
    }

挑战

设计您自己的自动完成功能！

15. 同一数据结构的两个实例

有些问题可以通过使用同一数据结构的两个不同实例来解决，所以当你遇到问题时，最好记住这一点。我见过的最常见的情况是：

队列
堆栈
数组

不要将自己局限于这些。

从数据流中查找中位数

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

例如，

[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 将数据流中的整数添加到数据结构中。
double findMedian() - 返回迄今为止所有元素的中位数。

解决方案

class MedianFinder {
    priority_queue<int, vector<int>, less<int>> L;
    priority_queue<int, vector<int>, greater<int>> H;    
public:

    MedianFinder() { }

    void addNum(int x) {
        if(L.empty() == false && x > L.top()) {
            H.emplace(x);
        } else {
            L.emplace(x);
        }

        if(H.size() > L.size() + 1) {
            L.emplace(H.top());
            H.pop();
        } else if(L.size() > H.size() + 1) {
            H.emplace(L.top());
            L.pop();
        }
    }

    double findMedian() {
        if(H.size() == L.size()) {
            return (H.top() + L.top()) * 0.5;
        } else {
            return H.size() > L.size() ? H.top() : L.top();
        }
    }

};

挑战

按难度递增的顺序：

杂项

16.位操作

这部分值得写一篇单独的文章。这里我将列出一些基本的技巧和常见的位操作问题。

这是我找到的关于这个主题最全面的网站。可以作为参考。

缺失号码

给定一个包含 n 个不同数字的数组，这些数字取自 0、1、2、...、n，找出数组中缺失的数字。

例 1：

输入：[3,0,1]
输出：2

解决方案

只需使用 XOR 运算符即可解决此问题：

任何位与其自身进行异或都会产生 0 -> a ^ a = 0
任何位与 0 进行异或都会产生原始位 -> a ^ 0 = a
XOR 具有结合性 = a ^ (b ^ c) = (a ^ b ) ^ c

如果我们将数组中的所有数字（[0,n] 范围内的整数）与 [0 到 n] 中的所有整数进行异或运算，则这些对将产生零，并且缺失的数字将与 0 进行异或运算（结果为其自身），从而解决我们的问题。

int missingNumber(const vector<int>& nums) {
        int res = nums.size();
        for(int i = 0; i < nums.size(); ++i)
            res ^= (i ^ nums[i]);
        return res;
    }

两个的力量

给定一个整数，编写一个函数来确定它是否是二的幂。

解决方案

我在一次采访中得到了这个。

2 的幂可以用二进制表示为前导 1 和一些 0：

2：1
4：10
8：100
16：1000

有了它，判断一个数是不是2的幂就很简单了。如果你知道下面这行代码的作用，就能很快搞定（我相信你自己肯定能搞定）：

x & (x-1)

这个技巧很值得了解，因为它被经常使用。

bool isPowerOfTwo(int n) {
        return n > 0 ? (n & (n - 1)) == 0 : false;
}

1 的数量

编写一个函数，接受一个无符号整数并返回其具有的“1”位数（也称为汉明重量）。

例 1：

输入：0000000000000000000000000000001011
输出：3
解释：输入的二进制字符串 0000000000000000000000000000001011 总共有三个‘1’位。

解决方案

这个问题非常简单：遍历输入中的所有位并计算其中有多少个是 1。

尝试使用我在上一个练习中向您展示的技巧来提高该算法的性能（在平均情况下）。

int hammingWeight(uint32_t n) {
        int sum = 0;
        while (n != 0) {
            sum++;
            n &= (n - 1);
        }
        return sum;  
    }

挑战

这些是为了让你练习前面的技巧：

17. 前“K”个元素

这是另一类非常常见的问题。给定一个元素列表，要求返回前 K 个元素，并将top定义为：

最大/最小
距离某个点最近/最远
列表中最常见的
ETC

我在面试中看到过以下一些问题（或某种变体）。

没有任何单一的数据结构能够始终提供正确的解决方案，但以下元素非常有用：

哈希表
优先级队列
排序（输入或作为中间步骤）

优先级队列通常提供更好的复杂性。

最常用的 k 个词

给定一个非空单词列表，返回其中出现频率最高的 k 个元素。你的答案应按频率从高到低排序。如果两个单词的频率相同，则字母顺序较低的单词排在前面。

例 1：

输入：["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出：["i", "love"]
解释：“i” 和 “love” 是两个出现频率最高的词。请注意，“i” 排在 “love” 之前，因为字母顺序较低。

解决方案

非常简单：计算每个单词出现的次数（使用哈希表）并以某种方式返回 k 个最常见的元素。

对于最后一部分，您可以：

将所有元素及其频率放入数组中并对其进行排序

或者

使用优先级队列

了解第二种方法是值得的，因为它可以应用于其他问题。

这是一个使用优先级队列的 C++ 简单解决方案。

vector<string> topKFrequent(const vector<string>& words, int k) {
        map<string, int> freq;
        for(const auto &w : words)
            freq[w]++;

        auto l = [](const pair<int, string> & p1, const pair<int, string> &p2){
            if(p1.first == p2.first)
                return p1.second < p2.second;
            else
                return p1.first > p2.first;
        };
        priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(l)> pq(l);

        for(auto it = freq.begin(); it != freq.end(); ++it){
            if(pq.size() < k){
                pq.push({it->second, it->first});
            } else {
                auto top = pq.top();
                if(top.first < it->second){
                    pq.pop();
                    pq.push({it->second, it->first});
                }
            }
        }
        vector<string> sol (k);
        while(!pq.empty()){
            sol[--k] = pq.top().second;
            pq.pop();
        }
        return sol;
    }

变化

离原点最近的 K 个点

我们有平面上的点列表。找出距离原点 (0, 0) 最近的 K 个点。这里，平面上两点之间的距离就是欧几里得距离。

您可以按任意顺序返回答案。答案保证是唯一的（顺序除外）。

例 1：

输入：points = [[1,3],[-2,2]], K = 1
输出：[[-2,2]]

解决方案

显而易见的解决方案是计算到每个点的距离，将它们添加到数组中，排序并获取前 k 个点。这很好，但可以使用优先级队列进行改进。

我们使用一个最大堆，其中堆的根是堆中的最大元素。为什么是最大值？因为我们的堆包含距离原点最近的 K 个点，而根指向所有其他点中距离原点最远的元素。如果我们找到一个更接近这个点的点，它可能仍然比其他点更远，但我们需要删除当前的堆顶，并将这个新点添加到堆中。

typedef pair<int, vector<int>> pivi;
public:
    vector<vector<int>> kClosest(const vector<vector<int>>& points, int K) {

        auto l = [] (const pivi& p1, const pivi &p2) {
            return p1.first < p2.first;
        };

        priority_queue<pivi, vector<pivi>, decltype(l)> pq(l);

        for(const auto &p : points){
            //Avoid taking the square root. Won’t change the result and it’s faster
            const int d = p[0] * p[0] + p[1] * p[1];

            if(pq.size() < K)
                pq.push({d, {p[0], p[1]}});
            else if(pq.top().first > d){
                pq.pop();
                pq.push({d, {p[0], p[1]}});
            }
        }

        vector<vector<int>> sol;

        for(int i = 1; i <= K; ++i){
            sol.push_back(pq.top().second);
            pq.pop();
        }
        return sol;
    }

18. K路合并

这些问题也很常见。并非所有问题都有唯一的解决方法，但如果你知道如何解决合并两个列表的问题，你就能把合并 K 个列表的问题解决成一堆更简单问题的实例。正如我提到的，这是一种非常强大的方法，你应该时刻牢记。

合并 2 个排序列表

合并两个已排序的链表，并将其作为一个新的已排序列表返回。新列表应由前两个列表的节点拼接而成。
示例：
输入：1->2->4，1->3->4；输出：1->1->2->3->4->4

解决方案

我们用本文开头提到的双指针技术来解决这个问题。在本例中，我们遍历的是链表而不是数组，但思路是一样的。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dh(1), *curr = &dh;
    while(l1 && l2){
        if(l1->val <= l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    if(l1){
        curr->next = l1;
    } else if(l2) {
        curr->next = l2;
    }

    return dh.next;
}

合并 k 个排序列表

给定一个链表数组，每个链表按升序排序。

将所有链接列表合并为一个排序链接列表并返回。

例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表为：
[
1->4->5,
1->3->4,
2->6
]
将它们合并为一个排序列表：
1->1->2->3->4->4->5->6

解决方案

这是上一个问题的通用版本。正如我所说，你可以通过一次合并两个列表来将这个问题简化为上一个问题的多个实例。不过，这里我将提出一个更高效的解决方案。

现在，我们不再需要两个排序列表，而是有了 K 个。我们需要从所有列表中选取下一个最小元素来创建一个列表。由于它们是排序的，所以它会是其中一个列表的第一个元素。幸运的是，有一个数据结构可以在 O(1) 内返回其最小元素，并且插入复杂度为 O(log K)：优先级队列。

对于每个列表，我们向优先级队列添加一对，包含：

名单上的首位
用于记住元素所属列表的索引

弹出一个元素后，我们将其值添加到我们的解决方案中，并将该列表的新头添加到优先级队列中（该对存储列表的值和索引）。

利用这些信息，尝试解决这个问题。相比于不先尝试就阅读我的解决方案，你从中学到的东西会更多。

ListNode* mergeKLists(vector<ListNode*>& lists) {
    typedef pair<ListNode*, int> pni;

    auto comp = [](const pni & p1, const pni& p2) { 
        return p1.first->val > p2.first->val; 
    };

    priority_queue<pni, vector<pni>, decltype(comp)> pq (comp);

    for(int i = 0; i < lists.size(); ++i){
        if(lists[i]){
            pq.push({lists[i], i});
            lists[i] = lists[i]->next;
        }
    }

    ListNode dh(-1), *curr = &dh;

    while(!pq.empty()){
        const auto p = pq.top(); pq.pop();

        curr->next = p.first;
        curr = curr->next;

        ListNode* next = lists[p.second];
        if(next){
            int idx = p.second;
            pq.push({next, idx});
            lists[p.second] = lists[p.second]->next;
        }
    }
    return dh.next;
}

19.滚动哈希

Rabin Karp是一个很好的例子，展示了如何巧妙地利用滚动哈希函数设计一个简单高效的算法。它可以用于在文本t中查找字符串s。

为了能够重建该算法，您需要记住的基本思想如下：

这是对蛮力方法的改进，在蛮力方法中，您需要比较s和每个候选子字符串c，这是低效的。
如果两个字符串相同，它们将产生相同的哈希值。
反之则不然：两个不同的字符串可能会产生相同的哈希值。
使用滚动哈希函数，我们可以在 O(1) 内计算新字符串的哈希值

如果我们将所有这些放在一起，我们将有效地计算哈希值，并且仅当c和s具有相同的哈希值时才比较它们，从而减少比较次数，从而减少算法的平均复杂度（最坏的情况是，我们需要比较所有子字符串并回到蛮力方法）。

在文本中查找字符串

返回大海捞针中第一次出现的索引，如果针不是大海捞针的一部分，则返回 -1。

例 1：

输入：haystack = "hello",needle = "ll"
输出：2

示例 2：

输入：haystack = "aaaaa",needle = "bba"
输出：-1

解决方案

基于以上段落，尝试自己编写Rabin-Karp算法来解决这个问题。

 int strStr(const string& haystack, const string& needle) {
    int nsize = needle.size();

    if(nsize == 0) 
        return 0;

    int hsize = haystack.size();
    if(nsize > hsize)
        return -1;

    int msbPower = 1;       
    int nhash = 0; 
    int hhash = 0;

    const int mod = 10000009; //A big prime number

    for(int i=0; i<nsize; i++) {
        if(i != 0) {
            msbPower *= 26;
            msbPower %= mod;
        }
        nhash = nhash*26+needle[i];
        nhash %= mod;
        hhash = hhash*26+haystack[i];
        hhash %= mod;
    }

    if(nhash == hhash && haystack.compare(0, nsize, needle) == 0) 
        return 0;

    for(int i=1; i<=hsize-nsize; i++) {
        hhash -= haystack[i-1]*msbPower; 
        hhash %= mod;
        if(hhash < 0)
            hhash += mod;
        hhash = hhash*26+haystack[i+nsize-1];
        hhash %= mod;
        if(nhash == hhash && haystack.compare(i, nsize, needle) == 0) 
            return i;
    }
    return -1;
}

20. 如何学习新的算法和数据结构

正如我在这里和其他文章中提到的，不要试图死记硬背。这样做只会适得其反。你最终会混淆概念，为错误的问题给出正确的解决方案，并且忘记你记住的内容。这就是为什么你需要理解算法。如果你理解基本的数据结构，并能将你的想法转化为代码，那么你也可以编写这些算法。

学习它们的最佳方式是我在描述 Rabin-Karp 算法时向您展示的方式：

1.理解该算法或数据结构试图解决的问题：了解其他替代方案的不足之处会很有帮助。2
.将其分解为定义算法的关键元素或步骤。理解每个元素及其之间的联系。
以此为基础，编写算法代码。

示例 1：二分查找

二分查找是对有序数组线性查找的改进。它每一步都将数组的大小减半，复杂度从 N 变为 O(logN)。
两点：a)由于数组已排序，通过将目标与数组的中间元素进行比较，我们可以在每一步丢弃一半的数组（与目标相比，该一半包含太大或太小的元素。b)如果指针交叉，即l > r，则无解。3.

template<typename T>
int binary_search(const vector<T>& v, int k) {
    int l = 0, r = v.size() - 1;
    while(l<=r) {
     const int m = l + (r - l) / 2;
     if(k == v[m]) {
         return m;
     } else if (k > v[m]) {
         l = m + 1;
     } else {
         r = m - 1;
     }
    }
    return -1;
}

示例 2：四叉树

我想向你展示如何将这种分解过程应用于更复杂的数据结构。你不太可能在面试中需要了解四叉树。我只是读过一次，觉得它们非常有趣，所以决定实现它们。

什么是四叉树？

来自维基百科：

四叉树是一种树形数据结构，其中每个内部节点恰好有四个子节点。四叉树是八叉树的二维类似物，最常用于通过递归方式将二维空间细分为四个象限或区域来划分二维空间……

它试图解决什么问题？

现在我们知道了正式的定义，我认为从它的一个应用可以更容易直观地了解四叉树可以做什么。

假设我们试图模拟一个由一堆粒子组成的物理系统，每个粒子都有一定的质量。每个粒子都会吸引系统中的其他粒子。如果我们有 N 个粒子，那么在模拟的每一步，我们需要处理的相互作用数量都会以 N^2 的速度增长。当 N 很大时，这会非常缓慢。

由于两个粒子之间的吸引力随距离的平方而衰减，我们可以忽略远处粒子的影响。那么，如何在不遍历所有粒子的情况下（这是我们一开始就试图避免的问题）知道哪些粒子距离较远呢？这时四叉树就派上用场了。

使用四叉树，我们可以高效地查询特定区域内的所有粒子。查找过程耗时 O(logN)，由于我们需要对 N 个粒子执行此操作，因此每一步的总耗时为 O(n log n)。

注意，此时我们不太关心具体实现。这更多的是对数据结构的高层次理解，并了解它在哪些方面有用。

在下一节中，我们将进行更详细的介绍。

四叉树的关键元素是什么？

让我们回到定义：

四叉树是一种树形数据结构，其中每个内部节点恰好有四个子节点。

它们将空间分解成可适应的单元
每个单元格（或桶）都有最大容量。当达到最大容量时，桶就会分裂
树形目录遵循四叉树的空间分解。

所以，我们的四叉树类和你可能遇到过的其他树（包括我之前介绍过的 trie 树）并没有太大区别。每个节点包含：

表示其最大容量的整数
一个布尔值，指示它是否是叶子（这意味着，该节点已被分割，因为它已达到其最大容量）
指向它的4个孩子
包含该节点所含点的数组

了解数据结构试图解决的问题，并将其分解为基本元素，可以更轻松地实现它，尤其是记住数据结构的用途和使用场景。你需要“记住”的只是它的定义和属性——如果你思考它试图解决的问题，就会更容易记住它们。

整合起来

您可以在这里尝试用您喜欢的语言来实现它。

class Solution {
private:
    Node *constructHelper(vector<vector<int>> &grid, int len, int x, int y) {
        int flag = grid[x][y];
        for (int i = x; i < x + len; i++)
            for (int j = y; j < y + len; j++)
                //if not a leaf, go deeper
                if (flag != grid[i][j])
                {
                    Node *tl = constructHelper(grid, len / 2, x, y);
                    Node *tr = constructHelper(grid, len / 2, x, y + len / 2);
                    Node *bl = constructHelper(grid, len / 2, x + len / 2, y);
                    Node *br = constructHelper(grid, len / 2, x + len / 2, y + len / 2);
                    return new Node(true, false, tl, tr, bl, br);
                }
        return new Node(grid[x][y] == 1, true, nullptr, nullptr, nullptr, nullptr);
    }

public:
    Node *construct(vector<vector<int>> &grid) {
        int n = grid.size();
        return (n == 0) ? nullptr : constructHelper(grid, n, 0, 0);
    }
};

如果您想了解有关此数据结构的更多信息，我建议您阅读这两个文章来了解四叉树的实际操作。

很高兴知道

这里列出了一些值得了解但文中未明确提及的主题。您无需一次性全部学习。

分离集合。它非常方便解决许多问题，并且易于通过数组或树状结构实现。
最短路径算法。Dijktra算法，以及至少知道的“启发式优化版本” A*算法。还有Bellman-Ford和Floyd-Warshall 算法。
最小生成树。它们是什么以及如何计算它们。以下是两种最常见的算法：Kruskal 算法（本质上是对边进行排序并计算连通分量，这可以使用不相交集轻松完成）和Prim 算法（与 Dijkstra 的最短路径算法非常相似）。
平衡树。平衡树有很多种，但了解红黑树就足够了。

结论

我列出了20个技巧，让你的下一次面试变得轻而易举。其中一些技巧你也会在工作中用到，或者它们或许能给你一些副业的灵感。

重点不在于学习书本上的每一个数据结构或算法。正如你所见，它们大多是一些基本技巧，或者在你已知的基本数据结构上进行了一些小调整。我想向你展示，你可以利用你已知的知识实现很多目标。

附言：希望本文对你有帮助。如果觉得有用，请点赞并分享这篇文章，访问我的博客www.yourdevopsguy.com ，或者在Twitter上和我们联系。上与我们交流。

文章来源：https://dev.to/codinglanguages/how-to-learn-not-memorize-any-algorithm-or-data-struction-analysis-of-20-problem-solving-techniques-you-must-know-d77

如何学习数据结构和算法。你必须知道的 20 种解决问题的技巧基于指针的技术基于递归的技术排序和搜索扩展基本数据结构杂项结论

如何学习数据结构和算法。你必须知道的20个解决问题的技巧

基于指针的技术

基于递归的技术

排序和搜索

扩展基本数据结构

杂项

结论

基于指针的技术

1. 两个指针

解决方案

挑战

解决方案

解决方案

解决方案

2. 指针以不同的速度移动

解决方案

解决方案

解决方案

挑战

3.滑动窗口

解决方案

挑战

基于递归的技术

4.动态规划

5.回溯

解决方案

解决方案

解决方案

挑战

6. 子集

解决方案

解决方案

解决方案

挑战

排序和搜索

7. 排序

解决方案

解决方案

挑战

8. 间隔

解决方案

解决方案

9.二分查找的变体

解决方案

挑战

10.广度优先搜索

解决方案

解决方案

挑战

11.深度优先搜索

解决方案

解决方案

挑战

12.拓扑排序

解决方案

挑战

扩展基本数据结构

13. 出队

解决方案

挑战

14.字典树

解决方案

解决方案

挑战

15. 同一数据结构的两个实例

解决方案

挑战

杂项

16.位操作

解决方案

解决方案

解决方案

挑战

17. 前“K”个元素

解决方案

解决方案

18. K路合并

解决方案

解决方案