注册

超实用的算法小技巧

本篇文章我们将介绍一些超级实用的算法小技巧,灵活使用这些算法小技巧可以帮助我们更好的解决遇到的问题,让我们的时间复杂度,空间复杂度大大降低,有效的提高我们的编程能力。

1 严格定义函数名称,出入参

我们在一开始拿到算法题,读懂题之后,就需要根据题意定义我们的函数名称,以及入参,函数的返回类型。日常的企业项目开发也是一样,我们在拿到需求之后,需要去定义接口,入参,出参。

我们一定要给处理函数起一个能够明确表达函数功能的名字比如:排序sort,搜索search,统一用英文表示(入参也是如此)。

leetcode技巧: 变量名称定义简单,可以提高算法执行速度,这也是在好多人在刷leetcode参数定义不那么规范的原因,往往在周赛或者一些比赛中一点点优势,就能助我们取得胜利。

2 严进宽出,边界判断

严进宽出就是说我们要对算法的入参进行严格的验证,比如我们经常要对数组、字符串进行非空校验,还有一些需要对边界值进行校验。

对于不符合规范的直接返回,很好的把控边界也可提升我们的算法效率。

笔试小技巧: 优雅严格的边界值判断,往往能给面试官留下很好的印象。

// 入参校验
if (nums == null || nums.length == 0) {
return -1;
}
// 边界值(不相等时,我们让左边指针移动到二分处,并且+1就很细节,因为中间点已经不符合,所以我们+1可以少循环一次)
while (l <= r) {
mid = l + (r - l) / 2;
   if (nums[mid] == target) {
  return mid;
  } else if (nums[mid] < target) {
       l = mid + 1;
  } else if (nums[mid] > target) {
       r = mid - 1;
  }
}

3 暴力解法

没有经过算法训练的同学,一般在解决算法问题时,只能想到暴力解法,常常就是多层嵌套函数,定义额外的空间。

往往时间复杂度都是O(N)、O(N²) 虽然也能解决算法问题,但是往往因为算法的执行效率过低,代码不够优雅让Offer与我们失之交臂。

不过暴力解法虽然效率不高,但是是我们必须掌握的,写出来永远比什么都写不出来要强的多,暴力解法就要求我们灵活应用每种数据结构的遍历,并加入条件判断逻辑。

以下几个技巧则可以帮助我们优化算法,提供算法的执行效率。

4 双指针(Two Pointers)

双指针是一种算法小套路,我们在好多地方可以见到双指针的妙用,比如二分查找,确定链表是否成环等,接下来我们就来一起探究一下双指针的妙用。

image.png

双指针一般有以下几种形式。

  • 普通双指针

    两个指针往同一个方向移动

        /**
        * 冒泡排序
        * @param nums
        */
       public static void sort(int [] nums) {
           if (nums == null || nums.length == 0) {
               return;
          }
           int temp = 0;
           for (int i = 0; i < nums.length - 1; i++) {
               for (int j = i + 1; j < nums.length; j++) {
                   if (nums[i] > nums[j]) {
                       temp = nums[i];
                       nums[i] = nums[j];
                       nums[j] = temp;
                  }
              }
          }
      }
  • 对撞双指针

    两个指针从两端向对方移动

    /**
    * 力扣704 二分查找
    * 二分查找算法是借助二分的思想,结合双指针来实现的一种搜索算法
    * @author zhj
    */
    public class Test704 {
       public static void main(String[] args) {
           int[] nums = {-1, 0, 3, 5, 9, 12};
           int index = search(nums, 5);
           System.out.println(index);
      }

       private static int search(int[] nums, int target) {
           if (nums == null || nums.length == 0) {
               return -1;
          }
           int l = 0;
           int r = nums.length - 1;
           int mid;
           while (l <= r) {
               mid = l + (r - l) / 2;
               if (nums[mid] == target) {
                   return mid;
              } else if (nums[mid] < target) {
                   l = mid + 1;
              } else if (nums[mid] > target) {
                   r = mid - 1;
              }
          }
           return -1;
      }
    }
  • 快慢双指针

    慢指针+快指针 解决环形链表问题

    /**
    * 力扣 141 环形链表
    * 给定一个链表,判断链表中是否有环
    * @author zhj
    */
    public class Test141 {
       public static void main(String[] args) {
           ListNode node = new ListNode(1);
           ListNode node1 = new ListNode(2);
           ListNode node2 = new ListNode(3);
           ListNode node3 = new ListNode(4);
           ListNode node4 = new ListNode(5);
           node.next = node1;
           node1.next = node2;
           node2.next = node3;
           node3.next = node4;
           node4.next = node2;
           System.out.println(isRing(node));
      }

       private static boolean isRing(ListNode node) {
           if (node == null || node.next == null) {
               return false;
          }
           ListNode s = node;
           ListNode f = node;
           while (f != null && f.next != null) {
               s = s.next;
               f = f.next.next;
               if (s == f) {
                   return true;
              }
          }
           return false;
      }
    }

5 滑动窗口

滑动窗口也是一种算法小技巧,可以极大的减少重叠部分计算量,尤其是当重叠部分比较大的时候,效果格外明显。滑动窗口主要解决的是连续定长子数组的问题,但是有一些非定长的也可以通过滑动窗口的思想来解决。

当我们移动窗口时只需要排除移除的一个数据,在加入移入的一个数据,窗口内其它数据是不需要做出改变的。

image.png

非定长一般需要通过加入内层循环来解决。

/**
* 力扣209 长度最小的子数组
* @author zhj
*/
public class Test209 {

   public static void main(String[] args) {
       int[] nums = {2,3,1,2,4,3};
       System.out.println(mumsLength(nums, 7));
  }

   private static int mumsLength(int[] nums, int sum) {
       if (nums == null || nums.length == 0) {
           return 0;
      }
       int res = nums.length + 1;
       int total = 0;
       int i = 0;
       int j = 0;
       while (j < nums.length) {
           total = total + nums[j];
           j++;
           while (total >= sum) {
               res = res < j-i ? res : j-i;
               total = total - nums[i];
               i = i + 1;
          }
      }
       if (res == nums.length + 1) {
           return 0;
      }
       return res;
  }
}

6 递归

一些复杂的问题,我们往往可以通过递归去简化。

特点:自己调自己,根据特点条件可以返回,不会陷入死循环。

递归的四个要素:

  • 参数
  • 返回值
  • 终止条件
  • 递归拆解

经典问题斐波那契数列

0,1,1,2,3,5... f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2)

int recursion(int n) {
   if (n < 2) {
       return n == 1 ? 1 : 0;
  }
   return recursion(n-1) + recursion(n-2);
}

7 高阶算法

除了上边一些简单的小技巧之外,还有许多高阶的算法,比如由递归引发的分治法、回溯法;还有树和图的遍历方法,深度优先遍历,广度优先遍历;还有经典的算法贪心算法、动态规划等等,本文将不做讲解,后续会单独更新在算法这一专栏中,希望大家持续关注。


作者:CoderJie
链接:https://juejin.cn/post/7056632496032579620
来源:稀土掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

0 个评论

要回复文章请先登录注册