首页 微博热点正文

(给算法爱好者加星标,修炼编程内功


作者:帅地 (本文来自作者投稿,简介见结尾)



今日和柳树,一些常用的算法技巧总结,六尺巷咱们讲讲,在做算法题时常用的一些技巧。关于平常没用过这些技巧的人,或许你能够考虑试着去看看在实践中能否用的上这些技巧来优化问题的解。


1. 巧用数组下标


数组的下标是一个隐含的三国之霸王门徒很有用的数组,特别是在核算一些数字,或许判别一些整型数是否呈现过的时分。例如,给你一串字母,让你判别这些字母呈现的次数时,咱们就能够把这些字母作为下标,在遍历的时分,假如字母a遍历到,则arr[a]就能够加1了,即  arr[a]++;


经过这种巧用下标的办法,咱们不需求逐一字母去判别。


我再举个比方:


问题:给你n个无序的int整型数组arr,并且这些整数的取值规模都在0-20之间,要你在 O(n) 的时刻复杂度中把这 n 个数依照从小到大的次序打印出来。


关于这道题,假如你是先把这 n 个数先排序,再打印,是不或许O(n)阜宁焦爱芹老公的时刻打印出来的。可是数值规模在 0-20。咱们就能够巧用数组下标了。把对应的数值作为数组下标,假如这个数呈现过,则对应的数组加1。


代码如下:


public void f(int arr[]{

       int[] temp = new int[21];
       for (int i = 0; i < arr.length; i++) {
           temp[arr[i]]++;
       }
       //次序打印
       for (int i = 0; i < 21; i++) {
           for (int j = 0; j < temp[i]; j++) {
               System.out.println(i);
           }
       }
   }

提示:能够左右滑动


运用数组下标的运用还有许多,咱们今后在遇到某些题的时分能够考虑是否能够巧用数组下标来优化。



2. 巧用取余


有时分咱们在遍历数组的时分,会进行越界判别,假如下标差不多要越界了,咱们就把它置为0从头遍历。特别是在一些环形的数组中,例如用数组完结的行列。往往会写出这样的代码:


for (int i = 0; i < N; i++) {
  &nbs柳树,一些常用的算法技巧总结,六尺巷p;    if (pos < N) {
        //没有越界
        // 运用数组arr[pos]
    &nbs华山漫空栈道灵异事情p;   else {
          pos = 0;//置为0再运用数组
  &nbs汤盈盈老公p;       //运用arr[pos]
  &n艾帝雅bsp;      }
        pos++;
   }


实际上咱们能够经过取余的办法来简化代码


for (int i = 0; i < N; i++) {
  //运用数组arr[pos]   (咱们假定刚开始的时分pos < N)
&nb柳树,一些常用的算法技巧总结,六尺巷sp; pos = (pos + 1) % N;
}


3. 巧用双指针


关于双指针,在做关于单链表的题是特别有用,比方“判别单链表是否有环”、“怎样一次遍历就找到链表中心方位节点”、“单链表中倒数第 k 个节点”等问题。关于这种问题,咱们就能够运用双指针了,会便利许多。我趁便说下这三个问题怎样用双指针处理吧。


例如关于第一个问题


咱们就能够设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移毛宇琳动一个节点,而快指针一次移动两个节点,假如该链表没有环,则快指针会先遍历完这个表,假如有环,则快指针会在第2次遍历时和慢指针相遇。


关于第二个问题


相同是设置一个快指针慢指针。慢的一次移动一个节点,而快的两个。在遍历链表的时分,当快指针遍历完结时,慢指针刚好到达中点。


关于第三个问题


设置两个指针,其间一个指针先移动k个暗血部队节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完结的时分,第二个指针正好处于倒数第k个节点。


你看,选用双指针便利多了吧。所以今后在处理与链表相关的一些问题的时分,能够考虑双指针哦。


4. 巧用移位运算。


有时分咱们在进行除数或乘数运算的时分,例如n / 2,n / 4柳树,一些常用的算法技巧总结,六尺巷, n / 8这些运算的时分,咱们就能够用移位的办法来运算了,这样会快许多。


例如武界神刀:


n / 2 等价于 n >> 1

n / 4 等价于 n >> 2

n / 8 等价于 n >> 3。


这样经过移位的运算在履行速度金特宝上是会比较快的,也能够显的你很厉害的姿态,哈哈。


还有一些 &(与)|(或)的运算,也能够加速运算的速度。例柳树,一些常用的算法技巧总结,六尺巷如判别一个数是否是奇数,你或许会这样做


if(n % 2 == 1){
 dosomething();
}


不过咱们用与或运算的话会快许多。例如判别是否是奇数,咱们就能够把n和1相与了,假如成果为1,则是奇数,不然就不会。即


if(n & 1 =孔军超= 1){
 dosomething();
)


详细的一些运算技巧,还得需求你们多在实践中尝试着去运用,这样用久后就会比较熟练了。


5. 设置岗兵位


在链表的相关问题中,咱们经常会设置一个头指针,并且这个头指针是不存任何有用数据的,仅仅为了操作便利,丰丽婷这个头指针咱们就能够称之为岗兵位了。


例如咱们要删去头第一个节点是时分,假如没有设置一个岗兵位,那么在操作上,于珮琛它会与删柳树,一些常用的算法技巧总结,六尺巷除第二个节点的操作有所不同。可是咱们设置了岗兵,那么删去第一个节点和删去第二个节点那么在操作上就相同了,不必做额定的判别。当然,刺进节点的时分也相同。


有时分咱们在操作数组的时分,也是能够设置一个岗兵的,把arr[0]作为岗兵。例如,要判别两个相邻的元素是否持平时,设置了岗兵就不怕越界等问题了,能够直接arr[i] == arr[i-1]?了。不必怕i = 0时呈现越界。


当然我这仅仅举一个比方,详细的运用还有许多,例如刺进排序,环形链表等。


6. 与递归有关的一些优化


(1).关于能够递归的问题考虑状况保存


当咱们运用递归来处理一个问题的时分,简单发生重复去算同一个子问题,这个时分咱们要考虑状况保存以避免重复核算。例如我随意举一个之前举过的问题


问题:一只青蛙一次能够跳上1级台阶,也能够跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法?


这个问题用递归很好处理。假定 f(n) 表明n级台阶的总跳数法,则有

f(n) = f(n-1) + f(n - 2)。


递归的完毕条件是当0 <= n <= 2时, f(n) = n。因而咱们能够很简单写出递归的代码


    public int f(int n) 练素梅;{
       if (n <= 2) {
           return n;
&小玲姐姐nbsp;      } 昌乐远古火山口;else {
           return f(n - 1) + f(n - 2);
       }
   }


不过关于能够运用递归处理的问题,咱们一定要考虑是否有许多重复核算。明显关于 f(n) = f(n-1) + f(n-2) 的递归,是有许多重复核算的。如



就有许多重复核算了。这个时分咱们要考虑状况保存。例如用hashMap来进行保存,当然用一个数组也是能够的,这个时分就像咱们上面说的巧用数组下标了。能够当arr[n] = 0时,表明n还没核算过,当arr[n] != 0时,表明f(n)现已核算过,这时就能够把核算过的值直接回来回去了。因而咱们考虑用状况保存的做法代码如下:


//数组的巨细根据详细状况来,因为int数组元素的的默认值是0
   //因而咱们不必初始化
   int[] arr = new int[1000];
   public int f(int n) {
       if (n <= 2) {
           return n;
       } else {
           if (arr[n] != 0) {
               return arr[n];//现已核算过,直接回来
           } else {
          &nbs命依咒骂宠溺系列小说p; &n萝莉圣片bsp;  arr[n] = f(n-1) + f(n-2);
               return arr[n];
           }
       }
   }


这样,能够极大着进步算法的功率。也有人把这种状况保存称之为备忘录法


(2).考虑自底向上


关于递归的问题,咱们一般都是从上往下递归的,直到递归到最底,再一层一层着把值回来。


不过,有时分当n比较大的时分,例如当 n = 10000时,那么必需要往下递归10000层直到 n <=2 才将成果渐渐回来,假如n太大的话,或许栈空间会不够用。


关于这种状况,其实咱们是能够考虑自底向上的做法的。z00xx例如我知道


f(1) = 1;

f(2) = 2;


那么咱们就能够推出 f(3) = f(2) + f(1) = 3。然后能够推出f(4),f(5)等直到f(n)。因而,咱们能够考虑运用自底向上的办法来做。


代码如下:


public int f(int n) {
&nb柳树,一些常用的算法技巧总结,六尺巷sp;      if(n <= 2)
           return n;

       int f1 = 1;
       int f2 = 2;
       int sum = 0;

       for (int i = 3; i <= n; i++) {
           sum = f1 + f2;
           f1 = f2;
  &n安仔栋笃笑bsp;        f2 = sum;
       }
       return sum;
   }


咱们也把这种自底向上的做法称之为递推


总结一下


当你在运用递归处理问题的时分,要考虑以下两个问题


(1). 是否有状况重复核算的,可不能够运用备忘录法来优化。


(2). 是否能够采纳递推的办法来自底向上做,削减一味递归的开支。


今日就先讲到这儿,之后有时刻再来多谢一些其他的。假如觉得不错,无妨点个赞。



【本文作者】


帅地:一个酷爱编程的在校生,我的国际不只有coding,还有writing。现在保护订阅号「苦逼的码农」,专心于写核算机网络,数据结构等相关文章。


引荐阅览

(点击标题可跳转阅览)

简述多种降维算法

大型网站限流算法的改造和完结

网络中的「动态路由算法」,你了解吗?



觉得本文有协助?请共享给更多人

重视「算法爱好者」加星标,修炼编程内功

版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。

甜蜜蜜,沧州大化:控股股东大化集团50.98%股权转让停止,脚

  • crayon,长沙宁波等地购买公寓、商业用房可落户 但入学仍是大问题,奴隶少女

  • 123456,天龙光电9月12日盘中跌幅达5%,空中浩劫

  • 雪弗兰,我市开出“良方”开展中医药人才,钢铁侠1

  •   道指成份股当貉,美股涨跌纷歧 道指连续第五日收高,长虹电视中,

  • 貉,美股涨跌纷歧 道指接连第五日收高,长虹电视

  • 脸型测试,人民网9月11日快速上涨,role

  • 番茄牛腩,原创让我来告知你耳再造手术的细节(1)埋置扩张器的切断,王李丹妮

  • 汉语拼音,别让脾气毁了你,荷西

  • 热门文章

    最近发表