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

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        res = -1
        freq = defaultdict(int)
        n = len(nums)
        for i in nums:
            freq[i] += 1
        if k == n:
            res = max(nums)
        elif k == 1:
            for i in freq:
                if freq[i] == 1:
                    res = max(res, i)
        else:
            if freq[nums[0]] == 1 and freq[nums[n - 1]] == 1:
                res = max(nums[0], nums[n - 1])
            elif freq[nums[0]] == 1:
                res = nums[0]
            elif freq[nums[n - 1]] == 1:
                res = nums[n - 1]
       
        return res

func largestInteger(nums []int, k int) int {
    count := make(map[int]int, 0)
    for i := 0; i <= len(nums) - k; i++ {
        for j := i; j < i + k; j++ {
            count[nums[j]]++
        }
    }
    res := -1
    for n, c := range(count) {
        if (c == 1 || len(nums) == k) && n > res {
            res = n
        }
    }
    return res
}

class Solution:
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)
        counter = Counter(nums)
        mx = -1
        if k == n:
            return max(counter.keys())

        if k == 1:
            for key, value in counter.items():
                if value == 1:
                    mx = max(mx, key)
                    
            return mx
        
        if counter[nums[0]] == 1 :
            mx = max(nums[0], mx)

        if counter[nums[-1]] == 1 :
            mx = max(nums[-1], mx)

        return mx

class Solution {
    public:
        int largestInteger(const std::vector<int> &nums, const int &k) {
            const int n = nums.size();
            if (k == n) return *std::max_element(nums.begin(), nums.end());
            std::unordered_map<int, int> a;
            for (auto &i: nums) {
                a[i]++;
            }

            if (k == 1) {
                int b = -1;
                for (const auto &i: a) {
                    if ((i.second == 1) && (i.first > b)) {
                        b = i.first;
                    }
                }
                return b;
            }

            if (a[nums[0]] > 1 && a[nums[n - 1]] > 1) return -1;
            return std::max((a[nums[0]] - 1 == 0) * nums[0], (a[nums[n - 1]] - 1 == 0) * nums[n - 1]);
        }
};

function maxNumberOfFamilies(n: number, reservedSeats: number[][]): number {
    const map = new Map();
    for (const [x, y] of reservedSeats) {
        if (!map.has(x)) {
            map.set(x, new Set());
        }
        map.get(x)!.add(y);
    }
    let res = 2 * (n - map.size);
    for (const arr of map.values()) {
        const l = [2, 3, 4, 5].every(x => !arr.has(x));
        const m = [4, 5, 6, 7].every(x => !arr.has(x));
        const r = [6, 7, 8, 9].every(x => !arr.has(x));
        if (l && r) {
            res += 2;
        } else if (l || m || r) {
            res += 1;
        }
    }
    return res;

};

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        set1 = {2, 3, 4, 5}
        set2 = {4, 5, 6, 7}
        set3 = {6, 7, 8, 9}
        rows = defaultdict(set[int])
        count = 0
        for seat in reservedSeats:
            rows[seat[0]].add(seat[1])
        for row in rows:
            intersect1, intersect2, intersect3 = rows[row].intersection(set1), rows[row].intersection(set2), rows[row].intersection(set3)
            if not intersect1 and not intersect3:
                count += 2
            elif not intersect1 or not intersect2 or not intersect3:
                count += 1

        return count + (n - len(rows)) * 2

class Solution {
    public:
        int maxNumberOfFamilies(const int &n, std::vector<std::vector<int>> reservedSeats) {
            int a = 0;
            const int b = 0b11110000, c = 0b00111100, d = 0b00001111;
            std::unordered_map<int, int> e;

            for (const auto &i: reservedSeats) {
                if (i[1] > 1 && i[1] < 10) {
                    e[i[0]] |= 1 << (9 - i[1]);
                }
            }

            a = 2 * (n - e.size());
            for (const auto &i: e) {
                if (!((b & i.second) || (d & i.second))) a += 2;
                else if (!((b & i.second) && (c & i.second) && (d & i.second))) a++;
            }
            return a;
        }
};

func maxNumberOfFamilies(n int, reservedSeats [][]int) int {
    res := n * 2
    mapRowToSeats := make(map[int][]int, 0)
    for _, seat := range reservedSeats {
        if _, ok := mapRowToSeats[seat[0]]; !ok {
            mapRowToSeats[seat[0]] = make([]int, 0)
        }
        mapRowToSeats[seat[0]] = append(mapRowToSeats[seat[0]], seat[1])
    }
    for _, seats := range mapRowToSeats {
        if !slices.Contains(seats, 2) && !slices.Contains(seats, 3) && !slices.Contains(seats, 4) && !slices.Contains(seats, 5) && !slices.Contains(seats, 6) && !slices.Contains(seats, 7) && !slices.Contains(seats, 8) && !slices.Contains(seats, 9) {
            continue
        }
        if !slices.Contains(seats, 4) && !slices.Contains(seats, 5) && !slices.Contains(seats, 6) && !slices.Contains(seats, 7) {
            res--
            continue
        }
        if !slices.Contains(seats, 2) && !slices.Contains(seats, 3) && !slices.Contains(seats, 4) && !slices.Contains(seats, 5) {
            res--
            continue
        }
        if !slices.Contains(seats, 6) && !slices.Contains(seats, 7) && !slices.Contains(seats, 8) && !slices.Contains(seats, 9) {
            res--
            continue
        }
        res -= 2
    }
    return res
}

maxNumberOfFamilies=(n,r,m=new
  Map(),p='reduce')=>[...r[p]((m,[a,b])=>m.set(a,(m.get(a)||0)|3<<(b>>1)>>2&7),m).values()][p]((r,m)=>r-((m+5)/6|0),n*2)

function resultArray(nums: number[]): number[] {
    const arr1: number[] = [nums[0]], arr2: number[] = [nums[1]];
    for (let i = 2; i < nums.length; i++) {
        if (arr1[arr1.length - 1] > arr2[arr2.length - 1]) arr1.push(nums[i]);
        else arr2.push(nums[i])
    }
    return arr1.concat(arr2);
};

function resultArray(nums: number[]): number[] {
  const sorted = [...new Set(nums)].sort((a, b) => a - b);

  const rank = new Map<number, number>();

  for (let i = 0; i < sorted.length; i++) {
    rank.set(sorted[i], i + 1);
  }

  const fw1 = new FenwickTree(sorted.length);
  const fw2 = new FenwickTree(sorted.length);

  const arr1: number[] = [nums[0]], arr2: number[] = [nums[1]];

  fw1.add(rank.get(nums[0])!, 1);
  fw2.add(rank.get(nums[1])!, 1);

  for (let i = 2; i < nums.length; i++) {
    const x = nums[i];
    const r = rank.get(x)!;

    const gt1 = arr1.length - fw1.query(r);
    const gt2 = arr2.length - fw2.query(r);

    if (
      gt1 > gt2 ||
      (gt1 === gt2 && arr1.length <= arr2.length)
    ) {
      arr1.push(x);
      fw1.add(r, 1);
    } else {
      arr2.push(x);
      fw2.add(r, 1);
    }
  }

  return [...arr1, ...arr2];
}

class FenwickTree {
  private tree: number[];

  constructor(size: number) {
    this.tree = new Array(size + 1).fill(0);
  }

  add(index: number, delta: number): void {
    for (let i = index; i < this.tree.length; i += i & -i) {
      this.tree[i] += delta;
    }
  }

  query(index: number): number {
    let sum = 0;

    for (let i = index; i > 0; i -= i & -i) {
      sum += this.tree[i];
    }

    return sum;
  }
}

class Solution:
    def resultArray(self, nums: List[int]) -> List[int]:
        arr1 = [nums[0]]
        arr2 = [nums[1]]
        n = len(nums)
        for i in range (2, n):
            if arr1[-1] > arr2[-1]:
                arr1.append(nums[i])
            else:
                arr2.append(nums[i])
        
        return arr1 + arr2

func resultArray(nums []int) []int {
    arr1 := make([]int, 0)
    arr2 := make([]int, 0)
    arr1 = append(arr1, nums[0])
    arr2 = append(arr2, nums[1])
    for i := 2; i < len(nums); i++ {
        if arr1[len(arr1) - 1] > arr2[len(arr2) - 1] {
            arr1 = append(arr1, nums[i])
        } else {
            arr2 = append(arr2, nums[i])
        }
    }
    arr1 = append(arr1, arr2...)
    return arr1
}

impl Solution {
      pub fn result_array(nums: Vec<i32>) -> Vec<i32> {
          let n = nums.len();
          let mut res = vec![0; n];
          let (mut lo, mut hi) = (0, n - 1);
          res[0] = nums[0];
          res[hi] = nums[1];
          for &x in &nums[2..] {
              let g = (res[hi] > res[lo]) as usize;
              hi -= g;
              lo += 1 - g;
              res[g * hi + (1 - g) * lo] = x;
          }   
          res[hi..].reverse();
          res
      }   
  }

class Solution {
    public:
        std::vector<int> resultArray(const std::vector<int> &nums) {
            const int n = nums.size();
            if (n == 2) return nums;
            std::vector<int> arr1{nums[0]}, arr2{nums[1]};
            int a = 0, b = 1, c = 2;
            while (c < n) {
                if (nums[a] > nums[b]) {
                    arr1.push_back(nums[c]);
                    a = c++;
                }
                else {
                    arr2.push_back(nums[c]);
                    b = c++;
                }
            }
            arr1.insert(arr1.end(), arr2.begin(), arr2.end());
            return arr1;
        }
};

class FenwickTree {
    public:
        FenwickTree(const int n) : n(n), tree(n + 1) {};

        void update(int i) {
            while (i < n + 1) {
                ++tree[i];
                i += i & -i;
            }
        }

        int query(int i) {
            int a = 0;
            while (i > 0) {
                a += tree[i];
                i -= i & -i;
            }
            return a;
        }

    private:
        const int n;
        std::vector<int> tree;
};

class Solution {
    public:
        std::vector<int> resultArray(const std::vector<int> &nums) {
            const int n = nums.size();
            if (n == 2) return nums;

            const std::set<int> s(nums.begin(), nums.end());
            std::vector<int> t(s.begin(), s.end()), arr1 = {nums[0]}, arr2 = {nums[1]};

            std::unordered_map<int, int> map;
            map.reserve(t.size());
            for (int i = 0; i < t.size(); ++i) {
                map[t[i]] = i + 1;
            }

            FenwickTree a1(t.size());
            FenwickTree a2(t.size());
            a1.update(map[nums[0]]);
            a2.update(map[nums[1]]);

            for (int i = 2; i < n; ++i) {
                const int &tmp = map[nums[i]];
                const int a = arr1.size() - a1.query(tmp), b = arr2.size() - a2.query(tmp);

                if (a > b) {
                    arr1.push_back(nums[i]);
                    a1.update(tmp);
                }
                else if (a < b) {
                    arr2.push_back(nums[i]);
                    a2.update(tmp);
                }
                else if (arr1.size() > arr2.size()) {
                    arr2.push_back(nums[i]);
                    a2.update(tmp);
                }
                else {
                    arr1.push_back(nums[i]);
                    a1.update(tmp);
                }
            }

            arr1.insert(arr1.end(), arr2.begin(), arr2.end());
            return arr1;
        }
};