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

class Solution {
    public:
        int stoneGameVIII(std::vector<int> &stones) {
            const int n = stones.size();
            for (int i = 1; i < n; ++i) {
                stones[i] += stones[i - 1];
            }

            int a = stones[n - 1];
            for (int i = n - 2; i > 0; --i) {
                a = std::max(a, stones[i] - a);
            }

            return a;
        }
};

function missingMultiple(nums: number[], k: number): number {
    const set = new Set(nums);
    let i = 1;
    while (true) {
        if (!set.has(k * i)) return k * i;
        i++
    }
    return -1;
};

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        set_n = set(nums)
        mul = 1
        while True:
            tmp = k * mul
            if tmp not in set_n:
                return tmp
            mul += 1

class Solution {
    public:
        int missingMultiple(std::vector<int> &nums, const int &k) {
            std::sort(nums.begin(), nums.end());
            int a = 0;

            for (const int &i: nums) {
                const int b = i / k;
                if (i % k != 0 || b == a) continue;
                if (b != a + 1) {
                    return (a + 1) * k;
                }
                a = b;
            }
            return (a + 1) * k;
        }
};

missingMultiple=f=(n,k,m=k)=>~n.indexOf(m)?f(n,k,m+k):m

missingMultiple=f=(n,k,m=k)=>(new Set(n)).has(m)?f(n,k,m+k):m;

impl Solution {
    pub fn missing_multiple(n: Vec<i32>, k: i32) -> i32 {
        let mut m = k;
        while n.contains(&m) { m+=k }
        m
    }
}

// Thấy hay nên để link tham khảo https://leetcode.com/problems/smallest-missing-multiple-of-k/solutions/8480901/solution-by-la_castille-vw2a/

func missingMultiple(nums []int, k int) int {
    mapNums := make(map[int]struct{}, len(nums))
    for _, num := range nums {
        mapNums[num] = struct{}{}
    }
    i := 1
    for {
        if _, ok := mapNums[k*i]; !ok {
            return k * i
        }
        i++
    }
}

public int missingMultiple(int[] nums, int k) {
Set existSet = new HashSet();
for (int num : nums) {
        existSet.add(num);
    }
int i = 1;
while (true) {
 if (!existSet.contains(k * i)){
 return k * i;
        }
        i++;
    }
}

class Solution {
    public:
        std::string shortestBeautifulSubstring(const std::string &s, const int &k) {
            int l = 0, r = 0, a = 0;
            std::string_view t;
            const char *p = &s[0];

            while (r < s.size()) {
                if (s[r] == '1') ++a;

                while (a > k || s[l] == '0') {
                    if (l == r) break;
                    if (s[l] == '1') --a;
                    ++l;
                }

                ++r;
                if (a == k) {
                    std::string_view b(p + l, r - l);
                    if (t == "" || b.size() < t.size() || b.size() == t.size() && b < t) t = b;
                }

            }

            return std::string(t);
        }
};

function shortestBeautifulSubstring(s: string, k: number): string {
    let l = 0;
    let count = 0;
    let res = '';

    for (let r = 0; r < s.length; r++) {
        if (s[r] === '1') count++;

        while (count > k) {
            if (s[l] === '1') count--;
            l++;
        }

        while (count === k && s[l] === '0') {
            l++;
        }

        if (count === k) {
            const cur = s.substring(l, r + 1);

            if (
                res === '' ||
                cur.length < res.length ||
                (cur.length === res.length && cur < res)
            ) {
                res = cur;
            }
        }
    }

    return res;
}

shortestBeautifulSubstring=(s,k,l='length',q='slice',o=[...s].flatMap((c,i)=>+c?i:[]))=>o[q](0,o[l]-k+1).reduce((r,_,p)=>
  (x=>!r||x[l]<r[l]||(x[l]==r[l]&&x<r)?x:r)(s[q](o[p],o[p+k-1]+1)),'')

shortestBeautifulSubstring=(s,k,q='slice',f='flatMap',o=[...s][f]((c,i)=>+c?i:[]))=>o[f]((v,p,a,x=s[q](v,a[p+k-1]+1))=>x?1e3+x.length+x:[]).sort()[0]?.[q](4)||''

impl Solution {
      pub fn shortest_beautiful_substring(s: String, mut k: i32) -> String {
          let b = s.as_bytes();
          let (mut c, mut best, mut st) = (0u128, 0u128, b.len());
          for i in 0..b.len() {
              let d = (b[i] == b'1') as u128;
              c = c << 1 | d;
              k -= d as i32;
              if k < 0 {
                  k = 0;
                  c &= (1u128 << (127 - c.leading_zeros())) - 1;
              }
              if k == 0 && (best == 0 || c < best) {
                  st = i + 1 - (128 - c.leading_zeros()) as usize;
                  best = c;
              }
          }
          if best == 0 { String::new() } else {
              s[st..st + (128 - best.leading_zeros()) as usize].to_string()
          }
      }
  }

class Solution:
    def shortestBeautifulSubstring(self, s: str, k: int) -> str:
        l_1 = [] # contains the index of '1' in the current window
        res = ""
        l_res = float(inf)
        count = 0
        for i in range(len(s)):
            if s[i] == '1':
                count += 1
                l_1.append(i)
                if count > k:
                    l_1.pop(0)
                    count = k
                
                curr_w = l_1[-1] - l_1[0] + 1
                if count == k and curr_w <= l_res:
                    if curr_w < l_res:
                        l_res = curr_w
                        res = s[l_1[0]:(l_1[-1] + 1)]
                    else:
                        tmp = s[l_1[0]:(l_1[-1] + 1)]
                        if tmp < res:
                            res = tmp
        
        return res

class Solution {
    public:
        std::string lexGreaterPermutation(const std::string &s, const std::string &target) {
            std::array<int, 26> a{0};
            for (char i: s) {
                ++a[i - 'a'];
            }

            std::string t;
            t.reserve(target.size());
            for (char i: target) {
                int tmp = i - 'a';
                if (a[tmp]) {
                    t.push_back(i);
                    --a[tmp];
                }
                else break;
            }

            if (t.size() < target.size()) {
                int tmp = target[t.size()] - 'a';
                for (int i = tmp + 1; i < 26; ++i) {
                    if (a[i]) {
                        t.push_back(i + 'a');
                        --a[i];
                        for (int j = 0; j < 26; ++j) {
                            t.append(a[j], j + 'a');
                        }
                        return t;
                    }
                }
            }

            while (t != "") {
                int b = t.back() - 'a';
                t.pop_back();
                ++a[b];

                int c = target[t.size()] - 'a';
                for (int i = c + 1; i < 26; ++i) {
                    if (a[i]) {
                        t.push_back(i + 'a');
                        --a[i];
                        for (int j = 0; j < 26; ++j) {
                            t.append(a[j], j + 'a');
                        }
                        return t;
                    }
                }
            }

            return "";
        }
};

class Solution {
    public:
        std::string lexPalindromicPermutation(const std::string &s, const std::string &target) {
            std::array<int, 26> a{0};
            for (char i: s) {
                ++a[i - 'a'];
            }

            int d = 0, e = -1;
            for (int i = 0; i < 26; ++i) {
                if (a[i] & 1) {
                    if (++d > 1) return "";
                    e = i;
                }
                a[i] /= 2;
            }

            const int h = s.size() / 2;
            std::string t;
            t.reserve(target.size());
            for (int i = 0; i < h; ++i) {
                int tmp = target[i] - 'a';
                if (a[tmp]) {
                    t.push_back(target[i]);
                    --a[tmp];
                } else break;
            }

            auto palindrome = [&](const std::string &t) {
                std::string a = t;
                if (e > -1) a.push_back(char(e + 'a'));

                for (auto i = t.rbegin(); i != t.rend(); ++i) {
                    a.push_back(*i);
                }
                
                return a;
            };

            if (t.size() == h) {
                std::string tmp = palindrome(t);
                if (tmp > target) return tmp;
            } else {
                for (int i = target[t.size()] - 'a' + 1; i < 26; ++i) {
                    if (a[i]) {
                        t.push_back(i + 'a');
                        --a[i];

                        for (int j = 0; j < 26; ++j) {
                            t.append(a[j], j + 'a');
                        }

                        return palindrome(t);
                    }
                }
            }

            while (t != "") {
                int b = t.back() - 'a';
                t.pop_back();
                ++a[b];

                int c = target[t.size()] - 'a';
                for (int i = c + 1; i < 26; ++i) {
                    if (a[i]) {
                        t.push_back(i + 'a');
                        --a[i];
                        for (int j = 0; j < 26; ++j) {
                            t.append(a[j], j + 'a');
                        }
                        return palindrome(t);
                    }
                }
            }

            return "";
        }
};

func lexicographicallySmallestArray(nums []int, limit int) []int {
    tempNums := make([]int, len(nums))
    copy(tempNums, nums)
    slices.Sort(tempNums)
    groupMap := make(map[int][]int, 0)
    group := 0
    numToGroup := make(map[int]int, 0)
    groupMap[0] = make([]int, 0)
    groupMap[0] = append(groupMap[0], tempNums[0])
    numToGroup[tempNums[0]] = 0
    for i := 1; i < len(tempNums); i++ {
        if tempNums[i] - tempNums[i-1] >  limit {
            group++
            groupMap[group] = make([]int, 0)
        }
        numToGroup[tempNums[i]] = group
        groupMap[group] = append(groupMap[group], tempNums[i])
    }
    for i, num := range nums {
        groupIndex := numToGroup[num]
        group := groupMap[groupIndex]
        nums[i] = group[0]
        groupMap[groupIndex] = group[1:]
    }
    return nums
}

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
        a = sorted((b, i) for i, b in enumerate(nums))
        t = [0] * n
        l, r = 0, 1

        while l < n:
            while r < n and a[r][0] - a[r - 1][0] < limit + 1:
                r += 1
            tmp = sorted(k for _, k in a[l:r])
            for j, i in enumerate(tmp):
                t[i] = a[l + j][0]
            l = r
            r += 1
        
        return t

class Solution {
    public:
        int minimumDeletions(const std::vector<int> &nums) {
            const int n = nums.size();
            int a = 0, b = 0;

            for (int i = 0; i < n; ++i) {
                if (nums[i] < nums[a]) a = i;
                if (nums[i] > nums[b]) b = i;
            }

            if (a > b) std::swap(a, b);
            return std::min(std::min(b + 1, n - a), a + 1 + n - b);
        }
};

class Solution {
    public int minimumDeletions(int[] nums) {
        int n = nums.length;
        int minIdx = 0, maxIdx = 0;


        for (int i = 1; i < n; i++) {
            if (nums[minIdx] > nums[i]) {
                minIdx = i;
                continue;
            }
            if (nums[maxIdx] < nums[i]) {
                maxIdx = i;
            }
        }
        int left = Math.min(minIdx, maxIdx);
        int right = Math.max(minIdx, maxIdx);
        return Math.min(Math.min(right + 1, n - left), left + 1 + n - right);
    }
}