CCI题目:3-6:Stack Sort

其实是冒泡排序,两个stack来回倒腾。
代码展示的是比较直观的算法,对st排序,用另一个栈buffer作为辅助空间,那么:

1.逐个从st中pop元素,先pop到一个临时变量,如果pop出来的元素比临时变量小,则直接进入buffer,否则,把临时变量顶入buffer,st新pop到临时变量。
最后把临时变量push进buffer。
2.将buffer中的元素全部倒回st
3.重复1,2两步,直到1中第一种情况不出现为止。

《CCI》上的解法更效率一些(在阶上没有提升),就是在st到buffer中处理的过程中,允许中途将buffer中的元素倒回一部分到st,直到临时变量找到位置,然后继续将st向buffer倒。直到st为空。

此外,想到一个O(nlogn)的方法,就是,既然要用到额外最多s.size()的空间,还不如建一个最大值堆,把从stackpop出来的内容放到堆里面,然后将最大值逐个push回去。O(n logn),比参考答案快。



题目
Write a program to sort a stack in ascending order. You should not make any assump- tions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.
注:是允许用额外的Stack作为辅助空间的。



Code

<

pre>

//
// main.cpp
// CCI.3.6.Sort a Stack
//
// Created by Qiu Xiangyu on 12-11-20.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include

using namespace std;
void sortStack(stack &st) {
stack buffer;
bool bubble = true;
int rnd = 1;
while (bubble) {
cout<<“round “<<rnd++<<endl;
bubble = false;
//1.dump numbers from st to buffer and change the order of them
int middle = st.top();
st.pop();
while (st.size()) {
if (middle > st.top()) {
//if st.top is less than the one pop before, then pop to buffer
buffer.push(st.top());
bubble = true;
} else {
//if st.top is ge the one pop before, then push the middle to buffer ,then pop to middle
buffer.push(middle);
middle = st.top();
}
st.pop();
}
buffer.push(middle);
//2.dump buffer to st
while (buffer.size()) {
st.push(buffer.top());
buffer.pop();
}
}
}
int main(int argc, const char * argv[])
{
std::cout << “Hello, World!\n”;
stack st;
srand((unsigned int)clock());
for (int i = 0; i < 100; ++i) {
st.push(rand() % 10);
}
sortStack(st);
while (st.size()) {
cout<<st.top()<<endl;
st.pop();
}
return 0;
}

LeetCode题目:Sort Colors

已经有点浆糊了,其实很简单,用i记录0应该放的位置,j记录2应该放的位置。
cur从0到j扫描,
遇到0,放在i位置,i后移;
遇到2,放在j位置,j前移;
遇到1,cur后移。
扫描一遍得到排好序的数组。
时间O(n)且一次扫描,空间O(1),满足要求。
这么做的前提是,拿到一个值,就知道它应该放在哪儿。(这点和快排的根据pivot交换元素有点像)



Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library’s sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
Could you come up with an one-pass algorithm using only constant space?



代码:16ms过大集合

class Solution {
public:
    inline void swap(int &a, int &b){
        int temp = a;
        a = b;
        b = temp;
    }
    void sortColors(int A[], int n) {
        if(n <= 1) return;
        int i = 0,j = n-1;
        int cur = i;
        while(cur <= j) {
            if(A[cur] == 0) {
                if(cur > i) {
                    swap(A[i++],A[cur]);
                } else {
                    ++cur;
                    ++i;
                }
            } else if (A[cur] == 2) {
                if(cur < j)
                    swap(A[j--],A[cur]);
                else 
                    return;
            } else 
                ++cur;
        }
    }
};

LeetCode题目:Merge Sorted Array

Merge Sorted Array
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.



从大到小,选取两个数组末端大的那个数,放到A的末尾即可。



代码:24ms过大集合,时间复杂度是O(n)

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        int last = m + n - 1;
        int lasta = m - 1;
        int lastb = n - 1;
        //select largest to right position
        while(lasta >= 0 && lastb >= 0) {
            A[last--] = (A[lasta] >= B[lastb] ? A[lasta--] : B[lastb--]);
        }
        //copy remain numbers in B to A
        for(int i = 0 ; i <= lastb; ++i)
            A[i] = B[i];
    }
};



Code rewrite at 2012-12-22

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int curi = m + n - 1;
        int ia = m - 1;
        int ib = n - 1;
        while(ia >= 0 && ib >= 0) {
            if(A[ia] >= B[ib]) {
                A[curi--] = A[ia--];
            } else {
                A[curi--] = B[ib--];
            }
        }
        while (ib >= 0) {
            A[curi--] = B[ib--];
        }
    }
};



Code rewrite at 2012-12-22, The simplest code

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int ia = m - 1, ib = n - 1, icur = m + n - 1;
        while(ia >= 0 && ib >= 0) {
            A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--];
        }
        while(ib >= 0) {
            A[icur--] = B[ib--];
        }
    }
};

LeetCode题目:Anagrams

这道题目花的时间比较长,一来是因为有点麻烦,二来是因为有好几次敲完代码没保存,结果一不小心让浏览器后退了一个页面~~~不得不重新敲一遍代码。

  1. 题目描述:
    Anagrams
    Given an array of strings, return all groups of strings that are anagrams.
    Note: All inputs will be in lower-case.
  2. 思路:
      题目是让找出在一个string数组中的所有类似(含有相同字符集,且其中每个字符出现的频率一样)的字符串组。

    1. 第一个问题就是如何判断两个字符串anagram。
      由于题目中限定了全部是小写,也就是说字符范围是’a’ ~ ‘z’,26个字符,所以可以直接开26个int的数组来统计每个字符串各个字符出现的频率,这样只要两个字符串得到的这种数组相等,就可以认为这两个字符串是类似的。
      这个算法的时间复杂度是O(m)。m为字符串长度。
    2. 第二个问题就是如何在字符串数组中挑出来类似的字符串。
      这个没有想到太好的方法,直接暴力破解吧,不过可以采用一些tricks跳过不必要的计算。
      比如先将字符串数组按字符串长度排序,那么长度相等的字符串就落到了一段段连续的地址上,这样就可以很方便地跳过字符串长度不相符的部分。
      还可以给第一步得到的int数组进行一个预计算,比如按照fp->abstract += fp->fingerPrint[i] * (i+1);的形式计算一个整数作为预判条件,可以先一步滤掉不可能类似的字符串,从而用单个int相等的判断来避免一部分的数组相等判断。这一步优化使得程序从large测试超时变成了960ms
  3. 收获:
    1. sort的第三个参数要传递一个静态的函数。
      在这个问题上纠结了不少的时间。
      另外函数的形式可以是:bool comp(const string &a, const string &b) 或者 bool comp(string a,string b)
    2. 容器的resize(n),resize(n,val)函数。

下面是代码
1.
这个代码直接进行int数组的相等判断
small 8ms, large 超时

class Solution {
public:
    vector getFingerPrint(string &str) {
        vector fp(26,0);
        for(int i = 0 ; i < str.size(); ++i) {
            fp[str[i]-'a'] ++;
        }
        return fp;
    }
    static bool AcsByLen(const string &stra, const string &strb) {
        return stra.size() < strb.size();
    }
    vector anagrams(vector &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vectorresult;
        if(strs.size() < 2) {
            return result;
        }
        vector >fps;//finger prints
        vector selected(strs.size(),false);
        // sort by length
        sort(strs.begin(),strs.end(),Solution::AcsByLen);
        // calculate the finger prints of strings
        for(int i = 0; i < strs.size(); ++i) {
            string &str = strs[i];
            vector fp = getFingerPrint(str);
            fps.push_back(fp);
        }
        for (int ia = 0 ; ia < strs.size(); ++ia) {
            if(selected[ia]) continue;
            string &stra = strs[ia];
            vector fpa = fps[ia];
            for(int ib = ia + 1 ; ib < strs.size(); ++ib) {
                if(selected[ib]) continue;
                string &strb = strs[ib];
                if(strb.size() > stra.size()) {
                    break;
                }
                vector fpb = fps[ib];
                if (fpb == fpa) {
                    if(!selected[ia]) {
                        selected[ia] = true;
                        result.push_back(stra);
                    }
                    selected[ib] = true;
                    result.push_back(strb);
                }
            }
        }
        return result;
    }
};

2.改进的代码先算了一个整数来作为字符串的抽象指纹,这个整数保证了如果是类似的字符串,这个抽象指纹一定相等;但是抽象指纹相等的字符串不一定是类似的。这个优化使得程序不超时了。
small 4ms, large 960ms

class Solution {
public:
    class FingerPrint {
        public:
            vector fingerPrint;
            int abstract;
    };
    FingerPrint * getFingerPrint(string &str) {
        FingerPrint *fp = new FingerPrint();
        fp->fingerPrint.resize(26,0);
        for(int i = 0 ; i < str.size(); ++i) {
            fp->fingerPrint[str[i]-'a'] ++;
        }
        fp->abstract = 0;
        for(int i = 0 ; i < 26; i ++) {
            fp->abstract += fp->fingerPrint[i] * (i+1);
        }
        return fp;
    }
    static bool AcsByLen(const string &stra, const string &strb) {
        return stra.size() < strb.size();
    }
    vector anagrams(vector &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vectorresult;
        if(strs.size() < 2) {
            return result;
        }
        vectorfps;//finger prints
        vector selected(strs.size(),false);
        // sort by length
        sort(strs.begin(),strs.end(),Solution::AcsByLen);
        // calculate the finger prints of strings
        for(int i = 0; i < strs.size(); ++i) {
            string &str = strs[i];
            FingerPrint &fp = *getFingerPrint(str);
            fps.push_back(fp);
        }
        for (int ia = 0 ; ia < strs.size(); ++ia) {
            if(selected[ia]) continue;
            string &stra = strs[ia];
            FingerPrint &fpa = fps[ia];
            for(int ib = ia + 1 ; ib < strs.size(); ++ib) {
                if(selected[ib]) continue;
                string &strb = strs[ib];
                if(strb.size() != stra.size()) {
                    break;
                }
                FingerPrint &fpb = fps[ib];
                if (fpb.abstract == fpa.abstract 
                && fpb.fingerPrint == fpa.fingerPrint) {
                    if(!selected[ia]) {
                        selected[ia] = true;
                        result.push_back(stra);
                    }
                    selected[ib] = true;
                    result.push_back(strb);
                }
            }
        }
        return result;
    }
};



Code rewrite at 2012-12-24, 1048ms pass large set.
Be aware of the usage of static data member in class, notice the last line in this code.
For a ascending sorting, the compare function is just like 'is the first object less than the second one?'.

class Solution {
public:
    static map > g_dict;
    static bool compareSign(const string & str0, const string & str1) {
        vector & v0 = Solution::g_dict[str0];
        vector & v1 = Solution::g_dict[str1];
        return v0 < v1;
    }
    static bool equalSign(const string & str0, const string & str1) {
        vector & v0 = Solution::g_dict[str0];
        vector & v1 = Solution::g_dict[str1];
        return v0 == v1;
    }
    static bool compare(const string & str0, const string & str1) {
        if(str0.size() < str1.size()) {
            return true;
        } else if(str0.size() > str1.size()) {
            return false;
        } else {
            return Solution::compareSign(str0,str1);
        }
    }
    vector anagrams(vector &strs) {
        Solution::g_dict.erase(Solution::g_dict.begin(),Solution::g_dict.end());
        for(int i = 0; i < strs.size(); ++i) {
            string &str = strs[i];
            vector sign(26,0);
            for(int j = 0; j < str.size(); ++j) {
                ++sign[str[j] - 'a'];
            }
            Solution::g_dict[str] = sign;
        }
        sort(strs.begin(),strs.end(),Solution::compare);
        vector ret;
        for (int i = 0; i < strs.size(); ++i) {
            string &str = strs[i];
            int c = 0;
            for (int j = i + 1; j < strs.size(); ++j) {
                if (strs[j].size() != str.size()) {
                    break;
                }
                if (!Solution::equalSign(strs[j], str)) {
                    break;
                }
                if (c == 0) {
                    ret.push_back(str);
                }
                ret.push_back(strs[j]);
                ++c;
            }
            i += c;
        }
        return ret;
    }
};
map > Solution::g_dict;

iOS开发中对NSArray或者NSMutableArray中的内容排序

在iOS开发中,排序是很简单的事情:


NSMutableArray *feedsBuffer;
//初始化buffer以及填充数据
//.......
//排序只需要两句话:已针对数组内对象的publishTime属性(NSDate)排序为例:
NSSortDescriptor *sortDescriptor = [[NSSortDescriptor alloc] initWithKey:@"publishTime" ascending:NO];
[feedsBuffer sortUsingDescriptors:[NSArray arrayWithObject:sortDescriptor]];

假如feedsBuffer是NSArray,那么有一个方法是

NSArray *sortedArray = [feedsBuffer sortedArrayUsingDescriptors:[NSArray arrayWithObject:sortDescriptor]];

如果排序的依据比较复杂,那么可以使用Block进行大小判断自定义:

[feedsBuffer sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
//返回三者其一:NSOrderedAscending, NSOrderedSame, NSOrderedDescending
return NSOrderedSame;
}];