题目 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; i...

判断一个链接有没有环，很著名的算法是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 the...

题目 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 mer...

题目 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...