题目：训练场上n(1≤n≤50000)个高矮都不相同的士兵从左到右排 成一行，依次编号为1，2，…，n。第i个士兵的身高H(i)，由于采用特殊单位，H(i)满足1≤H(i)≤2000000000。设第i个士兵右侧最 近的比他个高的士兵编号为j，则第i个士兵可看到在他的右侧比他矮的士兵的个数S(i)=j-i-1。（不考虑客观因素，比如视力范围等-,-）
求S(1)+S(2)+…+S(n)。
输入：
标准输入。
第一行为整数n，表示士兵的个数。
第二行n个整数，用一个空格隔开。分别表示编号为1,2。。。n的士兵的身高
输出：
S(1)+S(2)+…+S(n)的结果
例：
输入
6
10 3 7 4 12 2
输出
5
例子说明：
S(1) = 3
S(2) = 0
S(3) = 1
S(4) = 0
S(5) = 1
S(6) = 0
S(1)+S(2)+S(3)+S(4)+S(5)+S(6) = 3+0+1+0+1+0 = 5
Answer首先说一下：这个题是在网上看的，老题了，属于经典题目那样，至于是不是微软的，可能是，可能不是，但是目的是为了锻炼基础，巩固算法。至于我给的答案，虽然是我推敲了之后发的，但能力有限，并不代表是最好的，也是发到博客上和朋友们一起思考，看看如何优化到最好，这才是学习的过程，而不是单纯为了题目，所以，大家可以考虑下，过一段时间我再贴代码，高手或者看过的直接飘过即可。
大部分情况都不会写到O(n2)，而且题目也很简单，所以代码就不直接贴出来了。不算很难的东西：）
(1)一个整数数列，元素取值可能是0—65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。
注意：
(2)设计一个算法，找出二叉树上任意两个结点的最近共同父结点，复杂度如果是O(n2)则不得分。
(3)一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
(4)一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。复杂度最好是O(n)，如果是O(n2)则不得分。
(1)首先先对非0的数字进行排序，然后检查插值是否为0，如果为0，则不操作，否则与0的个数相减，最后判断0的个数是否大于0。这里排序我用了二叉排序树，这样能够一次读取之后排序并记录0的个数并把0排除在外。然后再先序遍历得到有序列，每个节点（除了第一个）与前一个节点的数字相减再减1（思考），如果等于0，就是连续的，大于0，看看有几个0可以用，比如等于1，我们还有1个0可以用，就OK，最后看看我们用了几个0。我的不是答案，只是探讨，也是巩固基础，可能还有更好的排序方式。
First题目不难，但是有一道弯，一转过去，就到了，虽然是编程题，但是不编程也能做出来。
新郎和新娘：三对情侣参加婚礼，三个新郞为A、B、C，三个新娘为X、Y、Z。有人不知道谁和谁结婚，于是询问了六位新人中的三位，但听到的回答是这样的：A说他将和X结婚；X说她的未婚夫是C；C说他将和Z结婚。
奇数的平方数：大于1000的奇数其平方与1的差是8的倍数。
某个问题：如果a+b+c=0，1/(a+1)+1/(b+2)+1/(c+3)=0，那么(a+1)^2+(b+2)^2+(c+3)^2的值为多少。
答案：（1）A!=X，C!=X，（2）证明奇数1，3，5，7，9的平方的尾数减去1除以8乘以1000即可，这是一个恒等式，看评论。（3）很简单的，36
PS：博客有点卡，原因是前面几个博客的图片是国外的链接，希望稍微好一点，这篇博客的目的是把原来的顶沉下。
问题描述：我们通常把一个数组里面出现的次数最多的数字称为众数，那么众数中，如果比例超过一半了，我们可以叫这个数字为这个数组的支配者，如{1,2,3,4,1,1,1,1,1,8,8}数组中，1就为这个数组的支配者，求支配者的数字并且求出支配者在数组中的索引。
众数问题：其实从支配者问题中，我们可以很容易的了解众数问题，只要加以修改即可。下面写我的思路（支配者问题）。
首先遍历一遍数组，每个数组放到一个Hash表里面，并把当前的数字的索引放到这个Hash表里（数字作为key），Hash表的结构为<int,List<int>>，也就是两个散列表。这样遍历一次就能够知道所有的数字和相应的索引。其次，如何知道是不是支配者，这里有个技巧，支配者在数组中，必然是两个相等的数字连在一起，如（1，1），前面我没说清楚，如果对这个有疑问，可以看评论，因为支配者的个数在N/2个以上，所以我们每次遍历的时候把可能是支配者的数字放到另一个链表中即可。这个时候我们遍历了一次（O(N)），然后我们最后再维护支配者的候选的节点就可以了，如{1,2,3,4,1,1,1,1,1,8,8}，我们会最后得到一个List，List里面存放两个支配者，1和8，最后我们遍历2次就能知道1是支配者，而8不是，这样就相当于遍历了一次数组，和一次筛选后的小型数组。而对于小型数组而言，最坏的情况的次数也只是N/2。
namespace FindHeavyNumber
{
class Program
{ static Dictionary<int,List<int>> numbers; static List<int> hNumbers; static int heavyNumber = -100; static bool isFined = false; static void Main(string[] args) { int[] words = { 1,2,1,3,1,4,1 ,1,8,2,1,1,3}; FindHeavy(words); Output(words.Length);
} static void FindHeavy(int[] array) { int fIndex = 0; int lIndex = 0; hNumbers = new List<int>
给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*…*A[n]/A[i]。你不能使用除法运算。
并不是最好的答案，互相学习一下。
using System;using System.Collections.Generic;using System.Text;namespace BuildArray{ class Program { static void Main(string[] args) { int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int[] result = GetArray(array); for (int i = 0; i < result.Length; i++) { Console.WriteLine(result[i]); } Console.ReadKey(); } static int[] GetArray(int[] array) { int[] a = new int[array.Length]; int[] b = new int[array.Length]; int[] ret = new int[array.Length]; int tempNum = 1; int sub = 0; for (int i = array.Length - 1; i >= 0; i–) { tempNum *= array[i]; b[i] = tempNum; } sub = b[0]; tempNum = 1; for (int i = 0; i < array.Length; i++) { tempNum *= array[i]; a[i] = tempNum; if(i - 1 >= 0&& i + 1 < array.Length) { ret[i] = a[i - 1] * b[i + 1]; } else { ret[i] = sub / array[i]; } } return ret; } }
}近日，Google Jobs在MIT校园内到处张贴着一份密码，企图在MIT校园里的一群变态中找出几个最变态的破密大牛。密码上面附文说，如果你能破解这份密码，你在 Google会很有前途。据说，这份密码包含了一个Google Jobs的电话号码，解开密码的人可以通过此电话留下自己的个人信息。目前，还没有人破解出这段密码来。
密文如下：8MLDQ6TUI6TFMLRHAANRA6Q8EFLDMQ86II2032S5J13JXOJ。希望大家先试试。虽然第一手思路也不是我自己写的。：）
其实这道题目说难也不是很难，但是说简单也不会很简单，这里我简单的说一下我的思路，毕竟是解密的东西，有时候还是要靠运气的。
首先我们看到了这个题目，想想可能是最简单的替换算法，最简单的东西就算还原了去看也满复杂的，首先我想到的是最简单的“凯撒替换”，关于什么是凯撒密码，可以去看这里。知道凯撒密码，我们就可以做一个简单的替换。然后试试。
static char GetChar2(char c){ switch (c) { case ‘0‘: return ‘4‘; case ‘1‘: return ‘5‘; case ‘2‘: return ‘6‘; case ‘3‘: return ‘7‘; case ‘4‘: return ‘8‘; case ‘5‘: return ‘9‘; case ‘6‘: return ‘a‘; case ‘7‘: return ‘b‘; case ‘8‘: return ‘c‘; case ‘9‘: return ‘d‘; case ‘a‘: return ‘e‘; case ‘b‘: return ‘f‘; case ‘c‘: return ‘g‘; case ‘d‘: return ‘h‘; case ‘e‘: return ‘i‘; case ‘f‘: return ‘j‘; case ‘g‘: return ‘k‘; case ‘h‘: return ‘l‘; case ‘i‘: return ‘m‘; case ‘j‘: return ‘n‘; case ‘k‘: return ‘o‘; case ‘l‘: return ‘p‘; case ‘m‘: return ‘q‘; case ‘n‘: return ‘r‘; case ‘o‘: return ‘s‘; case ‘p‘: return ‘t‘; case ‘q‘: return ‘u‘; case ‘r‘: return ‘v‘; case ‘s‘: return ‘w‘; case ‘t‘: return ‘x‘; case ‘u‘: return ‘y‘; case ‘v‘: return ‘z‘; case ‘w‘: return ‘0‘; case ‘x‘: return ‘1‘; case ‘y‘: return ‘2‘; case ‘z‘: return ‘3‘; case ‘ ‘: return ‘ ‘; default: return ‘*‘; }}然后我们的主体函数写成这样，看看下面的代码。
static void Main(string[] args){ string code = “8MLDQ6TUI6TFMLRHAANRA6Q8EFLDMQ86II2032S5J13JXOJ“; code = GetResult(code.ToLower()); Console.WriteLine(code); Console.ReadKey();}static string GetResult(string code){ string retcode = string.Empty ; for (int tempNum = 0; tempNum < code.Length; tempNum++) { retcode += GetChar2(code[tempNum]); } return retcode;}思路不是很难，然后看看结果。cqphuaxymaxjqpvleerveaucijphqucamm6476w9n57n1sn。晕，无语，显然不是我们想要的结果。难道不是凯撒密码，如果不是的话，那我就没办法了，毕竟我对密码学不是很了解。再看看密文，这里有个关键就是，英文里面破译了会说什么？Conguratulations，或者之类的，好吧，我们先map一下，Congratulations匹配8MLDQ6TUI6TFMLR。这样我们就有了一些基本的数字的匹配，但是还不能解决所有的内容。
这里我们可以看到凯撒密码是向后移位4格，刚好和JOBS有联系，而且C是8的话，刚好是以4开头，也就刚好缺少了0，1，2，3这四个数字，那么可以看出JOBS刚好就是0，1，2，3。所以我们可以把GetCode改成下面的代码（这个解释可能有点牵强，不过解密确实很多时候都是靠感觉和运气）。
static char GetChar(char c){ switch (c) { case ‘0‘: return ‘4‘; case ‘1‘: return ‘5‘; case ‘2‘: return ‘6‘; case ‘3‘: return ‘7‘; case ‘4‘: return ‘8‘; case ‘5‘: return ‘9‘; case ‘6‘: return ‘a‘; case ‘7‘: return ‘b‘; case ‘8‘: return ‘c‘; case ‘9‘: return ‘d‘; case ‘a‘: return ‘e‘; case ‘b‘: return ‘2‘; case ‘c‘: return ‘f‘; case ‘d‘: return ‘g‘; case ‘e‘: return ‘h‘; case ‘f‘: return ‘i‘; case ‘g‘: return ‘j‘; case ‘h‘: return ‘k‘; case ‘i‘: return ‘l‘; case ‘j‘: return ‘0‘; case ‘k‘: return ‘m‘; case ‘l‘: return ‘n‘; case ‘m‘: return ‘o‘; case ‘n‘: return ‘p‘; case ‘o‘: return ‘1‘; case ‘p‘: return ‘q‘; case ‘q‘: return ‘r‘; case ‘r‘: return ‘s‘; case ‘s‘: return ‘3‘; case ‘t‘: return ‘t‘; case ‘u‘: return ‘u‘; case ‘v‘: return ‘v‘; case ‘w‘: return ‘w‘; case ‘x‘: return ‘x‘; case ‘y‘: return ‘y‘; case ‘z‘: return ‘z‘; case ‘ ‘: return ‘ ‘; default: return ‘*‘; }}我们再运行一下，得到的答案是congratulationskeepsearchingorcall6476390570x10，再整理一下，答案就是congratulations keep searching or call 6476390570×10。这应该就是标准答案了。
按照某位解密大牛的原文，应该是这样解密的（个人感觉答案貌似是对的但是好像过程也挺牵强的，欢迎大家讨论）。
1) Pick out CONGRATULATIONS
The mapping is pretty straight forward with some gaps in the letters and some ambiguities.
2) Among the ambiguities are the letters J,O,B,S which map to 0,1,2,3
3) That resolves the ambiguities and the resulting map above is the logical result.
