剑指Offer

数据结构与算法名企面试题精讲

作者：何海涛

---

第1章：整数

第2章：数组

第3章：字符串

第4章：链表

第5章：哈希表

第6章：栈

第7章：队列

第8章：树

第9章：堆

第10章：前缀树

第11章：二分查找

第12章：排序

第13章：回溯法

第14章：动态规划

第15章：图

---

购买网址

• 京东网：https://item.jd.com/13371972.html
• 当当网：http://product.dangdang.com/29280950.html

---

勘误

第一版

• 第2页，面试题1的分析的第1段的第2行：求(2^31-1)/1，减1的操作将执行2^32-1次。应该改为：求(2^31-1)/1，减1的操作将执行2^31-1次。
• 第19页，面试题8的分析的第4段的第5-6行：再把指针P2向右移动一步指向数字6。应该改为：再把指针P2向右移动一步指向数字4。
• 第23页，面试题10的分析的第5段的最后一句话：那么数组中从第i+1个数字开始到第j个数字结束的子数组之和为k。应该改为：那么数组中从第j+1个数字开始到第i个数字结束的子数组之和为k。
• 第27页，面试题13的图2.2下面的第二段的“该子矩阵的数字之和等于sums[r2][c2]+sums[r1-1][c2]-sums[r2][c1-1]+sums[r1-1][c1-1]”，应改为“该子矩阵的数字之和等于sums[r2][c2]-sums[r1-1][c2]-sums[r2][c1-1]+sums[r1-1][c1-1]”。
• 第51页，面试题21的代码中的参数n改为k，即

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode front = head, back = dummy;
    for (int i = 0; i < n; i++) {
        front = front.next;
    }

    while (front != null) {
        front = front.next;
        back = back.next;
    }

    back.next = back.next.next;                    
    return dummy.next;
}

应该改为：

public ListNode removeNthFromEnd(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode front = head, back = dummy;
    for (int i = 0; i < k; i++) {
        front = front.next;
    }

    while (front != null) {
        front = front.next;
        back = back.next;
    }

    back.next = back.next.next;                    
    return dummy.next;
}

• 第112页，面试题42的题目描述

class RecentAverage {    
    public RecentCounter();
    public int ping(int t);
}

应该改为：

class RecentCounter {    
    public RecentCounter();
    public int ping(int t);
}

• 第249页，面试题89"分析确定状态转移方程"的第4段的第3行：因此f(1)=nums[0]。应该改为：因此f(0)=nums[0]。
• 第256页，第2段的第二行“当i等于时”，应改为“当i等于0时”。