thảo luận Leetcode contest, đường tới Guardian
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
- Trạng thái
đề gì toàn nặng implement không vậy
TLE_WA
Junior Member
Không đến O(n^2) đâu anh, lưu vào map là một loop qua các phần tử trong nums thôiRõ ràng giải O(n^2) + 0(n)*2^7 mà éo pass đcm tức điên
freedom.9
Senior Member
Cái đm nhà nó sửa cái clone ra accepted luôn, đồn như lời
Original version
Xoá cái final.copy() thành final ăn luôn, thật hả trời 
Original version
Python:
class Solution:
def countPairs(self, nums: List[int]) -> int:
def doSwap(mask, count, final, current):
n = len(current)
if count == 2:
final.add(int("".join(current)))
if count == 4:
final.add(int("".join(current)))
return
for i in range(n):
if (mask >> i)&1 == 1:
continue
for j in range(i + 1, n):
if i == j:
continue
if mask >> j & 1 == 1:
continue
temp = current[i]
current[i] = current[j]
current[j] = temp
newMask = mask
newMaks = (newMask << i) | 1
newMask = (newMask << j) | 1
doSwap(newMask, count + 2, final, current)
temp = current[i]
current[i] = current[j]
current[j] = temp
N = len(nums)
count = 0
frequency = defaultdict(int)
for num in nums:
frequency[num] += 1
cache = defaultdict(set)
for num in set(nums):
if num in cache:
continue
final = set()
current = list(str(num))
doSwap(0, 0, final, current)
cache[num] = final.copy()
count = 0
for i in range(N):
for j in range(i + 1, N):
if nums[j] in cache[nums[i]] or nums[i] in cache[nums[j]] or nums[i] == nums[j]:
count +=1
return countfreedom.9
Senior Member
Mình cũng nghĩ thế mà count sai, còn cả tiếng mà ko bình tĩnh để count nổiKhông đến O(n^2) đâu anh, lưu vào map là một loop qua các phần tử trong nums thôi
TLE_WA
Junior Member
để ý đề thì mỗi phần tử trong nums thì chỉ nên +1 với mỗi possible_new_num cho dù có nhiều cách để tạo ra, thêm một map đánh dấu việc này là xongMình cũng nghĩ thế mà count sai, còn cả tiếng mà ko bình tĩnh để count nổi
C++:
unordered_map<int, bool> have;
...
if (change != 0 && !have[change]) {
f[nums[i] + change]++;
have[change] = true;
}
...
if (change + change2 == 0 || have[change + change2]) continue;
f[nums[i] + change + change2]++;
have[change + change2] = true;
lilleboybk
Senior Member
Em cũng làm 1 cái map<num_i, count_i>, với num_i là các số khác nhau trong nums.Không đến O(n^2) đâu anh, lưu vào map là một loop qua các phần tử trong nums thôi
Với từng num_i, có luôn (count_i * (count_i + 1)) / 2 cặp.
Rồi thử swap 2 lần từ num_i xem được các số num_j, có thêm count_j * count_i cặp.
Xử lý xong num_i thì xoá khỏi Map.
freedom.9
Senior Member
Python:
class Solution:
def countPairs(self, nums: List[int]) -> int:
def doSwap(mask, count, final, current):
n = len(current)
if count == 2:
final.add(int("".join(current)))
if count == 4:
final.add(int("".join(current)))
return
for i in range(n):
if (mask >> i)&1 == 1:
continue
for j in range(i + 1, n):
if i == j:
continue
if mask >> j & 1 == 1:
continue
temp = current[i]
current[i] = current[j]
current[j] = temp
newMask = mask
newMaks = (newMask << i) | 1
newMask = (newMask << j) | 1
doSwap(newMask, count + 2, final, current)
temp = current[i]
current[i] = current[j]
current[j] = temp
N = len(nums)
count = 0
frequency = defaultdict(int)
for num in nums:
frequency[num] += 1
cache = defaultdict(set)
unique = set(nums)
for num in unique:
if num in cache:
continue
final = set([num])
current = list(str(num))
doSwap(0, 0, final, current)
cache[num] = final.copy()
count = 0
unique = list(unique)
n = len(unique)
for i in range(n):
for j in range(i + 1, n):
if unique[i] in cache[unique[j]] or unique[j] in cache[unique[i]]:
count += frequency[unique[i]]*frequency[unique[j]]
for num in unique:
count += frequency[num]*(frequency[num] - 1)//2
return countlilleboybk
Senior Member
Em nghĩ convert mảng đã cho và multiplier ra log ấy, quy về tìm xem mỗi phần tử được "cộng" bao nhiêu lần cái log_multipler thôi. Em làm kiểu "cố định" chỉ số là min + chặt nhị phân tìm số lần cộng tối đa của chỉ số này => tính ra số lần cộng của các số khác. Tý em xem có phải là solution không tại ko biết nó đúng hay sai.
thanhdonguyen01
Senior Member
Các thím cho em hỏi test case ở Q4 ạ.
Em thấy LeetCode báo TLE (sau khi pass 624 tests), nhưng khi cho chạy test case đấy riêng thì LeetCode nó vẫn chạy được mà không TLE, thế là sao ạ. Em cảm ơn (em dùng Python 3)
Em thấy LeetCode báo TLE (sau khi pass 624 tests), nhưng khi cho chạy test case đấy riêng thì LeetCode nó vẫn chạy được mà không TLE, thế là sao ạ. Em cảm ơn (em dùng Python 3)
freedom.9
Senior Member
Do nó tính tổng của tất cả các execution + lại chứ ko phải 1 single testcaseCác thím cho em hỏi test case ở Q4 ạ.
Em thấy LeetCode báo TLE (sau khi pass 624 tests), nhưng khi cho chạy test case đấy riêng thì LeetCode nó vẫn chạy được mà không TLE, thế là sao ạ. Em cảm ơn (em dùng Python 3)
TLE_WA
Junior Member
à sau khi đọc sol của top1 thì mình hiểu tại sao rồi, sau khi mỗi phần tử đều được nhân lên ít nhất 1 lần thì thứ tự sau khi nhân thêm một chu trình sẽ không thay đổi (một chu trình = n (n là số phần tử))
Modify một chút solution của top1, không nhất thiết phải <= 10**9, chỉ cần mỗi phần tử trong dãy được nhân lên ít nhất 1 lần là có thể thoát khỏi vòng lặp
Ví dụ cho dễ hình dung thì [5,3,11] với mul = 2 thì sau khi sort là [12, 20, 22] sẽ là giá trị của mảng sau khi thoát khỏi vòng lặp, lúc này dù ta có nhân như nào thì thứ tự vẫn sẽ duy trì như này (ý mình là nhân toàn bộ phần tử với multiplier cùng số lần nhân là xyz gì đó)
Python:
from sortedcontainers import SortedList
class Solution:
def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
def power(p, x, e):
base = x
answer = 1
while e:
if e & 1:
answer = (answer * base) % p
base = (base * base) % p
e >>= 1
return answer
if multiplier == 1:
return nums
mod = 10**9 + 7
mark = set()
n = len(nums)
sl = SortedList([(x, i) for i, x in enumerate(nums)])
while len(mark) != n:
x,i = sl[0]
sl.remove((x, i))
sl.add((x * multiplier, i))
mark.add(i)
k -= 1
if k == 0:
answer = [0] * n
for (x, i) in sl:
answer[i] = x % mod
return answer
q, r = k // n, k % n
p1, p2 = power(mod, multiplier, q + 1), power(mod, multiplier, q)
answer = [0] * n
for i in range(r):
x, idx = sl[i]
answer[idx] = (x * p1) % mod
for i in range(r, n):
x, idx = sl[i]
answer[idx] = (x * p2) % mod
return answerlilleboybk
Senior Member
Nếu thế thì ảo thật bác, chắc phải làm qua dạng này rồi hoặc làm cách trâu bò trước để tìm ra quy luật. Còn Q4 thấy kha khá bác TLE chứ ko cũng nhiều accepted.
freedom.9
Senior Member
Q4 tính ra ko khó lắm nhỉ, mình chỉ làm dạng bitmask swap 4 lần là ok, mình đoán là constrain này sẽ pass.
Mà Python TLE quá phải đi optimize, 629/630 mà convert qua Java hay C++ thì dư sức pass với bruteforce, Leetcode nó restrict với Python quá
Q3 đọc đề phát là skip luôn, K cao quá nghĩ binary search đau đầu lắm
via theNEXTvoz for iPhone
thanhdonguyen01
Senior Member
Thím cho em hỏi ý tưởng dùng bitmask này nhìn từ đâu ra được đấy thím
Em lúc nãy chỉ nghĩ ra hướng biến 2 số thành array rồi đếm swap tối thiểu để thành 1 mảng chung giống nhau
Em cảm ơn ạ 
freedom.9
Senior Member
À ngay q2 mình đã dùng swap rồi, q4 mình chỉ extend ra thêm bitmask vào và backtracking thôi.Thím cho em hỏi ý tưởng dùng bitmask này nhìn từ đâu ra được đấy thím
Em lúc nãy chỉ nghĩ ra hướng biến 2 số thành array rồi đếm swap tối thiểu để thành 1 mảng chung giống nhau
Ý tưởng là vì num chỉ max là 10^7 với 7 số, việc swap 2 số 2 lần thì max sẽ là C(4,7) số sẽ đc tạo ra, với length chỉ có 5000 thì constrain khá là thấp nên sẽ pass được Memory với Time complexity.
Nên đọc đề mình đã nghĩ tới brute force, còn với 7 số thì chọn ra 2 số i j rồi swap, để biết số nào đã đc swap rồi thì mình dùng 1 bitmask để đánh dấu thôi bác, mình khá vững phần bitmask này vì hay xài trong dp.
Gần đây mình hay có ý tưởng giải đc mấy câu hard nhưng hay bị bí ở phần implementation với đọc đề ẩu, chắc cẩn thận optimize tí nữa thì lên được Guardian rồi
hên nãy làm q2 nhanh nên vẫn trong top 1k2 
via theNEXTvoz for iPhone
lilleboybk
Senior Member
Thực ra ko cần bitmask cũng được bác. Em dùng 2 vòng for (i, j) cho 2 index cần swap thôi.Thím cho em hỏi ý tưởng dùng bitmask này nhìn từ đâu ra được đấy thím
Em lúc nãy chỉ nghĩ ra hướng biến 2 số thành array rồi đếm swap tối thiểu để thành 1 mảng chung giống nhau
JavaScript:
function swapTwice(u: number): number[] {
var len = 7;
var a: Set<number> = new Set();
const swapOne = (p: number) => {
var chars: string[] = (p + "").padStart(len, "0").split("");
for (var i = 0; i < len - 1; i++) {
for (var j = i + 1; j < len; j++) {
if (chars[i] === chars[j]) {
continue;
}
[chars[i], chars[j]] = [chars[j], chars[i]];
const new_num = Number(chars.join(""));
a.add(new_num);
[chars[i], chars[j]] = [chars[j], chars[i]];
}
}
};
swapOne(u);
const a1 = [...a];
for (var num of a1) {
swapOne(num);
}
return [...a];
}
function countPairs(nums: number[]): number {
const map: Map<number, number> = new Map();
nums.forEach((num) => {
map.set(num, (map.get(num) ?? 0) + 1);
});
var res = 0;
map.forEach((count1, num1) => {
res += (count1 * (count1 - 1)) / 2;
const a = swapTwice(num1);
a.forEach((num2) => {
if (num1 === num2) {
return;
}
if (!map.has(num2)) {
return;
}
var count2 = map.get(num2) ?? 0;
if (count2 === 0) {
return;
}
res += count1 * count2;
});
map.set(num1, 0);
});
return res;
}- Trạng thái
Chủ đề tương tự
