Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6ca9dcb

Browse files
refactor 191
1 parent962fac6 commit6ca9dcb

File tree

3 files changed

+75
-41
lines changed

3 files changed

+75
-41
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -431,7 +431,7 @@ Your ideas/fixes/algorithms are more than welcome!
431431
|200|[Number of Islands](https://leetcode.com/problems/number-of-islands/)|[Solution](../master/MEDIUM/src/medium/_200.java)| O(m*n)|O(m*n) | Medium| Union Find, DFS
432432
|199|[Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_199.java)| O(n)|O(h)| Medium | BFS
433433
|198|[House Robber](https://leetcode.com/problems/house-robber/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_198.java)| O(n)|O(n)| Easy | DP
434-
|191|[Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_191.java)| O(n)|O(1)| Easy | Bit Manipulation
434+
|191|[Number of 1 Bits](https://leetcode.com/problems/number-of-1-bits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_191.java)| O(1)|O(1)| Easy | Bit Manipulation
435435
|190|[Reverse Bits](https://leetcode.com/problems/reverse-bits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_190.java)| O(n)|O(1)| Easy | Bit Manipulation
436436
|189|[Rotate Array](https://leetcode.com/problems/rotate-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_189.java)| O(n)|O(n), could be optimized to O(1) | Easy
437437
|188|[Best Time to Buy and Sell Stock IV](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_188.java)| O(n*k)|O(n*k) | Hard | DP
Lines changed: 40 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -1,55 +1,55 @@
11
packagecom.fishercoder.solutions;
2-
/**191. Number of 1 Bits
2+
3+
/**
4+
* 191. Number of 1 Bits
5+
* Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
36
*
4-
Write a function that takes an unsignedintegerand returns the number of ’1' bits ithas(also known astheHamming weight).
7+
* For example, the 32-bitinteger’11'hasbinary representation 00000000000000000000000000001011, sothefunction should return 3.*/
58

6-
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.*/
79
publicclass_191 {
8-
//another cool trick that I learned: doing bitwise AND operation between n and n-1 will always flip the least significant 1 bit in n
9-
//to zero, here's the solution from Editorial:
10-
//example run for the above editorial solution: input 5, n will be 5&4 and becomes 4, then in the next run, n will become 4&3 which is 0, thus exit the while loop.
11-
publicinthammingWeight_editorial(intn) {
12-
intcount =0;
13-
while (n !=0) {
14-
count++;
15-
n &= (n -1);
16-
}
17-
returncount;
18-
}
1910

20-
publicstaticvoidmain(String...strings) {
21-
System.out.println(4 &5);
22-
_191test =new_191();
23-
System.out.println(test.hammingWeight_editorial(5));
11+
publicstaticclassSolution1 {
12+
/**Doing bitwise AND operation between n and n-1 will always flip the least significant 1 bit in n to zero
13+
example run for the above editorial solution: input 5, n will be 5&4 and becomes 4,
14+
then in the next run, n will become 4&3 which is 0, thus exit the while loop.*/
15+
publicinthammingWeight(intn) {
16+
intbits =0;
17+
while (n !=0) {
18+
bits++;
19+
n &= (n -1);
20+
}
21+
returnbits;
22+
}
2423
}
2524

26-
// you need to treat n as an unsigned value
27-
publicinthammingWeight(intn) {
28-
//cheers! Made it AC'ed on my own with an ease!
29-
intcount =0;
30-
for (inti =0;i <32;i++) {
31-
intone = (n >>>i) &1;//must use unsigned right shift operator
32-
if (one ==1) {
33-
count++;
25+
publicstaticclassSolution2 {
26+
publicinthammingWeight(intn) {
27+
intbits =0;
28+
intmask =1;
29+
for (inti =0;i <32;i++) {
30+
if ((n &mask) !=0) {
31+
bits++;
32+
}
33+
mask <<=1;
3434
}
35+
returnbits;
3536
}
36-
returncount;
3737
}
3838

39-
//then I turned to its Editorial solution: we can make it a little faster: at any time, when n becomes zero, that means there's
40-
//no more 1's there, then we could safely return! Cool!
41-
publicinthammingWeight_faster(intn) {
42-
intcount =0;
43-
for (inti =0;i <32;i++) {
44-
intone = (n >>>i) &1;//must use unsigned right shift operator
45-
if (one ==1) {
46-
count++;
47-
}
48-
if (n ==0) {
49-
returncount;
39+
publicstaticclassSolution3 {
40+
publicinthammingWeight(intn) {
41+
intbits =0;
42+
for (inti =0;i <32;i++) {
43+
if ((n &1) ==1) {
44+
bits++;
45+
}
46+
if (n ==0) {
47+
returnbits;
48+
}
49+
/**must use unsigned right shift operator since the problem says this is an unsigned value*/
50+
n >>>=1;
5051
}
52+
returnbits;
5153
}
52-
returncount;
5354
}
54-
5555
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.solutions._191;
4+
importorg.junit.BeforeClass;
5+
importorg.junit.Test;
6+
7+
importstaticjunit.framework.TestCase.assertEquals;
8+
9+
publicclass_191Test {
10+
privatestatic_191.Solution1solution1;
11+
privatestatic_191.Solution2solution2;
12+
privatestatic_191.Solution3solution3;
13+
14+
@BeforeClass
15+
publicstaticvoidsetup() {
16+
solution1 =new_191.Solution1();
17+
solution2 =new_191.Solution2();
18+
solution3 =new_191.Solution3();
19+
}
20+
21+
@Test
22+
publicvoidtest1() {
23+
assertEquals(1,solution1.hammingWeight(1));
24+
assertEquals(1,solution2.hammingWeight(1));
25+
assertEquals(1,solution3.hammingWeight(1));
26+
}
27+
28+
@Test
29+
publicvoidtest2() {
30+
// System.out.println(Integer.MAX_VALUE);
31+
// assertEquals(2147483648, Integer.MAX_VALUE);
32+
}
33+
34+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp