昨天晚上看了一个题目,这个题目很强,一开始在做的时候,没有考虑那么多,想来想去还是没有什么头绪,后来看到一个哥们写的题目发现特别简单,但是特别难懂,后来查了一下相关资料,哇,确实是一个强题,可能一般人来看这个题目的话,代码可能会写很多,而且效率也不算很高,但是这个标准解答还是很不错的。题目如下。
结果为0的序列:
考虑由1到n(n<=9)按递增顺序排成的序列1234…n,在他们之间加入加号,减号或者什么也不加,分别使它们做加法,减法或者将数字合并。然后求出结果,看看是否为0。
写一个程序,找出所有长度为n的结果为0的序列,返回序列的个数。
函数接口:int ResultIsZero(int n);
其中n表示序列的长度,int表示返回的序列的个数。
举例:
n = 8,返回10。
序列分别为:
1+2+3+4-5-6-7+8 = 0;
1+2+3-4+5-6+7-8 = 0;
1+2-3+4+5+6-7-8 = 0;
1+2-3-4-5-6+7+8 = 0;
1-2+3-4-5+6-7+8 = 0;
1-2-3+4+5-6-7+8 = 0;
1-2-3+4-5+6+7-8 = 0;
1+23-45+6+7+8 = 0;
12-34-56+78 = 0;
1-23-4+5+6+7+8 = 0;
如果你看明白了题目,你可以开始做这个题目了,如果你看明白了但是想了半天和我一样不会做的话,那就需要先来了解一下深度优先搜索DFS了。
了解百度百科,还有一个详细资料,关于图论的,关于迷宫的深度搜索算法。下面我给出一个迷宫的算法,迷宫如下图所示。

迷宫的代码如下:

Code#region Code

#include
<iostream>

using std::cout;

using std::endl;


int n[5][5];


int init()


…{
n[
0][0]=1;
n[
0][1]=1;
n[
0][2]=1;
n[
0][3]=1;
n[
0][4]=0;
n[
1][0]=1;
n[
1][1]=0;
n[
1][2]=1;
n[
1][3]=1;
n[
1][4]=1;
n[
2][0]=1;
n[
2][1]=1;
n[
2][2]=1;
n[
2][3]=0;
n[
2][4]=1;
n[
3][0]=0;
n[
3][1]=1;
n[
3][2]=0;
n[
3][3]=0;
n[
3][4]=0;
n[
4][0]=0;
n[
4][1]=1;
n[
4][2]=1;
n[
4][3]=1;
n[
4][4]=1;
return 0;
}


int find(int x,int y)


…{
cout
<<x<<“\t“<<y<<endl;
if(x==4&&y==4)

…{
cout
<<endl;
return 1;
}
else if(n[x][y]==0||x>4||y>4||x<0||y<0)

…{
return 0;
}

n[x][y]
=0;
return find(x,y+1)+find(x+1,y);
}


int main(void)


…{
init();
int r = find(0,0);
cout
<<r<<endl;
return 0;
}


#endregion
我们只有了解了迷宫的深度优先的搜索的递归算法,才能再来回头看我们前面说的题目,那个找结果为0的数字的表达式集合,我们同样可以用深度优先搜索计算,代码如下所示。

Code#region Code

#include
<iostream>

using std::cout;

using std::endl;


static int N;


static int ResultIsZeroDFS(int n, int total, int last)


…{
const int current = n+1;
int sub = total+last;
if( n == N )

…{
return (total+last == 0);
}
else

…{
int result = ResultIsZeroDFS(current, total, last*10+current)+
ResultIsZeroDFS(current, total
+last, current)+
ResultIsZeroDFS(current, total
-last, current);

return result;
}
}


int ResultIsZero(int n)


…{
N
= n;
return ResultIsZeroDFS(1, 0, 1);
}


int main(void)


…{
cout
<<ResultIsZero(8);
return 0;
}


#endregion
这个答案是不是很强,其实其中还有很多值得我们去学习。。
第一就是关于内存的速度的,其实不难,但是开发的时候想到的很少,能想到的优化的就是高人,我也是路过看到不错,觉得很有用,就贴过来了。

另一个就是《算法导论》了,国外的教材,也是MIT的标准教材,很好很强大,昨天看到了堆排序和快速排序(100页),用了好多张纸证明线性比较排序的上界和下界,堆排序和快速排序的最好的速度是nlogn,从数学角度上证明了线性比较排序(如判断a[1]>a[0])的最快就是nlogn,也就是说只要你是比较的,而且还是线性的,nlogn就是最快的了。
数学公式太复杂,什么期望啊,概率啊,极限啊,记的不是很清楚,让我自己推倒也没这个能力,不过倒是让我知道了,以后别想线性快速的排序还能超过nlogn了。:)
前面有一篇文章里面我写了LRU算法,其中还将一些算法更新了一下,现在我就做个笔记,写一下LRU算法的一些用途,另外说明一下,这里我们LRU算法都不会考虑空间不足的问题(因为从软件模拟来说基本不会存在这个问题),如果在CPU硬件设计上出现空间不足的话,我们直接将链表的第一个元素剔除即可,当然,也有相应硬件能够直接做这种事情。
当然,LRU不仅仅在硬件设计上有很好的作用,在软件设计上也有很好的作用,例如Orical的数据库就是用了LRU算法。我们可以先看看下面这个图。

Oracle的设计可以从上图看到,这里buffer(缓冲区)就像一个水池,水池的最小单位就是数据块。当每个数据块被读入buffer时,Oracle或相应的软件都会抽取数据块的头部,在内存中构建buffer header,并将这些buffer header串成链表的形式。而buffer header里面记录的指针就指向buffer中的该数据块本身。于是,当我们在搜索某个数据块时,就不用去缓冲区中找,而是直接扫描链表上该数据块所对应的buffer header,然后根据找到的buffer header所记录的指针就能到buffer中直接定位该数据块了。而维护buffer header就是hash表,而buffer header就是一个LRU维护的链表。
这里的buffer head就是数据的一些信息,例如如果我将数字存储到数据中,我可以通过一种方式获取其head的信息,存放到相应的hash组里面,而hash的key也是可以通过数据本身得到。例如我们可以将数字求100的余数得到key,然后余10得到页面id。例如25这个数字,我们可以余100为25,余10为5,那么我们就在缓冲区buffer[25,5]的地方将这个数据保存起来,下次我们取的时候可以直接从25获得hash的组id和存放的页面id,即25和5,则我们直接读取buffer[25,5]即可。
说了这么多,可以稍微总结一下,这个数据结构就是。
- hash表:存放数据的组,用于查找和维护。
- buffer head:LRU链表,被hash组维护,其内容为在内存(缓冲区)的页面id。
- buffer:缓冲区,用于存放数据。
简单的说,也就是当数据读入,我们通过一种方法获取组的id,然后在相应的组中维护一个页面id(链表),然后查找的时候直接通过组id和页面id得到数据,从而提高速度。
不过这里就会有一个问题,hash表这里就不存在冲突的问题了,因为hash表的value是一个链表结构,所以不存在冲突,如果有相同的key的话,我们直接在后面添加节点即可,但是在缓冲区的话就有可能有问题,例如25和125这两个值最后在缓冲区的位置应该是一样的,那么我们肯定不能覆盖掉,所以我们就查找25这个位置(25,5)后面的这个空间是否被使用(25,6),如果没被使用,则我们写到这个空间中,并更改LRU链表指针里面的值。
例如25会是第25组,其页id为5,当读到125的时候,发现也是25组和id为5,那么我们就查找6的位置,如果6位置没数据写入,那么OK,写到6的位置,并更新链表为第25组,页id为6,直到内存缓冲区被写满为止,我们都不覆盖。
这样我们解决了冲突问题,但是这样的话,查找也就出了问题,即不能够直接查找,同样是25和125这两个数,两个坐标最后会成为(25,5)和(25,6),但是我们两个数通过规则获得到的key和页面id是25和5。所以当我们查找的时候就不需要使用页面id,而是采用扫描的方式。即当我们搜索125这个数字的时候,可以获得组id,即25,然后扫描这个组维护的LRU链表,然后扫描内存块,查找是否是我们需要的数据,如果是,则返回。就是我们搜索125,发现组id为25,那么我们就找(25,5),发现数据为25,不是我们想要的,继续下一个链,(25,6)直到找到需要的数据。
不过上面我们也可以优化一下,即优化成结构体,每个数据都有自己的独立的页面id,而不是通过一种规则去找页面id,尽量避免冲突,提高效率。我们可以看一下Orical的做法。
“当前台进程发出SELECT或者其他DML语句时,Oracle根据SQL语句的执行计划找到符合SQL条件的数据块,然后Oracle会根据对请求的数据块的地址以及数据块的类型作为参数,应用hash函数以后,得到要找的数据块所处的hash bucket,也就是确定该数据块在哪条hash chain上。然后,Oracle进入该hash chain,从上面所挂的第一个buffer header开始,根据buffer header所含有的指针找到对应的块体,然后扫描其中的数据,确认其是否是SQL语句所需要的块,如果是,则返回该块里所需要的数据;否则,如果不是,则继续往下搜索,一直搜索到最后一个buffer header为止。如果一直都没有找到,则调用物理I/O,到数据文件里把该块所含有的内容复制一份到一个可用的buffer里,并构建该块的 buffer header,然后将该buffer header挂到hash chain上去。”
所以基本上我们可以明确算法了,下面我给一下C#模拟的代码。
namespace LRUandData

…{

定义LRU链表#region 定义LRU链表

public class LRUList

…{
public int pageNum;
public LRUList next;
}

#endregion

class Program

…{

定义数据块,缓冲区和hash表#region 定义数据块,缓冲区和hash表


static int[] numbers = …{ 100, 25, 64, 1001, 98, 52, 76, 33, 511, 72, 633, 1000 };
static int[,] buffer = new int[100, 100];
static Dictionary<int, LRUList> hash;

#endregion

static void Main(string[] args)

…{
hash = new Dictionary<int, LRUList>();
//初始化数据
InsertData();
//查询数据
int value = SearchData(33);
Console.WriteLine(value);
Console.ReadKey();
}


初始化数据#region 初始化数据

static void InsertData()

…{
//key的算法是求该数和100的余数
//pageNum的算法是求该数和10的余数
for (int i = 0; i < numbers.Length; i++)

…{
int key = numbers[i] % 100;
LRUList lrulist = new LRUList();
lrulist.pageNum = numbers[i] % 10;
lrulist.next = null;
int pageId = lrulist.pageNum;

//如果存在这个组则添加链表到尾部
if (hash.ContainsKey(key))

…{
LRUList templist = hash[key];
while (templist.next != null)

…{
templist = templist.next;
}

while (buffer[key, pageId] != 0)

…{
pageId++;
}
lrulist.pageNum = pageId;
templist.next = lrulist;
}
else

…{
//创建一个组
hash.Add(key, lrulist);
}
buffer[key, pageId] = numbers[i];
}
}

#endregion


查找数据#region 查找数据

static int SearchData(int number)

…{
int key = number % 100;
int retValue = -1;

if (hash.ContainsKey(key))

…{
LRUList list = hash[key];
LRUList templist = new LRUList();
LRUList slist = list;
//LRU算法,算第一个节点的值
if (number == buffer[key, list.pageNum])

…{
templist.pageNum = list.pageNum;
list = list.next;
slist = list;
retValue = number;
}
//不是第一个节点的值则遍历后面的节点
while (list.next != null)

…{
if (number == buffer[key, list.pageNum])

…{
templist = list.next;
templist.next = null;
list.next = list.next.next;
retValue = buffer[key, list.pageNum];
}
list = list.next;
}
list.next = templist;
//如果是尾部节点的值
//LRU链表有几个值得注意的地方,即第0个节点和最后节点的置换
if (number == buffer[key, list.pageNum])

…{
retValue = buffer[key, list.pageNum];
}
hash[key] = slist;
}

return retValue;
}

#endregion
}
}

上面的代码模拟了基本的操作,如果有更多功能只能大家自己改了。:)
从这里我们也可以看到,设计一个好的软件,数学,数据结构,计算机组成原理等等基础的东西是非常重要的,决定技术高度,基础的牢固程度最重要,举个老师给我们举了一百遍的例子,房子的高度由地基牢固程度决定,真的一点不假。
最近看了一下堆这个数据结构,虽然在平时不太用到,但是也是基本的数据结构之一,不太了解所以就要了解,而且网上也没有什么好的可以使用的堆的排序方法,所以研究了一天终于把堆和优先级队列弄了个大概,在这里分享一下代码(C/C++)。
堆和堆排序
堆不是堆栈的堆,堆是以数组描述的类似二叉树的结构,但是堆的数据结构和二叉树有本质的区别,二叉树是用散列的表的形式描述的,如使用指针,而堆是以数组形式描述的,只是可以看做是二叉树,具体的基础我就不再过多的说了,可以Google一下。
堆分大根堆和小根堆,大根堆就是根节点最大的堆,左右节点都小于父节点的值,而小根堆刚好想法,根节点是最小的值,而左右节点都大于父节点,如下图。

堆满足两个性质,(1)顺序,节点和子节点都有一定的顺序,不过注意,这里的顺序不是遍历的顺序,只是父子节点之间的顺序,即父节点大于子节点或父节点小于子节点。(2)完全二叉树的特性,在创建堆得时候,我们从第0个元素开始创建,顺序的填满每个节点。
在对一组数据排序的时候,我们可以使用堆排序进行排序,堆排序最坏的情况系下为O(nlogn),所以在数据量很大的情况下是很有优势的,下面给出C#的堆排序的步骤和代码。
- 生成大根堆或小根堆,从最后的节点开始遍历调整节点。
- 将根节点和最后一个节点调换并调整调换的节点并使之符合堆的性质。(如上面我们在最右下角插入0的时候,就不满足堆的性质,我们这里就要重新调整节点并使之成为堆)
下面是代码和丰富的注释。
class Program
{
static int[] numbers = { 3, 2, 1, 4, 9, 7, 8, 5, 6 };
//索引从0开始的堆
//父:(index – 1)/2
//左孩子:2*index+1
//右孩子:2*index+2
//小根堆
static void Main(string[] args)
{
//堆排序
heapSort(numbers);
//优先级队列
//Insert(numbers, 0);
//Delete(numbers);
//优先级队列是无序的,再次排序
//heapSort(numbers);
//输出
for (int i = 0; i < numbers.Length; i++)
{
Console.WriteLine(numbers[i]);
}
Console.ReadKey();
}
//先构造大根堆,然后大根堆调整顺序则返回小根堆顺序(顺序)
//先构造小根堆,然后小根堆调整顺序择返回大根堆顺序(逆序)
public static void heapSort(int[] arr)
{
//BuildMinHeap(numbers)
BuildMaxHeap(numbers);
for (int i = (arr.Length - 1); i > 0; i–)
{
Swap(ref arr[0], ref arr[i]); //将堆顶元素和无序区的最后一个元素交换
MaxHeapify(arr, i, 0); //将新的无序区调整为堆
}
}
private static void MaxHeapify(int[] arr, int heapSize, int i)
{
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
int large = i; // 临时变量,存放大的节点值
// 比较左子节点
if (left < heapSize && arr[left] > arr[large])
{
large = left;
}
// 比较右子节点
if (right < heapSize && arr[right] > arr[large])
{
large = right;
}
if (i != large)
{
Swap(ref arr[i], ref arr[large]);
MaxHeapify(arr, heapSize, large);
}
}
private static void MinHeapify(int[] arr, int heapSize, int i)
{
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
int small = i; // 临时变量,存放小的节点值
// 比较左子节点
if (left < heapSize && arr[left] < arr[small])
{
small = left;
}
// 比较右子节点
if (right < heapSize && arr[right] < arr[small])
{
small = right;
}
if (i != small)
{
Swap(ref arr[i], ref arr[small]);
MinHeapify(arr, heapSize, small);
}
}
//构造大根堆
static void BuildMaxHeap(int[] nums)
{
for (int i = nums.Length / 2 - 1; i >= 0; i–)
{
MaxHeapify(nums, nums.Length, i);
}
}
//构造小根堆
static void BuildMinHeap(int[] nums)
{
for (int i = nums.Length / 2 - 1; i >= 0; i–)
{
MinHeapify(nums, nums.Length, i);
}
}
private static void Swap(ref int a, ref int b)
{
int tmp;
tmp = a;
a = b;
b = tmp;
}
}
上述代码为堆排序代码,我们可以使用大根堆或者小根堆为堆进行排序操作,而且也具有不错的性能。堆排序顺序遍历是有序的,而堆得有序本身不是数的有序,也就是说堆这个数组在堆排序之后就变成有序的数组了,但是堆不一定有序。
注意:堆的特性,以0开始的索引的堆父节点为当前节点的值减去1除以2,左孩子为当前节点的值乘以2加1,右孩子为加2。以1开始的索引无序加减,直接除以2,或乘以2和乘以2加1。
优先级队列
优先级队列是一种特殊的队列,普通的队列是先进先出的,而优先级队列是根据优先级出的,例如操作系统的一些优先级进程管理等等,都可以使用优先级队列。优先级队列也有最小优先级队列和最大优先级队列。
从道理上来说,优先级队列可以是任何一种数据结构,线性的,非线性的,也可以是有序的或无序的。但是针对有序的来说,获取最小或最大的值是非常容易的,但是插入却是非常困难的,而对于无序的来说,插入是很容易的,但是获取最大最小的是很麻烦的,但是可以使用堆这种折中的模式来处理,下面是复杂度的几种比较。
顺序:
- 一次插入O(n)
- 一次删除O(1)
- 平均操作n次O(n2)
无序:
- 一次插入O(1)
- 一次删除O(n)
- 平均操作n次O(n2)
堆:
- 一次插入O(nlogn)
- 一次删除O(nlogn)
- 平均操作n次O(nlogn)
要知道,nlogn和n2的复杂度相差很多,所以我们使用堆来实现优先级队列,代码如下,可以直接补在上面的代码中,优先级队列每次出列都是出优先级最小或最大的一个元素(也可以说是值最小,这要看怎么去设计),所以优先级队列只是保证根节点以及堆的特性,并不保证堆这个数组的有序性。
- 优先级队列的插入操作:将节点放到最后一个元素x[n+1]中(如何动态构建数组根据语言来定),然后调整x[n+1]用ShiftUp函数保证满足堆得性质。
- 优先级队列的删除操作:取出第一个元素x[0],并将x[n]放到x[0]中,然后用ShiftDown函数将顶部节点下移以保证堆的特性(ShiftDown时还要将变换的节点上移)。
代码和丰富的注释如下。
//优先级队列操作后是无序的堆
//插入操作
public static void Insert(int[] arr, int num)
{
int[] arrs = new int[arr.Length + 1];
CopyTo(arr, arrs, 0);
arrs[arr.Length] = num;
ShiftUp(arrs, arrs.Length
- 1);
numbers
= arrs;
}
//删除操作
public static void Delete(int[] arr)
{
int ret = arr[0];
int[] arrs = new int[arr.Length - 1];
CopyTo(arr, arrs, 1);
Swap(
ref arrs[0], ref arrs[arrs.Length - 1]);
ShiftDown(arrs, arrs.Length, 0);
numbers
= arrs;
}
//CopyTo,动态修改数组
//不过这个地方我没有用动态数组,因为C/C++无法使用动态数组
//在实现的地方这里可以因语言不通而异
public static void CopyTo(int[] arr0, int[] arr1, int index)
{
for (int i = index, j = 0; i < arr0.Length + index && j < arr1.Length; i++, j++)
{
arr1[j] = arr0[i];
}
}
//将元素向上提
public static void ShiftUp(int[] arr, int index)
{
int pindex = (index - 1) / 2;
int large = index;
if (pindex >= 0 && arr[pindex] > arr[index])
{
large = pindex;
}
if (large != index)
{
Swap(ref arr[pindex], ref arr[index]);
ShiftUp(arr, large);
}
}
//将元素向下放
public static void ShiftDown(int[] arr, int heapSize, int index)
{
int left = 2 * index + 1; // 左子节点
int right = 2 * index + 2; // 右子节点
int large = index; // 临时变量,存放大/小的节点值
//小根堆这里是比较小节点,大根堆是比较大节点
//大根堆
//if (left < heapSize && arr[left] > arr[large])
// 比较左子节点
if (left < heapSize && arr[left] < arr[large])
{
large = left;
}
// 比较右子节点
if (right < heapSize && arr[right] < arr[large])
{
large = right;
}
if (index != large)
{
Swap(ref arr[index], ref arr[large]);
ShiftUp(arr, index);
ShiftDown(arr, heapSize, large);
}
}
堆和优先级队列在一般的工程应用中除非是特殊情况我们一般是使用不到的,但是对于比较多的数据的性能提高而言,我们可以使用堆排序,另外,堆排序还可以优先级队列进行排序,当我们将元素全部插入到优先级队列之后再全部拿出数据,就是一个有序的结果集了,但是普通的优先级队列的排序方法需要使用n+1个内存,不过我们可以优化它,这里就不再深入描述了。
2009/12/5 附 C++代码
#include <iostream>
#include <string>
#ifndef CONST
#define MAX 10
#endif
using namespace std;
class Heap
{
public:
Heap();
void Init();
void Sort();
void OutPut();
private:
int numbers[MAX];
void MakeToBigHeap();
void MaxHeap(int n[],int heapsize,int i);
void Swap(int n[],int i,int j);
};
Heap::Heap()
{
}
void Heap::Init()
{
for(int i=MAX;i>=0;i–)
{
numbers[i]=i;
}
}
void Heap::Sort()
{
MakeToBigHeap();
for(int i=MAX-1;i>0;i–)
{
Swap(numbers,0,i);
MaxHeap(numbers,i,0);
}
}
void Heap::OutPut()
{
for(int i=0;i<MAX;i++)
{
cout<<numbers[i]<<endl;
}
}
void Heap::Swap(int n[],int i,int j)
{
n[i] = n[i]^n[j];
n[j] = n[i]^n[j];
n[i] = n[i]^n[j];
}
void Heap::MaxHeap(int n[],int heapsize,int i)
{
int left = 2*i+1;
int right = 2*i+2;
int big = i;
if(left<heapsize&&n[left]>n[big])
{
big = left;
}
if(right<heapsize&&n[right]>n[big])
{
big = right;
}
if(i!=big)
{
Swap(n,i,big);
MaxHeap(n,heapsize,big);
}
}
void Heap::MakeToBigHeap()
{
for(int i=MAX/2-1;i>=0;i–)
{
MaxHeap(numbers,MAX,i);
}
}
int main()
{
Heap* heap = new Heap();
heap->Init();
heap->OutPut();
cout<<"after sort"<<endl;
heap->Sort();
heap->OutPut();
return 0;
}
题目:一个好汉三个帮,三个好汉九个帮,九个好汉二十七个帮,…停,今天不是让你算n个好汉几个帮(有兴趣的网友可以自己算),我们来看这个集合
{ 1, 3, 9, 27, 81, … }
这个集合是一个递增的无限集,每个元素都是3的幂。
我们把这个集合的所有子集按照元素和从小到大的顺序排好: {}(空集), { 1 }, { 3 }, { 1, 3 }, { 9 }, { 1, 9 }, { 3, 9 }, { 1, 3, 9 }, …
现在给定一个正整数n,求第n个子集的所有元素,并按从大到小的顺序排列好
例:
n的值 结果
1 { }
4 { 3, 1 }
6 { 9, 1 }
500 { 6561, 2187, 729, 243, 81, 3, 1 }
题目:给出一个包含各种括号的表达式,判断括号是否配对。括号配对的条件:括号必须先左后右,并且左右括号数量相等;对于多重括号,从外到内嵌套顺序为:{} -> [] -> () -> <>。例如{[(<>)]}。
接口: bool match(char* str); 合法返回true, 否则返回false。
输入范例:
{[(<>)]}
{}
<(>)
<()>
返回:
true
true
false
false
来自编程爱好者编程比赛题。

Answer1#region Answer1


思路#region 思路

//为什么这道题是一个有趣的题目?我们看看下面的分析
//1-1的二进制是多少?0000,和答案相符
//4-1的二进制是多少?0011,那就是3^2和3
//6-1的二进制是多少?0101,那就是3^3和3
//看到没?求集合,只要看n-1的二进制位置和3的此方的关系即可
//如500就是,500-1的二进制111110011看看答案是不是题目给
//的所需要的答案呢?这就是技巧。。

#endregion


Code#region Code

namespace FindThree

…{
class Program

…{
static Queue<int> bin;
static List<int> result;

static void Main(string[] args)

…{
MainTest(0);
MainTest(1);
MainTest(4);
MainTest(5);
MainTest(500);
Console.ReadKey();
}

static void MainTest(int number)

…{
bin = new Queue<int>();
result = new List<int>();

//转换为二进制,用队列
ConvertToBin(number);

Queue<int> tempBin = bin;

//从队列弹出,分别计算立方的次数
//这里也可以从正面计算,然后反序
for (int i = tempBin.Count - 1; i >= 0; i–)

…{
result.Add((int)Math.Pow(3, i));
}

OutPutList();
}


转换成二进制#region 转换成二进制

static void ConvertToBin(int number)

题目:训练场上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#region Answer


思路#region 思路

//前面要说的:
//当数据量很少的时候,我们可以用最最笨的方法,不过这里最最笨的方法是用来检测结果是否正确的
//最笨的方法名字叫OldFind,这个方法就是最笨的O(n2)复杂度的遍历,非常慢,因为2000000很大。
//所以,这个不是最终答案,那么首先我们知道空间很大,所以一般做法肯定不太可能,其次最好一次
//遍历(当然不是狭义的一次),所以我们就有NewFind方法,使用链表(散列表)去做

//思路:
//所以我们这样看,对于10,3,7,4,12,2这样的序列,当读到10的时候,去找下面的比10小的数字
//并不会很好的思路,因为这样相当于遍历了不只1次,所以我们将【可以看到右边的士兵的个数】变
//成【左边可以看到自己的个数】,也就是我们读10,他被看到的次数为0,读3,被看到的次数为1,读
//7,被看到的次数也为1。为了节约空间,我们用链表去做,每一次读到一个元素,查他之前的元素,如
//果之前的元素比当前的大,则+1,否则删掉那个节点,节约空间。相当于遍历了一次O(n),然后查找
//之前的最大数是线性的,但是比线性要快,因为删掉的节点会很多,例如上面这个序列,读到12的时候
//前面的所有值都被弹开了,再找2的时候,只需要找12即可。

#endregion


Code#region Code

namespace Soldiers

…{
class Program

…{
//转换成C#的输入,输入无所谓形式

static int[] numbers = …{ 7, 3, 4, 6, 8, 10, 9, 1, 12, 15, 6, 2, 90, 54, 23, 22, 55, 19 };
static List<int> tlist;

static void Main(string[] args)

…{
int num = OldFind(numbers);
Console.WriteLine(num);
num = NewFind(numbers);
Console.WriteLine(num);
Console.ReadKey();
}

static int NewFind(int[] array)

…{
int temp = 0;

tlist = new List<int>();

if (array.Length > 0)

…{
tlist.Add(array[0]);
}

for (int i = 1; i < array.Length; i++)

…{
tlist.Add(array[i]);
temp += GetLookedTimes(array[i]);
}

return temp;
}

static int GetLookedTimes(int data)

…{
int temp = 0;

for (int i = 0; i < tlist.Count; i++)

…{
if (tlist[i] < data)

…{
tlist.RemoveAt(i);
i–;
}
else if (tlist[i] != data)

…{
temp++;
}
}

return temp;
}


老的查找办法#region 老的查找办法
static int OldFind(int[] array)

…{
int temp = 0;

for (int i = 0; i < array.Length; i++)

…{
for (int j = i + 1; j < array.Length; j++)

…{
if (array[i] > array[j])

…{
temp++;
}
else if (array[i] < array[j])

…{
break;
}
}
}

return temp;
}
#endregion
}
}

#endregion

#endregion
问题描述:我们通常把一个数组里面出现的次数最多的数字称为众数,那么众数中,如果比例超过一半了,我们可以叫这个数字为这个数组的支配者,如{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>