首页 > 世链号 > 【聚币网】算法数据结构中有哪些奇技?
币言链语  

【聚币网】算法数据结构中有哪些奇技?

摘要:本文会列举一些常见的算法题,如何用这些技巧来解决,通过使用这些方法,可以让一些算法题变的更加简单。

作者:苦逼的码农 / 帅地

本文会列举一些常见的算法题,如何用这些技巧来解决,通过使用这些方法,可以让一些算法题变的更加简单。

1、用 n & (n - 1) 消去 n 最后的一位 1

在 n 的二进制表示中,如果我们对 n 执行

n = n & (n - 1)

那么可以把 n 最右边的 1 消除掉,例如

[code]

 n = 1001 n - 1 = 1000 n = n & (n - 1) = (1001) & (1000) = 1000 

[/code]

这个公式有哪些用处呢?

其实还是有挺多用处的,在做题的时候也是会经常碰到,下面我列举几道经典、常考的例题。

(1)、判断一个正整数 n 是否为 2 的幂次方

如果一个数是 2 的幂次方,意味着 n 的二进制表示中,只有一个位 是 1,其他都是 0。我举个例子,例如

2^0 = 0…..0001

2^1 = 0…..0010

2^2 = 0….0100

2^3 = 0..01000

…..

所以呢,我们只需要判断 N 中的二进制表示法中是否只存在一个 1 就可以了。按照平时的做法的话,我们可能会对 n 进行移位,然后判断 n 的二进制表示中有多少个
1。所以做法如下

[code]

 boolean judege(int n) { int count = 0; int k = 1; while (k != 0) { if ((n & k) != 0) { count++; } k = k << 1; } return count == 1; } 

[/code]

但是如果采用 n & (n - 1) 的话,直接消去 n 中的一个 1,然后判断 n 是否为 0 即可,代码如下:

[code]

 boolean judege(int n){ return n & (n - 1) == 0;// } 

[/code]

而且这种方法的时间复杂度我 O(1)。

(2)、整数 n 二进制中 1 的个数

对于这种题,我们可以用不断着执行 n & (n - 1),每执行一次就可以消去一个 1,当 n 为 0 时,计算总共执行了多少次即可,代码如下:

[code]

 public int NumberOf12(int n) { int count = 0; int k = 1; while (n != 0) { count++; n = (n - 1) & n; } return count; 

[/code]

(3)、将整数 n 转换为 m, 需要改变多少二进制位?

其实这道题和(2)那道题差不多一样的,我们只需要计算 n 和 m 这两个数有多少个二进制位不一样就可以了,那么我们可以先让 n 和 m
进行异或,然后在计算异或得到的结果有多少个 1 就可以了。例如

令 t = n ^ m

然后计算 t 的二进制位中有多少 1 就可以了,问题就可以转换为(2)中的那个问题了。

2、双指针的应用

在之前的文章中 ,我也有讲过双指针,这里我在讲一下,顺便补充一些例子。

(1)、在链表中的应用

对于双指针,我觉得用的最对的就是在链表这里了,比如“判断单链表是否有环”、“如何一次遍历就找到链表中间位置节点”、“单链表中倒数第 k
个节点”等问题。对于这种问题,我们就可以使用双指针了,会方便很多。我顺便说下这三个问题怎么用双指针解决吧。

例如对于第一个问题

我们就可以设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移动一个节点,而快指针一次移动两个节点,如果该链表没有环,则快指针会先遍历完这个表,如果有环,则快指针会在第二次遍历时和慢指针相遇。

对于第二个问题

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

对于第三个问题

设置两个指针,其中一个指针先移动 k 个节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完成的时候,第二个指针正好处于倒数第 k 个节点。

有人可能会说,采用双指针时间复杂度还是一样的啊。是的,空间复杂度和时间复杂度都不会变,但是,我觉得采用双指针,更加容易理解,并且不容易出错。

(2)、遍历数组的应用

采用头尾指针,来遍历数组,也是非常有用的,特别是在做题的时候,例如我举个例子:

题目描述 : 给定一个有序整数数组和一个目标值,找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。

[code]

 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 

[/code]

其实这道题也是 leetcode 中的两数之和,只是我这里进行了一下改版。对于这道题,一种做法是这样:

从左到右遍历数组,在遍历的过程中,取一个元素 a,然后让 sum 减去 a,这样可以得到 b,即 b = sum -a。然后由于数组是有序的,我们再利用二分查找,在数组中查询 b 的下标。

在这个过程中,二分查找的时间复杂度是 O(logn),从左到右扫描遍历是 O(n),所以这种方法的时间复杂度是 O(nlogn)。

不过我们采用双指针的方法,从数组的头尾两边向中间夹击的方法来做的话,时间复杂度仅需为
O(n),而且代码也会更加简洁,这里我给出代码吧,代码如下:

[code]

 public int[] twoSum1(int[] nums, int target) { int[] res = new int[2]; int start = 0; int end = nums.length - 1; while(end > start){ if(nums[start] + nums[end] > target){ end--; }else if(nums[start] + nums[end] < target){ start ++; }else{ res[0] = start; res[1] = end; return res; } } return res; } 

[/code]

这个例子相对比较简单,不过这个头尾双指针的方法,真的用的挺多的。

3、a ^ b ^ b = a 的应用

两个相同的数异或之后的结果是 0,而任意数和 0 进行异或的结果是它本身,利用这个特性,也是可以解决挺多题,我在 leetcode
碰到过好几道,这里我举一些例子。

(1)数组中,只有一个数出现一次,剩下都出现两次,找出出现一次的数

这道题可能很多人会用一个哈希表来存储,每次存储的时候,记录 某个数出现的次数,最后再遍历哈希表,看看哪个数只出现了一次。这种方法的时间复杂度为
O(n),空间复杂度也为 O(n) 了。

我们刚才说过,两个相同的数异或的结果是 0,一个数和 0 异或的结果是它本身,所以我们把这一组整型全部异或一下,例如这组数据是:1, 2, 3, 4, 5,
1, 2, 3, 4。其中 5 只出现了一次,其他都出现了两次,把他们全部异或一下,结果如下:

由于异或支持交换律和结合律,所以 :

1^2^3^4^5^1^2^3^4 = (1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。

通过这种方法,可以把空间复杂度降低到 O(1),而时间复杂度不变,相应的黛米如下

[code]

 int find(int[] arr){ int tmp = arr[0]; for(int i = 1;i < arr.length; i++){ tmp = tmp ^ arr[i]; } return tmp; } 

[/code]

总结

这阵子由于自己也忙着复习,所以并没有找太多的例子,上面的那些题,有些在之前的文章也是有写过,这里可以给那些看过的忘了的复习一些,并且也考虑到可能还有一大部分人没看过。

所以呢,希望看完这篇文章,以后遇到某些题,可以多一点思路,如果你能用上这些技巧,那肯定可以大大降低问题的难度。

 

免责声明
世链财经作为开放的信息发布平台,所有资讯仅代表作者个人观点,与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论,请提供相关材料,发送到:2785592653@qq.com。
风险提示:本站所提供的资讯不代表任何投资暗示。投资有风险,入市须谨慎。
世链粉丝群:提供最新热点新闻,空投糖果、红包等福利,微信:juu3644。