题目 Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most wa...

题目 The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q'...

题目 Implement int sqrt(int x). Compute and return the square root of x. x is guaranteed to be a non-negative integer. 我的思路 我能想到的只有暴力方法，从一个位置开始，一步一步加一，直到找到平方根。 代码 int mySqrt(int x) { long long times = 0; int y = x; while (y > 0) { y >>= 1; ++times; ...

判断一个链接有没有环，很著名的算法是Floyd判圈算法，也叫龟兔算法。但是，原来还有一种算法，可以比Floyd更快一点，这种算法叫做Brent判圈算法。 算法思想 用2个指针rabbit和turtle从链表头出发。 rabbit先一步一步走，最多走2步，如果走到尽头，则无环，如果和turtle相遇，则有环，否则，本轮结束。 这个时候，把turtle放到rabbit当前位置，rabbit继续一步一步走，但是最多走4步，如果走到尽头，则无环，如果和turtle相遇，则有环，否则，本轮结束。 然后，把turtle放到rabbit当前位置，rabbit继续一步一步走，但是最多走8步，如果走到尽头，则...

题目 Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array. Could you do it without extra space and in O(n) runtime? Example: Input: [4,3,2,7,8,2,3,1] Output: [2,3] 思路 想了好久，终于想出来了。首先，题...

题目 Given an 2D board, count how many battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules: You receive a valid board, made of only battleships or empty slots. Battleships can only be placed horizon...

题目 Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible. Note: n is a positive integer, which is in the range of [1, 10000]. All the integers in th...

题目 Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the me...

题目 Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subarray [4, -1, 2, 1] has the largest sum = 6. 思路一 首先，可以直接两重循环，找到所有的子数组，然后计算出来和最大的那个，时间复杂度为O(n)，空间复杂度为O(1)。代码如下...

summary : 乘法 对于复数的乘法，我们是这样算的: (a + bi)(c + di) = ac - bd + (bc + ad)i 但是，据说伟大的数学家高斯注意到的一个现象: (bc + ad) = (a + b)(c + d) - ac - bd 这样，原来要进行ac, bd, bc, ad四次乘法，现在就只需要进行(a + b)(c + d), ac, bd 三次乘法，虽然多了几次加法，但是对于计算机来说，乘法计算远比加法慢，在数据量很大的情况 下，这个小技巧将会使算法性能得到极大的提升。...

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

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

summary : 好不容易才想要刷道题，居然碰上了这么一道蛋疼的题，刚开始没看懂题（英语不好）， 去查了单词才看懂了，然后想了半天没想出来，还是去看人家的解题报告才有了一些 灵感，水到爆了，我靠！ 解题思路 题目意思是，输入一个数a的字符串，而且最后一个数必然是{1, 3, 7, 9}中的一个， 求一个位数不超过数a的数b，使得b^3的尾数是a。^ 显然，要得到一个数的最后一位，模10,同理，要得到最后2位，模20,..., 我居然还去搜了一下怎么得到一个数的尾数，结果找到了一篇五年级奥数的培训文章 （这不是赤裸裸地鄙视吗？？？）。 于是，我们可以从个位开始匹配，刚开始就是{1, 3,...

summary : 这题很明显，可以用2个栈来模拟，车进去是一个栈s，然后相当于有一个让道（可以看作 一个栈ss），储存先不出去的车厢。读取输入的车的顺序，放进数组里面，然后s先初始化 一个完整的栈n......2，1。对于输出的车的顺序的每一个元素，先检查的栈顶元素是否与它相 同，再检查ss的栈顶元素是否与它相同，如果都不相同，则s的栈顶元素出栈，继续找下一 元素，如果都找不到，则该顺序不可能产生。 代码: #include <iostream> #include <stack> using namespace std; const int N = 1001...

summary : 一看题目，总觉得直接sort就可以A了，但是交上去就是WA，无奈之下，只好google一下 偷看一下人家的分析。。。。。。。果然是有特殊情况！比如 dc dcc，直接sort，得到 的是dcdcc,而正确答案是dccdc，于是要自己写比较函数了！！ 代码: #include <iostream> #include <string> using namespace std; bool cmp(string s1,string s2) { int i,j; for(i = j = 0; i < s1.size() &...

summary : 好久没刷题了，就去水题集里面挑了道水题做，居然绞尽脑汁想不出来，后来还是百度了一下， 发现网上有关这道题的博客一篇都没有，于是，google,终于找到了一篇！看注释: 求两直线的交点，交点必存在 。 我真的是太水了，可能天生就是这么笨，这样都想不到。于是不看他的代码，自己研究了一下， 结果............还是不会！无奈之下，看人家的代码吧......看了代码，很短，自卑了一下， 再看程序的核心，完全不懂！我差点羞愧而死......又研究了这份代码许久，终于是放弃了。 于是加了博主的QQ，博主人真的好，特地加了详细的注释，一看注释的内容就有种被鄙视的感觉。 我...

summary : 我本来是想找用来练习栈的题的，看到了这个题，一想，这个和八皇后问题有点类似， 可以用回溯解决，便开始了，纠结了2天，发现输不出答案来的，找了1天，终于找出了bug， 当看到黑色的屏幕上出现一行白色的一行数字时，我内牛满面............但是，ctrl+c,ctrl+v， 返回一了一个红红的WA，我检查了一下，发现第一人测试数据完了之后，栈没有清空， 还好C++允许在中间声明变量，我把stack对象放到中间，就解决问题了，然后还发现， 第一个测试数据完了之后，全都标志成了1了，我又把数组全部标志成了0，这时， 发现输入2时，没有输出的，我以为进入了循环，又在调试...

summary : 闲得慌，便逃课出来，突然有刷题的冲动，于是开始了刷水题之旅。很快一道水题就A了， 然后碰到了1318这道。 题目大意: 输入整数N，(n >= 3 && n <= 15),构造魔方阵，使每行，每列及对角线的数字的和都相等， 然后输出这个和，并且输出这个矩阵。 分析： 根据提示：Imagine that the square is rounded. That is, the last row is connected with the first row and the last column is connected with the f...

summary : 题目大意: N个硬币围成一圈，两个人来博弈，每次只能拿一至两个(相邻)，Alice先拿， 最后一个拿的赢，写程序，给定N，判断是谁赢。 分析: 这是一道非常有趣的题，对于像我这样的初学者来说，题目的分析可能要费很大功夫， 但是一旦分析出来，就可以几行代码解决掉。 基本知识：给定N个硬币，排成一列，两个人取，每次只能拿一至两个，则A只需要将这 N个硬币从中间取出一或两个硬币，分成数目相等的两部分，然后B在一边拿多少个，A就 在另一边拿多少个，最终，A必定是最后一个拿的，所以A必定会赢！ 延伸到此题：围成一圈的硬币，第一个取的人必定会把圆圈断开成一列，然后，结果被第 二...

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 : 题意 重新定义了数的表示， 0 => {} 1 => {{}} 2 => {{},{{}}} 3 => {{},{{}},{{},{{}}}} 给出右边的集合形式的表示，计算两个数相加的结果，结果也以集合的形式表示。 分析 找规律，0是空集，1是集合里面包含了整个0的集合的表示，接着2，左边是1的集合里面 的东西，右边是1整个集合的表示，中间用逗号分开，对于3，左边是2的集合里面的东西， 右边是2整个集合的表示，中间用逗号分开。 利用上面的规律，给定任意的整数，就可以通过递归来输出集合的形式了。 怎么根据集合的形式得到整数呢？ 看逗号！0和...

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

summary : 题意 购物狂去买东西，买3件付两件的钱，最便宜的那件不用付。比如买了3个item，分别为 200元，150元，400元，则只需付600元，折扣为150元。如果买超过3件，一起付钱的话， 也只是不用付最便宜那件。这样当然不划算，于是可以多次付钱，每次选3件。不够3件就没 办法了，没有折扣。要求写程序求最大折扣是多少。 我的解法 购物狂是贪心的，这里就是贪心的思想。拿价格最高的3件先去付钱，再从剩下的里面拿 价格最高的3件。最后如果剩下不够3件的，则只能直接付钱了。非常简单，直接排序， 然后根据买的商品的件数，如果刚好是3的倍数，则把下标为3的倍数减一的价钱相加。如果 余...