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

class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid[0].length;
        int[] maxRight = new int[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            int[] row = grid[i];
            int rightMost = -1;
            for (int j = 0; j < n; j++) {
                if (row[j] == 1) {
                    rightMost = j;
                }
            }
            maxRight[i] = rightMost;
        }


        for (int i = 0; i < n - 1; i++) {
            int target = -1;

            for (int j = i; j < n; j++) {
                if (maxRight[j] <= i) {
                    target = j;
                    break;
                }
            }

            if (target == -1) return -1;

            while (target > i) {
                int temp = maxRight[target];
                maxRight[target] = maxRight[target - 1];
                maxRight[target - 1] = temp;
                count++;
                target--;
            }
        }

        return count;
    }
}

func minSwaps(grid [][]int) int {
    n:=len(grid)
    arr :=[]int{}
    for _,row:= range grid{
        cnt:=0
        for i:=n-1;i>0;i--{
            if row[i]==1{
                break;
            }
            cnt++;
        }
        arr = append(arr, cnt)
    }
    steps := 0
    for i := 0; i < n; i++ {
        need := n - 1 - i 
        j := i
        for j < n && arr[j] < need {
            j++
        }
        if j == n {
            return -1
        }

        for j > i {
            arr[j], arr[j-1] = arr[j-1], arr[j]
            j--
            steps++
        }
    }
    return steps
}

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        arr = ['0']
        def convert(s):
            new_s = ""
            for c in s:
                new_s += '1' if c == '0' else '0'
            return new_s[::-1]

        for i in range(1 , n + 1):
            arr.append(arr[i - 1] + '1' + convert(arr[i - 1]))
        
        return arr[n][k - 1]

class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        if n == 1:
            return "0"
        length = (1 << n) - 1

        mid = (length + 1) // 2
        if k < mid:
            return self.findKthBit(n-1,k)

        elif k == mid:
            return "1"
        
        else:
            mirror = self.findKthBit(n - 1, length - k + 1)
            return "1" if mirror == "0" else "0"

public class Solution
{
    public char FindKthBit(int n, int k)
    {

        bool Find(int n,int k)
        {
            if (n == 1)
                return false;
            int size = (1 << n) - 1;
            int mid = size / 2 + 1;
            if (k == mid)
                return true;
            if (k > mid)
                return !Find(n-1, size-k+1);
            return Find(n - 1, k);
        }
        return Find(n, k) ? '1' : '0';


    }
}

class Solution {
    public char findKthBit(int n, int k) {
        StringBuilder sb = new StringBuilder("0");

        for (int i = 1; i < n && sb.length() < k; i++) {
            String curr = sb.toString();
            
            sb.append("1");
            
            StringBuilder next = new StringBuilder(curr);
            invert(next);
            next.reverse();
            
            sb.append(next);
        }

        return sb.charAt(k - 1);
    }

    private void invert(StringBuilder sb) {
        for (int i = 0; i < sb.length(); i++) {
            sb.setCharAt(i, sb.charAt(i) == '0' ? '1' : '0');
        }
    }
}

func findKthBit(n int, k int) byte {
     if n == 1 {
        return '0'
    }
    mid := 1 << (n - 1)
    if k == mid {
        return '1'
    }
    if k<mid{
        return findKthBit(n-1,k)
    }

    return byte('1'-findKthBit(n-1,mid*2-k)+'0')
}

public class Solution
{
    public int NumSpecial(int[][] mat)
    {
        int n=mat.Length;
        int m=mat[0].Length;
        int[] row = new int[n];
        int[] col = new int[m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                row[i] += mat[i][j];
                col[j] += mat[i][j];
            }
        int count = 0;
        for(int i=0;i<n;i++)
            for (int j = 0; j < m; j++)
            {
                if (row[i] == 1 && col[j] == 1 && mat[i][j] == 1)
                    count++;
            }
        return count;

    }
}

class Solution {
    public int numSpecial(int[][] mat) {
        int res = 0, m = mat.length, n = mat[0].length;
        int[][] mem1 = new int[m][n];

        for (int i = 0; i < m; i++) {
            boolean exist = false;
            int idx = -1;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    if (!exist) {
                        idx = j;
                        exist = true;
                    } else {
                        exist = false;
                        break;
                    }
                }
            }
            if (exist) {
                mem1[i][idx] = 1;
            }
        }

        int[][] mem2 = new int[m][n];

        for (int j = 0; j < n; j++) {
            boolean exist = false;
            int idx = -1;
            for (int i = 0; i < m; i++) {
                if (mat[i][j] == 1) {
                    if (!exist) {
                        idx = i;
                        exist = true;
                    } else {
                        exist = false;
                        break;
                    }
                }
            }
            if (exist) {
                mem2[idx][j] = 1;
            }
        }

        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m; i++) {
                if (mem1[i][j] == 1 & mem2[i][j] == 1) {
                    res++;
                }
            }
        }

        return res;
    }
}

class Solution {
    public int numSpecial(int[][] mat) {
        int res = 0, m = mat.length, n = mat[0].length;
        int[] sumRow = new int[m];
        int[] sumCol = new int[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sumRow[i] += mat[i][j];
                sumCol[j] += mat[i][j];
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (sumRow[i] == 1 && sumCol[j] == 1 && mat[i][j] == 1)
                    res++;
            }
        }

        return res;
    }
}

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        rows = [0]*m
        cols = [0]*n
        for i in range(m):
            for j in range(n):
                rows[i] += mat[i][j]
                cols[j] += mat[i][j]

        specialCells = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1 and rows[i] == 1 and cols[j] == 1:
                    specialCells += 1
        
        return specialCells

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        m , n = len(mat) , len(mat[0])
        def check(i , j):
            for k in range(m):
                if k != i and mat[k][j] == 1: return False
            
            for k in range(n):
                if k != j and mat[i][k] == 1: return False
            
            return True
        
        res = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    if check(i , j): res += 1
                
        return res

class Solution {
    public int numSpecial(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int result = 0;
        int[] sumOnRow = new int[m];
        int[] sumOnCol = new int[n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                sumOnRow[r] += mat[r][c];
                sumOnCol[c] += mat[r][c];
            }
        }

        for (int r = 0; r < m; r++) {
            if (sumOnRow[r] != 1) continue;
            for (int c = 0; c < n; c++) {
                if (mat[r][c] == 1) {
                    if (sumOnCol[c] == 1) {
                        result++;
                    }
                    break;
                }
            }
        }
        return result;
    }
}

func numSpecial(mat [][]int) int {
    m:=len(mat)
    n:=len(mat[0])
    rows:= make([]int, m)
    cols:=make([]int,n)
    for i,row:=range mat{
        for j,num:=range row{
            if num==1{
                rows[i]++;
                cols[j]++
            }
        }
    }
    res:=0
    for i,row:=range mat{
        for j,num:=range row{
            if num == 1 && rows[i] == 1 && cols[j] == 1 {
                res++
            }
        }
    }
    return res;
}

class Solution {
    public int minOperations(String s) {
        int cnt = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != (i % 2 == 0 ? '0' : '1'))
                cnt++;
        }

        return Math.min(cnt, n - cnt);
    }
}

func minOperations(s string) int {
    res := len(s)

    count := func(startNum int) int {
        num, cnt := startNum, 0
        for _, c := range s {
            if int(c-'0') != num {
                cnt++
            }
            num = 1 - num
        }
        return cnt
    }

    res = min(res, count(0))
    res = min(res, count(1))
    return res
}

public class Solution
{
    public int MinOperations(string s)
    {
        int rtn = 0;
        int n = s.Length;
        for (int i = 0; i < n; i++)
        {
            if (i % 2 == s[i] - '0')
                rtn++;
        }
        return Math.Min(rtn,n-rtn);
    }
}

class Solution:
    def minOperations(self, s: str) -> int:
        def go(start):
            ops = 0
            for char in s:
                if char != str(start):
                    ops += 1
                
                start = 1 - start

            return ops

        return min(go(0), go(1))

class Solution:
    def minOperations(self, s: str) -> int:
        length = len(s)
        count1 = 0 # start with '0'
        count2 = 0 # start with '1'
        for i in range(length):
            if i % 2 == 0:
                if s[i] == '0': #start with '1'
                    count2 += 1
                else: #start with '0'
                    count1 += 1
            else:
                if s[i] == '0':
                    count1 += 1
                else:
                    count2 += 1
        return min(count1, count2)