add some bit problems (#294) · wxpython/algorithms@b905623 · GitHub
Skip to content

Commit b905623

Browse files
goswami-rahulHai Hoang Dang
goswami-rahul
authored and
Hai Hoang Dang
committed
add some bit problems (keon#294)
* add arrays/max_ones_index * add 2 algorithms to algorithms/bit * update all READMEs
1 parent b39f4e5 commit b905623

11 files changed

Lines changed: 166 additions & 23 deletions

‎README.md‎

Lines changed: 7 additions & 4 deletions

‎README_CN.md‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
[English](https://github.com/yunshuipiao/algorithms/blob/master/README.md) | 简体中文 | [日本語](README_JP.md)
1+
[English](README.md) | 简体中文 | [Deutsch](README_GE.md) | [日本語](README_JP.md)
22

33
Python版数据结构和算法
44
=========================================
@@ -70,7 +70,8 @@ pip3 uninstall -y algorithms
7070
- [flatten：数组降维](algorithms/arrays/flatten.py)
7171
- [garage：停车场](algorithms/arrays/garage.py)
7272
- [josephus_problem: 约瑟夫问题](algorithms/arrays/josephus_problem.py)
73-
- [longest_non_repeat：最长不重复子串](algorithms/arrays/longest_non_repeat.py/)
73+
- [max_ones_index](algorithms/arrays/max_ones_index.py)
74+
- [longest_non_repeat：最长不重复子串](algorithms/arrays/longest_non_repeat.py/)
7475
- [merge_intervals：合并重叠间隔](algorithms/arrays/merge_intervals.py)
7576
- [missing_ranges：遗失的范围](algorithms/arrays/missing_ranges.py)
7677
- [plus_one：加一运算](algorithms/arrays/plus_one.py)
@@ -101,7 +102,9 @@ pip3 uninstall -y algorithms
101102
- [bit：位操作](algorithms/bit)
102103
- [bytes_int_conversion：字节整数转换](algorithms/bit/bytes_int_conversion.py)
103104
- [count_ones：统计1出现的次数](algorithms/bit/count_ones.py)
105+
- [count_flips_to_convert](algorithms/bit/count_flips_to_convert.py)
104106
- [find_missing_number：寻找缺失数](algorithms/bit/find_missing_number.py)
107+
- [flip_bit_longest_sequence](algorithms/bit/flip_bit_longest_sequence.py)
105108
- [power_of_two：2的n次方数判断](algorithms/bit/power_of_two.py)
106109
- [reverse_bits：反转位](algorithms/bit/reverse_bits.py)
107110
- [single_number2：寻找出现1次的数（2)](algorithms/bit/single_number2.py)

‎README_GE.md‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
[English](README.md) | [简体中文](https://github.com/yunshuipiao/algorithms/blob/master/README_CN.md) | Deutsch | [日本語](README_JP.md)
1+
[English](README.md) | [简体中文](README_CN.md) | Deutsch | [日本語](README_JP.md)
22

33
[![Open Source Helpers](https://www.codetriage.com/keon/algorithms/badges/users.svg)](https://www.codetriage.com/keon/algorithms)
44
[![Build Status](https://travis-ci.org/keon/algorithms.svg?branch=master)](https://travis-ci.org/keon/algorithms)
@@ -65,6 +65,7 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
6565
- [garage](algorithms/arrays/garage.py)
6666
- [josephus_problem](algorithms/arrays/josephus_problem.py)
6767
- [longest_non_repeat](algorithms/arrays/longest_non_repeat.py/)
68+
- [max_ones_index](algorithms/arrays/max_ones_index.py)
6869
- [merge_intervals](algorithms/arrays/merge_intervals.py)
6970
- [missing_ranges](algorithms/arrays/missing_ranges.py)
7071
- [plus_one](algorithms/arrays/plus_one.py)
@@ -95,7 +96,9 @@ Um das Projekt zu deinstallieren tippen Sie folgendes:
9596
- [bit](algorithms/bit)
9697
- [bytes_int_conversion](algorithms/bit/bytes_int_conversion.py)
9798
- [count_ones](algorithms/bit/count_ones.py)
99+
- [count_flips_to_convert](algorithms/bit/count_flips_to_convert.py)
98100
- [find_missing_number](algorithms/bit/find_missing_number.py)
101+
- [flip_bit_longest_sequence](algorithms/bit/flip_bit_longest_sequence.py)
99102
- [power_of_two](algorithms/bit/power_of_two.py)
100103
- [reverse_bits](algorithms/bit/reverse_bits.py)
101104
- [single_number](algorithms/bit/single_number.py)

‎README_JP.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -54,6 +54,7 @@ if __name__ == "__main__":
5454
- [flatten](arrays/flatten.py)
5555
- [garage](arrays/garage.py)
5656
- [josephus_problem](arrays/josephus_problem.py)
57+
- [max_ones_index](algorithms/arrays/max_ones_index.py)
5758
- [longest_non_repeat](arrays/longest_non_repeat.py/)
5859
- [merge_intervals](arrays/merge_intervals.py)
5960
- [missing_ranges](arrays/missing_ranges.py)
@@ -85,7 +86,9 @@ if __name__ == "__main__":
8586
- [bit : ビット](bit)
8687
- [bytes_int_conversion](bit/bytes_int_conversion.py)
8788
- [count_ones](bit/count_ones.py)
89+
- [count_flips_to_convert](algorithms/bit/count_flips_to_convert.py)
8890
- [find_missing_number](bit/find_missing_number.py)
91+
- [flip_bit_longest_sequence](algorithms/bit/flip_bit_longest_sequence.py)
8992
- [power_of_two](bit/power_of_two.py)
9093
- [reverse_bits](bit/reverse_bits.py)
9194
- [single_number](bit/single_number.py)

‎algorithms/arrays/__init__.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,7 @@
33
from .garage import *
44
from .josephus import *
55
from .longest_non_repeat import *
6+
from .max_ones_index import *
67
from .merge_intervals import *
78
from .missing_ranges import *
89
from .move_zeros import *

‎algorithms/arrays/max_ones_index.py‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
"""
2+
Find the index of 0 to be replaced with 1 to get
3+
longest continuous sequence
4+
of 1s in a binary array.
5+
Returns index of 0 to be
6+
replaced with 1 to get longest
7+
continuous sequence of 1s.
8+
If there is no 0 in array, then
9+
it returns -1.
10+
11+
e.g.
12+
let input array = [1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1]
13+
If we replace 0 at index 3 with 1, we get the longest continuous
14+
sequence of 1s in the array.
15+
So the function return => 3
16+
"""
17+
18+
19+
def max_ones_index(arr):
20+
21+
n = len(arr)
22+
max_count = 0
23+
max_index = 0
24+
prev_zero = -1
25+
prev_prev_zero = -1
26+
27+
for curr in range(n):
28+
29+
# If current element is 0,
30+
# then calculate the difference
31+
# between curr and prev_prev_zero
32+
if arr[curr] == 0:
33+
if curr - prev_prev_zero > max_count:
34+
max_count = curr - prev_prev_zero
35+
max_index = prev_zero
36+
37+
prev_prev_zero = prev_zero
38+
prev_zero = curr
39+
40+
if n - prev_prev_zero > max_count:
41+
max_index = prev_zero
42+
43+
return max_index

‎algorithms/bit/__init__.py‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,3 +13,5 @@
1313
from .has_alternative_bit import *
1414
from .insert_bit import *
1515
from .remove_bit import *
16+
from .count_flips_to_convert import *
17+
from .flip_bit_longest_sequence import *

‎algorithms/bit/count_flips_to_convert.py‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
"""
2+
Write a function to determine the number of bits you would need to
3+
flip to convert integer A to integer B.
4+
For example:
5+
Input: 29 (or: 11101), 15 (or: 01111)
6+
Output: 2
7+
"""
8+
9+
10+
def count_flips_to_convert(a, b):
11+
12+
diff = a ^ b
13+
14+
# count number of ones in diff
15+
count = 0
16+
while diff:
17+
diff &= (diff - 1)
18+
count += 1
19+
return count

‎algorithms/bit/flip_bit_longest_sequence.py‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
"""
2+
You have an integer and you can flip exactly one bit from a 0 to 1.
3+
Write code to find the length of the longest sequence of 1s you could create.
4+
For example:
5+
Input: 1775 ( or: 11011101111)
6+
Output: 8
7+
"""
8+
9+
10+
def flip_bit_longest_seq(num):
11+
12+
curr_len = 0
13+
prev_len = 0
14+
max_len = 0
15+
16+
while num:
17+
if num & 1 == 1: # last digit is 1
18+
curr_len += 1
19+
20+
elif num & 1 == 0: # last digit is 0
21+
if num & 2 == 0: # second last digit is 0
22+
prev_len = 0
23+
else:
24+
prev_len = curr_len
25+
curr_len = 0
26+
27+
max_len = max(max_len, prev_len + curr_len)
28+
num = num >> 1 # right shift num
29+
30+
return max_len + 1

‎tests/test_array.py‎

Lines changed: 25 additions & 13 deletions

0 commit comments

Comments
 (0)