一些常见算法的汇总

概率计算

1
2
3
4


static bool GetProbability(int percentage)
{
	return Random.Range(0, 100) < percentage;
}

判断两个时间段是否相交或重叠

1

bool overlap = a.start < b.end && b.start < a.end;

通过相交判断，可以求得相交最多的片段集合，用两层 for 循环即可

夹逼定理

夹逼定理，时间到了动画自动播放判断

1
2
3
4
5


preTime = curTime;
curTime += deltaTime;
bool canPlay() {
	return preTime <= fireTime && curTime > fireTime；
}

引用计数

常用于成对出现的，比如一进一出，这个过程中，如果时序不确定，则可以使用引用计数来解决这个问题。

加权平均法

加权平均法，即将各数值乘以相应的单位数，然后加总求和得到总体值，再除以总的单位数。平均数的大小不仅取决于总体中各单位的值的大小，而且取决于各标志值出现的次数，由于各标志值出现的次数对其在平均数中的影响起着权衡轻重的作用，因此叫做权数。

举例说明，下面是一个同学的某一科的考试成绩：平时测验 80，期中 90，期末 95

学校规定的科目成绩的计算方式是：

平时测验占 20%；期中成绩占 30%；期末成绩占 50%；

这里，每个成绩所占的比重叫做权数或权重。那么，

加权平均值 = 8020% + 9030% + 95*50% = 90.5 算数平均值 = (80 + 90 + 95)/3 = 88.3

随机选择

1
2
3
4
5
6
7
8


// 等概率的选取一个集合中的一个元素
int random_number(int max) {
    return rand() % max;
}

int random_select(const vector<int>& v) {
    return v[random_number(v.size())];
}

上面的C++代码并不是绝对等概率的，因为使用了rand()取余来获取随机数，这个函数产生的随机数通常是不均匀分布的。现在考虑另外一种情况，如果不知道集合的长度，只能使用迭代器，那么random_select该如何实现了？我刚好看到一篇博客对这个问题做了说明，C#的解决方法如下：

 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


using System;
using System.Collections.Generic;

namespace RandomSelect {
	
	class Program {
		
		static Random random = new Random();
		
		public static T RandomSelect<T>(IEnumerable<T> enumerable) {
			int count = 0;
			T selected = default(T);
			
			var enumerator = enumerable.GetEnumerator();
			while (enumerator.MoveNext()) {
				if (random.Next(++count) == 0) {
					selected = enumerator.Current;
				}
			}
			
			return selected;
		}
		
		public static void Main(string[] args) {
			var list = new List<int> { 1, 2, 3, 4, 5 };
			int testCount = 32;
			for (int i = 0; i < testCount; ++i) {
				Console.Write(RandomSelect(list));
				Console.Write(" ");
				if ((i + 1) % 10 == 0) {
					Console.WriteLine();
				}
			}
			Console.WriteLine();
			
			Console.Write("Press any key to continue . . .");
			Console.ReadKey(true);
		}
	
	}

}

一次产生多个不同的随机数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


//generate many different random num
int *resultNums = new int[totalEnergyNum];
for (int i = 0; i < totalEnergyNum; i++)
{
    resultNums[i] = IwRandMinMax(0, validBubbleNum);
    for (int j = 0; j < i; j++)
    {
        if (resultNums[j] == resultNums[i])
            i--;
    }
}
delete []resultNums;

汉诺塔问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


//汉诺塔问题
void move(char getone,char putone)//将一个盘子从一根针移到另一根上
{
    cout<<getone<<"-->"<<putone<<endl;
}

void hanoi(int n,char one,char two,char three)//将多个盘子从一根针移到另一根上
{
    if(n==1)
        move(one,three);
    else
    {
        hanoi(n-1,one,three,two);//将A上n-1个盘子移动到B上（借助C）
        move(one,three);//把A上剩下的一个盘子移动到C上
        hanoi(n-1,two,one,three);//将n-1个盘子从B移到C上（借助A）
    }
}

判断是否为回文数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


//判断是否为回文数，如121,676
bool isHuiwen(long n)
{
    long p,m;
    p=n;
    m=0;
    while(p)
    {
        m = m*10 + p%10;
        p = p/10;
    }
    return (m==n);
}

判断数字回文的方法很简单，比如121，要进行判断，先对121求余运算得到末尾数字1；接下来要得到数字2，可以接着对121进行除以10的运算变成12，继续求余可以得到2；循环使用上述方法，最终可以得到新的m，判断m与n是否相等即可。

判断一个数是否是2的幂次方

1
2
3
4


// 判断一个数是否是2的幂次方
bool IsPowerOfTwo(int num) {
    return ((num - 1) & num) == 0;
}

求一个数的二进制中1的个数

1
2
3
4
5
6
7
8
9


// 求一个数的二进制中1的个数
int GetNumberOfOne(int num) {
    int count = 0;
    while (num) {
        num = (num - 1) & num;
        count++;
    }
    return count;
}

二维数组按列转为一维数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// 把下列二维数组按列转为一维数组，输出：12 56 34 78
string[,] arr = new string[2, 4] { {"1","2","3","4" },{"5","6","7","8" } };

string[] ss = new string[arr.Length];
int index = 0;
for (int j = 0; j < arr.GetLength(1); j++)
{
    int jj = j;
    for (int i = 0; i < arr.GetLength(0); i++)
    {
        j = jj;
        ss[index++] = arr[i, j];
        if (j < arr.GetLength(1) - 1)
        {
            j++;
            ss[index++] = arr[i, j];
        }
    }
}

全排列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


void FullPermutation(int a[], int len, int i)
{
    // 全排列，比如数组{1,2,3}，一共3个数字，那么全排列有6个，阶乘。
    // i默认为0，len为数组长度。
    if (i == len-1) {
        // 递归的出口，输出全排列的数据
        for_each(a, a+len, [](int n) { cout << n << " ";});
        cout << endl;
        return;
    }
    if (i < len) {
        for (int j = i; j < len; j++) {
            // 如果i开始为0，那么就是第一个数不断与后面的数字互换
            swap(a[i], a[j]);
            // 然后i开始递增，第i个数不断与后面的数互换，意味着范围不断减小，直至为一个数
            // n个元素的全排列 = （一个元素作为前缀）+（n-1个元素的全排列），和阶乘一样
            FullPermutation(a, len, i+1);
            swap(a[i], a[j]);
        }
    }
}

求最大连续子数组

 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


//寻找整型数组的最大连续子数组，并输出起止位
//加上一个数使子数组变大，减去一个数使子数组变小
//遍历过程中，如果中间变量tmp为负时，则丢弃已经遍历的和
int MaxSubArray(int data[], int size, size_t &beg, size_t &end)
{
    int tmp = 0;
    int maxvalue = 0;
    size_t tmp_beg = 0;
    for(size_t i=0; i<size; i++)
    {
        tmp += data[i];
        if (tmp < 0)//如果小于0，则起始位变为i+1,负数情况暂且不考虑
        {
            tmp = 0;
            tmp_beg = i + 1;
        }
        if (tmp > maxvalue)//如果更新后的值变大，则更新maxvalue与终止位end与起始位beg
        {
            maxvalue = tmp;
            end = i;
            if (tmp_beg <= end)
            {
                beg = tmp_beg;
            }
        }
    }
    //全负数的情况
    if (maxvalue == 0)
    {
        maxvalue = data[0];
        for (size_t j = 0; j < size; j++)
        {
            if (data[j] > maxvalue)
            {
                maxvalue = data[j];
                beg = end = j;
            }
        }
    }
    return maxvalue;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// 测试函数
void testMaxSubArray()
{
    //求数组中连续的最大数，并输出起止位
    int data[] = {-1, 98, 8, 76, -23, -988, 22, 12, 32, 48, 23, 23 ,23, -8 -987};
    int data1[] = {1, 2, -2, 1};
    size_t beg = 0;
    size_t end = 0;
    cout << MaxSubArray(data1, sizeof(data1)/sizeof(data1[0]), beg, end) << endl;
    if (beg == end)
    {
        cout << beg << endl;
    }
    else
    {
        cout << beg << " " << end << endl;
    }
}

字符串循环右移

 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


//把一个char字符串循环右移n位
void loopMove(char *pStr, int n)
{
    if (n <= 0 || NULL==pStr)
        return;
    const int len = strlen(pStr);//数组长度
    n = n % len;//实际要移动的位数
    char *tmp = new char[len + 1];//临时数组

    for (int i = 0, j = n; i < len - n; ++i)//把数组的一半移动到临时数组的右侧
    {
        tmp[j++] = pStr[i];
    }

    for (int k = 0; k < n; ++k)//把数组的另一半移动到临时数组的左侧
    {
        int p = len - n + k;
        tmp[k] = pStr[p];
    }
    tmp[len] = '\0';//填充数组最后一位
    
    for (int m = 0; m <= len; ++m)
    {
       pStr[m] = tmp[m];
    }
    delete []tmp;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


//字符串循环右移的strcpy版本
void loopMove1(char* pStr, int n)
{
    if (n <=0 || NULL == pStr)
        return;
    const int len = strlen(pStr);//数组长度
    n = n % len;//实际要移动的位数
    char *tmp = (char*)malloc((len + 1) * sizeof(char));
    memset(tmp, 0, len + 1);
    //原字符串pStr复制到tmp，tmp的下标从n处开始,pStr下标从0开始
    strncpy(tmp + n, pStr, len - n);
    //原字符串pStr复制到tmp，tmp的下标从0处开始,pStr下标从len-n开始
    strncpy(tmp, pStr + len - n, n);
    tmp[len] = '\0';//填充最后一位
    strcpy(pStr, tmp);//把结果填充到原字符串中
    free(tmp);//释放资源
}

 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


//字符串循环右移的翻转版本
/*例如字符串hello，右移2位，则lo将被移出，我们分别翻转前后两部分，得到leh ol，
然后全部翻转得到lohel,这就是想要的结果。
*/
void reverseStr(char* str, size_t begin, size_t end)
{
    //不断从两头交换字符来进行翻转
    if (str != NULL && strlen(str) > 1)
    {
        char temp;
        while(begin < end)
        {
            temp = str[begin];
            str[begin] = str[end];
            str[end] = temp;
            begin++;
            end--;
        }
    }
}
void loopMove2(char* pStr, int n)
{
    if (n <=0 || NULL == pStr)
        return;
    const int len = strlen(pStr);//数组长度
    n = n % len;//实际要移动的位数
    reverseStr(pStr, 0, len - n - 1);//先翻转左边部分
    reverseStr(pStr, len - n, len - 1);//后翻转右边部分
    reverseStr(pStr, 0, len - 1);//翻转整个字符串
}

常见算法汇总

文章目录