数据结构和算法是面试中的一个难点，需要求职者具备较强的逻辑能力和编程能力。

很多编程基础薄弱的求职者甚至“谈算法色变”，在这个手撕代码的环节败下阵来。

其实有部分记忆力比较强的同学，可能之前没有专门学习过数据结构和算法，但通过面试之前疯狂刷leetcode，把常考的题目背下来，在面试中也能“碰巧”通过，但这样的复习方式，其实笔者是不太认可的。一来，单纯的背题目，并不能真正的掌握数据结构和算法，就算碰巧通过面试，到了工作中，阅读代码时，还是很难理解别人在代码中运用到的数据结构和算法的设计巧思；二来，假设在面试中，你遇到背过的题目，虽然可以把代码快速的写出来，但假如面试官一问你代码的思路，就很容易露怯，一旦答不上来，就会很尴尬。

所以，建议大家系统的去学习一下数据结构和算法，并且至少要掌握一门编程语言。当有一定基础后，再去leetcode刷算法题，再次重申，这里的刷题不是去背答案，而是先经过自己的思索，尝试自己去解题，实在不会的，再去看题解，然后反复练习，归纳每种数据结构、每种算法的使用场景，这样才能以不变应万变，就算面试官出了没见过的新题，也能运用合适的数据结构和算法进行解题。

另外，需要注意的是：一般来说，编程题（算法题），在面试环节中只能算得上是必须但不是最重要的，只是众多考核方面中的其中一个，不一定就直接决定求职者的成败，但可以确定的是，能够在这个环节回答出色，必然会成为面试的加分项。

新手在解答数据结构和算法题时的一些注意事项：

当你有一定数据结构和算法的基础后，你在解题时，可以遵循四大解题步骤去完成算法题：

常考的数据结构有：链表、数组、树、堆、栈、队列、向量、哈希表等。

常考的算法有：递归、二分查找、排序、树的操作、图论、Hash算法、分治法、动态规划等。

此外还需要掌握时间复杂度和空间复杂度，一般空间不足可以加大运力，但是时间不足将成为程序运行的硬伤。所以我们一般更注重时间复杂度，大家应该掌握时间复杂度的计算方式（大O表示法）。

数据结构和算法在面试中常考的考点有：

3.1.1 数组和链表的区别？

【考点映射】

【出现频度】★★★★☆

【难度】★★☆

【参考答案】

数组：

数组中的元素在内存中是连续存放的，每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。

数组操作的时间复杂度：

假如数组的长度为 n。

访问：O（1） （访问特定位置的元素）

插入：O（n ）（最坏的情况发生在插入发生在数组的首部并需要移动所有元素时）

删除：O（n） （最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时）

链表

链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

对比

---

3.1.2 如何反转链表？

【考点映射】

【出现频度】★★★☆

【难度】★★★

【题目描述】

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
（leetcode 206题）

【参考答案】

思路分析：

在解这道链表反转的题目时，不要被链表存储的数据所迷惑，不要纠结链表的一个节点，当前存储的是什么值，这样容易把自己给绕糊涂了。其实这一道题，我们更需要关心的是链表的指针。

另外，我们在leetcode上刷题的时候，leetcode是不给我们提供测试用例的验证过程的，这让很多初学算法的求职者很困惑，看了leetcode官方题解的示例代码，拿到自己的IDE工具上，却不知道该如何把算法跑起来。

其实，我们在解算法题的时候，考察的更多是求职者的思路，有时候甚至在面试过程中，写出来的也是一些伪代码，如果面试中还要考察代码的运行情况，那么写出来的代码就太多了，你需要自己去构造一个节点类，还需要去构造一个链表类，还要去写一个链表反转的测试类，这样下来，其实是非常没有必要的，写了很多代码，但是解题的关键代码却很少。

所以，我们在面试中解算法题的时候，我们只要把自己的算法思路写正确，没有特别明显的逻辑漏洞和语法漏洞，基本上就可以得分了。然后在leetcode刷题过程中，要求就是代码能够通过leetcode的测试即可。

题归正转，反转链表的解法主要有两种：双指针迭代法和递归法。

双指针迭代法的思路就是：遍历链表，依次把当前链表的指针指向前一个指针，然后把当前节点的前一个指针再指向当前节点的下一个节点。由于是单链表，没有引用其前一个节点，所以必须事先用一个变量存储其前一个节点。在更改引用之前，还要存储后一个节点，最后返回新的头引用。

解算法可以分为4个步骤：模拟、规律、匹配和边界。

第一步、模拟：

第二步、规律：

本质上就是让当前节点的后继指针指向前驱节点（用pre变量存储），而前驱节点（pre）的后继指针指向当前节点的后继节点（next），最终再返回遍历所有节点后的头节点的引用即可完成。

第三步、匹配：

采用双指针迭代算法。

第四步、边界值：

当链表只有一个节点（next指针指向null），或者链表为空，则无需进行遍历操作。

当分析完成后，我们就可以很容易写出代码（Java）：

/**
 * Definition for singly-linked list.
 * 题目已经帮我们构造好了一个链表节点定义
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 边界值判断：当链表只有一个节点，或者链表为空，无需反转链表
        if (head == null || head.next == null){
            return head
        }
        // 定义一个pre变量，用于存储当前节点的前驱节点
        ListNode pre = null;
        // 定义一个cur变量，用于存储当前节点，链表的第一个节点是传入的 head 节点。
        ListNode cur = head;

        while (cur != null) {
            // next 变量存储当前节点的后继节点
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        head = pre
        return head;
    }
}

双指针迭代法的算法复杂度：

使用递归法解题会更加简洁，但是我们需要特别注意递归的终止条件。

模拟：

递归就好比是俄罗斯套娃，我们假设已经有了一个反转链表的方法，然后丢入一个启动节点，比如：节点1让其反转。接下来，又把节点1的后继节点——节点2，丢入反转链表的方法里，让节点2也进行反转...依次类推，我们最终把最后一个节点——节点5也进行反转，再把最后一个节点当作新的头引用返回。这样就可以达到反转链表的目的。但值得注意的是，反转完毕后，第一个节点要指向null，否则节点就会有环，递归将无止境进行下去。

代码（Java）：

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

递归法的算法复杂度：

【知识点延伸】

链表（Linked List）是一种常见的基础数据结构，是一种线性表。物理存储结构上是非连续、非顺序的存储结构。

链表分为单链表和多链表，

单链表的特点就是：一个节点包含数据和 next 指针两个部分，next 指针指向下一个节点；

双链表的特点就是，一个节点不仅包含数据和 next 指针，还包含 pre 指针。 pre 指针指向前一个节点。

我们在面试中，遇到的大多数都是单链表，所以大家在学习链表的时候，应该以了解单链表的特性和常用操作为主。

学习一种数据结构，要对该数据结构的常用操作要有所了解，需要懂得推算常用操作的时间复杂度。

另外，数据结构一般要和编程语言相结合，我们能够轻松的用编程语言把数据结构给表达出来，然后也知道你所熟悉的编程语言，是如何操作该数据结构的。比如，下面是链表的常用操作，大家应该能够用编程语言去表达出来，因为在面试过程中，关于链表的题型，其实本质上就是在操作链表。

以下题目也是链表的常考题，大家下来可以上牛客题霸去多多练习：

---

3.1.3 求数组中第k个最大元素？

【考点映射】

【出现频度】★★★☆

【难度】★★★★

【题目描述】

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。（leetcode 215题）
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2：
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

【参考答案】

要求数组中的第k个最大的元素，其实只要把数组排好序，我们就可以很轻松的找到第k个最大的元素。

此题有三种解法：暴力法、堆排序法、快速排序法。这里讲解其中的两种解法：暴力法和堆排序法。

暴力法：

暴力法也是我们最容易想到的方法。但是面试中，不到万不得已的情况，最好不要用暴力法，因为暴力法太过于简单，这就失去了面试官想要考察你的能力的意义。推荐还是优先使用堆排序法和快速排序法。

主要就是先想办法把一个数组（假设长度是n）排好序（假设元素是从小到大排序），第k个最大元素，其实就是倒数的第（n-k）个元素。

模拟：

代码很简单，利用的是编程语言自带的列表排序方法即可解决。（Java）

import java.util.Arrays;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

堆排序法：

这里首先介绍一下堆这个数据结构。堆是一种特殊的完全二叉树，它有以下特点：

（1）每个节点下最多有两个孩子节点。

（2）不管从上到下，还是从左到右，节点都是填满的。

（3）每个节点都大于等于（或小于等于） 它的孩子节点。假如每个节点都大于或等于它的孩子节点，我们称之为“最大堆”（或大根堆）；假如每个节点都小于或等于它的孩子节点，我们称之为“最小堆”（或小根堆）。

堆排序法有两种解题思路：

假设k=2，这样，我们只要把堆顶元素移出去k-1次，就可以得到最大的第k个元素

我们示例代码里面，采用第一种方式：构建最大堆来求解。（Java版）

class Solution {
    public int findKthLargest(int[] nums, int k) {
    // 寻找第k个最大元素
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        // 这里构建2次最大堆，每次把堆顶元素弹出
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }

    public void buildMaxHeap(int[] a, int heapSize) {
        // 构建一个最大堆
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    public void maxHeapify(int[] a, int i, int heapSize) {
        // 堆化
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

---

3.1.4 求连续子数组的最大和

【考点映射】

【出现频度】★★★☆

【难度】★★★★

【题目描述】

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。（leetcode 第53题）
要求时间复杂度为O(n)。
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

【参考答案】

此题的解法有很多种，包括暴力法、贪心算法、动态规划和分治法。

暴力法比较容易想到，即利用双指针进行迭代，把全部的连续子数组都找出来，并算出每个连续子数组的和，然后再找出连续子数组最大和，比较暴力和简单，这里就不做讲解了。

这里重点讲解贪心算法和动态规划。

贪心算法：

解题思路就是：只需遍历一次，若当前指针所指元素之前的和小于0，则丢弃之前的数列。

模拟：

代码示例（Java）：

class Solution {
    public int maxSubArray(int[] nums) {
        //特判
        if(nums == null || nums.length == 0) return 0;
        //初始化
        int curSum = 0;
        int preSum = 0;
        int maxSum = Integer.MIN_VALUE;
        //遍历数组
        int len = nums.length;
        for(int i = 0; i < len; i++){
            if(preSum < 0){     //更新当前值
                curSum = 0;
            }       
            curSum += nums[i];      // 计算当前值
            maxSum = Math.max(maxSum,curSum);   // 存储最大值
            preSum = curSum;
        }