几个关于串的小算法题：最小K个数、连续子数组的最大和、字符串全排列求法、数组循环移位

最小K个数：

法一：

用改装的快速排序，分割函数不变。

分割后返回的标号index若等于k-1或k则退出，

大于k，则递归左侧

小于k，则递归右侧

此法复杂度为O(n)，但会移动原始数据

法二：

借助拥有k个节点的最大堆

若总元素数小于等于k，则全部返回

遍历所有元素，依次增加到一个最大堆中，对堆的元素数保持计数

若元素数达到n==k，则在处理下一个数据d 时，

若d大于等于最大堆堆顶值，则直接抛弃

否则，删除堆顶元素，并将d加入到堆中。

最终，堆中剩余的k个元素即为最小的k个

此法复杂度O(klogk) ，但好处是无需移动原始数据，适合大数据情况

连续子数组的最大和

问题描述：输入一个整数数组，数组中有正数也有负数，一个或连续的多个整数组成一个子数组，求所有子数组的和的最大值。

解决方案：

主要思路：若前面字串的累加和是正的，再加上下一个数可能还会变大。后面再加上一个负数也没事，因为后面可能会有个绝对值更大的正数，导致总体继续增长

而若前面的和是已经是负的，就没必要再累加下去了。就算后面是正数，前面的也只会扯后腿。因此抛弃

如：3 -2 3 -5 5 ，看了第一个元素后累加和是3，加上第二个后变成1，但再后面的3让总体变成了4。再看到-5后总体变-1，就没必要再累加下去了，只会拖累前面的和。需要重新计数，是5。因此最后结果是5

int sum = INT_MIN;   // 初始sum为最小32位有符号数
    int curSum = 0; //当前最小和
    for(int i = 0; i < length; ++i) //遍历整个数组
    {
        if(curSum <= 0)   //若当前和小于0，则说明已经下降，需要重新开始计数
            curSum = data[i];    //重新计数
        else
            curSum += data[i]; //继续累加，给后面机会！

        if(curSum > sum) //判断是否更大
            sum = curSum;
    }

字符串全排列求法

递归方案：

按照人手动计算的思路，先固定第一个元素，后面的递归计算全排列。而第一个元素总共有strlen（str）种可能，可以使用循环。

思路：

假设序列中没有重复元素。若有，则只要让重复元素在循环中只进行一次即可

if(begin == end) // 递归中止条件
printf("%s\n", str);

for(char *x = begin; x < end; x++) //递归
        {
            // 交换x和begin指向的字符
            Swap(x, begin);
            Permutation(str, begin + 1, end);    //递归后面的序列
            // 恢复x和begin指向的字符
            Swap(x, begin);
        }

数组循环移位k

循环左移直观方法：建一个k大小的缓冲区，先把0~k-1元素复制出来，把后面元素移动到前面，然后把缓冲区中的k个值移动回数组的最后

改进版循环左移（原地交换版）：

首先将前k个元素原地求逆，然后后面所有元素原地求逆，然后整个数组原地求逆。

1234567循环右移3位 1234567-> 3214567-> 3217654-> 4567123

循环右移，即为求逆变换的是最后k个元素和前面的元素，然后整体求逆。

补充：软件开发 , C语言 ,