/OfferOrientedAlgorithms

《剑指Offer:数据结构与算法名企面试题精讲》

剑指Offer

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

作者:何海涛


第1章:整数

第2章:数组

第3章:字符串

第4章:链表

第5章:哈希表

第6章:

第7章:队列

第8章:

第9章:

第10章:前缀树

第11章:二分查找

第12章:排序

第13章:回溯法

第14章:动态规划

第15章:


购买网址


勘误

第一版

第1章 整数

  • 第2页,面试题1的分析的第1段的第2行:求(2^31-1)/1,减1的操作将执行2^32-1次。应该改为:求(2^31-1)/1,减1的操作将执行2^31-1次。

第2章 数组

  • 第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]”。

第4章 链表

  • 第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;
}

第6章 栈

  • 第104页,第3行:宽是1(5-1-1=3)。应该改为:宽是3(5-1-1=3)。

第7章 队列

  • 第112页,面试题42的题目描述
class RecentAverage {    
    public RecentCounter();
    public int ping(int t);
}

应该改为:

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

第8章 树

  • 第156页,面试题57“值和下标之差都在给定的范围内”的第二种解法“时间复杂度为O(n)“的分析的第二段的第三、四行”则再判断编号为id-1和id-2的这两个相邻的桶中是否存在...“,应该改为:则再判断编号为id-1和id+1的这两个相邻的桶中是否存在...

第14章 动态规划

  • 第245页,面试题88“使用缓存的递归代码”参考代码中的minCostClimbingStairs函数
public int minCostClimbingStairs(int[] cost) {
    int len = cost.length;
    int[] dp = new int[len];
    helper(cost, len - 1, dp);
    return Math.min(dp[len - 2], dp[len - 1]);
}

应该改为:

public int minCostClimbingStairs(int[] cost) {
    int len = cost.length;
    int[] dp = new int[len];
    dp[0] = cost[0];
    helper(cost, len - 1, dp);
    return Math.min(dp[len - 2], dp[len - 1]);
}

增加了一行代码初始化dp[0]。

  • 第249页,面试题89的"分析确定状态转移方程"的第4段的第3行:因此f(1)=nums[0]。应该改为:因此f(0)=nums[0]。
  • 第256页,第2段的第二行“当i等于时”,应改为“当i等于0时”。
  • 第300页,面试题103的"分析确定状态转移方程"的第4行:再加上1枚标号为i-1的硬币。应该改为:再加上0枚标号为i-1的硬币。