Bài 1:
Cho 2 số n và m, chèn tất cả các bit của m vào n theo khoảng từ i đến j. Có thể chắc chắn là số lượng bit của n luôn lớn hơn m, và i-j = số lượng bit của m.
Ví dụ:
Input: n = 1024
m = 19
i = 2
j = 6
Output: n = 1100
Giải thích
(1024)10 = (10000000000)2
(19)10 = (10011)2
kết quả : (10001001100)2 = (1100)10
Cách làm như sau
1. xoá toàn bộ bit từ i đến j (về 0) của n
2. dịch m sang trái i bit
3. trả về kết quả m & n
Bước 1 là khó nhất, chúng ta áp dụng cách làm thông thường là tạo mặt nạ.
Mặt nạ của chúng ta gồm 3 phần, bên trái j, bên phải i là 1, ở giữa i j là 0.
let allOnes = ~0
let left = allOnes << (j + 1)
let right = ((1 << i) - 1)
let mask = left | right
sau đó chỉ cần & n với mặt nạ vừa tạo là xong.
Bài 2:
Cho một số nguyên và một lần duy nhất đổi bit 0 thành bit 1. Cài đặt hàm tìm chuỗi 1 dài nhất sau khi thực một lần đổi bit.
Ví dụ:
Input: 1775 (tương ứng: 11011101111)
Output: 8
Gỉai thích: nếu đổi bit thứ 9 thì có chuỗi 1 dài nhất là 6, đổi bit thứ 5 ta có chuỗi 8
Hmm, giải như thế nào đây ta?
Ý tưởng đầu tiên của mình là đếm toàn bộ số 1 bên trái và phải của toàn bộ số 0, sau đó trả về max tổng trái phải….
ví dụ 101110111, phải của 0 đầu là 3, trái là 3, phải 0 sau là 3, trái là 1, vậy kết quả sẽ là max( 3+3, 3+1) + 1 = 7.
Nếu duyệt 2 lần thì sẽ double work việc tìm 1 trái phải, nên chúng ta có cách duyệt tối ưu hơn là đếm 1 đến khi gặp 0 thì gán bên phải là hiệu của index hiện tại với index 0 tìm thấy trước đó, bên trái sẽ được tính cho đến khi gặp 0 tiếp theo, thực hiện update lại max nếu cần.
func flipToWin(_ input: Int) -> Int {
var maxLength = 0
var currentLength = 0
var previousLength = 0
var clone = input
while clone > 0 {
let num = clone & 1
if num == 1 {
currentLength += 1
} else {
previousLength = (clone & 2) == 0 ? 0 : currentLength
currentLength = 0
}
maxLength = max(previousLength + currentLength, maxLength);
clone >>= 1
}
return maxLength + 1
}
Happy Coding!