特殊技巧

位运算

Java中支持的位运算
位与（&）：二元运算符，两个为1时结果为1，否则为0
位或（|）：二元运算符，两个其中有一个为1时结果就为1，否则为0
位异或（^）：二元运算符，两个数相同时结果为0，否则为1。任何数和0做异或结果仍然是原来的数，任何数和自身做异或结果还是0，异或运算满足交换律和结合律。异或-1 (二进制全为1) 相当于取反
位取非（~）：一元运算符，取反操作，即1变为0，0变为1
左移（<<）：一元运算符，按位左移一定的位置。高位溢出，低位补0，符号位不变。
右移（>>）：一元运算符，按位右移一定的位置。高位补符号位，符号位不变，低位溢出。
无符号右移（>>>）：一元运算符，高位补零，低位溢出。

位移操作

Java中的位移操作只针对int类型的有效，Java中，一个int的长度始终是32位，也就是4个字节，它操作的都是该整数的二进制数。也可作用于以下类型，即 byte，short，char，long(它们都是整数形式)。当为这四种类型时，JVM先把它们转换成int类型再进行操作。

左移（<<）

高位溢出，低位补0，符号位不变。移动位数超过该类型的最大位数，则进行取模，如对Integer型左移34位，实际上只移动了两位。左移一位相当于乘以2的一次方，左移n位相当于乘以2的n次方。

右移（>>）

高位补符号位，符号位不变，低位溢出。右移一位相当于除以2的一次方，右移n位相当于除以2的n次方。除不尽向下取整。

无符号右移（>>>）

高位补零，低位溢出。即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0

Java 不直接支持无符号左移操作，因为在 Java 中所有的整数类型（如 byte, short, int, 和 long）都是有符号的。这意味着所有的左移操作 (<<) 都是有符号的，即它会保留整数的符号位。

然而，在 Java 中，由于整数是有符号的，并且使用补码表示法，所以实际上不需要无符号左移操作。当你进行左移操作时，高位溢出的部分会被丢弃，低位则用0填充，这在效果上与无符号左移是一样的。

例如，对于一个 int 类型的值，其范围是 -2,147,483,648 到 2,147,483,647（32位），如果你对一个正数进行左移，那么高位溢出的位会被丢弃，低位用0填充，而负数的情况也是一样，只是高位的符号位会被保持。

位运算的使用

判断奇偶数

我们通过二进制判断奇偶数的话，看的是二进制最后一位，如果最后一位为0的话是偶数，为1的话是奇数。

int num = 5;	
System.out.println(num + "是" + ((num&1) == 0 ? "偶数":"奇数"));
// 0101
// 0001
// 0001 = 1  所以是奇数

获取二进制位是1还是0

int n = 86;
System.out.println(n + "的第五位是" + (((n&(1<<4))>>4) == 0 ? "0":"1"));
System.out.println(n + "的第五位是" + (((n>>4)&1) == 0 ? "0":"1"));
// 右移四位后则最低为就是第五位

交换两个整数变量的值

int num1 = 10;
int num2 = 20;
num1 = num1^num2;
num2 = num1^num2;
num1 = num1^num2;
System.out.println("num1=" + num1 + ", num2=" + num2);
//num2可以看成是num1^(num2^num2)，故结果为num1
//num1可以看成是(num1^num1)^(num2^num2)^num2，故结果为num2

不用判断语句，求整数的绝对值

负数的绝对值为，补码取反+1，即 ~a+1。而一个32 bit的int类型的正数 >> 31，结果为0，负数 >> 31 为-1。

即 (a >> 31) 的结果为 0 或者 -1。如果 a 为负数，(a >> 31) ^ a 相当于 ~a，则需要 + 1 才能得到 a 的绝对值

且一个32 bit的int类型的正数 >>> 31，结果为0，负数 >>> 31为1。

所以代码为:

1
2
3

int a = -10;
int b = ((a >> 31) ^ a) + (a >>> 31);
System.out.println("a=" + a + ", b=" + b);

也可以写成

int a = -86;
int b = a >> 31;
// 当a为正时：b = 0，a ^ b = a;
// 当a为负时：b = -1，a ^ b = ~a;
return (a ^ b) - b; // 也可以写为：(a ^ (a >> 31)) - (a >> 31)

常见面试题

2*8怎么运算性能最好

实际采用位运算的方式是性能最好的，因为计算机对于计算数据的话，都是以二进制来进行运算的，所以使用位运算相比直接使用(+、-、 *、/)运算符，要更高效，能显著调高代码在计算机中的执行效率。相当于2 << 3。

136. 只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间

class Solution {
    public int singleNumber(int[] nums) {
        //使用异或运算  a^a = 0   a^0=a
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }
}

扩展：只出现两次的数字。一个数组里面只有一个数字出现两次其他都是一次

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

本题常见的三种解法：

哈希表统计法：遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出众数。此方法时间和空间复杂度均为 O(N)。
数组排序法：将数组 nums 排序，数组中点的元素一定为众数。
摩尔投票法：核心理念为票数正负抵消，此方法时间和空间复杂度分别为 O(N) 和 O(1) ，为本题的最佳解法。

摩尔投票法：

class Solution {
    public int majorityElement(int[] nums) {
        //nums的众数为x 票数和为votes 
        // 众数的票数+1 非众数-1 那么总票数一定大于0
        //如果数组的前m个数字的票数和为0 那剩余的n-m个数字的票数和仍然大于0，且众数仍然是x
        //当总票数votes为0时，当前的数字设置为众数x
        //核心思想就是抵消原则 众数和非众数的抵消 非众数之间的抵消
        int x = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) x = num;
            if (num == x) {
                votes += 1;
            } else {
                votes += -1;
            }
        }
        return x;
    }
}

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。

解答：排序分成三个部分。类似于快速排序。

class Solution {
    public void sortColors(int[] nums) {
        int l = 0, r = nums.length - 1;
        int i = 0;
        //l是记录最左边的1的位置 也就是下一个插入0的地方
        //r是下一个插入2的位置
        while (i <= r) {
            if (nums[i] == 0) {
                swap(nums, i ,l);
                i++;
                l++;
            } else if (nums[i] == 1) {
                i++;  //这里l的位置不变
            } else {
                //这里不用i++ 因为换过来的num[r]也可能等于2   所以r-1，继续交换  直到num[r]不等于2
                swap(nums, i, r);
                r--;
            }
        }
    }
    void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

31. 下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。必须** 原地 **修改，只允许使用额外常数空间。

解法：我们会尽可能的将低位的数字变大，这样才符合下一个排列的定义。

也就是从低位往高位检查，观察某一位在下一个排列中是否可以被更大的数代替。

假设第k个位置就是需要替换的位置。其实就是将 k 位到低位的所有数作为候选，判断是否有更大的数可以填入 k 位中。

class Solution {
    public void nextPermutation(int[] nums) {
        //为了更好理解，我们结合样例来分析，假设样例为 [1,3,5,4,1]：
        int n = nums.length, k = n - 1;//k就是那个需要被替换的数
        //从后往前找，找到第一个下降的位置，记为 k。注意k 以后的位置是降序的。 在样例中就是找到 3
        while (k - 1 >= 0 && nums[k - 1] >= nums[k]) {
            k--;
        }
        if (k == 0) {   //已经是最大的排序的 目前就是降序 直接翻转即可，会比sort快
            reverse(nums, 0, n - 1);
        } else {
            //从k往后找，找到最小的比 k 要大的数。 找到 4
            int a = k;
            while (a + 1 < n && nums[a + 1] > nums[k - 1]) { //这里的k-1就是3的位置
                a++;    //因为k之后的是降序的  所以就一直修改a的值 直到最后一个就是最小的
            }
            //将两者交换。注意此时 k 以后的位置仍然是降序的。
            swap(nums, k - 1, a);
            //直接将 k 以后的部分翻转（变为升序）
            reverse(nums, k, n - 1);
        }
    }
    void reverse(int[] nums, int a, int b) {
        int l = a, r = b;
        while (l < r) {
            swap(nums, l++, r--);
        }
    }
    void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

class Solution {
    public int findDuplicate(int[] nums) {
        //如果数组中有重复的数字, 那么就会产生多对一的映射，形成的链表就一定有环
        //找到数组中的重复整数 <==> 找到链表的环入口 那么这道题就相当于环形链表2
        //以数组 [1,3,4,2,2] 为例,我们将数组下标 n 和数 nums[n] 建立一个映射关系 f(n)，
        //其映射关系 n->f(n) 为：0->1 1->3 2->4 3->2 4->2
        // 环： 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 ....
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

Julian's Blog

力扣top100-特殊技巧