算法数据结构中有哪些奇技淫巧？
2021-03-13 22:29
标签：number 不容易 面试 很多 表示法 两数之和 遍历 示例 -- 之前我也写过一两篇与算法技巧相关的文章 一些常用的算法技巧总结 【算法技巧】位运算装逼指南 今天的这篇文章，算是一种补充，同时会列举一些常见的算法题，如何用这些技巧来解决，通过使用这些方法，可以让一些算法题变的更加简单。 在 n 的二进制表示中，如果我们对 n 执行 n = n & (n - 1) 那么可以把 n 最右边的 1 消除掉，例如 这个公式有哪些用处呢？ 其实还是有挺多用处的，在做题的时候也是会经常碰到，下面我列举几道经典、常考的例题。 （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。所以做法如下 但是如果采用 n & (n - 1) 的话，直接消去 n 中的一个 1，然后判断 n 是否为 0 即可，代码如下： 而且这种方法的时间复杂度我 O(1)。 （2）、整数 n 二进制中 1 的个数 对于这种题，我们可以用不断着执行 n & (n - 1)，每执行一次就可以消去一个 1，当 n 为 0 时，计算总共执行了多少次即可，代码如下： （3）、将整数 n 转换为 m,需要改变多少二进制位？ 其实这道题和（2）那道题差不多一样的，我们只需要计算 n 和 m 这两个数有多少个二进制位不一样就可以了，那么我们可以先让 n 和 m 进行异或，然后在计算异或得到的结果有多少个 1 就可以了。例如 令 t = n ^ m 然后计算 t 的二进制位中有多少 1 就可以了，问题就可以转换为（2）中的那个问题了。 在之前的文章中 ，我也有讲过双指针，这里我在讲一下，顺便补充一些例子。 （1）、在链表中的应用 对于双指针，我觉得用的最对的就是在链表这里了，比如“判断单链表是否有环”、“如何一次遍历就找到链表中间位置节点”、“单链表中倒数第 k 个节点”等问题。对于这种问题，我们就可以使用双指针了，会方便很多。我顺便说下这三个问题怎么用双指针解决吧。 我们就可以设置一个慢指针和一个快指针来遍历这个链表。慢指针一次移动一个节点，而快指针一次移动两个节点，如果该链表没有环，则快指针会先遍历完这个表，如果有环，则快指针会在第二次遍历时和慢指针相遇。 一样是设置一个快指针和慢指针。慢的一次移动一个节点，而快的两个。在遍历链表的时候，当快指针遍历完成时，慢指针刚好达到中点。 设置两个指针，其中一个指针先移动k个节点。之后两个指针以相同速度移动。当那个先移动的指针遍历完成的时候，第二个指针正好处于倒数第k个节点。 有人可能会说，采用双指针时间复杂度还是一样的啊。是的，空间复杂度和时间复杂度都不会变，但是，我觉得采用双指针，更加容易理解，并且不容易出错。 （2）、遍历数组的应用 采用头尾指针，来遍历数组，也是非常有用的，特别是在做题的时候，例如我举个例子： 题目描述:给定一个有序整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。 所以返回 [0, 1] 其实这道题也是 leetcode 中的两数之和，只是我这里进行了一下改版。对于这道题，一种做法是这样： 从左到右遍历数组，在遍历的过程中，取一个元素 a，然后让 sum 减去 a，这样可以得到 b，即 b = sum - a。然后由于数组是有序的，我们再利用二分查找，在数组中查询 b 的下标。 在这个过程中，二分查找的时间复杂度是 O(logn)，从左到右扫描遍历是 O(n)，所以这种方法的时间复杂度是 O(nlogn)。 不过我们采用双指针的方法，从数组的头尾两边向中间夹击的方法来做的话，时间复杂度仅需为 O(n)，而且代码也会更加简洁，这里我给出代码吧，代码如下： 这个例子相对比较简单，不过这个头尾双指针的方法，真的用的挺多的。 两个相同的数异或之后的结果是 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)，而时间复杂度不变，相应的黛米如下 这阵子由于自己也忙着复习，所以并没有找太多的例子，上面的那些题，有些在之前的文章也是有写过，这里可以给那些看过的忘了的复习一些，并且也考虑到可能还有一大部分人没看过。 所以呢，希望看完这篇文章，以后遇到某些题，可以多一点思路，如果你能用上这些技巧，那肯定可以大大降低问题的难度。 完 算法数据结构中有哪些奇技淫巧？ 标签：number 不容易 面试 很多 表示法 两数之和 遍历 示例 -- 原文地址：https://blog.51cto.com/15015171/2554970
1、用 n & (n - 1)消去 n 最后的一位 1
n = 1001
n - 1 = 1000
n = n & (n - 1) = (1001) & (1000) = 1000
boolean judege(int n) {
int count = 0;
int k = 1;
while (k != 0) {
if ((n & k) != 0) {
count++;
}
k = k boolean judege(int n){
return n & (n - 1) == 0;//
}
public int NumberOf12(int n) {
int count = 0;
int k = 1;
while (n != 0) {
count++;
n = (n - 1) & n;
}
return count;2、双指针的应用
例如对于第一个问题
对于第二个问题
对于第三个问题
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9public 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] 3、a ^ b ^ b = a 的应用
int find(int[] arr){
int tmp = arr[0];
for(int i = 1;i 总结
当当史上最低价格买书优惠正在进行中，想买书的赶紧入手：
你没听错，当当3折买书！！3折！别怪我没提醒你！
你可能会喜欢
1、腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？
2、为什么你学不会递归？告别递归，谈谈我的一些经验
3、一文读懂一台计算机是如何把数据发送给另一台计算机的
4、如何只用2GB内存从20/40/80亿个整数中找到出现次数最多的数
5、字符串匹配Boyer-Moore算法：文本编辑器中的查找功能是如何实现的？
上一篇：两道看似简单的面试高频算法题
下一篇：vba数颜色代码