1. 在一个数组中找出出现次数超过n/2的元素
第一次看到这个题目是在《编程之美》上，书上给的算法是，每次从数组中删除两个不一样的元素，那最后剩下的就是出现次数超过n/2的元素，但是这种很直观的办法要么就是破坏原来的数组，要么将原数组复制一份，这样都不好，有没有空间需求是O(0)，而且不破坏原数组的方法呢？ 下面就是这样的一种方法，用一个计数器统计出现次数，如果发现一个跟现在保存的值不一样的，就将其减一，如果计数变成0，那么就需要更新这个值，其思想跟之前的类似，但是它的空间需求是O(0)的。下面是代码：
{
int[] list = new int[] { 1, 2, 3, 2, 2, 3, 4, 2, 3, 2, 1, 2, 2, 4, 2, 1, 2, 1 };
// int[] list = new int[] {2,1,2,1,2};
int count = 1;
int majorityElement = list[0];
for (int index = 1; index < list.Length; index++)
{
if (majorityElement != list[index])
{
if (count == 0) //之前出现的次数都因为有同等数量的不相同元素而被抵消，这时考虑更换majorityElement的值
{
majorityElement = list[index];
count++;
}
else // 碰到相异元素，抵消一次
{
count--;
}
}
else //碰到相同元素，增加一次
{
count++;
}
//do see intermediate output enable following line
//System.out.println(list[index]+": " + count);
}
if (count > 0)
Console.WriteLine("Majority Element: " + majorityElement);
else
Console.WriteLine("no any element appear over n/2 times");
}
2. String Permutation
Printing all permutations of a string is a very common interview question. We'll discuss this problem and some interesting variations of it. The original problem of string permutation says, "print all permutations of a string". As an example, if the string is "abc" there are 6 permutations {abc, acb, bac, bca, cab, cba}. Assume that string contains no duplicate elements. 代码如下：
{
if(index>totallen-1)
return;
if(index == (totallen-1))
cout<<src<<i++<<endl;
int i = 0;
for(i = index;i<totallen;i++)
{
char t = ' ';
if(index != i)
{
std::swap(src[index],src[i]);
t = src[index];
src[index] = src[i];
src[i] = t;
}
stringpermutate(src,index+1,totallen);
if(index != i)
{
t = src[index];
src[index] = src[i];
src[i] = t;
}
}
}
3. Search An Element In A Sorted Rotated Array
这是用来考察二叉搜索的一道好题，基本思路是找到rotate发生的点，将数组分为两部分，然后分别在这两部分中进行二叉搜索，代码如下：
{
if(endIndex >= beginIndex)
{
int mid = (endIndex-beginIndex)/2;
if(arr[mid] >arr[mid+1])
return mid;
else if(arr[mid] > arr[endIndex])
{
return findPivot(arr,mid+1, endIndex);
}
else
{
return findPivot(arr,beginIndex, mid-1);
}
}
return -1;
}
int binarySearch(int *arr, int beginIndex, int endIndex, int pattern)
{
if(endIndex >= beginIndex) //二叉搜索很简单，但是这一步检查很重要，因为在搜索递归的过程中，beginIndex和endIndex的差距越来越小，直至超越就是停止的时候
{
int mid = (endIndex-beginIndex)/2;
if(arr[mid] == pattern)
return mid;
else if(arr[mid]>pattern)
{
return binarySearch(arr, beginIndex, mid-1, pattern);//endIndex在变小
}else
{
return binarySearch(arr, mid+1, endIndex, pattern);//beginIndex在变大
}
}
return -1;
}
int RotatedBinarySearch(int *arr, int len, int pattern)
{
int pivot = findPivot(arr, 0, len-1);
if(pivot == -1)
{
return binarySearch(arr,0,len-1,pattern);
}
else
{
if(arr[pivot]==pattern ) // return value of findPivot is >=0, here we only need consider special case :0
return pivot;
if(arr[len-1]<pattern)
return binarySearch(arr,0,pivot-1, pattern);
else
return binarySearch(arr,pivot,len-1, pattern);
}
}
STL中有rotate的实现，其中包括3种方法，每种方法对迭代器的要求是不一样的，这里分别实现一下，尤其复习一下GCD的应用。