Find Min in Rotated Array
剑指Offer一道题，一开始以为和leetcode一样，后来才发现leetcode是找target，Offer是找数组的最小元素。本质都是二分的应用，因为有序数组旋转其实是分成了两个有序数组，
有序数组的查找首选二分，但是至于怎么二分又是考察分析能力了。先从左部旋转一般情况考虑，即不考虑0个或n个的时候，因此旋转1…n-1个元素， 2 3 4 5 1及3 4 5 1 2的时候，中间数均比首尾数字要大，
其实如果大于首，说明mid一定在前一数组，前一个数组均大于后一数组元素，当然也大于尾，当4 5 1 2 3 及 5 1 2 3 4的时候，mid小于首，必位于后一数组，也必小于后一有序数组中后面的任一元素。
因此对于a[mid]>a[low]， 搜索区间变为后面区间，low=mid+1, a[mid]<a[low], 搜索区间位于前面区间，因此且可能包含mid, 因为Mid位于后于区间，可能是min, high=mid, 接下来由于需要保持了每次a[low]是前一数组，
a[high] 是后一数组中，因此当最后搜索到low+1=high,时，high是后一数组的首元素，也即min，返回即可。因此前面不应该是low=mid+1，因此mid+1 可能属于后一区间了，要么特殊处理这个，所以前面改为low=mid可以
保证每次low在前一有序数组，high在后一有序数组的性质。
接下来考虑特殊情况，也即左旋0或n个元素，其实结果一样，此时第一次low<mid<high, 那么我就单独写一个条件语句，如果是这种直接返回a[low] 即可了。
因此代码如下： (当前不考虑出现重复数的情况)
int SearchMinIndexInRotatedSortedArray(int a[], int n) {
int low=0,high=n-1;
while(low+1<high)
{
int mid=low+(high-low)/2;
if(a[mid]>a[low] && a[mid]>a[high])
low=mid+1;
else if(a[mid]<a[low] && a[mid]<a[high] )
high=mid;
else if(a[mid]<a[high] && a[mid]>a[low])
return low;
}
return high;
}
最后吸取荷兰国旗的教训，没测过OJ的都不敢保证正确性，基于上述找minidnex算法，写了一个leetcode在左旋数组里找target元素的算法，因为模仿上面从中间来直接和target元素比大小似乎看不出
target运算应该在上区间和下区间，因此还是先找minindex，然后和a[0]比较大小以确定在上区间还是下区间，然后进行二分就可以了，但是还要处理这种没有旋转的特殊情况，尤其注意
这种找min的算法while循环执行至少需要有3个element，因此要处理下0 1 2的情况是否可以统一起来。这道题目没有用很大的数据恰时间，因此随便一个线性查找都可以解决，不过面试可是有面试官的，因此
还是要拿对数时间的算法。
class Solution {
public:
int search(int a[], int n, int target) {
if(n==0) return -1;
int low=0,high=n-1;
bool rotated=true;
while(low+1<high)//at least three ele
{
int mid=low+(high-low)/2;
if(a[mid]>a[low] && a[mid]>a[high])
low=mid;
else if(a[mid]<a[low] && a[mid]<a[high] )
high=mid;
else if(a[mid]<a[high] && a[mid]>a[low])
{
rotated=false;
break;
}
}
//return a[high];
if(n==2)//two ele
{
if(a[0]<a[1])
rotated=false;
else
;
}
int l,h;
if(rotated==false)
l=0,h=n-1;
else
{
if(target>=a[0])//former interval
l=0,h=low;
else if(target<a[0])//latter interval
l=high,h=n-1;
}
while(l<=h)
{
int mid=l+(h-l)/2;
if(a[mid]<target)
l=mid+1;
else if(a[mid]>target)
h=mid-1;
else
return mid;
}
return -1;
}
};
今天群里说到指针排序，差点忘记了，之前好像是学过的，可以避免频繁的数据交换
顺便补充下，今天突然有点忘了的位运算，找x的最低位为1，其他bit赋0的数，用x&(-x) 可以得到，或者x& ~(x-1)， 因为x>0的时候，-x 取反加1了，这个是找只有两个数字只
出现一次，而其他数字都出现偶数次，那么返回这两个数中任意一个的时候用到，firstonebit=x&(-x) 接下来就可以每个数a[0..n-1]&firstonebit便可以将剩余的数分成两组了，
为什么是找最低位为1的呢，主要是因为得到这个数方便，完全可以找任意一位bit为1的，这个数也是有32bit的一个数，只是x的最低位为1的位为1，其他都为0，这样一个数。
for(int i=0;i<len;i++)
std::count<<*result++;
看到July博客的代码，这个不由得想起运算符优先级，MS校招笔试还考过，post-increment>*(取内容)>pre-increment，因此是先后面但是后增是先参与一次运算，再自增，又是相当于
先去当前result指向的值，再往后移。
http://www.cppblog.com/aqazero/archive/2012/11/10/8284.html
绝对值的或运算又有点忘记了
int i=a>>31;
return (a^i)-i
今天测了一道KMP居然TLE了，于是乎以为是需要优化，想起July的优化next数组，但是似乎没有对时间进行优化，中间WA TLE WA了，然后AC，期间范的错误现在总结起来依次为 忘记删除文件重定向了，TLE是
不能用iostream做输入输出，和scanf prinf在大数据上性能确实可能存在很大的差距，本次实测也是如此，差点以为算法还有问题。。。后一次WA是以为转化为char数组可以提高性能，后来发现本地编造的数据
都是0-9所以可以转char完全不考虑题目的数据范围，以为int一次加4个字节会比较慢，其实是错误的，然后终于AC了，还是MSVC编译的，而且他有next的函数，以至于产生重名要改next名字。
另外认识群里华科和东北大学的ACMer，还有输入输出加速，不过了解下最贵没坏处，都是利用getchar 和putchar的高效率来实现的，利用递归思想
void out(x)
{
if(x>9)
out(x/10);
putchar(x%10+’0’);
}
输入则是处理正负数实现 http://blog.csdn.net/shahdza/article/details/6317011
今天发现GCC 3.3的版本编译iostream 下的 scanf printf 可以， 到了4.7就不行了，所以C的还是尽量stdio.h吧
今天想个题目，找和为偶数的最长子序列，首选最长字段和，突然发现自己有一种新的理解这个递推方程的思路，比之前的好理解多了，非常有说服力，b[j]还是表示以a[j]为子序列尾的最大字段和的最优值，
那么b[j]长度要么为1，要么>=2吧，按长度来分，如果长为1，就是a[j],如果>=2就是至少包含a[j] a[j-1]， 那么里面一定蕴含了一个b[j-1]的最优解，如果b[j-1]最优的话，b[j]也最优，因此b[j]=max{b[j-1]+a[j], a[j]}
然后才考虑b[j-1]<0 选后者，大于0选前者，而不是本末倒置。但是发现偶数的这个题，不具备这个性质似乎，因为b[j-1]左边再加奇数，a[j]又是奇数，就会至少b[j-1]+2了，还与b[j-1]左端有关了。
想Kruskal算法的时候，有集合的操作，主要是查找元素所在的集合，以及集合的合并操作，想起了并查集，STL有个set但是里面不提供集合合并的操作，于是查到set_union, 还有merge这两个都是合并两个有序数组的算法，只是
前者删除重复数，后者保留，因此也称为何叫set union了，复杂度O(m+n) 但是我不需要有序，似乎会浪费些时间，于是看到set1.insert(set2.begin(),set2.end())的做法，但是这种不好，因为到时候怎么去维护这些集合呢，
频繁的删除操作，因此需要list存放sets么，好像太复杂了，发现还是裸写一个并查集比较好，这个是专门处理不想交集合的，维护方便，代码也不难。什么时候再连一个，就当练习并查集，这个还是比较重要的。