thảo luận Leetcode mỗi ngày

anoldvozer1710.v2 said:

bài hôm nay có giải đc array in-place ko ae. Chứ tạo mảng mới thì ez quá

Spoiler: TypeScript

JavaScript:

function shuffle(nums: number[], n: number): number[] {
    if (nums.length === 2) {
        return nums;
    }
    let arr: number[] = [];
    for (let i = 0; i < n; i++) {
        arr.push(nums[i]);
        arr.push(nums[i+n]);
    }
    return arr;
};

Click to expand...

anoldvozer1710.v2 said:

bài hôm nay có giải đc array in-place ko ae. Chứ tạo mảng mới thì ez quá

Click to expand...

Spoiler

ví dụ toy ghép thế này:

ban đầu:
x1 x2 x3 x4 x5 x6 x7 x8 x9 y1 y2 y3 y4 y5 y6 y7 y8 y9

ghép x9, x8, ... x2, x1 vào trước slot của chỗ nó sau khi shuffle:
x1x1 x2 x2x3 x4 x3x5 x6 x4x7 x8 x5x9 y1 x6y2 y3 x7y4 y5 x8y6 y7 x9y8 y9
ở đây toy đi ngược x9, x8 để khỏi phải tách ví dụ x3 từ x2x3 nếu đi từ x1, x2 lên. Nhưng đi xuôi tách ra có khi lại lẹ hơn vì ko bị cache miss

(ghép vào sau cũng được, nhưng tới khi ghép y1, y2,... thì hơi lằng nhằng)

ghép y1, y2, ..., y9 vào trước slot của nó sau khi shuffle. Ở đây phải tách lấy y là phần sau của mỗi số ở slot
x1x1 y1x2 x2x3 y2x4 x3x5 y3x6 x4x7 y4x8 x5x9 y5y1 x6y2 y6y3 x7y4 y7y5 x8y6 y8y7 x9y8 y9y9

sau đó lấy phần trước của số ở mỗi slot là xong:
x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 x6 y6 x7 y7 x8 y8 x9 y9

bước ghép y1, y2, ... có thể optimize gán thẳng luôn ko cần ghép:
x1x1 y1 x2x3 y2 x3x5 y3 x4x7 y4 x5x9 y5 x6y2 y6 x7y4 y7 x8y6 y8 x9y8 y9

để ghép 2 số a1 a2 với nhau thành a1a2 thì nếu biết trước a1, a2 <= n thì có thể ghép bằng cách nhân a1 với m>n rồi cộng a2: a1a2 = a1*m + a2. Ở đây n=1000 thì có thể chọn m=1001, số 1001 cũng là số chúng nó chọn, nhưng có thể tối ưu hơn chọn m=1024=2^10 thì phép nhân a1*m có thể tối ưu thành dịch trái 10 bit, và bước cuối cùng thay vì chia 1001 thì có thể xài dịch phải 10 bit.

C++:

struct Solution {
    vector<int> shuffle(vector<int>& nums, const int n) {
        for (int i = n; i--;) nums[2*i] += nums[i] << 10;
        for (int i = n, j = 1; i < 2*n; ++i, j += 2) nums[j] = nums[i] & 0x3ff;
        for (int i = 0; i < n; ++i) nums[2*i] >>= 10;
        return move(nums);
    }
};

<<10, >>10, &0x3ff chưa nhìn quen thì thấy ghê thế thoy chứ ghi là *1024, /1024, %1024 biên dịch xài -O2 nó cũng tối ưu được hết

Violet_7 said:

có, vì giá trị mỗi phần tử nhỏ (max 1000)

Click to expand...

Spaghetti Code said:

đọc lời giải thì thấy tụi nó ghép số lại

Spoiler

ví dụ toy ghép thế này:

ban đầu:
x1 x2 x3 x4 x5 x6 x7 x8 x9 y1 y2 y3 y4 y5 y6 y7 y8 y9

ghép x9, x8, ... x2, x1 vào trước slot của chỗ nó sau khi shuffle:
x1x1 x2 x2x3 x4 x3x5 x6 x4x7 x8 x5x9 y1 x6y2 y3 x7y4 y5 x8y6 y7 x9y8 y9
ở đây toy đi ngược x9, x8 để khỏi phải tách ví dụ x3 từ x2x3 nếu đi từ x1, x2 lên. Nhưng đi xuôi tách ra có khi lại lẹ hơn vì ko bị cache miss

ghép y1, y2, ..., y9 vào trước slot của nó sau khi shuffle. Ở đây phải tách lấy y là phần sau của mỗi số ở slot
x1x1 y1x2 x2x3 y2x4 x3x5 y3x6 x4x7 y4x8 x5x9 y5y1 x6y2 y6y3 x7y4 y7y5 x8y6 y8y7 x9y8 y9y9

sau đó lấy phần trước của số ở mỗi slot là xong:
x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 x6 y6 x7 y7 x8 y8 x9 y9

bước ghép y1, y2, ... có thể optimize gán thẳng luôn ko cần ghép:
x1x1 y1 x2x3 y2 x3x5 y3 x4x7 y4 x5x9 y5 x6y2 y6 x7y4 y7 x8y6 y8 x9y8 y9

để ghép 2 số a1 a2 với nhau thành a1a2 thì nếu biết trước a1, a2 <= n thì có thể ghép bằng cách nhân a1 với m>n rồi cộng a2: a1a2 = a1*m + a2. Ở đây n=1000 thì có thể chọn m=1001, đây cũng là cách chúng nó chọn, nhưng có thể tối ưu hơn chọn m=1024=2^10 thì phép nhân a1*m có thể tối ưu thành dịch trái 10 bit, và bước cuối cùng thay vì chia 1001 thì có thể xài dịch phải 10 bit.

C++:

struct Solution {
    vector<int> shuffle(vector<int>& nums, int n) {
        for (int i = n; i--;) nums[2*i] += nums[i] << 10;
        for (int i = n, j = 1; i < 2*n; ++i, j += 2) nums[j] = nums[i] & 0x3ff;
        for (int i = 0; i < n; ++i) nums[2*i] >>= 10;
        return move(nums);
    }
};

Click to expand...

anoldvozer1710.v2 said:

Vừa vô xem solution thấy top toàn in-place thật. Mà sao tạo array mới mà Space Complexity vẫn là O(1) thế thím

nhìn loằng ngoằng mì tôm vãi đạn

via theNEXTvoz for iPhone

Click to expand...

thanbaiks said:

Spoiler: JavaScript

JavaScript:

var shuffle = (nums, n) => Array(n).fill().flatMap((_, idx) => [nums[idx], nums[n+idx]]);

Click to expand...

NecNec said:

ngắn gọn vậy bác

Click to expand...

NecNec said:

Bài hôm nay không hiểu đề bài, bác nào giải thích lại giúp với

Click to expand...

function totalFruit(fruits: number[]): number {
    const map: Map<number, number> = new Map();
    let i = 0, max = 0;
    for (let j = 0; j < fruits.length; j++) {
        if (map.has(fruits[j])) {
            map.set(fruits[j], map.get(fruits[j]) + 1)
        } else {
            map.set(fruits[j], 1);
        }
        // Maintain map size to have only 2 keys
        while (map.size > 2) {
            map.set(fruits[i], map.get(fruits[i]) - 1);
            if (map.get(fruits[i]) === 0)
                map.delete(fruits[i]);
            i++;
        }
        max = Math.max(max, j - i + 1);
    }

    return max;
};

anoldvozer1710.v2 said:

Cho 1 array dạng [x1, x2, x3, x4,....,xn].
Chọn 1 sub-array sao cho sub-array có độ dài lớn nhất đồng thời chỉ có 2 loại giá trị phân biệt. Ví dụ [1,2,1] là được còn [1,2,3] thì không được.
Yêu cầu: return độ dài của sub-array đó
Ví dụ: fruits = [1,2,3,2,2]
-> Đáp án là 4 vì sub-array [2,3,2,2] có 2 giá trị phân biệt là 2 và 3.

Spoiler: Cách làm

Sử dụng brute-force để duyệt trên từng mảng con, hoặc tối ưu hơn là sử dụng sliding window vàluôn duy trì window đó luôn chỉ có 2 loại giá trị

Spoiler: TypeScript 7/2 Sliding Window

JavaScript:

function totalFruit(fruits: number[]): number {
    const map: Map<number, number> = new Map();
    let i = 0, max = 0;
    for (let j = 0; j < fruits.length; j++) {
        if (map.has(fruits[j])) {
            map.set(fruits[j], map.get(fruits[j]) + 1)
        } else {
            map.set(fruits[j], 1);
        }
        // Maintain map size to have only 2 keys
        while (map.size > 2) {
            map.set(fruits[i], map.get(fruits[i]) - 1);
            if (map.get(fruits[i]) === 0)
                map.delete(fruits[i]);
            i++;
        }
        max = Math.max(max, j - i + 1);
    }

    return max;
};

Click to expand...

var totalFruit = function(fruits) {
    const n = fruits.length;
    let cnt = Array(n+1).fill(0), groups = 0, ans = -Infinity, j = 0;
    for (let i = 0; i < n; i++) {
        if (!cnt[fruits[i]]) {
            groups++;
        }

        cnt[fruits[i]]++;
        while (groups > 2) {
            if (!--cnt[fruits[j++]]) {
                groups--;
            }
        }

        ans = Math.max(ans, i - j + 1);
    }

    return ans;
};

thanbaiks said:

Đây tưởng gọi là 2 pointers

Spoiler: JS

JavaScript:

var totalFruit = function(fruits) {
    const n = fruits.length;
    let cnt = Array(n+1).fill(0), groups = 0, ans = -Infinity, j = 0;
    for (let i = 0; i < n; i++) {
        if (!cnt[fruits[i]]) {
            groups++;
        }

        cnt[fruits[i]]++;
        while (groups > 2) {
            if (!--cnt[fruits[j++]]) {
                groups--;
            }
        }

        ans = Math.max(ans, i - j + 1);
    }

    return ans;
};

Click to expand...

anoldvozer1710.v2 said:

Cho 1 array dạng [x1, x2, x3, x4,....,xn].
Chọn 1 sub-array sao cho sub-array có độ dài lớn nhất đồng thời chỉ có 2 loại giá trị phân biệt. Ví dụ [1,2,1] là được còn [1,2,3] thì không được.
Yêu cầu: return độ dài của sub-array đó
Ví dụ: fruits = [1,2,3,2,2]
-> Đáp án là 4 vì sub-array [2,3,2,2] có 2 giá trị phân biệt là 2 và 3.

Click to expand...

function totalFruit(fruits: number[]): number {
  let l = fruits.length
  if (l < 3) return l
  let max = 0
  let temp = 0
  let i = 0
  let basket1 = -1
  let basket2 = -1
  let checkpoint = 0
  while (i < l) {
    if (basket1 === basket2 && basket1 === -1) {
      temp++
      basket1=fruits[i]
      i++
      continue
    }
    if (basket1 >= 0 && basket1 !== fruits[i] && basket2 < 0) {
      temp++
      basket2=fruits[i]
      checkpoint = i
      i++
      continue
    }
    if (fruits[i] !== basket1 && fruits[i] !== basket2) {
      max = max < temp ? temp : max
      i = checkpoint
      basket1 = -1
      basket2 = -1
      temp = 0
      continue
    }
    temp++
    if (i === l - 1) {
      max = max < temp ? temp : max
    }
    i++
  }
  return max
};

anoldvozer1710.v2 said:

2 Pointers là kiểu 1 nhanh - 1 chậm hoặc 1 đầu - 1 cuối chứ thím

via theNEXTvoz for iPhone

Click to expand...

thanbaiks said:

Đúng rồi. Thấy i của thím chạy đuổi theo j mà

Click to expand...

• 2 Pointers Technique: chỉ quan tâm đến value tại 2 điểm i và j thôi, ít quan tâm/ không quan tâm đến các giá trị trong khoảng (i, j). Thường áp dụng cho mấy bài tìm kiếm
• Sliding window: Sử dụng tất cả các giá trị trong khoảng window, chứ k phải chỉ 2 giá trị, thường áp dụng cho mấy bài tính toán

• Fast-slow runner: Cái này em thấy thường là mấy bài Linked List hoặc, tốc độ chạy của 2 thằng khác nhau, ví dụ con trỏ 2 chạy nhanh gấp đôi con trỏ 1 thì con trỏ 2 chạy đến phần tử cuối linked list thì con trỏ 1 mới chạy đến giữa.
• First-last: Chắc là mấy bài dùng binary search