系列文章目录
目录
系列文章目录
前言
一、位运算的基本运算
二、位运算的技巧
三、布隆过滤器
总结
前言
本系列是个人力扣刷题汇总，本文是数与位。刷题顺序按照[力扣刷题攻略] 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 value
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i >= 1;
}
return result;
}
}
191. 位1的个数 – 力扣（LeetCode）
通过循环，将 n 与 1 进行位与操作，统计最低位是否为 1，然后将 n 右移一位，继续处理下一位，直到 n 的所有位都处理完。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
// 将 n 与 1 进行位与操作，统计最低位是否为 1
count += (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 >= 1;
right >>= 1;
shift++;
}
// 将最长公共前缀左移，右边用零填充
return left 
338. 比特位计数 – 力扣（LeetCode）
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n+1];
ans[0] = 0;
for(int i = 1; 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;
wh服务器托管网ile(i 
371. 两整数之和 – 力扣（LeetCode）
利用了异或运算和与运算的性质，避免使用传统的加法运算符。
class Solution {
public int getSum(int a, int b) {
//当进位数没有了，证明计算完成
while (b != 0) {
//计算不进位的数
int tempA = a ^ b;
//计算进位的数
int tempB = (a & b) 
三、布隆过滤器
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 ();
}
}
public void add(int key) {
int h = hash(key);
Iterator 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 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 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 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 0) {
value--;
}
int pre = suffix[rank[i] - 1];
while (i + value 
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 
总结
布隆过滤器这里难一点，其他都很简单，开心！
DC3算法还要去搞清楚一下。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: Word和Excel的文档应该如何设置自动保存呢？
哈喽大家好，我是咕噜美乐蒂。在今天的工作中，美乐蒂在编辑文档的时候，电脑突然关机了！！！后果很严重，就是之前码的字都没有了！！！为了让小伙伴们避免这种情况的发生，美乐蒂决定为大家整理一篇文档自动保存的方法，以避免这种情况的发生。真的是泪的教训啊呜呜呜…… Wo…
