==============================================================================
==============================================================================
2^32 = 4294967296 约43亿
==============================================================================
==============================================================================
给定一个40亿个32位整数的顺序文件，找出一个不在文件中的数。（1.足够内存 2.几百字节内存+几个外部“临时”文件）
二分（分治的思想）
1.如果足够内存：位图技术
2.几百字节内存和几个稀疏顺序文件：二分搜索技术
==============================================================================
==============================================================================
==============================================================================
==============================================================================
*长度N的整数数组，只准使用乘法，不能使用除法，计算任意N-1个数的组合中乘积最大的一组，并写出时间复杂度。
1.P[i] = s[i-1] * t[i+1];
扫描两次得到s[i-1]和t[i-1]数组，以空间换时间。
2.正负性方法
==============================================================================
==============================================================================
《编程之美》找矩阵
bool Find(int * matrix,int rows,int columns,intnumber)
{
bool found = false;
if(matrix != NUll && rows>0&& columns>0)
{
int row = 0;
int column = columns - 1;
while(row<rows && column>=0)
{
if(matrix[row*columns + column] ==number)
{
found = true;
break;
}
else if(matrix[row*columns +column]>number)
--column;
else ++row;
}
}
return found;
}
==============================================================================
==============================================================================
最长递增子序列的长度
2.16 要求低时间复杂度
设LIS[i]：前i个元素中，最长递增子序列的长度
O(N^2)的解法：
int LIS(int [] array)
{
int[] LIS = new int[array.length];
for(int i = 0;i<array.length;i++)
{
LIS[i] = 1;
for(int j = 0;j<i;j++)
{
if(array[i]>array[j]&&
LIS[j]+1 > LIS[i])
LIS[i] = LIS[j]+1;
}
}
return Max(LIS);
}
==============================================================================
==============================================================================
==============================================================================
==============================================================================
将一个n元一维向量向左旋转i个位置（仅使用数十个额外字节的存储空间，在正比于n的时间内完成）
方法一：
移动x[0]到临时变量t，移动x[i]-x[0],x[2i]-x[i],...,t-x[lost]
方法二：
ab-ba
(arbr)r - ba
方法三：
递归迭代法：先分析原问题ab-ba,子问题
==============================================================================
==============================================================================
给定一个英语字典，找出其中的所有变位词的集合，例如pots,stop,tops
使用基于排序的标识：额外的键，将单词中字母按字母表顺序排列。先水平排序再垂直排序。
将单词内字母排序使得同一个变位词中单词具有标准型。
标识：当使用等价关系来定义类时，定义一种标识使类中每一项标识相同且唯一。
==============================================================================
==============================================================================
POJ四个链表操作问题 - 4 values whose sun is 0
#include<stdio.h>
#include<stdlib.h>
#define MAXN 4001
int apb{MAXN*MAXN],cpd[MAXN*MAXN];
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
int cmp(const void* a,const void* b)
{
return (*(int*)a - *(int*b));
}
int bin_search(int* a ,int key, int n);
int main()
{
int n,i,j,ans,t;
while(!scanf("%d",&n))//位取反
{
for(i = 0;i<n;++i)
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
for(i=o;i<n;++i)
for(j=0;j<n;++j)
{
apb[i*n+j] = a[i]+b[j];
cpd[i*n+j] = c[i]+d[j];
}
qsort(apb,n*n,sizeof(int),cmp);
t=n*n;
for(ans = i = 0;i<t;++i)
ans +=bin_search(apd,-cpd[i],t);
printf("%d\n",ans);
}
return 0;
}
int bin_search(int*a,int key,int n) //二分搜索函数
{
int cnt,up,low,mid,t;
cnt = 0;up = n-1;low = 0;
while(low<=up)
{
mid = (up+low)>>1;
if(key == a[mid])
break;
if(key < a[mid])
up = mid - 1;
else low = mid + 1;
}
if(key == a[mid])
{
++cnt;
t = mid;
while(t>0 && key == a[--t])
++cnt;
while(mid<n-1 && key ==a[++mid])
++cnt;
}
return cnt;
}
==============================================================================
==============================================================================
==============================================================================
==============================================================================
N个人，每个人一个权重。每个孩子至少一个糖果，所分配权重较高者会比邻居获得更多糖果。问至少需要多少糖果？
1.找到波谷，设为1
2.从左到右，从每一个1开始，其后比前一个多1个，直到波峰
3.从右到左，从每一个1开始，其后比前一个多1个，直到波峰
4.波峰的孩子，与第2步中相比，取最大的
5.求和
==============================================================================
==============================================================================
试题：abcd全排列，实现代码