@@ -26,121 +26,110 @@ a=n&(n-1)
2626
2727diff=(n&(n-1))^n
2828
29+ diff = n&-n;
30+
2931## 常见题目
3032
3133[ single-number] ( https://leetcode-cn.com/problems/single-number/ )
3234
3335> 给定一个** 非空** 整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
3436
35- ``` go
36- func singleNumber (nums [] int ) int {
37- // 10 ^10 == 00
38- // 两个数异或就变成0
39- result := 0
40- for i := 0 ;i< len ( nums);i++ {
41- result=result^nums[i]
42- }
43- return result
37+ ``` dart
38+ int singleNumber(List< int> nums) {
39+ //两个相同的数异或就变成0
40+ //任何数和0 异或 值不变
41+ int result = 0;
42+ for (var element in nums) {
43+ result = result ^ element;
44+ }
45+ return result;
4446}
47+
4548```
4649
4750[ single-number-ii] ( https://leetcode-cn.com/problems/single-number-ii/ )
4851
4952> 给定一个** 非空** 整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
5053
51- ``` go
52- func singleNumber (nums []int ) int {
53- // 统计每位1的个数
54- var result int
55- for i := 0 ; i < 64 ; i++ {
56- sum := 0
57- for j := 0 ; j < len (nums); j++ {
58- // 统计1的个数
59- sum += (nums[j] >> i) & 1
60- }
61- // 还原位00^10=10 或者用| 也可以
62- result ^= (sum % 3 ) << i
63- }
64- return result
54+ ``` dart
55+ //1.将数组中每个数，对应的位数进行叠加。如果出现一次的那个数，那个位是0 则为 3n，如果 是1则是3n+1
56+ //2.然后将每一位叠加和对3求余数（3n mod 3 或者 (3n+1)mod3），余数不是1就是0
57+ //3.将余数归位到原来的数中，就是结果
58+ int singleNumber(List<int> nums) {
59+ int result = 0;
60+
61+ for (var i = 0; i < 64; i++) {
62+ int sum = 0;
63+ for (var element in nums) {
64+ sum += ((element >> i) & 1);
65+ }
66+ result = result | ((sum % 3) << i);
67+ }
68+ return result;
6569}
6670```
6771
6872[ single-number-iii] ( https://leetcode-cn.com/problems/single-number-iii/ )
6973
7074> 给定一个整数数组 ` nums ` ，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
7175
72- ``` go
73- func singleNumber (nums []int ) []int {
74- // a=a^b
75- // b=a^b
76- // a=a^b
77- // 关键点怎么把a^b分成两部分,方案：可以通过diff最后一个1区分
78-
79- diff := 0
80- for i := 0 ;i<len (nums);i++{
81- diff^=nums[i]
76+ ``` dart
77+ //1.对列表所有元素xor,获取的结果为 两个只出现一次的元素异或结果
78+ //2.取出最后结果的最后一位为1的数
79+ //3.通过这个数进行&操作可以将原数组进行划分，分到了两个不同的单元
80+ //4.对划分后的两个单元进行xor操作，就可以获取结果
81+ List<int> singleNumber(List<int> nums) {
82+ int diff = 0;
83+ for (var element in nums) {
84+ diff ^= element;
85+ }
86+ diff = diff & -diff;
87+ List<int> res = [0, 0];
88+ for (var element in nums) {
89+ if ((diff & element) == 0) {
90+ res[0] ^= element;
91+ } else {
92+ res[1] ^= element;
8293 }
83- result := []int {diff,diff}
84- // 去掉末尾的1后异或diff就得到最后一个1的位置
85- diff=(diff&(diff-1 ))^diff
86- for i := 0 ;i<len (nums);i++{
87- if diff&nums[i]==0 {
88- result[0 ]^=nums[i]
89- }else {
90- result[1 ]^=nums[i]
91- }
92- }
93- return result
94+ }
95+ return res;
9496}
97+
9598```
9699
97100[ number-of-1-bits] ( https://leetcode-cn.com/problems/number-of-1-bits/ )
98101
99102> 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为[ 汉明重量] ( https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F ) ）。
100103
101- ``` go
102- func hammingWeight (num uint32 ) int {
103- res := 0
104- for num!= 0 {
105- num=num&(num- 1 )
106- res++
107- }
108- return res
104+ ``` dart
105+ int hammingWeight(int n) {
106+ int res = 0;
107+ while (n > 0) {
108+ n = n & (n - 1);
109+ res++;
110+ }
111+ return res;
109112}
113+
110114```
111115
112116[ counting-bits] ( https://leetcode-cn.com/problems/counting-bits/ )
113117
114118> 给定一个非负整数 ** num** 。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
115119
116- ``` go
117- func countBits (num int ) []int {
118- res := make ([]int ,num+1 )
119-
120- for i := 0 ;i<=num;i++{
121- res[i]=count1 (i)
120+ ``` dart
121+ List<int> countBits(int n) {
122+ List<int> res = [];
123+ for (int i = 0; i <= n; i++) {
124+ int temp = 0;
125+ int iPos = i;
126+ while (iPos > 0) {
127+ iPos = iPos & (iPos - 1);
128+ temp++;
122129 }
123- return res
124- }
125- func count1 (n int )(res int ){
126- for n!=0 {
127- n=n&(n-1 )
128- res++
129- }
130- return
131- }
132- ```
133-
134- 另外一种动态规划解法
135-
136- ``` go
137- func countBits (num int ) []int {
138- res := make ([]int ,num+1 )
139- for i := 1 ;i<=num;i++{
140- // 上一个缺1的元素+1即可
141- res[i]=res[i&(i-1 )]+1
142- }
143- return res
130+ res.add(temp);
131+ }
132+ return res;
144133}
145134```
146135
@@ -150,42 +139,43 @@ func countBits(num int) []int {
150139
151140思路：依次颠倒即可
152141
153- ``` go
154- func reverseBits (num uint32 ) uint32 {
155- var res uint32
156- var pow int =31
157- for num!=0 {
158- // 把最后一位取出来，左移之后累加到结果中
159- 160- num>>=1
161- pow--
142+ ``` dar
143+ int reverseBits(int n) {
144+ int res = 0;
145+ for(int i = 0 ; i < 32 ;i++) {
146+ int temp = (n & 1);
147+ res = (res<<1) + temp;
148+ n = (n >> 1);
162149 }
163- return res
164- }
150+ return res;
151+ }
165152```
166153
167154[ bitwise-and-of-numbers-range] ( https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/ )
168155
169156> 给定范围 [ m, n] ，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
170157
171- ``` go
172- func rangeBitwiseAnd (m int , n int ) int {
173- // m 5 1 0 1
174- // 6 1 1 0
175- // n 7 1 1 1
176- // 把可能包含0的全部右移变成
177- // m 5 1 0 0
178- // 6 1 0 0
179- // n 7 1 0 0
180- // 所以最后结果就是m<<count
181- var count int
182- for m!=n{
183- m>>=1
184- n>>=1
185- count++
186- }
187- return m<<count
158+ ``` dart
159+ int rangeBitwiseAnd(int m, int n) {
160+ // m 5 1 0 1
161+ // 6 1 1 0
162+ // n 7 1 1 1
163+ // 把可能包含0的全部右移变成
164+ // m 5 1 0 0
165+ // 6 1 0 0
166+ // n 7 1 0 0
167+ // 所以最后结果就是m<<count
168+ //一句话这道题的核心就是找公共前缀
169+ int count = 0;
170+ while (m != n) {
171+ m >>= 1;
172+ n >>= 1;
173+ count++;
174+ }
175+ int result = (m << count);
176+ return result;
188177}
178+
189179```
190180
191181## 练习
0 commit comments