summary : 面试中经常会让你写出三种遍历中的一种的非递归版本，通常是中序遍历和后序遍历，前序 遍历很少，因为前序遍历毕竟比较简单。 以我的智商，没有做过的话，只能想出来前序遍历的非递归版本，而中序遍历和后序遍历则 是绞尽脑汁都想不出来。最终参考了别人的做法，才理解并写出来了，算是记忆，估计再过 一段时间我又忘了。不过到时可以翻开我的这篇文章看看。 前序遍历 这个是最简单的。用一个栈存储节点，先输出栈顶元素的值，再把左右孩子的节点入栈（如 果有的话）。由于在遍历的时候是先遍历左子树再遍历右子树，那么反过来，在入栈的时候， 就先把右孩子入栈，再把左孩子入栈。 中序遍历 有难度。得先从...

summary : 面了两家公司，都是这个题，都不会做。不管以后还去不去面试，我都 一定 要把这 货给解决！ 学了四年计算机，四年了，始终无法理解动态规划的精妙，能看懂，但是叫我想，我想不 出来。贪心思想，都能说，但是真正要运用，却不会。有的时候，智商问题就是无解。 假定给一个序列为：-10 1 2 3 4 -5 -23 3 7 -21。 开始分析。不管是用暴力方法还是用动态规划的方法，都必须要用一个数存放目前最大的 子段和，就用sum来记录吧。每得到一个临时的子段和，都要和这个最大的子段和比较， 如果临时的子段和较大，则更新，这个临时的子段和就叫temp_sum吧。有的时候，可能 要求...

二分查找 ::: {.code-include lexer="cpp"} ./binary-search.cpp ::: 有两个地方需要说明一下： 写这种程序，函数入口处必须断言，以保证程序的健壮性。 原来的 (low + high) / 2 写成 low + ((high - low) >> 1) 可以防止越界 以及提高效率。 快排 如果没啥要求，就写递归版的。 ::: {.code-include lexer="cpp"} ./qsort_r.cpp ::: 如果要写非递归版的，就用栈记录要排列的子序列的两个边界值。 ::: {.co...

在《剑指Offer》一书看到的题目。要求push, pop, min的时间复杂度都为O(1) 一开始我能想到的方法是，用一个指针指向当前栈中最小的元素，当有新元素进来时， 和当前最小元素比较，如果较小则更新指针，否则不做更改。但是当元素出栈时，就出现 问题了，如果出栈的是最小的那个元素，那我这个指针应该指向哪里呢？ 再想，如果我用2个指针，一个指向次小元素，一个指向最小元素，会怎样呢？其实也不行， 这样是换汤不换药，当最小元素出栈时，次小元素也不知道指向哪里？ 没办法，我记录所有元素的顺序就行了。这样的话，空间复杂度会翻倍，但是这是让3个 函数时间复杂度都为O(1)以空间换时间的办法。 实际上...

summary : 这是我去人人面试的时候遇到的题，当时我写出来健壮性不好，立马就被刷了。 题目 给出两个单链表，升序排序好了，要求合并两个链表，合并之后还是升序排序，而且去重。 链表的节点结构如下： struct Node { : int value; struct Node \*next; }; 分析 没啥好分析，合并加去重，关键是要注意很多特殊情况，要写多一些测试用例。这里，我 用的是递归的方式实现，每次取得两个链表比较之后的头节点，并放到合并之后的链表的 后面。 我的代码 ::: {.code-include lexer="cpp"} ./merge...

summary : 题目 输入数字n，打印从1到最大的n位十进制数。如输入3,则打印1, 2, 3 ... 999。 分析 考虑特殊情况，n是否可以是负数或0。问面试官，n是否可以很大？如果n可以是很大，则 不能用int, long long来存，这个时候变成了高精度数据的问题，应该用字符串。而从 1到最大的N位数，其实就是这么多位数字的从0到9的全排列，于是可以递归地打印出来。 代码 ::: {.code-include lexer="cpp"} ./print_one_to_max_n_digit_number.cpp :::...

summary : 很经典的一道题，而且是很多位运算的题目的鼻祖，掌握它，很多问题的变种就可以解决 了。 题目 实现一个函数，输入一个整数，返回这个整数的二进制表示中1的个数。 分析 对于正数和0，很简单，先和0x1进行与运算，如果结果是1,则最低位是1。然后不断右移， 进行相同的判断，直到这个数变成0为止。 但是对于负数，就不能像上面那样做了，因为右移的话，左边会补1,则无法判断什么时候 结束了。这样有两种方法： 对于负数，规定右移31次就结束。 对于负数，先用0x1和这个数进行与运算，然后把0x1左移一位，变成了0x2，再进行 与运算，直到变成了0。这样也是移动了31次。 更好的...

summary : 在《剑指Offer》里面看到的一道题，非常有趣。 题目 把数组的开头一部分元素放到数组的末尾得到的新数组称为原数组的旋转。现在输入一个 递增排序的数组的旋转，如{3, 4, 5, 1, 2}，找到这个数组的最小值（这里是1）。 分析 不可能直接遍历一次找到最小值。 本人比较笨，想不出来办法，看了书上的解析才知道，可以用二分查找的思想。当时觉得 太神了。方法是这样的：用left记录整个数组的第一个元素的下标，right记录最后一个 元素的下标，求两个下标的中间下标mid，如果mid指向的元素比left指向的要大，则说明 mid所在的范围为原数组递增的部分，这个时候把le...

summary : 这是一个很老很老的题，我做它，就是为了练习，练到能闭着眼睛在纸上写出来。 题目 输入某二叉树的前序遍历和中序遍历的结果，重新建立这棵二叉树，输出它的后序遍历。 假设不含重复数字，类型为int。 分析 根据前序遍历和中序遍历求后序遍历是经典的二叉树问题了，不管是在选择题中还是在 写代码的题中，都会碰到。首先，要人脑会做，而且要有方法做，不是试出来的。主要 的思想是递归。比如前序遍历为1, 2, 4, 7, 3, 5, 6, 8，中序遍历为4, 7, 2, 1, 5, 3, 8, 6，则1肯定为根节点，然后从中序遍历中找到1,则1的左边的数字为左 子树，右边的为右子树。然...

summary : 《剑指Offer》里面看到的一道题，很有意思。 题目 给定一个二维数组，每一行按照从左到右递增排好序了，每一列按照从上到下递增排好序 了，写一个函数，输入这个二维数组和一个整数，判断数组中是否含有这个整数。 分析 抽象问题变具体。考虑下面的二维数组: 1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15 要查找某个整数，关键是"夹逼"，不断缩小范围，因为是有序的。从哪里开始呢？首先， 左上角和右下角是肯定不行，因为这两个地方不能"夹逼"。以左上角为例，往右边是变 大，往下边也是变大，当要查找的整数比左...

summary : 这是千年老题，看起来简单，要考虑的问题非常多。 题目 写一个函数atoi，把字符串转化成整数。 分析 转成整数不难，从头遍历，比如字符串1234,求整数的过程为： result = (((0 * 10 + 1) * 10 + 2) * 10 + 3) * 10 + 4 关键是要考虑特殊情况。 * 传入的字符串头指针为空 * 传入的字符串为空 * 传入的字符串有非数字字符 * 负数 * 溢出 目前，我的处理是，除了负数之外的特殊情况都打印错误信息，异常退出。负数则先按正数 处理，返回的时候加上符号。 代码 ::: {.code-include lexer="c...

summary : 题目 给出一个字符串，单词以空格隔开，写一个函数，传进这个字符串的指针，修改这个 字符串，使得单词的顺序相反，比如"I am a student"变成"student a am I"。要求不能 开辟缓冲区，不能用库函数，不能用 std::string 。 解法 这是千年的老题了，我之前去腾讯面试的时候第一个问题就是这个，结果我不会做，直接被 淘汰了。方法是先把整个字符串倒序，再按单词倒序，这样，求字符串长度是O(n)，将整个 字符串倒序是O(0.5n)，按单词倒序是O(1.5n)，一共O(3n)，即为O(n)的时间复杂度。 说起...

summary : 今天去参加人人的笔试，好多人，好多大神，题目也很难。倒数第二题是这样的。 题目 现在有一个长度为n的数组a，里面有超过一半的整数为一个定值，在不用排序，不开辟新 数组的情况下，用最快的算法找出来这个数， int find(int *a, int n) 。 分析 唉，纠结了好久没做出来，果然算法不行的人是要被虐的，没办法，只能多练了。搜了一 下，原来这题也是千年的老题，看了 这里 的分析，才暗暗觉得人家的算法的高明。 只需要两个变量，一个记录当前值，一个是计数器。初始的时候，当前值为第一个元素， 计数器为1。然后遍历整个数组，遇到和当前值不同的数，计数器减1，相同则加1...