#3 LeetCode Daily t? c?c gà

?? bài

Tr? v? s? l?n thay ??i t?i thi?u ?? làm ??p cho chu?i s

V?y nh? th? nào là ??p? ??p t?c là có th? chia nh? chu?i s ra thành nhi?u chu?i con, m?i chu?i con có ?? dài ch?n, và m?i chu?i con ch? ch?a 0 ho?c 1.

Tam s? tí

Ban ??u t?i ??c ?? kh?ng k?, t?i c? ngh? là ch? ???c chia ra thành 2 chu?i con, nh? v?y thì s? khá là khoai. T?i ?? ??nh b? cu?c và xem solution nh?ng có m?t th? l?c siêu nhiên nào ?ó b?o t?i ??c l?i ??, và th? là...

Y t??ng

G?i ?? dài chu?i ban ??u là n, chia nh? chu?i ban ??u n/2 chu?i con (m?i chu?i con ch? ch?a 2 ky t?), s? l?n thay ??i t?i thi?u chính là s? chu?i con mà chúng có 2 ky t? khác nhau.

Ch?ng h?n: chu?i "1010" chia ra thành "10" và "10" => 2 chu?i con có 2 ky t? khác nhau => s? l?n thay ??i t?i thi?u là 2. T??ng t? v?i 01110000 => 01 11 00 00 => 1 chu?i con có 2 ky t? khác nhau => s? l?n t?i thi?u là 1.

Tri?n khai

T?i loop qua t?ng ky t? c?a chu?i ban ??u, ch? loop qua ky t? có index l? (1, 3, 5, 7, 9...) và so sánh v?i ky t? có index ch?n tr??c ?ó. N?u khác nhau thì ??m s? thêm 1.

class Solution {
???? public int minChanges(String s) {
??????? char[] binaryLetters = s.toCharArray();
??????? char evenIndexLetter;
??????? int numberOfChanges = 0;
??????? for (int oddIndex = 1; oddIndex <= binaryLetters.length - 1; oddIndex += 2) {
??????????? evenIndexLetter = binaryLetters[oddIndex - 1];
??????????? if (binaryLetters[oddIndex] != evenIndexLetter) {
??????????????? numberOfChanges++;
??????????? }
??????? }
??????? return numberOfChanges;
??? }
}        

?? ph?c t?p th?i kh?ng

?? ph?c t?p th?i gian: O(n/2) => O(n) vì loop qua t?i ?a n/2 l?n (ch? loop qua index l?).

?? ph?c t?p kh?ng gian: O(1) vì t?i ch? ch?a th?ng tin d? li?u bi?n ??m.

K?t qu?

T?i ch?y th? thì th?y runtime khá t?t, tuy nhiên memory ch? beats ???c t?i ?a 20%.

T?i ?u l?i

T?i ?ang b?n kho?n kh?ng hi?u t?i sao, ?? ph?c t?p kh?ng gian c?a t?i ch? là O(1) nh?ng memory thì l?i x?p bét. Ngh? nát óc kh?ng ra, t?i bèn xem solution c?a ng??i có ch? s? memory t?t nh?t.

class Solution {
??? public int minChanges(String s) {
??????? int count=0;
??????? for(int i=0;i<s.length();i+=2){
??????????? if(s.charAt(i)!=s.charAt(i+1)){
??????????????? count++;
??????????? }
??????? }
??????? return count;?
??? }
}        

Té ra là h? kh?ng dùng String.toCharArray() nh? t?i, mà h? dùng th?ng charAt() lu?n. T?i ?oán ?ay có th? là nguyên nhan chính d?n ??n vi?c gi?i pháp c?a t?i chi?m nhi?u memory (do t?i m?t b? nh? ch?a thêm m?ng binaryLetters)

T?i s?a l?i solution và submit l?i vài l?n thì k?t qu? ?? khá t?t r?i.