wordpress插件 网站跳转,网站建设模拟实训题,seo文章优化技巧,wordpress 秀主题系列文章目录 目录
系列文章目录
前言
一、位运算的基本运算
二、位运算的技巧
三、布隆过滤器
总结 前言
本系列是个人力扣刷题汇总#xff0c;本文是数与位。刷题顺序按照[力扣刷题攻略] Re#xff1a;从零开始的力扣刷题生活 - 力扣#xff08;LeetCode#xff0…系列文章目录 目录
系列文章目录
前言
一、位运算的基本运算
二、位运算的技巧
三、布隆过滤器
总结 前言
本系列是个人力扣刷题汇总本文是数与位。刷题顺序按照[力扣刷题攻略] Re从零开始的力扣刷题生活 - 力扣LeetCode
位运算其实之前的 左程云算法与数据结构代码汇总之排序Java-CSDN博客
也有总结到过。 原数异或0等于本身原数异或本身等于0。异或可以看作无进位相加。 一、位运算的基本运算
136. 只出现一次的数字 - 力扣LeetCode class Solution {public int singleNumber(int[] nums) {int result0;for(int num:nums){resultresult^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[n1];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 LinkedListInteger();}}public void add(int key) {int h hash(key);IteratorInteger 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);IteratorInteger 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);IteratorInteger 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 n6774;int[] s;int[] v;public MyHashMap() {snew int[n];vnew int[n];Arrays.fill(s,n);}public void put(int key, int value) {int kf(key);s[k]key;v[k]value;}public int get(int key) {int kf(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 kx%n;while(s[k]!xs[k]!n){k;if(kn) k0;}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;}
}总结
布隆过滤器这里难一点其他都很简单开心
DC3算法还要去搞清楚一下。
