《剑指Offer》题目总结

对《剑指Offer》一书中出现的题目进行总结。
部分新颖的题目或者思路采用 [*] 标签进行标记
牛客网在线训练链接:挑战剑指Offer

二叉树的遍历

通过递归进行前序、中序、后序遍历二叉树

// 先序遍历

void preOrder(Node *node) {
    if (node == nullptr) return ;
    printf("%d\n", node->val);

    // 遍历左子树
    preOrder(node->left);

    // 遍历右子树
    preOrder(node->right);
}

// 中序遍历

void inOrder(Node *node) {
    if (node == nullptr) return ;

    // 遍历左子树
    inOrder(node->left);

    printf("%d\n", node->val);

    // 遍历右子树
    inOrder(node->right);
}

// 后续遍历
void postOrder(Node *node) {
    if (node == nullptr) return ;

    // 遍历左子树
    postOrder(node->left);

    // 遍历右子树
    postOrder(node->right);

    printf("%d\n", node->val);
}   

通过非递归前序、中序、后序遍历二叉树

思路:
递归就是一个栈的调用过程,所以非递归遍历的时候也要引入栈来实现。
https://blog.csdn.net/silence1772/article/details/83623336

// 非递归先序遍历
void preOrder(Node *root) {
    if (root == nullptr) return ;

    stack<Node *> stack;
    stack.push(root);

    while(!stack.empty()) {
        Node *node = stack.top();
        stack.pop();

        printf("%d\n", node->val);

        if (node->right) stack.push(node->right);
        if (node->left) stack.push(node->left);
    }
}

// 非递归中序遍历
void inOrder(Node *root) {
    if (root == nullptr) return ;

    stack<Node *> stack;
    Node *node = head;

    while (!stack.empty() || node != nullptr) {
        while(node != nullptr) {
            stack.push(node);
            node = node->left;
        }

        node = stack.top();
        stack.pop();

        printf("%d\n", node->val);

        node = node->right;
    }
}

// 非递归后序遍历
void postNode(Node *root) {
    if (root == nullptr) return ;

    Node *last = nullptr;
    Node *node = root;

    stack<Node *> stack;
    stack.push(node);

    while(!stack.empty()) {
        node = stack.top();

        // 三种可以打印根节点的情况
        if ((node->left == nullptr && node->right == nullptr) ||
            (last == node->left && node->right == nullptr) ||
             last == node->right) {
            
            // 1. 无左右节点
            // 2. 左节点遍历完,右节点为空
            // 3. 上一个打印的节点是右节点
            printf("%d\n", node->val);
            stack.pop();
            last = node;

        } else {
            if (node->right) stack.push(node->right);
            if (node->left) stack.push(node->left);
        }
    }

}

代码的鲁棒性

22. 链表中倒数第k个指针

输入一个链表,输出该链表中倒数第k个结点。(倒数第一个为最后一个)

思路: 采用快慢指针的方法,倒数第k个,就先让快指针走k-1步,然后快慢指针一起走,当快指针到最后一个节点时,慢指针指向的为倒数第k个指针。

注意:

  • 倒数第1个是最后一个,倒数第二个的话,应该是快指针在结尾,慢指针指向倒数第二个,以此类推,快慢指针应该间隔(k-1)个节点。
  • 记得判断链表是否有k个节点长。

[*] 24. 翻转链表

输入一个链表,反转链表后,输出新链表的表头。

思路: 主要是保存前节点和后节点,防止链表断开。

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {

        if (pHead == nullptr) return nullptr;

        ListNode *pReversedHead = nullptr;
        ListNode *pPre = nullptr;
        ListNode *pNode = pHead;

        while (pNode != nullptr) {
            ListNode *pNext = pNode->next;
            if (pNext == nullptr) {
                pReversedHead = pNode;
            }

            pNode->next = pPre;
            pPre = pNode;
            pNode = pNext;
        }

        return pReversedHead;
    }
};

25. 合并两个排序的链表

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

思路:
可用循环,可用递归,较为简单。

[*] 26. 树的子结构

输入两棵二叉树A,B,判断B是不是A的子结构。

思路:

  1. 先遍历树的每一个节点,看A是否存在某个节点与B的根节点相同
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
    if (pRoot1 == nullptr || pRoot2 == nullptr) return false;

    bool res = false;
    if (pRoot1->val == pRoot2->val) {
        res = DoesTree1HasTree2(pRoot1, pRoot2);
    }
    
 // 根节点不符合要求,继续查找左结点
    if (!res) {
        res = HasSubtree(pRoot1->left, pRoot2);
    }

 // 左节点不符合要求,继续查找右节点。
    if (!res) {
        res = HasSubtree(pRoot1->right, pRoot2);
    }

    return res;
}

2.当在A中找到与B根节点相等的节点时,挨个去比对AB树

bool DoesTree1HasTree2(TreeNode *pRoot1, TreeNode *pRoot2) 
{
    if (pRoot1 == nullptr || pRoot2 == nullptr) return false;

    if (pRoot1->val != pRoot2->val) return false;

    return DoesTree1HasTree2(pRoot1->left, pRoot2->left) && DoesTree1HasTree2(pRoot1->right, pRoot2->right);
}

代码的完整性

16. 数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

思路: [*]

如果按照正常思路做的话,需要考虑好数的范围,指数的正负等情况。

可以考虑使用递归的方式去解决

an = an/2 * an/2 (n为偶数)

an = an-1/2 * an-1/2 * a (n为基数)

最后考虑指数的正负问题即可

double Power(double base, int exponent) {
    unsigned int unexp = abs(exponent);

    if (unexp == 0) return 1;
    if (unexp == 1) return base;

 // unexp >> 1 强制转换成int, 所以可以暂时忽略基数的问题
    double res = Power(base, unexp >> 1);
    res *= res;
    if (unexp & 0x1 == 1) {
        res *= base;
    }

    return (exponent > 0 ? res : 1 / res);
}

21. 调整数组顺序使奇数位于偶数前面

题目1: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分。

题目2: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,*并保证奇数和奇数,偶数和偶数之间的相对位置不变。*

思路:

假如输入内容为: [1,2,3,4,5,6,7]

第一题: 第一题没有考虑排序的稳定性,也就是更换之后不需要考虑相对位置。可以考虑前后指针往中间查询,前指针直到查询到第一个偶数为止,后指针直到查询到第一个基数位置,然后做交换。


位运算

15. 二进制中1的位数

输入一个整数n,输出该数二进制表示中1的个数。

思路:

  • 正常思路是循环右移整数n,然后和1做与运算判断最后一位是否是1,直到为0时结束。但是这种方式仅仅适用于正数,因为负数右移时会一直补充1,这样就会出现最后全为1,导致死循环。

  • 因为每次移位后都与1(flag)做与运算去查看最后一位是否是1,可以转换思路,每次不再是n右移,而是flag左移,然后n与flag与运算是否是等于flag,也可以判断每一位是否是1。但是写代码的时候要注意一个优先级问题。

int  NumberOf1(int n) {
     int flag = 1;
     int count = 0;

     while (flag) {
        // 注意这里有一个算数优先级问题
        // 最开始的写法是
        // if (flag & n == flag) 注意运算时没有加括号
        // 导致结果一直错误
        if ((flag & n) == flag) count++;
        
        flag = flag << 1;
     }

     return count;
 }
  • [*] 以2进制 n = 0010 1100 为例子

    1. a = n – 1,如果最低位为0,就会向前借位,直到碰到第一个1,此时 a 为 0010 1011, 相当于第一个1左边不变,自己变为0,右边的0全部变为1。
    2. b = a & n, 由1知道,第一个1左侧不变,右侧取反,此时b 为 0010 1000, 也就是从第一个1开始,右侧所有数变为0
    3. 以此循环下去,直到n变为0000 0000
 int  NumberOf1(int n) {
     int count = 0;

     while (n) {
        count++;
        n = (n - 1) & n;
     }
     
     return count;
 }

数组

4. 二维数组中的查找

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

思路:
可从右上角(左下角)考虑,因为这两个角可以通过与target对比大小,然后决定舍弃一行还是一列的问题。

[*] 66. 构建乘积数组

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

思路:
B[i]=A[0]A[1]A[i-1]A[i+1]A[n-1] 可以写成
B[i] = C[i] * 1 * D[i];
其中
C[i] = C[i – 1] * A[i – 1];
D[i] = D[i + 1] * A[i + 1];

vector<int> multiply(const vector<int>& A) {
    vector<int> B;
    int n = A.size();

    B.push_back(1);
    for(int i = 1; i < n;i++) {
        B.push_back(B[i - 1] * A[i - 1]);
    }
    
    double temp = 1;
    for(int i = n - 2; i >= 0; i--) {
        temp *= A[i + 1];
        B[i] *= temp;
    }

    return B;
}

字符串

5. 替换空格

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路:
考虑从后往前复制,可以减少字母的移动。

**

递归和循环

10. 斐波那契数列

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39

思路:
传统的递归容易产生重复计算,可以考虑从下到上的方式计算。

10.2 跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

思路:
一开始没理解为什么采用斐波那契。
1级台阶有1种跳法,2级有(11, 2)两种跳法,3级有(11, 12, 21)3种;
当有n阶时,如果第一步跳了1个,那么剩下的跳法是f(n-1)种,如果第一步跳了2个,剩下的跳法是f(n-2)种,所以f(n) = f(n-1) + f(n-2)

10.3 变态跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路:
比上一个题目有更多的可能性
1: 只有一种跳法
2: 第一步可以跳1下或者2下, 如果跳1下,那么剩下的台阶有f(2-1)种可能,如果跳两下则有f(2-2)种可能。 f(2) = f(2-1) + f(2-2)
3: 第一步可以跳1,2,3下,剩下的则有f(3-1),f(3-2),f(3-3)种。 f(3) = f(3-1)+f(3-2)+f(3-3)

总结:
f(n-1) = f(0) + f(1) + f(2) …. + f(n-2)
f(n) = f(0) + f(1) + f(2) …. + f(n-2) + f(n-1)

所以: f(n) = f(n-1) + f(n-1) = 2 * f(n-1)

f(0) = 1;
f(1) = 1;
f(n) = 2 * f(n-1)

10.4 矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

思路:
通过画图可以了解规律
1. n = 1, 1种
2. n = 2, 2种
3. n = 3, 如果第一块砖已经确定,则有f(3-1)种铺法,如果两块转铺好则有f(3-2)种铺法
4. 总结 f(n) = f(n-1) + f(n-2)


链表

6. 从头到尾打印链表

输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

思路:
此过程是一个先进后出(后进先出)的过程,可以考虑使用一个栈来实现。当然递归本质上也是一个种栈结构。

  • 栈实现,后进先出
  • 递归,先递归到结尾,然后依次回到每一个节点。

18. 删除链表中重复的节点

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

23. 链表中环的入口结点

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

思路:
1. 先找出是否存在环,快慢指针法,快指针2步走,慢指针1步走;
2. 循环链环,找出环的长度len;
3. 快指针先走len,这样快慢指针相差的距离就是环的长度。

注意:
在判断是否存在闭环的时候,需要注意两点
1. 开始时快慢指针不要都从pHead开始,因为如果一开始两指针就指向pHead的话,循环在第一步就终结;

ListNode *fast = pHead->next;
ListNode *slow = pHead;

while (fast != nullptr && slow != nullptr)
  1. 因为快指针每次需要多走一步,所以要经常判断快指针是否为null;
fast = fast->next;
if (fast != nullptr) fast = fast->next;


栈与队列

9. 用两个栈实现队列

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

思路:

  • push: 只需要往stack1中添加即可。
  • pop: 如果stack2中有元素,直接弹出栈顶即可,如果没有元素,则将stack1的元素依次出栈然后放入stack2中。类似于把stack1中的元素倒入stack2。

面试思路

27. 二叉树的镜像

题目描述
操作给定的二叉树,将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义:源二叉树 
            8
           /  \
          6   10
         / \  / \
        5  7 9 11
        镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7  5

思路:
递归,每次都只交换自己的左右节点即可。

注意:
终结状态不光要判断pRoot == null, 还要判断 (pRoot->left == null && pRoot->right == null) 是&&不是||, 因为只有一个子节点时也可以做镜像操作。


举例让抽象具体化

32. 从上到下打印二叉树

从上往下打印出二叉树的每个节点,同层节点从左至右打印。

思路:
题目较为简单,考虑先进先出,通过队列即可解决。

注意: 队列是queue,在C++中queue的第一个元素为front()而不是top().


综合

把字符串转换成整数

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能,但是string不符合数字要求时返回0),要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字,否则返回0

思路:
可以考虑正常的转换过程

注意:
1. 输入不合法的时候除了返回0,还应该设置一个全局变量表示输入无效;
2. 允许输入+/-符号;
3. 如果可能的话,还要判断数值的边界。


知识迁移能力

53. 数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

思路:
题目的主要目的是找到firstK和lastK,可以通过二分法单独去找firstK和lastK, 找到后做减法即可。因为是O(logn), 所以多查一个也没有关系。

注意:
在判断是否是fisrtK的时候,需要判断是否是数组中的第0个数字,如果不是的话,需要判断一下这个数的前一个数是什么数。同理可以找到lastK。

55. 二叉树的深度

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

思路:
不要考虑的太复杂,一个树的深度计算为: 左子树高度和右子树高度相对较大的一个+1; 所以可以考虑采用递归的方式去实现。

int TreeDepth(TreeNode* pRoot)
{
    if (pRoot == nullptr) return 0;

    int leftHeight = TreeDepth(pRoot->left);
    int rightHeight = TreeDepth(pRoot->right);

    return (leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
}

55.2 平衡二叉树

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

思路:
1. 根据55题目去判断左子树和右子树的高度,不过会有重复计算的节点。
2. 遍历到每个节点时可以通过判断左右子树的深度去判断它是不是平衡的。

bool IsBalanced_Solution(TreeNode* pRoot) {
    int depth = 0;
    return IsBalancedCore(pRoot, &depth);
}

bool IsBalancedCore(TreeNode *pRoot, int *depth) {
    if (pRoot == nullptr) {
        *depth = 0;
        return true;
    }

    int left, right;
    if (IsBalancedCore(pRoot->left, &left) && IsBalancedCore(pRoot->right, &right)) {
        if (abs(left - right) <= 1) {
            *depth = 1 + (left > right ? left : right);
            return true;
        }
    }

    return false;
}

注意:
平衡二叉树是要判断每个节点,而不是单纯只判断pRoot的左右子树深度差。

// 错误
return (diff <= 1);

// 正确
if (diff > 1) return false;

return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right)

56. 数组中只出现一次的两个数字

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路:
异或运算,可通过异或运算的结果求其中一个为1的位,为1的原因是因为这两个数该为是不一样的,所以可以区分开。

57. 和为S的两个数字

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

思路:
考虑头指针和尾指针的方式,当和小于S时,增大头指针,当和大于S时,减小尾指针。

57.2 和为S的连续正数序列

输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

思路:
从第一个数和第二个数开始做加法,如果小于当前值,则end+1,如果大于当前值,则start+1,记得和要先减去start。 前提是保证start < end 和start 小于中位数。

58. 翻转字符串

I am a student. ==> student. a am I

思路:
一开始翻转一次,最后在以空格为分隔符继续翻转每个单词

注意:
如果以遇到空格时才做翻转,那么在while循环外需要再做一次翻转(比如一个单词的情况);

58.2 左旋转字符串

字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”

思路:
和58题相同的思路,甚至简单,只需要先把整个翻转,然后根据输入的数字n将字符串分为两个单词,各自翻转。