leetcode note (23/01/01)

wonderful world·2022년 10월 30일

kind	level	title	note
DP	medium	longest-increasing-subsequence	WIP
DP?	medium	4Sum II	WIP. O(n^4)?
DP	medium	subarray-sum-equals-k	WIP
DP	medium	jump game II	WIP
DP	easy	counting bits	dp[n]=dp[n//2]+n%2
greedy	medium	increasing triplet subsequence	WIP
backtracking	medium	combination sum	no backtracking but recursion
linked list	hard	merge-k-sorted-lists	node->list, use sorted, list->node. complexity?
?	medium	permutation-in-string	WIP
stack	medium	remove k digits	stack? but recursion with subproblems
math?	medium	maximum split of positive even integers	make a increasing numbers for target sum
fenwick tree	hard	count good triplets in an array	WIP, fenwick tree
gcd	hard	count array pairs divisible by k	WIP.
hashtable	medium	construct string with repeat limit	decrease value until hashmap not empty
hashtable	medium	subarray sum equals k	WIP
graph,dfs	medium	clone graph	dfs with maintaining visited
binary search	medium	minimum time to complete trips	no equation!, just do binary search over time `t`. that's it.
bfs	medium	maximum width of binary tree	bfs with node numbering for width
greedy?	medium	delete and earn	wip
?	medium	append K integers with minimal sum	WIP
hashtable	medium	count-artifacts-that-can-be-extracted	using `all` and set exists
greedy	medium	remove duplicate letters	WIP
greedy	medium	maximize-number-of-subsequences-in-a-string	biweekly-contest-74, count < in two arrays
?	medium	find-palindrome-with-fixed-length	WIP, weekly-contest-286
binary search	hard	split array largest sum	l,r 을 max(nums), sum(nums) 로 설정
?	medium	number of ways to select buildings	WIP
?	hard	encrypt and decrypt strings	WIP, weekly-contest-287
heap	easy	kth largest element in a stream	heapq
heap	medium	maximum product after k increments	using heapq.heappop(), heappush()
prefix sum	medium	maximum trailing zeros in a cornered path	WIP, 구간합
DP	easy	maximum subarray	DP basic
kruskal	medium	min cost to connect all points	graph, minimum spanning tree, WIP
union find	medium	smallest-string-with-swaps	WIP
BFS, union find	medium	is graph bipartite	PASS but repeat yourself
BFS, union find, floyd warshall	medium	evaluate division	WIP, repeat yourself
stack	medium	remove all adjacent duplicates in string II	Timelimit, repeat yourself
tree	medium	count-nodes-equal-to-average-of-subtree	다르게 풀기, 파마리터 쓰지않고 반환값으로 축적
DP	medium	count-number-of-texts	WIP
DP	medium	count sorted vowel strings	WIP 데일리릿코드
heap	medium	network delay time	WIP heappush, heappop
math, bit	medium	largest combination with bitwise and greater than zero	WIP, 제약사항에서 24bit 로 표현됨을 파악.
DP	medium	coin change	점화식. DP[n]
DP	medium	ones and zeros	memo:(index, zeros,ones), best=max(best, go(i+1,zs,os)+1)
sliding window	medium	minimum-operations-to-reduce-x-to-zero	WIP, daily/06/11
hashtable	medium	match substring after replacement	OK. cache twice
bisect,binary search	medium	successful pairs of speels and potions	OK. bisect.bisect_right() instead of BN
DP	medium	triangle	OK. memo[(row,col)] = min_value
sliding window, greedy?	medium	Longest Binary Subsequence Less Than or Equal to K	DP 적용 불가? it doesn't say continuous subsequence so it can't be DP. i realize it a bit too late as well
DP	medium	count-number-of-ways-to-place-houses	WIP, dp[i][k] += dp[i - 1][j]
union find, count pair	medium	count unreachble pairs of nodes in an undirected graph	WIP, ufind, count pair: `total += counts[k] * (N - (counts[k]))`
binary indexed tree	medium	range sum query	WIP
?	medium	count number of bad pairs	WIP
dfs	medium	reachable nodes with restrictions	solved but need to practice
greedy	medium	longest ideal subsequence	WIP
combinatorics	medium	construct smallest from di string	OK. itertools.permatations
modulo divide, combinatorics	medium?	긴 케이크 나눠주기	LGE 코드잼 B번문제. modulo 연산의 성질 divide
bit	medium	bitwise-xor-of-all-pairings	WIP
bit	medium	minimize xor	WIP
sliding window	hard	2444. Count Subarrays With Fixed Bounds	wip
sort	medium	2453. destroy sequential targets	tuple sort
binary search	hard	2454. next greater element IV	wip
graph, dfs	medium	most-profitable-path-in-a-tree	WIP
deque	easy	number-of-distinct-averages	deque.popleft(), pop() for min, max after sort
math	medium	6279. distinct prime factors of product of array	WIP. too much time to solve
greedy	2522. Partition string into substrings with values at most K	WIP. see the solution

favorite contestants
https://leetcode.com/superluminal/
https://leetcode.com/veraci/ https://leetcode.com/contest/weekly-contest-283/
https://leetcode.com/numb3r5/ https://leetcode.com/contest/biweekly-contest-72/
https://leetcode.com/wisest/ https://leetcode.com/contest/biweekly-contest-74
https://leetcode.com/LarryNY/ https://leetcode.com/contest/biweekly-contest-74
https://leetcode.com/Tlatoani kotlin user
https://leetcode.cn/lucifer1006
https://leetcode.cn/u/asdfasdfasdf123123/
https://leetcode.cn/u/shawnxi/
https://leetcode.com/nyu_ldf/

funny

[math] 6279. distinct prime factors of product of array

6279. distinct prime factors of product of array

by https://leetcode.com/nyu_ldf/

class Solution(object):
    def distinctPrimeFactors(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        m, a = [False] * 1001, 0
        for n in nums:
            i = 2
            while i * i <= n:
                while not n % i:
                    n, m[i] = n / i, True
                i += 1
            m[n] |= n > 1
        for v in m:
            a += 1 if v else 0
        return a

[greedy] 2522. Partition string into substrings with values at most K

2522. Partition string into substrings with values at most K
by https://leetcode.com/nyu_ldf/

class Solution(object):
    def minimumPartition(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """
        c, p = 0, 0
        for i in range(len(s)):
            if int(s[i]) > k:
                return -1
            p = p * 10 + int(s[i])
            if p > k:
                c, p = c + 1, int(s[i])
        return c + 1

[deque] number-of-distinct-averages

number-of-distinct-averages
by https://leetcode.com/LarryNY/

class Solution:
    def distinctAverages(self, nums: List[int]) -> int:
        nums.sort()
        q = collections.deque(nums)
        s = set()
        
        while len(q) > 0:
            s.add(q.popleft() + q.pop())
        return len(s)

[dfs] most profitable path in a tree

most-profitable-path-in-a-tree
by https://leetcode.com/LarryNY/

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        N = len(amount)
        e = collections.defaultdict(list)
        
        for u, v in edges:
            e[u].append(v)
            e[v].append(u)
        parent = [None] * N
        time = [None] * N
            
        def dfs(node, par, t):
            parent[node] = par
            time[node] = t
            for v in e[node]:
                if v != par:
                    dfs(v, node, t + 1)
        dfs(0, -1, 0)
        
        btime = [None] * N

        current = bob
        t = 0
        while current != 0:
            btime[current] = t
            if btime[current] < time[current]:
                amount[current] = 0
            elif btime[current] == time[current]:
                amount[current] //= 2
            current = parent[current]
            t += 1
            
        INF = 10** 20
        best = -INF
        def dfs2(node, par, current):
            down = 0
            for v in e[node]:
                if v != par:
                    dfs2(v, node, current + amount[v])
                    down += 1
            if down == 0:
                nonlocal best
                best = max(best, current)
                    
        dfs2(0, -1, amount[0])
        
        return best

[binary search] 2454. next greater element IV

https://leetcode.com/contest/biweekly-contest-90/problems/next-greater-element-iv/
by https://leetcode.cn/u/shawnxi/

class Solution:
    def secondGreaterElement(self, nums: List[int]) -> List[int]:
        
        from sortedcontainers import SortedList
        
        tmp = defaultdict(list)
        
        for idx,i in enumerate(nums):
            tmp[i].append(idx)
            
        q = SortedList()
        res = [-1]*len(nums)
        
        for k in sorted(tmp.keys(),reverse=True):
            for i in tmp[k]:
                idx = q.bisect_left(i)
                if idx+1<len(q):
                    res[i]=nums[q[idx+1]]
            for i in tmp[k]:
                q.add(i)
                
        return res

[sort] 2453. destroy sequential targets

https://leetcode.com/contest/biweekly-contest-90/problems/destroy-sequential-targets/
by https://leetcode.cn/u/shawnxi/

class Solution:
    def destroyTargets(self, nums: List[int], space: int) -> int:
        
        tmp = defaultdict(list)
        
        for i in nums:
            tmp[i%space].append(i)
            
        return sorted((-len(v),min(v)) for v in tmp.values())[0][1]

[sliding window] count-subarrays-with-fixed-bounds

https://leetcode.com/problems/count-subarrays-with-fixed-bounds/description/
by https://leetcode.cn/u/981377660LMT/

class Solution:
    def countSubarrays(self, nums: List[int], minK: int, maxK: int) -> int:
        n = len(nums)
        res, left = 0, 0
        pos1, pos2 = -1, -1
        for right in range(n):
            if nums[right] == minK:
                pos1 = right
            if nums[right] == maxK:
                pos2 = right
            if nums[right] < minK or nums[right] > maxK:
                left = right + 1
            res += max(0, min(pos1, pos2) - left + 1)

        return res

[bit] minimize xor

https://leetcode.com/contest/weekly-contest-313/problems/minimize-xor/
by https://leetcode.cn/u/asdfasdfasdf123123/

class Solution {
public:
    int minimizeXor(int num1, int num2) {
        int ans = 0;
        int cnt = __builtin_popcount(num2);
        for (int i = 30; i >= 0 && cnt; --i) {
            if (num1 & (1 << i)) {
                ans ^= (1 << i);
                --cnt;
            }
        }
        for (int i = 0; i <= 30 && cnt; ++i) {
            if (!(num1 & (1 << i))) {
                ans ^= (1 << i);
                --cnt;
            }
        }
        return ans;
    }
};

by larryny

def minimizeXor(num1, ,num2):
    count=0
    while num2>0:
        if num2&1==1:
            count+=1
        num2 >>= 1
    
    r=0
    omit..

[bit] bitwise xor of all pairings

by numb3r5
https://leetcode.com/contest/biweekly-contest-88/problems/bitwise-xor-of-all-pairings/

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        a = 0
        if len(nums2)%2:
            for i in nums1:
                a ^= i
        if len(nums1)%2:
            for i in nums2:
                a ^= i
        return a

[modulo property] LGE codejam B

https://leetcode.com/playground/hZNrJrpm
Albert는 길이가 $n$ 인 길다란 케이크를 구웠다. 이 케익은 $n$ 등분 할 수 있도록 총 $n$ 개의 칸으로 미리 나눠져있고, 일부 칸에는 과일 토핑이 올려져있다.

예를 들어 아래 그림은 $n = 8$ 인 케이크이고 $0$ 은 토핑이 없는 칸, $1$ 은 과일 토핑이 있는 칸을 나타낸다. 이를 정수 배열로 나타내면 $A = [0, 1, 1, 0, 0, 1, 1, 0]$ 로 표현할 수 있다. 구체적으로, $A[i]$ 는 $i$ 번째 칸에 토핑이 있으면 $1$ , 없으면 $0$ 이다.

Albert는 이 케이크를 정확히 $k-1$ 번 잘라 $k$ 개의 조각으로 나누고 싶은데, 아래 조건을 만족하도록 자르고 싶다:

조건 1: 각 케이크 조각에 포함된 토핑이 올라간 칸의 개수가 모두 동일해야한다.
조건 2: 버려지는 칸이나 조각이 생겨서는 안된다.
예를 들어 $k = 2$ 인 경우 버려지는 칸이나 조각 없이 위 케이크를 자를 수 있는 방법은 총 $7$ 가지 존재한다. 그 중 조건 1을 만족하는 경우는 아래와 같이 세 가지 방법이다. 각 케이크 조각에는 토핑이 올라간 칸이 두 개씩 있다.

다른 예로, 아래 그림은 $n = 5$ , $A = [0, 1, 0, 1, 0]$ , $k = 2$ 인 경우 위 조건들을 만족하면서 케이크를 자를 수 있는 두 가지 방법을 나타낸다.

입력으로 $n$ , $k$ , 그리고 토핑의 유무를 나타내는 배열 $A$ 가 주어졌을 때, 조건을 만족하며 케이크를 자를 수 있는 방법이 총 몇 가지 있는지 구해보자. 단, 답이 매우 클 수 있으므로 $10^9+7$ 로 나눈 나머지를 출력한다.

MAX = 10**9 + 7

def mod_inverse(b,m):
    g = math.gcd(b, m)
    if (g != 1): return -1
    return pow(b, m - 2, m)

def mod_divide(a,b,m):
    a = a % m
    inv = mod_inverse(b,m)
    if(inv == -1): return -1
    return (inv*a) % m
    
def ncr(n, r, limit=MAX):
    r = min(r, n-r)
    if r == 0: return 1
    res = 1
    for k in range(1,r+1):
        res = mod_divide(res*(n-k+1), k, limit)
    return res

% 모듈로 연산을 divide 에 적용 시 그냥 적용하면 안 됨!
nCr combination 갯수를 구할 때 그 값을 MAX(10^9+7) 이내로 표현할 때 최종 결과에 % MAX 하면 실제 기대 값과 다름.

[combinatorics] construct-smallest-number-from-di-string

https://leetcode.com/contest/weekly-contest-306/problems/construct-smallest-number-from-di-string/
by superluminal

from itertools import permutations
class Solution(object):
    def smallestNumber(self, pattern):
        """
        :type pattern: str
        :rtype: str
        """
        n = len(pattern) + 1
        for p in permutations(range(1, n+1), n):
            for i in xrange(n-1):
                if pattern[i] == 'I' and p[i] > p[i+1]:
                    break
                if pattern[i] == 'D' and p[i] < p[i+1]:
                    break
            else:
                return ''.join(str(v) for v in p)

[greedy] longest ideal subsequence

22/08/07 weekly contest
https://leetcode.com/contest/weekly-contest-305/problems/longest-ideal-subsequence/
by nume3r5

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        x = [ord(i)-97 for i in s]
        res = [0]*26
        for i in x:
            cur = 0
            for j in range(26):
                if abs(i-j) <= k:
                    cur = max(cur, res[j])
            cur += 1
            res[i] = max(res[i], cur)
        return max(res)

[dfs] reachable nodes with restrictions

22/08/07 weekly contest
https://leetcode.com/contest/weekly-contest-305/problems/reachable-nodes-with-restrictions/
by numb3r5

class Solution:
    def reachableNodes(self, n: int, e: List[List[int]], restricted: List[int]) -> int:
        edges = defaultdict(list)
        for i, j in e:
            edges[i].append(j)
            edges[j].append(i)
        seen = [False]*n
        ok = [True]*n
        for i in restricted:
            ok[i] = False
        def dfs(x):
            seen[x] = True
            for i in edges[x]:
                if not seen[i] and ok[i]:
                    dfs(i)
        dfs(0)
        return sum(seen)

[?] count number of bad pairs

https://leetcode.com/contest/biweekly-contest-84/problems/count-number-of-bad-pairs/
08/06 biweekly contest
by numb3r5

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        l = [nums[i]-i for i in range(len(nums))]
        d = defaultdict(int)
        res = 0
        for pos, i in enumerate(l):
            res += pos-d[i]
            d[i] += 1
        return res

by larryNY

class Solution:
    def countBadPairs(self, nums: List[int]) -> int:
        c = collections.Counter()
        total = 0
        matched = 0
        for i, x in enumerate(nums):
            matched += c[i - x]
            total += i
            c[i - x] += 1
        return total - matched

[union find, count pair] count-unreachable-pairs-of-nodes-in-an-undirected-graph

06/28 disjoint 셋을 구하기 위해 union find 알고리즘 적용. 구해진 disjoint 셋에서 조합가능한 pair 의 갯수를 찾는 문제로 해석
count unreachble pairs of nodes in an undirected graph
by https://leetcode.com/LarryNY/

class Solution:
    def countPairs(self, N: int, edges: List[List[int]]) -> int:
        parent = [i for i in range(N)]
        
        def ufind(x):
            if parent[x] != x:
                parent[x] = ufind(parent[x])
            return parent[x]
        
        def uunion(a, b):
            ua = ufind(a)
            ub = ufind(b)
            
            parent[ua] = ub
        
        for u, v in edges:
            uunion(u, v)
            
        counts = collections.Counter()
        for i in range(N):
            counts[ufind(i)] += 1
            
        total = 0
        for k in counts.keys():
            total += counts[k] * (N - (counts[k]))
        return total // 2

[sliding window] Longest Binary Subsequence Less Than or Equal to K

Longest Binary Subsequence Less Than or Equal to K
by https://leetcode.com/LarryNY/

    def longestSubsequence(self, s: str, k: int) -> int:
        s = s[::-1]
        N = len(s)
        
        best = s.count("0")
        current = 0
        for i in range(N):
            if s[i] == "1":
                current += (1 << i)

                if current > k:
                    break
                best += 1
        return best

subproblem 으로 나눌 수 있다고 생각하여 DP 를 생각했는데.. 적용불가??
아래는 DP 적용 전 recursive 형태

class Solution:
    def longestSubsequence(self, s: str, k: int) -> int:
        m2 = {}
        
        def lessthan(seq, k):
            nonlocal m2
            if seq in m2: return m2[seq]
            y = int(seq, 2) <= k
            m2[seq] = y
            return y
            
        def go(s, seq):
            if s == '' and seq == '': return 0
            if s == '': return len(seq) if lessthan(seq, k) else 0
                        
            ans = max(
                go(s[1:], seq+s[0]),
                go(s[1:], seq)
            )
            
            return ans
        return go(s, '')

TBD: 왜 DP 적용이 불가한지 정리할 것. 혹은 DP 적용가능함을 보일 것.

[bisect] successful pairs of speels and potions

by https://leetcode.com/wwwwodddd

class Solution:
    def successfulPairs(self, a: List[int], b: List[int], d: int) -> List[int]:
        b.sort()
        z = []
        for i in a:
            z.append(len(b) - bisect_left(b, (d + i - 1) // i))
        return z

[bit] largest combination with bitwise and greater than zero

https://leetcode.com/contest/weekly-contest-293/problems/largest-combination-with-bitwise-and-greater-than-zero/

각 비트마다 몇 개의 candidate 들이 1 이 되는 지를 세고 모든 비트에 대해 이 카운트 값이 가장 큰 수를 반환

by Tlatoani

class Solution {
    fun largestCombination(candidates: IntArray): Int {
        return (0 until 29).map { d -> candidates.count { it and (1 shl d) != 0 } }.max()!!
    }
}

by lucifer1006

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        ans = 0
        for i in range(30):
            ans = max(ans, len([c for c in candidates if (c & (1 << i)) > 0]))
        return ans

[DP] count-number-of-texts

https://leetcode.com/problems/count-number-of-texts/
by LarryNY

class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        MOD = 10 ** 9 + 7                
                
        N = len(pressedKeys)
        dp = [0] * (N + 1)
        dp[0] = 1
        for x in range(N):
            k = int(pressedKeys[x])
            dp[x + 1] = dp[x]
            
            c = 3
            if k == 7 or k == 9:
                c = 4
                
            for i in range(c - 1):
                if x - i - 1 < 0 or pressedKeys[x] != pressedKeys[x - i - 1]:
                    break
                dp[x + 1] += dp[x - i - 1]
            dp[x + 1] %= MOD
        #print(dp)
        return dp[N]

점화식 방식으로 DP 적용.

[tree] count-nodes-equal-to-average-of-subtree

https://leetcode.com/contest/weekly-contest-292/problems/count-nodes-equal-to-average-of-subtree/
by LarryNY

class Solution:
    def averageOfSubtree(self, root: Optional[TreeNode]) -> int:
        ans = 0         
        def go(node):
            if node is None:
                return (0, 0)
            
            left = go(node.left)
            right = go(node.right)
            
            total = left[0] + right[0] + node.val
            count = left[1] + right[1] + 1
            
            if total // count == node.val:
                #print(total, node.val, count)
                nonlocal ans
                ans += 1
                
            return (total, count)
                
        go(root)
        return ans

[prefix sum]

https://leetcode.com/contest/weekly-contest-289/problems/maximum-trailing-zeros-in-a-cornered-path/
by superluminal

class Solution(object):
    def maxTrailingZeros(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        a = grid
        m, n = len(a), len(a[0])
        def _top(c):
            r = [row[:] for row in c]
            for i in xrange(1, m):
                for j in xrange(n):
                    r[i][j] += r[i-1][j]
            return r
        def _left(c):
            r = [row[:] for row in c]
            for i in xrange(m):
                for j in xrange(1, n):
                    r[i][j] += r[i][j-1]
            return r
        def _best(c2, c5):
            t2 = _top(c2)
            l2 = _left(c2)
            t5 = _top(c5)
            l5 = _left(c5)
            r = 0
            for i in xrange(m):
                for j in xrange(n):
                    v2 = t2[i][j] + l2[i][j] - c2[i][j]
                    v5 = t5[i][j] + l5[i][j] - c5[i][j]
                    r = max(r, min(v2, v5))
            return r
        c2 = [[0]*n for _ in xrange(m)]
        c5 = [[0]*n for _ in xrange(m)]
        for i in xrange(m):
            for j in xrange(n):
                v = a[i][j]
                while v % 2 == 0:
                    c2[i][j] += 1
                    v //= 2
                while v % 5 == 0:
                    c5[i][j] += 1
                    v //= 5
        r = _best(c2, c5)
        for row in c2: row.reverse()
        for row in c5: row.reverse()
        r = max(r, _best(c2, c5))
        c2.reverse()
        c5.reverse()
        r = max(r, _best(c2, c5))
        for row in c2: row.reverse()
        for row in c5: row.reverse()
        r = max(r, _best(c2, c5))
        return r

prefix sum 참고: https://www.crocus.co.kr/843

[?] minimum rounds to complete all tasks

https://leetcode.com/contest/weekly-contest-289/problems/minimum-rounds-to-complete-all-tasks/
by superluminal
y = 3a + 2b 에서 MIN(a+b) 를 구하기? y 는 주어짐. a, b 는 마음대로 정할 수 있음.
y+2 / 3 ==> MIN(a+b)

from collections import Counter
class Solution(object):
    def minimumRounds(self, tasks):
        """
        :type tasks: List[int]
        :rtype: int
        """
        c = Counter(tasks)
        if min(c.itervalues()) < 2:
            return -1
        return sum((v+2)//3 for v in c.itervalues())

[heap] maximum product after k increments

https://leetcode.com/contest/weekly-contest-288/problems/maximum-product-after-k-increments/
by LarryNY

class Solution:
    def maximumProduct(self, nums: List[int], k: int) -> int:
        h = nums
        heapq.heapify(h)
        
        for _ in range(k):
            t = heapq.heappop(h)
            heapq.heappush(h, t + 1)
            
        MOD = 10 ** 9 + 7
        c = 1
        for x in h:
            c *= x
            c %= MOD
        return c

[hashtable] count-artifacts-that-can-be-extracted

https://leetcode.com/contest/weekly-contest-284/problems/count-artifacts-that-can-be-extracted/
by superluminal

class Solution(object):
    def digArtifacts(self, n, artifacts, dig):
        """
        :type n: int
        :type artifacts: List[List[int]]
        :type dig: List[List[int]]
        :rtype: int
        """
        ans = 0
        s = set((x, y) for x, y in dig)
        for r1, c1, r2, c2 in artifacts:
            if all((r, c) in s
                   for r in xrange(r1, r2+1)
                   for c in xrange(c1, c2+1)):
                ans += 1
        return ans

cells-in-a-range-on-an-excel-sheet

https://leetcode.com/contest/weekly-contest-283/problems/cells-in-a-range-on-an-excel-sheet/
by superluminal

class Solution(object):
    def cellsInRange(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        a, i, _, b, j = s
        s = [chr(x) for x in xrange(ord(a), ord(b)+1)]
        t = [chr(x) for x in xrange(ord(i), ord(j)+1)]
        return [x+y for x in s for y in t]

[?] append-k-integers-with-minimal-sum

https://leetcode.com/contest/weekly-contest-283/problems/append-k-integers-with-minimal-sum/
by https://leetcode.com/veraci/
why it works??

class Solution(object):
    def minimalKSum(self, A, K):
        ans = K * (K + 1) // 2
        level = K + 1
        for x in sorted(set(A)):
            if x < level:
                ans += level - x
                level += 1
        return ans

[greedy] maximumSubsequenceCount

https://leetcode.com/problems/maximize-number-of-subsequences-in-a-string/
https://leetcode.com/contest/biweekly-contest-74
by https://leetcode.com/LarryNY/

lass Solution:
    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
        nt = []
        
        for c in text:
            if c in pattern:
                nt.append(c)
                
        nt = "".join(nt)
        
        def go(s):
            total = 0
            seen = 0
            
            for c in s:
                if c == pattern[0]:
                    seen += 1
                else:
                    total += seen
            return total

        if pattern[0] == pattern[1]:
            x = len(nt) + 1
            return x * (x - 1) // 2
        
        return max(go(nt + pattern[1]), go(pattern[0] + nt))

[hashtable] divide-array-into-equal-pairs

https://leetcode.com/contest/biweekly-contest-74/problems/divide-array-into-equal-pairs/
by me and https://leetcode.com/numb3r5/
Incidentally same!

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        c = Counter(nums)
        return all([n%2==0 for n in c.values()])

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        c = Counter(nums)
        return all(i%2 == 0 for i in c.values())

[math] find-palindrome-with-fixed-length

https://leetcode.com/contest/weekly-contest-286/problems/find-palindrome-with-fixed-length/
by superluminal

class Solution(object):
    def kthPalindrome(self, queries, intLength):
        """
        :type queries: List[int]
        :type intLength: int
        :rtype: List[int]
        """
        k = (intLength + 1) // 2
        p = intLength % 2
        ans = []
        for v in queries:
            x = 10**(k-1) + v - 1
            if x >= 10**k:
                ans.append(-1)
                continue
            s = str(x)
            ans.append(int(s[:len(s)-p] + s[::-1]))
        return ans

2227. Encrypt and Decrypt Strings

https://leetcode.com/contest/weekly-contest-287/problems/encrypt-and-decrypt-strings/
by superluminal

class Encrypter:

    def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
        self.lookup = {}
        for k, v in zip(keys, values):
            self.lookup[k] = v
        self.dictionary = dictionary
        self.rlookup = collections.defaultdict(list)
        for word in self.dictionary:
            self.rlookup[self.encrypt(word)].append(word)
        

    def encrypt(self, word1: str) -> str:
        ans = []
        for c in word1:
            ans.append(self.lookup[c])
        return "".join(ans)

    def decrypt(self, word2: str) -> int:
        return len(self.rlookup[word2])

wonderful world

hello wirld

이전 포스트

xv6

다음 포스트