思考篇-各种面试题

数组相关

1. 请实现一个函数，把字符串中的每个空格替换成“%20”。例如输入“We are happy.”，则输出“We%20are%20happy.”。

   解题思路: 首先遍历一遍数组，统计空格的个数，计算新字符串的大小。如果可以创建新的数组，则创建新的数组，然后遍历旧数组，依次拷贝，遇到空格做替换。时间复杂度为O(n)。如果不能创建新的数组，则使用两个指针，从后向前，逐字符遍历，遇到空格做替换，直到两个指针相等，时间复杂度O(n)。

2. 旋转数组

   把一个有序数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

   现有一旋转数组，给定一个值，判断该值在不在数组中。比如[7,8,9,1,3,4,5,6]

   参考答案

   解题思路: 使用两个指针p1和p2，分别指向数组的开始和末尾位置，使用二分查找，二分查找结束条件: 当p1和p2相邻时，查找结束。p2指向该数组的最小值。(有种特殊情况需要顺序遍历) 时间复杂度O(lgn)

3. 给定一个数组，将数组中的奇数放到偶数的前面。

   解题思路: 使用两个指针，一个指向头部，向后移动；一个指向尾部，向前移动，中间做一些操作，直到相遇。时间复杂度O(1)

4. 数组中有一个数字出现的次数超过数字长度的一半，请找出这个数字。例如输入一个长度为9的数组{1，2，3，2，2，2，5，4，2}，由于2在数组中出现的次数为5，超过了数组长度的一半，因此输出为2。

   解题思路: 有一个成熟的近似O(n)的算法可以在一个数组中找到任意第k大的数字。所以只要找到将中间位置设为k，就可以在O(n)的时间复杂度下找到那个数字。

   为什么是近似O(n)呢？因为每次都是随机挑选一个数字，这个数字并不一定是第k小的数，所以需要进行收敛，虽然收敛的过程还是很快的，但是每次收敛都执行一个O(n)的遍历，所以是近似O(n)。

5. 连续子数组的最大和

   输入一个整型数组，数组里有正数也有负数。数组中的一个或连续的多个组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)

   如果之前数字的和为负数，则最大和从下一个数字开始计算。

6. 把数组排成最小的数

   输入一个正整数数组，把数组里面所有的数拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则符合要求的是321323

   解题思路: xxx

7. 在一个单调非递减的数组里，给定一个数，找到第一个大于等于该数的位置，若数组中最大的数都小于给定的数，则返回数组的长度。

   参考答案

   解题思路: 二分查找的变种。注意各种边界条件的检查

8. 螺旋数组

   给定一个n*n的矩阵，生成螺旋矩阵。

   参考答案

链表相关

1. 单链表反转
   核心代码如下:

   Node *new_head = NULL;
   Node *old_head = list->head->next;
   Node *temp = head;
   while (old_head != NULL) {
       old_head = old_head->next;
       temp->next = new_head;
       new_head = temp;
       temp = old_head;
   }
   list->head->next = new_head;

2. 删除单链表节点

   解题思路: 将下一个节点的值复制到当前节点，让当前节点指向下一个节点的下一个节点，删除下一个节点。特殊的地方: 如果删除的节点是尾节点，扔需要遍历。若是头结点，将头结点置为NULL。时间复杂度O(1)

3. 得到链表的倒数第k个节点

   解题思路: 使用两个节点，第一个指向头结点，与第二个节点相距k-1，当第二个节点指向尾节点时，第一个就指向了倒数第k个节点。时间复杂度O(n)

4. 合并两个有序链表

   解题思路: 可以使用递归，也可以使用循环。记住对输入链表是否为空的检查。

堆相关

1. 输入n个整数，找出其中最小的k个数。

   解题思路:若n是一个非常大的数，则考虑创建一个有k个元素的大顶堆。

树相关

树的遍历

1. 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果都不包含重复的数字。例如输入前序遍历序列[1, 2, 4, 7, 3, 5, 6, 8]和中序遍历序列[4, 7, 2, 1, 5, 3, 8, 6]，请构建出二叉树。

树的子结构

1. 输入两颗二叉树A和B，判断B是不是A的子结构。二叉树节点定义如下:

   struct BinaryTreeNode {
       int value;
       BinaryTreeNode *left;
       BinaryTreeNode *right;
   };

算法相关

递归与循环

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

   解题思路:斐波那契数列

位运算

1. 请实现一个函数，输入一个整数，输出该数二进制表示中1的个数

   解题思路: 正数与负数在计算机中的表示是不一样的，正数是原码表示，负数是补码表示。小技巧:将一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0

   异或运算: 相同为0，不同为1