给定一个数组，每个数都是正数，求所有子数组和等于m，如果没有这样的子数组，求所有子数组和大于m并且最小。换言之，就是求所有的子数组和>=m,并且最小。      滑动窗口经典题，因为所有的数都是正数，所以如果小的数组的和小于m，则它的子数组的和全部小于m。于是我们可以动态维护窗口里的值，并且不断滑动。当然也可以保存前缀和sum[i] = a[1] + a[2] +... + a[i] (下标从1开始），则子数组[i..j]对应于sum[j] - sum[i - 1]。我们维护窗口[i..j]的和，如果它小于m，则扩大它++j, 如果它和大于m，则减小它++i, 这样我们利用O(n)的时间...

简单题，统计词频，输出出现次数最多的单词，如果不唯一，全部按照字典顺序输出。   注意点：    （1） 单词定义，数字和字母的连续字符   （2） 字母全转变为小写      可以先把字符串中非数字和字母的位置全变为空白，再用sstream从字符串中一个一个读出连续的字符——这时连续字符只可能是数字和字母了，所以读出一个就是一个单词，利用map统计词频，并记录词频最大值。   遍历map，输出词频等于最大值的所有单词。注意C++ STL map迭代时，自动key的字典顺序由小到大迭代，所以我们不用担心顺序问题。      代码：     #include <cstdio> #in...

简单题，给定月饼的种类和市场总需求量，再给定每种月饼的重量和售价（这些重量的价钱），求最多能卖多少钱——每种月饼可以卖任意数量，得到的钱就是那个售价的比例。      分析： 著名的0-1背包问题，可以取一部分。可以简单地证明，肯定优先取“性价比”最高地，这里“性价比”指的是单位重量的售价。因为如果我们不取“更贵”的，我们可以用更贵的换掉便宜的，从而获得更大的收益。   所以就变成简单的贪心了，把月饼按单位重量售价由高到低排序，当然我是用乘法代替的除法，不过因为都是浮点数，可能直接用除法问题也不大。   然后就从最贵的开始选了，装满要的市场量为止——或者所有都取完了，仍然没达到市场需求。   ...

简单题，按照题目说的，把一个四位数各位数字由大到小排，再由小到大排，排好之后求差（允许有首0），得到的结果继续这么做，直到出现6174或者0000为止。   C/C++ 可以方便用sscanf, sprintf从字符串里读数，以及把数写进字符串。所以就是一个while循环了。照着模拟就好。     #include <cstdio> #include <cstring> #include <string> #include <algorithm> using namespace std; char s[6]; int main() { int n...

不难的题，给定n个硬币，问能否凑出m块钱。如果有解，输出字典序最小的解。   经典背包问题。现判断解的存在性，我们把钱币按面值由小到大排序，大于m的扔掉，排好后假设是a[0..n - 1]。   我们用bool数组can[x][y]表示用[x..n - 1]的硬币是否能凑出y块钱，   初值全是false，只有can[n][0] = true， 因为这表示什么硬币都不用，我们只能凑出0块钱。   递推：   can[i][j] = can[i + 1][j] || can[i + 1][j - a[i]];   这表示要用[i..n - 1]的硬币凑出j块钱，要么就是用[i + 1.. n -...

简单题，对一个0到(n-1)的排列排序，允许的操作是把一个数和0交换。   首先，假设任意两个数可以交换，次数其实就是每个（圈长-1)的总和。   什么叫做圈呢？ 就是a应该在b的位置，b应该在c的位置，c应该在d的位置。。。。最后一个数应该在a的位置，这个圈假设包含m个元素，我们交换(m - 1)次，每次可以把一个元素放在正确的位置上，并且最后m个数肯定都在自己的位置了……所以题目等价于找圈。   对于这个题，多了一个条件，我们只能和0交换。   如果我们找到一个圈0，在圈里，我们可以每次用0和某一个交换，同样(m - 1)次之后，所有数在自己的位置。   如果0不在圈里，我们可以现交换一次...

不喜欢这种题——模拟AVL树，要不断地做旋转以维护树地平衡，返回最终根节点。   AVL树及旋转比较复杂，具体可以参看   http://blog.chinaunix.net/uid-25324849-id-2182877.html   除了旋转就没别的东西了。。。。。      代码：     #include <cstdio> #include <cstring> #include <string> using namespace std; struct node { int val, height; node *left, *right; }; nod...

简单题，给定A, B, C,判断是否有A + B > C。 这3个数都是64-bit整数，所以要用long long。但是加法可能溢出……   clmits头文件包含了    LLONG_MAX和LLONG_MIN    我们其实要判断   （1） A + B >  LLONG_MAX, 即 A >  LLONG_MAX - B， 注意B可能是负数，这样 LLONG_MAX - B也越界了，而且只有B是非负数，它与A的和才可能上溢出，所以我们判断(B >= 0) && (  A >   LLONG_MAX - B) 这时A + B >  LL...

给定一些整数值，构造一个完全排序二叉树。   完全的定义是，几乎是满的二叉树，但是最后一层可能从右往左按顺序少了一些叶子节点。      其实这个题也不难。中序遍历排序二叉树，得到值的顺序是排好顺序的。我们用编号为1的节点为根，编号x的节点左孩子是2 ＊ x, 右孩子是2 * x + 1。完全的意思是说，编号是连续出现的，恰好是1-n，我们从1开始左中序遍历，维护编号就可以了，编号>n的不用就可以了。     #include <cstdio> #include <string> #include <cstring> #include <algo...

简单题，集合求交。正规做法是用数组存好，排好顺序，用O(n)的归并方法求交。   我直接用了C++ STL的set存了所有的集合，求交就不用排序了，用iterator迭代就可以了。求交的方法就是哪个iterator对应的数小，就移动哪个，如果相等就找到了一个相交的元素。当然还要算一下并集元素的个数，因为要算相似度，用交集元素个数除以并集元素个数。  #include <set> #include <cstdio> using namespace std; set<int> a[52]; double give(int x,int y) { int inter...

无聊题，题目给了两个指标，德和才(x,y)，然后让对一些任根据x, y排序。   又给了两个阈值a<=b，如果x,y都不小于a才人才考虑排序，所以我读入的时候把两个值都小于a的扔掉了 (--i, --n)。   排序原则：   （1） 如果两个指标都不小于b，这个叫做圣人，要排前面   （2） 如果德不小于b，才小于b，这种人叫做君子，排位比圣人稍差，第二位   （3） 两个指标都小于b，并且才不低于德的人叫做愚人，排第三位   （4） 不满足以上条件（可能两个指标都小于b，也可能德小于b，才不小于b)，称为小人，排位最后。      同一个级别的人，按照德才的总和排位，较大的排再在前，...

给定一棵树 （无向无环图）——先判断给定的到底是不是树，如果是树，以那些节点为根能得到的尽可能高的树。   分析： 判断是否是树比较简单，可以用dfs, bfs求连通分量，如果是1就是树，当然我采取的是并查集，类似kruskal算法加边，顺便统计连通分量的个数。然后有两种办法处理。一种是暴力——比较好理解，以每个节点为根dfs一次求出高度。这种算法的时间复杂度是O(n2)，好在n不大10000，这种暴力可以通过。   代码：  #include <cstdio>  #include <cstring>  #include <string>  #include...

简单题，给定两个字符串，最先同一个位置共同出现的A-G之间的字母代表星期几。接着最先共同位置出现的0..9或者A-N之间的字符表示时间的小时。再给两个字符串，最先共同位置同时出现的字母，位置表示时间的分钟，最后输出星期几个，几点几分，作为约会时间。   应该没有什么坑。   直接做就可以。     #include <cstdio> #include <cstring> #include <string> #include <cctype> using namespace std; const char *week[] = {"MON&...

给定两个非负实数，用类似于科学记数法的形式表示为0.xxxxx * 10 ^ k的形式，小数点第一位非0 （当然原数为0除外），保留小数直接截断或者补0，不需要四舍五入，问处理之后它们是否相等。      分析： 其实题目说的还不是很清晰，比如原数为0的时候，指数k应该为多少，我理解是0.0 * 10 ^ 1这样，所以这种情况我把k处理为1了，也不知道有没有这样的case。因为数字有100位，我们需要用字符串读入，对字符串处理。   首先对于整数部分，我们需要移动指数k，整数有多少位，k就要变成负几，当然首0要考虑，小数部分的首0也一样，所以k要不注意+1或者-1，小心处理一下，最后标准化之后...