算法 之 矩阵的对角线问题

• 在处理矩阵的时候，有时候题目就喜欢考察这个对角线元素的问题，这个时候，我们就要学会枚举这个对角线的元素
  • 如果知道矩阵的一个元素(i,j),那么左上角的对角线的元素就是(x-1,y-1),右下角的对角线元素就是(i+1,j+1),通过一个循环，判断坐标没有超过边界，即可遍历完全部的元素
  • 如果知道对角线的开始的位置(通过两次枚举，分别是枚举左下角和右上角的情况)，对于左下角的元素，一直枚举(x+1,y+1),最后判断这个x+1<=n-1就是到底即可，对于右上角的元素，一直枚举(x+1,y+1),然后判断y+1<=n-1,也就是列到最右边即可
  • 如何判断是否在一条对角线上？主对角线上，行-列的值相同，副对角线上，行+列的值相同
  • 注意，得另外开变量来枚举位置，不能修改当前的行与列

3446.按对角线进行矩阵排序

3446.按对角线进行矩阵排序

• 按照上面说的第一种枚举方式

class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        # 直接暴力求解
        n = len(grid)
        # 总的来说，右上角的数量就是 n-1,非递减，升序排序
        # 左下角的情况就是  n，非递增，也就是降序排序
        #处理右上角
        ans = [[0]*n for _ in range(n)]
        for i in range(1,n):
            r,l,store = 0,i,[] 
            while l <= n-1:
                store.append(grid[r][l])
                r,l = r + 1,l+1
            store.sort()
            r,l,m = 0,i,0
            while l <= n-1:
                ans[r][l] = store[m]
                r,l,m = r+1,l+1,m+1
        # 处理左下角,j枚举的是行
        for j in range(n):
            r,l,store = j,0,[]
            # 最后都是会到达最后一行的
            while r <= n-1:
                store.append(grid[r][l])
                r,l = r+1,l+1
            store.sort(reverse=True)
            r,l,m = j,0,0
            while r <= n-1:
                ans[r][l] = store[m]
                r,l,m = r+1,l+1,m+1
        return ans

2711.对角线上不同值的数量差

2711.对角线上不同值的数量差

• 按照第一种方式进行暴力枚举

class Solution:
    def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:
        m,n = len(grid),len(grid[0])
        ans = [[0]*n for _ in range(m)]
        # 从最后一行开始
        for r in range(m):
            for l in range(n):
                # 直接强行暴力左上角与右下角
                storeleft, storeright = set(), set()
                # 当前位置(r,l),左上角的是 (r-1,l-1),右下角元素就是(r+1,l+1)
                # 暴力左上角
                tr,tl = r,l
                while tr - 1 >= 0 and tl - 1 >= 0:
                    storeleft.add(grid[tr - 1][tl - 1])
                    tr -= 1
                    tl -= 1
                # 暴力右下角
                tr, tl = r, l
                while tr + 1 <= m - 1 and tl + 1 <= n - 1:
                    storeright.add(grid[tr + 1][tl + 1])
                    tr += 1
                    tl += 1
                ans[r][l] = abs(len(storeleft) - len(storeright))
        return ans

51.N皇后

51.N皇后

• 按照第三种方法，进行判断是否在同一对角线上+搜索

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        # N 皇后问题 也是一个排列的问题，是一个全排列的问题
        # 在全排列的基础上增加了这个不能在同一个斜线的问题
        col = [0]*n  # col[i]定义为第i行的所放在的列号
        # 这个valid(r,c)表示当前所在的行号r,要放入的列号c

        def valid(r,c):
            for R in range(r):
                C = col[R]
                if r+c == R+C or r-c == R-C:
                    return False
            return True
        
        ans = []
        def dfs(r,s):
            if r == n:
                ans.append(['.'*c + 'Q' + '.'*(n-1-c) for c in col])
                return
            for c in s:
                if valid(r,c):
                    col[r] = c 
                    dfs(r+1,s-{c})
        dfs(0,set(range(n)))
        return ans