力扣刷题篇之位运算

系列文章目录

前言

一、位运算的基本运算

二、位运算的技巧

三、布隆过滤器

总结

前言

本系列是个人力扣刷题汇总，本文是数与位。刷题顺序按照[力扣刷题攻略] Re：从零开始的力扣刷题生活 - 力扣（LeetCode）

位运算其实之前的左程云算法与数据结构代码汇总之排序（Java）-CSDN博客

也有总结到过。原数异或0等于本身，原数异或本身等于0。异或可以看作无进位相加。

一、位运算的基本运算

136. 只出现一次的数字 - 力扣（LeetCode）

class Solution {public int singleNumber(int[] nums) {int result=0;for(int num:nums){result=result^num;}return result;}
}

190. 颠倒二进制位 - 力扣（LeetCode）

通过循环，将 result 左移一位，然后将 n 的最低位加到 result 中，最后右移 n，处理下一位。重复这个过程直到处理完 n 的所有位。

public class Solution {// you need treat n as an unsigned valuepublic int reverseBits(int n) {int result = 0;for (int i = 0; i < 32; i++) {// 将 result 左移一位，空出最低位result <<= 1;// 取 n 的最低位，加到 result 中result |= (n & 1);// 右移 n，继续处理下一位n >>= 1;}return result;}
}

191. 位1的个数 - 力扣（LeetCode）

通过循环，将 n 与 1 进行位与操作，统计最低位是否为 1，然后将 n 右移一位，继续处理下一位，直到 n 的所有位都处理完。

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int count = 0;while (n != 0) {// 将 n 与 1 进行位与操作，统计最低位是否为 1count += (n & 1);// 将 n 右移一位n >>>= 1;}return count;}
}

201. 数字范围按位与 - 力扣（LeetCode）

通过找到 left 和 right 二进制表示的最长公共前缀来解决。因为对于任何不同的位，按位与的结果一定是 0。

class Solution {public int rangeBitwiseAnd(int left, int right) {int shift = 0;// 找到最长公共前缀while (left < right) {left >>= 1;right >>= 1;shift++;}// 将最长公共前缀左移，右边用零填充return left << shift;}
}

338. 比特位计数 - 力扣（LeetCode）

class Solution {public int[] countBits(int n) {int[] ans = new int[n+1];ans[0] = 0;for(int i = 1; i <= n; i++) {ans[i] = ans[i >> 1] + i % 2;}return ans;}
}

二、位运算的技巧

260. 只出现一次的数字 III - 力扣（LeetCode）

这个之前就总结过了。

先全部异或，再找从右边开始两个数不同的第一位（为1的位）；通过&其补码获得，最后分两组进行异或。

class Solution {public int[] singleNumber(int[] nums) {int xorAll = 0;for(int x:nums){xorAll ^= x;}int lowBit = xorAll & -xorAll;int[] ans = new int[2];int a1 = 0, a2 = 0;for(int x:nums){if((x & lowBit) != 0){a1 ^= x;}else{a2 ^= x;}}return new int[]{a1,a2};}
}

342. 4的幂 - 力扣（LeetCode）

class Solution {public boolean isPowerOfFour(int n) {long i = 1;while(i < n){i*=4;}return i == n;}
}

371. 两整数之和 - 力扣（LeetCode）

利用了异或运算和与运算的性质，避免使用传统的加法运算符。

class Solution {public int getSum(int a, int b) {//当进位数没有了，证明计算完成while (b != 0) {//计算不进位的数int tempA = a ^ b;//计算进位的数int tempB = (a & b) << 1;a = tempA;b = tempB;}return a;}
}

三、布隆过滤器

705. 设计哈希集合 - 力扣（LeetCode）

这种之前哈希表已经总结过了

class MyHashSet {/** Initialize your data structure here. */boolean[] map = new boolean[1000005];public MyHashSet() {}public void add(int key) {map[key] = true;}public void remove(int key) {map[key] = false;}/** Returns true if this set contains the specified element */public boolean contains(int key) {return map[key] == true;}
}/*** Your MyHashSet object will be instantiated and called as such:* MyHashSet obj = new MyHashSet();* obj.add(key);* obj.remove(key);* boolean param_3 = obj.contains(key);*/

// class MyHashSet {//     /** Initialize your data structure here. */
//     boolean[] map = new boolean[1000005];
//     public MyHashSet() {//     }//     public void add(int key) {
//         map[key] = true;
//     }//     public void remove(int key) {
//         map[key] = false;
//     }//     /** Returns true if this set contains the specified element */
//     public boolean contains(int key) {
//         return map[key] == true;
//     }
// }// /**
//  * Your MyHashSet object will be instantiated and called as such:
//  * MyHashSet obj = new MyHashSet();
//  * obj.add(key);
//  * obj.remove(key);
//  * boolean param_3 = obj.contains(key);
//  */class MyHashSet {private static final int BASE = 769;private LinkedList[] data;/** Initialize your data structure here. */public MyHashSet() {data = new LinkedList[BASE];for (int i = 0; i < BASE; ++i) {data[i] = new LinkedList<Integer>();}}public void add(int key) {int h = hash(key);Iterator<Integer> iterator = data[h].iterator();while (iterator.hasNext()) {Integer element = iterator.next();if (element == key) {return;}}data[h].offerLast(key);}public void remove(int key) {int h = hash(key);Iterator<Integer> iterator = data[h].iterator();while (iterator.hasNext()) {Integer element = iterator.next();if (element == key) {data[h].remove(element);return;}}}/** Returns true if this set contains the specified element */public boolean contains(int key) {int h = hash(key);Iterator<Integer> iterator = data[h].iterator();while (iterator.hasNext()) {Integer element = iterator.next();if (element == key) {return true;}}return false;}private static int hash(int key) {return key % BASE;}
}

706. 设计哈希映射 - 力扣（LeetCode）

class MyHashMap {static int n=6774;int[] s;int[] v;public MyHashMap() {s=new int[n];v=new int[n];Arrays.fill(s,n);}public void put(int key, int value) {int k=f(key);s[k]=key;v[k]=value;}public int get(int key) {int k=f(key);if(s[k]==n) return -1;return v[k];}public void remove(int key) {v[f(key)]=-1;}public int f(int x){int k=x%n;while(s[k]!=x&&s[k]!=n){k++;if(k==n) k=0;}return k;}
}/*** Your MyHashMap object will be instantiated and called as such:* MyHashMap obj = new MyHashMap();* obj.put(key,value);* int param_2 = obj.get(key);* obj.remove(key);*/

1044. 最长重复子串 - 力扣（LeetCode）

基于DC3算法的后缀数组构建，并使用后缀数组求解最长重复子串问题

DC3算法，该算法用于构建后缀数组。后缀数组构建完成后，根据height数组找到最长的重复子串。这个还要仔细研究

class Solution {public static String longestDupSubstring(String s) {int length = s.length();int[] arr = new int[length];for (int i = 0; i < length; i++) {arr[i] = s.charAt(i);}DC3 dc3 = new DC3(arr);int[] height = dc3.getHeight();int[] suffix = dc3.getSuffix();int max = height[0];// height中的最大值int maxIndex = -1;// height中的最大值的下标for (int i = 1; i < length; i++) {if (height[i] > max) {maxIndex = i;max = height[i];}}return maxIndex == -1 ? "" : s.substring(suffix[maxIndex]).substring(0, max);}private static class DC3{private final int[] suffix;// 后缀数组,里面的元素按照字典序从小到大排.suffix[a]=b表示b对应的后缀排第a名private final int[] rank;// suffix的伴生数组,含义和suffix相反.rank[a]=b表示a对应的后缀排第b名private final int[] height;// height[i]表示第i名后缀和第i-1名后缀的最长公共前缀的长度,i从0开始,i表示名次public int[] getSuffix() {return suffix;}public int[] getRank() {return rank;}public int[] getHeight() {return height;}public DC3(int[] arr) {suffix = suffix(arr);// 求arr的后缀数组rank = rank(suffix);height = height(arr);}private int[] height(int[] arr) {int length = arr.length;int[] result = new int[length];for (int i = 0, value = 0; i < length; i++) {if (rank[i] != 0) {if (value > 0) {value--;}int pre = suffix[rank[i] - 1];while (i + value < length && pre + value < length && arr[i + value] == arr[pre + value]) {value++;}result[rank[i]] = value;}}return result;}private int[] rank(int[] suffix) {int length = suffix.length;int[] result = new int[length];// 将suffix数组的下标和元素值互换即可for (int i = 0; i < length; i++) {result[suffix[i]] = i;}return result;}private int[] suffix(int[] arr) {int max = getMax(arr);int length = arr.length;int[] newArr = new int[length + 3];System.arraycopy(arr, 0, newArr, 0, length);return skew(newArr, length, max + 1);}private int[] skew(int[] arr, int length, int num) {// eg:下标为0,3,6,9,12...属于s0类;下标为1,4,7,10,13...属于s1类;下标为2,5,8,11,14...属于s2类;int n0 = (length + 2) / 3;// s0类个数int n1 = (length + 1) / 3;// s1类个数int n2 = length / 3;// s2类个数int n02 = n0 + n2;// s02类的个数// 按照定义,n0个数要么比n1和n2多1个,要么相等.因此s12的大小用n02而不是n12是为了处理边界条件,防止数组越界判断int[] s12 = new int[n02 + 3];int[] sf12 = new int[n02 + 3];// 记录s12类的排名// 统计s12类下标都有哪些,放到s12中for (int i = 0, j = 0; i < length + (n0 - n1); i++) {if (i % 3 != 0) {s12[j++] = i;}}// 将s12类排序,排序结果最终会放到sf12中radixPass(arr, s12, sf12, 2, n02, num);// 按照"个位数"排序,结果放到sf12中radixPass(arr, sf12, s12, 1, n02, num);// 按照"十位数"排序,结果放到s12中radixPass(arr, s12, sf12, 0, n02, num);// 按照"百位数"排序,结果放到sf12中int rank = 0; // 记录了排名int ascii1 = -1, ascii2 = -1, ascii3 = -1;// 记录了3个字符的ascii码for (int i = 0; i < n02; i++) {if (ascii1 != arr[sf12[i]] || ascii2 != arr[sf12[i] + 1] || ascii3 != arr[sf12[i] + 2]) {rank++;ascii1 = arr[sf12[i]];ascii2 = arr[sf12[i] + 1];ascii3 = arr[sf12[i] + 2];}if (sf12[i] % 3 == 1) {s12[sf12[i] / 3] = rank;// 计算s1类的排名} else {// sf12[i]的值只有s1或s2类的,因此走到这里必定是s2类的s12[sf12[i] / 3 + n0] = rank;// 计算s2类的排名}}if (rank < n02) {sf12 = skew(s12, n02, rank + 1);// 递归调用直到有序,有序的排名结果放到sf12中for (int i = 0; i < n02; i++) {s12[sf12[i]] = i + 1;}} else {// 若s12已经有序了,则根据s12直接得到sf12即可for (int i = 0; i < n02; i++) {sf12[s12[i] - 1] = i;}}// 对s0类进行排序,排序结果放到sf0中int[] s0 = new int[n0];int[] sf0 = new int[n0];for (int i = 0, j = 0; i < n02; i++) {if (sf12[i] < n0) {s0[j++] = 3 * sf12[i];}}radixPass(arr, s0, sf0, 0, n0, num);int[] suffix = new int[length];// 记录最终排序for (int p = 0, t = n0 - n1, k = 0; k < length; k++) {int i = sf12[t] < n0 ? sf12[t] * 3 + 1 : (sf12[t] - n0) * 3 + 2;int j = sf0[p];if (sf12[t] < n0 ? abOrder(arr[i], s12[sf12[t] + n0], arr[j], s12[j / 3]): abOrder(arr[i], arr[i + 1], s12[sf12[t] - n0 + 1], arr[j], arr[j + 1], s12[j / 3 + n0])) {suffix[k] = i;t++;if (t == n02) {for (k++; p < n0; p++, k++) {suffix[k] = sf0[p];}}} else {suffix[k] = j;p++;if (p == n0) {for (k++; t < n02; t++, k++) {suffix[k] = sf12[t] < n0 ? sf12[t] * 3 + 1 : (sf12[t] - n0) * 3 + 2;}}}}return suffix;}private void radixPass(int[] arr, int[] input, int[] output, int offset, int limit, int num) {int[] barrel = new int[num];// 桶// 统计各个桶中元素的数量for (int i = 0; i < limit; i++) {barrel[arr[input[i] + offset]]++;}for (int i = 0, sum = 0; i < num; i++) {int temp = barrel[i];barrel[i] = sum;sum += temp;}// 将本趟基排结果放到output中for (int i = 0; i < limit; i++) {output[barrel[arr[input[i] + offset]]++] = input[i];}}// 比较(x1,y1)和(x2,y2)的字典序,前者<=后者返回trueprivate boolean abOrder(int x1, int y1, int x2, int y2) {return (x1 < x2) || (x1 == x2 && y1 <= y2);}// 比较(x1,y1,z1)和(x2,y2,z2)的字典序,前者<=后者返回trueprivate boolean abOrder(int x1, int y1, int z1, int x2, int y2, int z2) {return (x1 < x2) || (x1 == x2 && abOrder(y1, z1, y2, z2));}// 获取数组的最大值private int getMax(int[] arr) {int max = Integer.MIN_VALUE;for (int i : arr) {max = Math.max(max, i);}return max;}}
}

211. 添加与搜索单词 - 数据结构设计 - 力扣（LeetCode）

class WordDictionary {private WordDictionary[] items;  // 数组用于存储子节点boolean isEnd;  // 表示当前节点是否是一个单词的结束节点public WordDictionary() {items = new WordDictionary[26];  // 初始化子节点数组}// 向 WordDictionary 中添加单词public void addWord(String word) {WordDictionary curr = this;int n = word.length();// 逐个字母遍历单词for (int i = 0; i < n; i++) {int index = word.charAt(i) - 'a';// 如果当前节点的子节点数组中没有对应字母的节点，则创建一个新的节点if (curr.items[index] == null) {curr.items[index] = new WordDictionary();}curr = curr.items[index];  // 继续向下遍历}curr.isEnd = true;  // 将单词的最后一个字母节点的 isEnd 设置为 true，表示这是一个单词的结束}// 搜索给定的单词public boolean search(String word) {return search(this, word, 0);}// 递归搜索单词private boolean search(WordDictionary curr, String word, int start) {int n = word.length();// 如果已经遍历完单词，判断当前节点是否是一个单词的结束节点if (start == n) {return curr.isEnd;}char c = word.charAt(start);// 如果当前字母不是通配符 '.'，直接查找对应的子节点if (c != '.') {WordDictionary item = curr.items[c - 'a'];return item != null && search(item, word, start + 1);}// 如果字母是通配符 '.'，遍历当前节点的所有子节点，递归调用 search 方法for (int j = 0; j < 26; j++) {if (curr.items[j] != null && search(curr.items[j], word, start + 1)) {return true;}}return false;}
}