一、如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针）
struct node { char val; node next;}
bool check(const node head) {} //return false : 无环；true: 有环
一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）：
bool check(const node head)
{
if(head==NULL)
return false;
node low=head, fast=head->next;
while(fast!=NULL && fast->next!=NULL)
{
low=low->next;
fast=fast->next->next;
if(low==fast)
return true;
}
return false;
}
一个指针每次在链表中前进一个位置，另一个前进两个。
“并行”！
/**
得到如下样式的二维数组
zigzag（jpeg编码里取象素数据的排列顺序）
0, 1, 5, 6,14,15,27,28,
2, 4, 7,13,16,26,29,42,
3, 8,12,17,25,30,41,43,
9,11,18,24,31,40,44,53,
10,19,23,32,39,45,52,54,
20,22,33,38,46,51,55,60,
21,34,37,47,50,56,59,61,
35,36,48,49,57,58,62,63
/
#include <iostream>
#include <algorithm>
using namespace std;
#define DEMENTION 6
int main()
{
int array[DEMENTION][DEMENTION];
int i, j, k;
int flag = 1;
int count = 1;
for(k=0; k<DEMENTION; ++k) {
if(flag) {
flag = 0;
for(i=0,j=k; i<=k&&j>=0; ++i,–j) {
array[j][i] = count++;
}
}
else {
flag = 1;
for(i=0,j=k; i<=k&&j>=0; ++i, –j) {
array[i][j] = count++;
}
}
}
for(k=DEMENTION-1; k>=0; –k) {
if(flag) {
flag = 0;
for(i=DEMENTION-k,j=DEMENTION-1; i<DEMENTION&&j>=DEMENTION-k; ++i,–j) {
array[j][i] = count++;
}
}
else {
flag = 1;
for(i=DEMENTION-k,j=DEMENTION-1; i<DEMENTION&&j>=DEMENTION-k; ++i,–j) {
array[i][j] = count++;
}
}
}
for(i=0; i<DEMENTION; ++i) {
copy(array[i], array[i]+DEMENTION, ostream_iterator<int>(cout, " "));
cout << endl;
}
return 0;
}
or
/ 数组赋值 /
squa = NN;
for(i = 0; i < N; i++)
for(j = 0; j < N; j++) {
s = i + j;
if(s < N)
a[i][j] = s(s+1)/2 + (((i+j)%2 == 0)? i : j);
else {
s = (N-1-i) + (N-1-j);
a[i][j] = squa - s(s+1)/2 - (N - (((i+j)%2 == 0)? i : j));
}
}
三、给定九个数，例如：1，3，3，5，6，7，8，8，9计算出这九个数的排列的种数。需要考虑重复情况，如果给定9个1，则只有一种结果。
限制：不能使用stl库
要求：完成函数 unsigned int foo(unsigned int arr);
输入算法代码，并给出算法复杂度分析。
分析：
#include <cstdlib>
#include <iostream>
using namespace std;
unsigned int foo(unsigned int arr)
{
unsigned int p[] ={1,2,6,24,120,720,5040,40320,362880};
unsigned int i,j,c,s=p[8];//first the number is p99
for(i = 0; i < 7; i++)
for(j = i+1; j < 8; j++)
{
if(arr[i]>arr[j]) //swap two number
{
arr[i]^=arr[j];
arr[j]^=arr[i];
arr[i]^=arr[j];
}
}
i = 0;
c = 0;
while(i<8)
{
j = i+1;
while(arr[i]==arr[j])//compute the number of the repetition
{
c++;
j++;
}
s/=p[c];
c=0;
i=j;
}
return s;
}
int main()
{
unsigned int a[]={1,3,3,5,6,7,8,8,9};
cout<<"The number of permutation is: "<<foo(a)<<endl;
system("pause");
return 0;
}
还可以改进排序那部分。
四、有一个数在一个数组中出现50%以上，让你在O(n)的时间内，O(1)的空间复杂度，找出那个数，其中数组内的数都是随机数，但是有范围。
一个数超过了50%，那么就每次拿这个数（设为A）和其它数抵消，最后剩下的肯定是它，但是空间复杂度是O(1)，所以只能顺序的读入数组，且不能整个存 储。那么就不能保证每次都是拿A和非A抵消，再一想，只要抵消两个不同的数就行了，那么如果碰到两个相同的数呢，留一个，但是要记录重复的次数，稍加考虑 就能看出，这个次数始终记录的都会是一个数重复的次数，不会出现要同时记录多个数的重复次数，因为遇到不同的就抵消了，这样的话只要开3个数的空间，顺序 扫描一边数组就能得出所要求的数。下面举个简单例子：
数组内数为：2 2 2 4 4 3 3 2 2 2
经过三步处理之后当前数是2，重复次数是3，遇到4，当前数还是2，重复数-1=2，如此下去，当遇到第二个3时，当前数是3，遇到下一个2，抵消，再遇到2，当前数就是2，最后当前数仍是2，重复数是1，则所求是2…
五、经典DP：用面值为1、2、5、10、20的纸钞组合出100块钱，一共有多少种可能。
C(n,S)：用前n种纸钞组合出S块钱的组合数，1<=n<=5
总可能数 ＝ C(4,100) + C(4,80) + C(4,60) + … + C(4,20) + C(4,0)
C(4,100):不用20的纸钞
C(4,80) :用1张20的纸钞
C(4,0) :用5张20的纸钞
C(4,80) = C(3,80) + C(3,70) + … + C(3,10) + C(3,0)
C(4,60) = C(3,60) + C(3,50) + … + C(3,10) + C(3,0)
…
记录重复出现的中间结果，达到优化
六、另类最大递增子序列问题：一个数组（其中每个元素都互不相同），它的子序列是指从原数组中抠掉若干个元素留下来的序列（因此并不要求连续）。递增子序列是指那些元素递增的子序列。最大递增子序列是指这样的一些递增子序列：无论从原数组中返还哪个元素，都不会使得这个子序列再增长为一个更长的递增子序列了。（注意，最大递增子序列不同于最长递增子序列。）求一个算法，返回一个数组中的最大递增子序列的个数。
英文描述：
A subsequence of a sequence of numbers a is the result of erasing zero or
more elements from a. An increasing subsequence is a subsequence in which
each element (except the first) is strictly greater than the previous
element. An increasing subsequence of a is maximal if unerasing any of the
erased elements of a does not result in a longer increasing subsequence.
but not a maximal increasing subsequence. {1,2,4,5}, {1,3,4,5}, {1,2,6} and
{1,3,6}, on the other hand, are maximal increasing subsequences.
第前一个问题的"扩展"版本是"最长递增子序列"问题：最长递增子序列问题要求一个算法返回数组中最长的递增子序列的长度。问题严格描述如下：设L=<a1
,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
二分法，分为两部分，分别找出各自的最大递增子序列，然后合并
七、Write a function to find the two closest points given N points in X-Y
coordinates, and analyze the time and space complexity of your function.
The input to this funciton is a pointer or reference to an array of
points, along with N. The ouput is a pointer or reference to a two-element array that stores
the coordinates of the two points closest to each other.
雕琢分而治之最近点对算法：http://jcst.ict.ac.cn/content/papere.asp?lg=cn&i=7406
八、Write a function to find any subset of 3 integers from a set of N
integers that have a sum with the smallest absolute value, and analyze
the time and space complexity of your function.
The input to this funciton is pointer or reference to any array of
integers, along with the value of N.
When N>=3, the ouput is a 3-element array of integers, such that their
sum has the smalles absolute value.
When N<3, the ouput is null.
For example,given the following input:{-99, -66, 0, 2, 3}, your
function should return {0,2,3}
如果有3个0， 那么直接返回。
如果有2个0，看最小的正数和最大的负数。
如果有1个0或没有0，对正数和负数排序，对每个负数a，在正数数组中查找两个离-a 最近的元素；对每个正数，在负数数组中找两个离-a最近的元素。
如何“对每个负数a，在正数数组中查找两个离-a 最近的元素“？
将正数序列（已排好序）中每一个数减去|a/2|，问题转化为“在这个新的序列中找两个数，使得和的绝对值最小”，
进一步转化为“在新序列中，将所有负数取其绝对值，插入到正数序列中（O(N)）并标记好这些数，然后找距离这些数距离最近的点（O(N)）”
因此总的可以在O(N2)解决
九、给出n个石头，每个石头都有一个权值。要求从最左边开始向右敲，再从最右边开始向左敲，每个石头只能敲一次且必须敲一次，求一种敲法，使得敲法序列中相邻两个石头的权值的差之和最小。
http://groups.google.com/group/pongba/msg/5e0a258fc35ca21c
？？
十、有 A-H 8种颜色，每种颜色有一个分值。给出n个珠子，每个珠子有8个面，每个面上都涂有颜色。把这n个珠子串起来变成一个环，要求相邻两个珠子的接触面颜色必须相同，总分值为每相邻两个珠子的接触面颜色的分值之和。求这n个珠子可以获得的最大分值。
？？
十一、只翻转列，使得满足要求的行最多
Jack has bought a rectangular table containing a grid of lamps. Each lamp is initially either "on" or "off". There is a switch underneath each column, and when the switch is flipped, all the lamps in that column reverse their states ("on" lamps become "off" and vice versa).
A row in the grid is considered lit if all the lamps in that row are "on". Jack must make exactly K flips. The K flips do not necessarily have to be performed on K distinct switches. His goal is to have as many lit rows as possible after making those flips.
You are given a string[] initial, where the j-th character of the i-th element is ‘1’ (one) if the lamp in row i, column j is initially "on", and ‘0’ (zero) otherwise. Return the maximal number of rows that can be lit after performing exactly K flips.
- initial will contain between 1 and 50 elements, inclusive.
- Each element of initial will contain between 1 and 50 characters, inclusive.
- Each element of initial will contain the same number of characters.
- Each element of initial will contain only the digits ‘0’ and ‘1’.
- K will be between 0 and 1000, inclusive.
分析：
Sooner or later you should notice one very important fact: all equal rows remain equal after any number of flips. So, if some row is lit at any moment, all initially equal rows will be lit as well and all other rows will not be lit. Therefore, the solution is to try for each row to make lit, and if it is possible, count the number of rows equal to this one and choose among such rows one with the maximal number of equal rows.
How to check if the given row can be lit after exactly K flips ? Note that the order of flips doesn’t affect on the final result. Also, making 2 flips in the same column doesn’t change row at all. Suppose we have M "off" lamps in this row. To be able to switch all these lamps to the "on" state we need exactly M flips. So, K should be no less than M. Now, if (K-M) is even, we can flip always the first column and at the end the row will be lit. If (K-M) is odd, it’s impossible to lit this row after exactly (K-M) flips.
struct LampsGrid {
int mostLit( vector <string> initial, int K ) { // caret here
int res = 0;
for ( int i=0; i<(int)initial.size(); ++i ) {
int zeros = count(initial[i].begin(), initial[i].end(), ‘0’);
if ( zeros%2 == K%2 && zeros <= K ) {
res = max( res, count(initial.begin(), initial.end(), initial[i]) );
}
}
return res;
}
};
十二、Tree of Tree
You’re given a tree with weights of each node, you need to find the maximum subtree of specified size of this tree.
Tree Definition
A tree is a connected graph which contains no cycles.
Input
There are several test cases in the input.
The first line of each case are two integers N(1 <= N <= 100), K(1 <= K <= N), where N is the number of nodes of this tree, and K is the subtree’s size, followed by a line with N nonnegative integers, where the k-th integer indicates the weight of k-th node. The following N - 1 lines describe the tree, each line are two integers which means there is an edge between these two nodes. All indices above are zero-base and it is guaranteed that the description of the tree is correct.
Output
One line with a single integer for each case, which is the total weights of the maximum subtree.
Sample Input
3 110 20 30
0 1
0 2
3 2
10 20 30
0 1
0 2
Sample Output
3040
Author: LIU, Yaoting
Source: ZOJ Monthly, May 2009
#include<iostream>
#include<vector>
using namespace std;
const int M=105;
int n,k;
int d[M][M],w[M];
vector<int> sun[M];
void dp(int x,int y){
int i,j,t1[M];
memset(t1,0,sizeof(t1));
for(i=1; i<=k; i++){
for(j=1; j<=i; j++)
t1[i]=max(t1[i], d[x][j]+d[y][i-j]);
}
for(i=1; i<=k; i++) d[x][i]=max(d[x][i],t1[i]);
}
void dfs(int now,int pre){
int len=sun[now].size();
int cnt=0;
//if(pre!=-1 && len==1) { d[now][1]=w[now]; return; }
for(int i=0; i<len; i++){
if(sun[now][i]!=pre) {
dfs(sun[now][i],now);
d[now][1]=w[now];
dp(now,sun[now][i]);
cnt++;
}
}
if(cnt==0) d[now][1]=w[now]; //初始化。。
}
int main(){
while(scanf("%d%d",&n,&k) != EOF ){
for(int i=0; i<n; i++) {
scanf("%d",&w[i]); sun[i].clear();
}
int l,r;
for(int i=1; i<n; i++) {
scanf("%d%d",&l,&r);
sun[l].push_back(r);
sun[r].push_back(l);
}
int res=0;
memset(d,0,sizeof(d));
dfs(0,-1);
for(int i=0; i<n; i++) res=max(res,d[i][k]);
printf("%dn",res);
}
return 0;
}
十三、
对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。
如：18！＝6402373705728000，尾部连续0的个数是3。
int ZeroNumber(int n)
{
int base = 5;
int sum = 0;
while (n >= base) {
sum += n / base;
base *= 5;
}
return sum;
}