一些小算法

Posted on | Edited on

0、1、2排序

一串由0、1、2三个数字组成的数组，现要求把他们按有小到大的顺序排序，时间复杂度o(n)，空间复杂度o(1)。

使用三个指针，指针b，cur初始化时指向数组开头，e指向数组结尾。类似于快速排序的partition过程，如果cur指针指向的数字是0，那么与b交换，并且b++，cur++。如果cur指针指向的数字是1，那么cur++。如果cur指向的数字是2，那么与e交换，e--，注意此时cur并不向后移动，原因是有可能于e指向的数字是0，当cur于e交换后，cur指向的数字变为0，从而可以在下次循环中再与b交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void MySort(vector<int> &arr)
{
    int b = 0;
    int cur = 0;
    int e = arr.size()-1;
    while(cur <= e)
    {
        if( arr[cur] == 0 )
        {
            swap(arr[b], arr[cur]);
            b++;
            cur++;
        }
        else if(arr[cur] == 1)
        {
            cur++;
        }
        else 
        {
            swap(arr[cur], arr[e]);
            e--;
        }
    }
}

01背包问题

当前有N件物品，第i件物品物品的价值为value[i]、体积是need[i]，现有一个背包容量为M，求该背包能装下的物品的价值和最大是多少。

使用动态规划，另dp[i][j]表示对于前i件物品，背包容量为j时最大能得到的价值。对于第i件物品，可以决定放入背包或不放入背包，如果放入背包，则dp[i][j]=dp[i-1][j-need[i]]+value[i]，如果不放入背包，则dp[i][j]=d[i-1][j]，从而可以得到dp方程：

dp[i][j] = max(dp[i-1][j-need[i]] + value[i] , dp[i-1][j])

我们发现计算dp[i][j]时，仅需要dp[i-1][k]的值（0<=k<=j），从而可以把空间开销优化为o(n)，并且从后向前dp，对于这个一维大小为M的数组，循环N词，最后在dp数组中取最大的数，即可得到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>

using namespace std;

int N, M;
const int MAXM = 100001;
const int MAXN = 501;
int val[MAXN];
int need[MAXN];
int dp[MAXM];

int solve()
{
    memset(dp, 0, sizeof(dp));
    //init
    for( int i = M ; i >= need[0]; i-- )
    {
         dp[i] = val[0];
    }
    //dp
    for( int i = 1 ; i < N ; i++ )//i item
    {
        for( int j = M ; j >= need[i]; j-- )
        {
            dp[j] = max(dp[j], dp[j-need[i]] + val[i]);
        }
    }
    int res = 0;
    for( int i = 0 ; i < M ; i++ )
    {
        res = max(res, dp[i]);
    }
    return res;
}

int main(int argc, char *argv[])
{
    cin>>N>>M;
    int needTemp, valTemp;
    for( int i = 0 ; i < N ; i++ )
    {
        cin>>needTemp>>valTemp;
        need[i] = needTemp;
        val[i] = valTemp;
    }
    cout<<solve()<<endl;
}

寻找数组中个数大于一半的数

在一个数组中，有一个数字出现的次数大于数组长度的一半，求得这个数。

我们可以寻找两个不同的数，然后把他们消除，这样剩下的数字就是所求，但是我们很难在o(1)的时间内找到两个不同的数字，可以用另一种思路，即记录候选结果res和其次数n，如果遇到的字符不等于当前的字符，则把他们消除，即n--，如果相同则n++，如果n==0，就把当前字符作为出现最多的字符，把n置为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int FindOneNumber(vector<int> arr)
{
    int res = arr[0];
    int n = 1;
    for( int i = 1 ; i < arr.size() ; i++ )
    {
        if(n == 0)
        {
            res = arr[i];
            n++;
        }
        else if( arr[i] == res )
        {
            n++;
        }
        else
        {
            n--;
        }
    }
    return res;
}

整数划分

输入一个整数n，输出这个整数的所有划分方法，例如对于4，我们可以得到：4、3+1、2+1+1、1+1+1+1这四种划分方案。

为了使得有相同数字不同顺序组成的方案记作一种方案，我们另m表示当前整数划分方案中最大的数字，curSum表示当前方案已经构成的和，如果curSum==n则输出当前方案，否则尝试从m到1加入到方案中，并递归调用，注意回溯时，需要删除之前添加的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void IntSplitPrint(int n, int m, int curSum, vector<int> & cur)
{
    if( curSum == n )
    {
        for( int i = 0 ; i < cur.size() ; i++ )
        {
            cout<<cur[i]<<" ";
        }
        cout<<endl;
    }
    else
    {
        for( int i = m ; i > 0 ; i-- )
        {
            if( i + curSum <= n )
            {
                cur.push_back(i);
                IntSplitPrint(n, i, curSum + i, cur);
                cur.pop_back();
            }
        }
    }
}

最近公共祖先

一颗二叉树， 给定二叉树的两个节点u,v，求这两个节点的最近公共祖先。

使用先序遍历的方法递归遍历二叉树，在从叶子节点向根节点回溯的时候，如果该节点u、v分别在该节点的左右子树，那么该节点就是这两个给定节点的最近公共祖先。如果u、v都在给定节点的左子树或右子树上，那么就返回左子树或右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int MAXN = 1000;
class Node
{
    public:
        int left;
        int right;
        Node(){left = -1;right = -1;}
};

Node arr[MAXN];

int LCA(int root, int node1, int node2)
{
    if( root == -1 )
    {
        return -1;
    }
    if( root == node1 || root == node2 )
    {
        return root;
    }
    int left = LCA(arr[root].left, node1, node2);
    int right = LCA(arr[root].right, node1, node2);
    if( left != -1 && right != -1  )
    {
        return root;
    }
    else if(left != -1)
    {
        return left;
    }
    else if (right != -1)
    {
        return right;
    }
    else
    {
        return -1;
    }
}

奇偶排序

给定一列整数数列，对其其数字进行奇偶排序，奇数在前面，偶数在后面。

类似于快速排序的partition过程，前后两个指针begin，end，分别向中间移动，直到begin和end都不符合要求时，交换这两个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void OddEvenSort(vector<int> &arr)
{
    int begin = 0;
    int end = arr.size()-1;
    while(begin < end)
    {
        if( arr[begin] % 2 == 1 )
        {
            begin++;
        }
        else if( arr[end] % 2 == 0)
        {
            end--;
        }
        else
        {
            swap(arr[begin], arr[end]);
        }
    }
}

二分搜索

给定一个有序数组arr，和一个整数num，在数组中arr找到num所在的下标，如果没有找到，则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int BinSearch(vector<int> & arr, int num, int start, int end)
{
    while(start <= end)
    {
        int mid = (end - start)/2 + start;
        if( arr[mid] > num )
        {
            end = mid-1;
        }
        else if( arr[mid] < num )
        {
            start = mid+1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

最长公共子串

给定两个字符串a、b，求这两个字符串的最长公共子串。

使用动态规划的方法，另dp[i][j]表示a以第i个字符结尾的子串和b以第j个结尾的子串的公共子串的长度，从而如果a[i] = b[j]，那么dp[i][j]=dp[i-1][j-1]+1，否则的话dp[i][j]=0。我们发现dp[i][j]至于dp[i-1][j-1]有关，从而可以优化空间复杂度到o(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int lsc(const string & str1, const string & str2)
{
    vector<int> dp(str2.size() + 1, 0);
    int res = 0;
    for( int i = 0 ; i < str1.size() ; i++ )
    {
        for( int j = str2.size() - 1 ; j >= 0 ; j-- )
        {
            if( str1[i] == str2[j] )
            {
                dp[j + 1] = dp[j] + 1;
                res = max(res, dp[j + 1]);
            }
            else
            {
                dp[j + 1] = 0;
            }
        }
    }
    return res;
}

最长回文子串

返回一个字符串的最长回文子串，经典的MAnacher算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const int MAXLEN = 230000;
int dp[MAXLEN];
string PreProcess(string &str)
{
    string res;
    res += "^#";
    for (int i = 0; i <str.size(); i++)
    {
        res += str[i];
        res += "#";
    }
    return res;
}

int Manacher(string &str)
{
    int mx = 0;
    int id = 0;
    int i = 0;
    int res = 0;
    while(i < str.size())
    {
        dp[i] = i > mx ? 1 : min(dp[2*id-i],mx-i);
        while(str[i-dp[i]] == str[i+dp[i]])
        {
            dp[i]++;
        }
        res = max(res,dp[i]);
        if(i + dp[i] > mx)
        {
            mx = i + dp[i];
            id = i;
        }
        i++;
    }
    return res - 1;
}

最长下降子串

给定一个数组，返回最长下降子串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int Lds(vector<int> arr)
{
    if( arr.size() == 0 )
    {
        return 0;
    }
    vector<int> dp(arr.size(), 0);
    dp[0] = 1;
    int res = 1;
    for( size_t i = 1 ; i < arr.size() ; i++ )
    {
        if( arr[i] <= arr[i-1])
        {
            dp[i] = dp[i-1] + 1;
            res = max(res, dp[i]);
        }
        else
        {
            dp[i] = 1;
        }
    }
    return res;
}

洗牌算法

给定一个数组，和随机数发生器，对于该数组进行洗牌，使得每个数在每个位置出现的概率相等。 注意从后向前洗牌，对于第i个数，生成一个0到i的随机数，然后与这个数进行交换，这样这个数被放到这个位置的概率为1/n, 第二个数的概率为((n-1)/n) * (1/(n-1)) = 1/n, 以此类推。

1
2
3
4
5
6
7
void shuffle(vector<int> & arr)
{
    for( int i = arr.size() - 1 ; i >= 0 ; i-- )
    {
        swap(arr[i], arr[rand()%(i + 1)]);
    }
}

抽样算法

从1-N的N个数中随机抽取M个数，使得每个数被取到的概率相等。

Floyd算法的结构很容易递归的理解：为了从1..10中产生一个5元素样本，首先从1..9中产生一个4元素样本，然后在加上第5个元素。

我们用归纳法证明每个元素被取到的概率是一样的。 当M=1时，显然成立。假设Sample(M-1,N-1)成立，即1..N-1被取到的概率都是M-1/N-1。 那么在Sample(M,N)中，N被取到的概率为1/N+M-1/N=M/N. 对于1..N-1中的任意数一个数，在Sample(M,N)中被取到的概率是M-1/N-1+(1-M-1/N-1)/N=M/N.

1
2
3
4
5
6
7
8
9
10
11
set<int> sample(int m, int n)
{
    set<int> res;
    for(int i = n - m + 1; i <= n; i++)
    {
        int t = rand() % i + 1;
        if(res.count(t)) res.insert(i);
        else res.insert(t);
    }
    return res;
}

堆排序

非常经典的堆排序，注意在整理堆和堆排序的时候，只需要使用sink函数即可，从中间的位置开始，从后向前下沉，即可完成堆的整理。然后每次交换队顶与最后一个元素的位置，在下沉堆顶即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//big heap
void sink(vector<int> &arr, int pos, int N)
{
    while( 2 * pos + 1 < N)
    {
        int ch = pos * 2 + 1;
        if(ch + 1 < N && arr[ch] < arr[ch + 1]) ch++;
        if(arr[pos] < arr[ch]) swap(arr[pos], arr[ch]);
        pos = ch;
    }
}
//no use
void swim(vector<int> & arr, int pos)
{
    while(pos > 0)
    {
        int fa = (pos - 1) / 2;
        if(arr[fa] < arr[pos]) swap(arr[fa], arr[pos]);
        pos = fa;
    }
}
void heapsort(vector<int> & arr)
{
    for(int i = (arr.size() + 1)/ 2; i >= 0; i--) sink(arr, i, arr.size());
    for(int i = arr.size() - 1; i >= 0; i--)
    {
        swap(arr[0], arr[i]);
        sink(arr, 0, i);
    }
}