首页 - 最近大事件 - 世越号,不败战神,纯电动汽车-简书咨询,大数据采集简书内容,分享给你最实用的信息

世越号,不败战神,纯电动汽车-简书咨询,大数据采集简书内容,分享给你最实用的信息

发布时间:2019-07-10  分类:最近大事件  作者:admin  浏览:212

来自:苦逼的码农(微信号:di201805)

作者:帅地

个人简介:一个酷爱编程的在校生,我的国际不只要coding,还有writing。现在保护订阅号「苦逼的码农」,专心于写「算法与数据结构」,「Java」,「核算机网络」。

之前我也写过一两篇与算法技巧相关的文章

一些常用的算法技巧总结

【算法技巧】位运算装逼攻略

今日的这篇文章,算是一种弥补,同时会罗列一些常见的算法题,怎样用这些技巧来处理,经过运用这些办法,能够让一些算法题变的愈加简略。

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

在 n 的二进制表明中,假如咱们对 n 履行

n = n & (n - 1)

那么能够把 n 最右边的 1 消除去,例如

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

这个公式有哪些用途呢?

其实仍是有挺多用途的,在做题的时分也是会常常碰到,下面我罗列几道经典、常考的例题。

(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。所以做法如下

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

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

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

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

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

关于这种题,咱们能够用不断着履行 n & (n - 1),每履行一次就能够消去一个 1,当 n 为 0 时,核算一共履行了多少次即可,代码如下:

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

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

其实这道题和(2)那道题差不多相同的,咱们只需求核算 n 和 m 这两个数有多少个二进制位不相同就能够了,那么咱们能够先让 n 和 m 进行异或,然后在核算异或得到的成果有多少个 1 就能够了。例如

令 t = n ^ m

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

2、双指针的运用

在之前的文章中 ,我也有讲过双指针,这儿我在讲一下,趁便弥补一些比方。

(1)、在链表中的运用

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

例如关于第一个问题

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

关于第二个问题

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

关于第三个问题

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

有人或许会说,选用双指针时刻复杂度仍是相同的啊。是的,空间复杂度和时刻复杂度都不会变,可是,我觉得选用双指针,愈加简单了解,而且不简单犯错。

(2)、遍历数组的运用

选用头尾指针,来遍历数组,也是十分有用的,特别是在做题的时分,例如我举个比方:

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

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

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

从左到右遍历数组,在遍历的过程中,取一个元素 a,然后让 sum 减去 a,这样能够得到 b,即 b = sum - a。然后因为数组是有序的,咱们再使用二分查找,在数组中查询 b 的下标。

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

不过咱们选用双指针的办法,从数组的头尾两头向中心夹攻的办法来做的话,时刻复杂度仅需为 O(n),而且代码也会愈加简练,这儿我给出代码吧,代码如下:

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;

}

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

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),而时刻复杂度不变,相应的黛米如下

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

总结

这阵子因为自己也忙着温习,所以并没有找太多的比方,上面的那些题,有些在之前的文章也是有写过,这儿能够给那些看过的忘了的温习一些,而且也考虑到或许还有一大部分人没看过。

所以呢,期望看完这篇文章,今后遇到某些题,能够多一点思路,假如你能用上这些技巧,那必定能够大大下降问题的难度。


●编号940,输入编号直达本文

●输入m获取文章

程序员数学之美

程序员数学学习

训练数学逻辑思维

下一篇
快捷导航
最新发布
标签列表