各种算法七 - 咕

发布时间:2017-2-21 4:09:45 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"各种算法七 - 咕",主要涉及到各种算法七 - 咕方面的内容,对于各种算法七 - 咕感兴趣的同学可以参考一下。

各种算法七

    在第六篇中,我简单的提了一下递归的思想;至于什么是递归,以及我对递归的理解,你可以看我的这篇博文:http://www.cnblogs.com/mc67/p/5114008.html

如果,不理解递归就看上面的图,如果还是不理解,就自己百度;

1.递归应用:阶乘函数

递归的作用在于把问题的规模不断缩少,直到问题缩少到能简单地解决

阶乘n!= 1 * 2 * 3 * 4 * ··· * n 

         //具体的实现;        //ps阶乘的英文是:factorial        public static int factorial(int n)        {            if (n == 1)            {                return 1;            }            else            {                return  n * factorial(n - 1);            }        }

然后就是我们的....

2.递归的应用输入 n,求斐波那契数列第n个数,

   这到道题可以说是被我们的面试官考烂的一道一呀;

   首先你得要找出斐波那契数的规律滴啊:0 1 1 2 3 5 8 13 21......

   第3项开始,每一项都等于前两项之和

 public static int fibonacci(int n)        {            if (n == 0) { return 0; }            if (n == 1) { return 1; }            //从第三项,开始,我们的规律就出来了滴啊;            return fibonacci(n) + fibonacci(n - 1);            //这个及时我们的额规律滴哎呀;,效果还是不错滴哎呀        }

3.递归的应用:找到我们的回文数滴呀

 首先你要理解什么是我们的额回文数滴呀;

就是一个字符串,从左到右边,以及从右到左边,完全是一样的;level aoa oco aabb

递归的作用在于把问题的规模不断缩少,直到问题缩少到能简单地解决

1. 字符串长度可能会奇数或偶数:

  • 如果字符串长度是奇数,字符串会剩下最中间那位字符,但其不影响回文。当检查到长度为1的时候即代表此字符串是回文
  • 如果字符串长度是偶数,当两端的字符串两两比较检查后不会剩下字符。即检查到长度为0的时候即代表此字符串是回文

2. 如果检查到两端两个字符不相同。则说明此字符串不是回文,直接返回0,不需要继续检查

数组问题存在奇数和偶数的情况是,我们一般不用 len/2 的方式,而使用的是我们的low 和 high 两个类似指针的效果来进行寻找滴哎呀;

        //接下来是我们回文数的 判断滴啊;        public static int fun(int low, int high, string arr, int length)        {            //数组的长度在不断的减小滴呀;            if (length == 0 || length == 1) { return 1;}            if (arr[low] != arr[high]) { return 0; }            //否则就继续查找;匹配滴呀;            return  fun(low+1,high-1,arr,length-2);                    }

效果还是不错滴呀;不过,当然有我们的优化方式了滴呀;效果还是不错滴呀;

public static int fun2(int low, int high, string arr)        {            if (low < high)            {                if (arr[low] != arr[high]) { return 0; }                return fun2(low + 1, high - 1, arr);            }else            {                return 1; //两个指针都已经超出了,还没遇到不想等的值,我们就返回一滴呀;            }        }

4.递归的应用:字符串反转;

 将字符串 fuck 翻转,变为kcuf

先看看我们的常规方式的呀;

 public static void reverseString( string val)        {            //最low的方式,            var newString = "";            var len = val.Length;            for(var i = 0; i < len; i++)            {                newString += val[len-1-i];            }            Console.WriteLine(newString);            //low逼方式二            string str = "";            for(var i = len - 1; i >= 0; i--)            {                str += val[i]; //这样是我们的额low方式之一滴呀;            }            Console.WriteLine("low method :{0}",str);            Console.WriteLine();            //当然有我们的方式三滴呀;效果还是不滴呀;            var low = 0;            var high = len - 1;            //折是一种交换的方式滴呀;            var arr = val.ToArray();            for(var i = 0; i < len; i++)            {                if (low < high) //用这种方式就不存在所谓的奇数个 和 偶数个的区分了滴呀;效果还是不错i呀;                {                    //这里可以加一个判断,如果相同,就不交换滴啊;                    if(arr[low]!=arr[high])                    {                        char temp = arr[low];                        arr[low] = arr[high];                        arr[high] = temp;                    }                    low++;  //这里我们可以将i 和low high 三个变量关联起来,但是,没这个必要,否则逻辑就不清晰了;                    high--;                }else                {                    break;                }            }            foreach (var i in arr)            {                Console.Write(i.ToString());            }        }

接下来就是我们的优化了滴呀;

接下来使用我们的递归进行各种优化滴呀;效果还是不错i哎呀;然后..........

你会发现上面的代码都是嵌套在我们的for 循环中滴啊;那么我们可以使用递归来替换滴啊;

public static  int reverseStr(int low,int high,char [] arr,int length)        {                     if (length==0 || length == 1)            {                return 0;            }            if (arr[low] != arr[high])            {                char temp = arr[low];                arr[low] = arr[high];                arr[high] = temp;            }            return reverseStr(low+1,high-1,arr,length-2);        }

最后额效果还是不错滴呀

最后的优化滴呀;

  

       public static  int reverseStr(int low,int high,char [] arr)        {                     if (low>high)            {                return 0; //这种方式也是可以滴呀;//而且效果不错滴呀;            }            if (arr[low] != arr[high])            {                char temp = arr[low];                arr[low] = arr[high]; //这里就是交换的事项滴啊                arr[high] = temp;            }            return reverseStr(low+1,high-1,arr);        }

5.递归的应用:折半查找滴啊;

  这种查找,的前提是我们的数组是有序的顺序滴呀;才有折半意义滴呀;查找又是另外一个比较大的话题了;

 第一种查找:漫无目的的遍历;

 第二种查找:折半循环查找;可以将循环的次数减少为:len/2 但是这种方式仅仅限于偶数个的数组中,奇数的话,无法整除,但是我们可以使用low 和 high两个指针滴呀;

 第三种查找:对有序数组的这边查找,现在我们讨论的就是现在这种滴呀;

 还是先看我们比较low的算法,然后再一步一步的优化吧

        public static int LookUpIndex()        {            string str = "fuck the life";            char key = 'e';//找到第一个就停止了;            int len = str.Length;            int low = 0;            int high = len - 1;            //一般又是一个循环            for (var i = 0; i < len; i++)            {                if (low > high) return -1;                if (str[low] == key) { return low; };//返回下标                if (str[high] == key) { return high; } //返回下标                low++;                high--;            }            return -1;        }

用我们的递归来替换我们的for循环滴啊;

        public static int LookUpIndex2(int low,int high,int [] arr,int key)        {            //记住这查找的是我们额有序数组滴呀;                        int middle = (low + high) / 2;            if (arr[middle] == key) { return middle; } //这里就不能返回执行的数字的额小标了;            if (low > high) { return 0; } //终止我们循环的条件滴呀;我不知道这个算不算我们正规意义上的递归滴呀;            if (arr[middle] > key)            {                //在左边进行查找//就要移动我们额high                high = middle - 1;                return LookUpIndex2(low,high,arr,key);            }else            {                //在右边进行查找滴啊                low = middle + 1;                return LookUpIndex2(low, high, arr, key);//继续我们的额折半查找滴哎呀;                            }                    }

这样我们递归的常用方式就总结到这里滴啊;


上一篇:STM32F10xxx 之 System tick Timer(SYSTICK Timer)
下一篇:Swift Protobuf 初探 —— 继 XML 后,JSON 也要被淘汰了吗

相关文章

相关评论