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

func maxMatrixSum(matrix [][]int) int64 {
    countNegative := 0
    minNumb := math.Abs(float64(matrix[0][0]))
    sum := 0

    for _, row := range matrix {
        for _, col := range row {
            if col < 0 {
                countNegative++
            }

            if math.Abs(float64(col)) < minNumb {
                minNumb = math.Abs(float64(col))
            }

            sum += int(math.Abs(float64(col)))
        }
    }

    if countNegative%2 == 0 {
        return int64(sum)
    }

    return int64(sum - (int(minNumb) * 2))
}

class Solution {
    public long maximumTotalDamage(int[] power) {
        Map<Integer, Integer> map = new HashMap();
        long ans = 0;
        for(int num:power){
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        long [][] dp = new long[map.size()][2];
        int index =0;
        for(Integer key:map.keySet()){
            dp[index][0]=key;
            dp[index][1]=map.get(key);
            index++;
        }
        Arrays.sort(dp,(a,b)->(int)a[0]-(int)b[0]);
        ans = dp[0][0] * dp[0][1];
        dp[0][1]= ans;
        int n =dp.length;
        if(n<2) return ans;
        long last=0;
        if(dp[1][0]>dp[0][0]+2){
            ans+= dp[1][0] *dp[1][1];
        } else{
            ans = Math.max(ans, dp[1][0] *dp[1][1]);
        } 
        dp[1][1]=ans;
        for(int i =2;i<dp.length;i++){
            long cur_dmg=dp[i][0]*dp[i][1];
            if(dp[i][0]>dp[i-1][0]+2){
               ans += cur_dmg; 
               last = dp[i-1][1];            
            }
            else if(dp[i][0]>dp[i-2][0]+2){
                ans =Math.max(dp[i-2][1]+cur_dmg, dp[i-1][1]);
                last = dp[i-2][1];  
            }
            else{
                ans=Math.max(last+cur_dmg,Math.max(dp[i-1][1],dp[i-2][1]));
                last = dp[i-2][1];
            }
            
            dp[i][1] = ans;
        }
        return ans;
       
    }
}

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        freq = defaultdict(int)
        for item in power:
            freq[item] += 1
        
        powers = sorted(freq.keys())
        n = len(powers)
        
        @lru_cache(None)
        def go(index):
            if index >= n:
                return 0
            
            cast = powers[index] * freq[powers[index]] 
            if index + 1 < n and powers[index + 1] > powers[index] + 2:
                cast += go(index + 1)
            elif index + 2 < n and powers[index + 2] > powers[index] + 2:
                cast += go(index + 2)
            else:
                cast += go(index + 3)
            
            notCast = go(index + 1)
            
            return max(cast, notCast)
        
        return go(0)

class Solution {
    public long maxMatrixSum(int[][] matrix) {
        int negativeCount = 0;
        long sum = 0;
        int min = 100000;
        for (int i =0;i<matrix.length;i++){
            for (int j = 0;j<matrix[0].length;j++){
                int abs = Math.abs(matrix[i][j]);
                sum+=abs;
                min = Math.min(min,abs);
                if(matrix[i][j]<0)
                    negativeCount++;
            }
        }
        return negativeCount%2==0?sum:sum-2*min;
    }
}

class Solution:
    def maximumTotalCost(self, nums: List[int]) -> int:
        @cache
        def f(i, sign):
            if i >= len(nums):
                return 0
            r1 = sign * nums[i] + f(i+1, -sign)
            r2 = nums[i] + f(i+1, -1)
            return max(r1, r2)

        return f(0, 1)

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        arr = [num % k for num in nums]
        
        remains = defaultdict(list)
        for i in range(len(arr)):
            remains[arr[i]].append(i)
        
        dp = [[1] * k for _ in range(len(arr))]
        res = -inf

        for i in range(len(arr)):
            r = arr[i] % k
            for j in range(k):
                if j >= r:
                    needed = j - r
                else:
                    needed = k + j - r
                
                remain_list = remains[needed]
                if not remain_list:
                    continue
                idx = bisect_left(remain_list, i)
                idx -= 1
                if idx < 0:
                    continue

                dp[i][j] = 1 + dp[remain_list[idx]][j]
                res = max(res, dp[i][j])

        return res

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        m = len(board)
        n = len(board[0])
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        def hash(board):
            currentHash = ""
            for i in range(m):
                for j in range(n):
                    currentHash += str(board[i][j])

            return currentHash

        queue = deque()
        currentHash = hash(board)
        for i in range(m):
            for j in range(n):
                if board[i][j] == 0:
                    queue.append((i, j, board, currentHash, 0))

        visited = set()
        visited.add(currentHash)
        while queue:
            r,c, currentBoard, hashedBoard, steps = queue.popleft()
            if hashedBoard == "123450":
                return steps

            for dx, dy in directions:
                nx = r + dx
                ny = c + dy
                if 0 <= nx < m and 0 <= ny < n:
                    currentBoard[r][c], currentBoard[nx][ny] = currentBoard[nx][ny], currentBoard[r][c]
                    hashes = hash(currentBoard)
                    if hashes not in visited:
                        visited.add(hashes)
                        queue.append((nx, ny, copy.deepcopy(currentBoard), hashes, steps + 1))

                    currentBoard[r][c], currentBoard[nx][ny] = currentBoard[nx][ny], currentBoard[r][c]

        return -1

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        def boardToTuple(b):
            return (tuple(b[0]), tuple(b[1]))
        target = ((1,2,3), (4,5,0))
        if boardToTuple(board) == target:
            return 0

        idx, idy = 0, 0
        for i in range(2):
            for j in range(3):
                if board[i][j] == 0:
                    idx, idy = i, j
                    break

        existed = set(boardToTuple(board))
        q = deque([(idx, idy, board)])
        result = 0
        while q:
            n = len(q)
            result += 1
            for _ in range(n):
                u, v, temp = q.popleft()
                if u - 1 >= 0:
                    temp[u][v], temp[u - 1][v] = temp[u - 1][v], temp[u][v]
                    nextTup = boardToTuple(temp)
                    if nextTup == target:
                        return result
                    if nextTup not in existed:
                        existed.add(nextTup)
                        q.append((u-1, v, copy.deepcopy(temp) ))
                    temp[u][v], temp[u - 1][v] = temp[u - 1][v], temp[u][v]
                
                if u + 1 < 2:
                    temp[u][v], temp[u + 1][v] = temp[u + 1][v], temp[u][v]
                    nextTup = boardToTuple(temp)
                    if nextTup == target:
                        return result
                    if nextTup not in existed:
                        existed.add(nextTup)
                        q.append((u+1, v, copy.deepcopy(temp) ) )
                    temp[u][v], temp[u + 1][v] = temp[u + 1][v], temp[u][v]
                if v - 1 >= 0:
                    temp[u][v - 1], temp[u][v] = temp[u][v], temp[u][v - 1]
                    nextTup = boardToTuple(temp)
                    if nextTup == target:
                        return result
                    if nextTup not in existed:
                        existed.add(nextTup)
                        q.append((u, v - 1, copy.deepcopy(temp)))
                    temp[u][v - 1], temp[u][v] = temp[u][v], temp[u][v - 1]
                if v + 1 < 3:
                    temp[u][v + 1], temp[u][v] = temp[u][v], temp[u][v + 1]
                    nextTup = boardToTuple(temp)
                    if nextTup == target:
                        return result
                    if nextTup not in existed:
                        existed.add(nextTup)
                        q.append((u, v + 1, copy.deepcopy(temp) ))
                    temp[u][v + 1], temp[u][v] = temp[u][v], temp[u][v + 1]
        return -1

class Solution {
    public String hash(int[][] board) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                str.append(board[i][j]);
            }
        }

        return str.toString();
    }

    public int slidingPuzzle(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

        Deque<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();

        int steps = 0;
        String start = hash(board);
        visited.add(start);
        queue.offerLast(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                String hashedBoard = queue.pollFirst();

                if (hashedBoard.equals("123450")) {
                    return steps;
                }

                int zero = hashedBoard.indexOf('0');
                for (int[] dir : directions) {
                    int newRow = zero / 3 + dir[0], newCol = zero % 3 + dir[1];
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                        int newIndex = newRow * 3 + newCol;
                        StringBuilder sb = new StringBuilder(hashedBoard);
                        sb.setCharAt(zero, sb.charAt(newIndex));
                        sb.setCharAt(newIndex, '0');

                        String newHashed = sb.toString();
                        if (!visited.contains(newHashed)) {
                            visited.add(newHashed);
                            queue.offerLast(newHashed);
                        }
                    }
                }
                size--;
            }
            steps++;
        }

        return -1;
    }
}

class Solution {
    static Map<String, Integer> hm = new HashMap<>(Map.of("[[1,2,3],[4,0,5]]", 1, "[[4,1,2],[5,0,3]]", 5
    , "[[3,2,4],[1,5,0]]", 14, "[[3,0,1],[2,4,5]]", 14, "[[4,3,5],[2,1,0]]", 8, "[[1,2,3],[4,5,0]]", 0
    , "[[2,3,5],[1,4,0]]", 6, "[[3,0,5],[4,2,1]]", 12, "[[3,0,1],[4,5,2]]", 12, "[[0,4,1],[2,5,3]]", 9));
    { hm.put("[[5,3,2],[0,4,1]]", 18); hm.put("[[3,1,0],[2,4,5]]", 13); hm.put("[[1,4,3],[5,2,0]]", 14);
      hm.put("[[4,2,0],[5,1,3]]", 7); hm.put("[[0,5,2],[4,3,1]]", 15); hm.put("[[2,4,1],[5,3,0]]", 12);
      hm.put("[[1,3,4],[0,2,5]]", 14);
    }

    public int slidingPuzzle(int[][] board) {
        return Optional.ofNullable(hm.get(Arrays.deepToString(board).replaceAll(" ",""))).orElse(-1);
    }
}

var slidingPuzzle = function (board) {
    const mask = 7;
    const neighbors = {
        0: [1, 3],
        1: [0, 2, 4],
        2: [1, 5],
        3: [0, 4],
        4: [1, 3, 5],
        5: [2, 4],
    };
    const expected = 1 | 2 << 3 | 3 << 6 | 4 << 9 | 5 << 12;
    const enqueued = [];
    function* next(n, zi) {
        for (const m of neighbors[zi]) {
            const k = (n >> (3 * m)) & mask;
            yield [n & (~(mask << (3 * m))) | (k << (zi * 3)), m];
        }
    };
    let n = 0, zi = 0, ans = 0;
    let q = new Queue(), nextq = new Queue();
    for (const [i, m] of board.flat().reverse().entries()) {
        n = n << 3 | m;
        if (!m) {
            zi = 5 - i;
        }
    }
    q.enqueue([n, zi]);
    while (true) {
        while (!q.isEmpty()) {
            const [n, zi] = q.dequeue();
            if (n === expected) {
                return ans;
            }
            for (const [n2, zi2] of next(n, zi)) {
                if (!enqueued[n2]) {
                    enqueued[n2] = true;
                    nextq.enqueue([n2, zi2]);
                }
            }
        }
        if (nextq.isEmpty()) {
            break;
        }
        ans++;
        [q, nextq] = [nextq, new Queue()];
    }
    return -1;
};

class Solution {
    public int slidingPuzzle(int[][] board) {
        int W = board[0].length;
        int H = board.length;
        Set<String> visited = new HashSet();
        Queue<String> q = new LinkedList<>();
        q.add(toString(board));
        int step=0;
        int[][] cur =new int[H][W];
        String target ="123450";
        while(!q.isEmpty()){
            int len = q.size();
            for(int k =0 ; k < len;k++){
                String cur_state = q.poll();
                
                if(cur_state.equals(target)) return step;
                paste(cur, cur_state);
                int i=0;
                int j =0;
                for(int pos = 0;pos <cur_state.length();pos++){
                    if(cur_state.charAt(pos)=='0') {
                        i = pos/W;
                        j = pos%W;
                        break;
                    }
                }
                //swap left
                if(i>0){
                    int temp = cur[i][j];
                    cur[i][j]= cur[i-1][j];
                    cur[i-1][j]=temp;
                    String state =toString(cur);
                    if(!visited.contains(state)){
                        visited.add(state);
                        q.add(state);
                    }
                    paste(cur, cur_state);
                }
                //swap right
                if(i<H-1){
                    int temp = cur[i][j];
                    cur[i][j]= cur[i+1][j];
                    cur[i+1][j]=temp;
                    String state = toString(cur);
                    if(!visited.contains(state)){
                        visited.add(state);
                        q.add(state);
                    }
                    paste(cur, cur_state);
                }
                //swap up
                if(j>0){
                     int temp = cur[i][j];
                    cur[i][j]= cur[i][j-1];
                    cur[i][j-1]=temp;
                    String state = toString(cur);
                    if(!visited.contains(state)){
                        visited.add(state);
                        q.add(state);
                    }
                    paste(cur, cur_state);
                }
                //swap down
                if(j<W-1){
                     int temp = cur[i][j];
                    cur[i][j]= cur[i][j+1];
                    cur[i][j+1]=temp;
                    String state = toString(cur);
                    if(!visited.contains(state)){
                        visited.add(state);
                        q.add(state);
                    }
                    paste(cur, cur_state);
                }
            }
            step++;
        }
        return -1;
    }
    public String toString(int[][] board){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < board.length; i++) {
            for(int j =0 ; j < board[0].length;j++){
                sb.append(board[i][j]);
            }
        }
        return sb.toString();
    }
    public void paste(int[][] board, String val) {
        for (int i = 0; i < board.length; i++) {
            for(int j =0 ; j < board[0].length;j++){
                board[i][j] = val.charAt(i*board[0].length+j)-'0';
            }
        }
    }
}

class Solution:
    def maximumTotalCost(self, nums: List[int]) -> int:
        n = len(nums)
        @lru_cache(None, False)
        def go(operation, index):
            if index == n:
                return 0
           
            gain = operation*nums[index]
            notSplit = go(operation*(-1), index + 1)
            split = go(1, index + 1)
            return max(notSplit, split) + gain
       
        return go(1, 0)