1 題目描述

2 解題思路

設二維前綴和pre(i,j) 表示矩陣matrix 中所有滿足0≤x<i 且 0≤y<j 的元素執(zhí)行按位異或運算的結果

考慮pre矩陣的一個2×2 的子部分

pre(i,j)	pre(i,j) ^ matrix(i,j+1)
pre(i,j) ^ matrix(i+1,j)	pre(i,j) ^ matrix(i,j+1) ^ matrix(i+1,j) ^ matrix(i+1,j+1)

那么pre(i+1,j+1)=pre(i,j) ^ matrix(i,j+1) ^ matrix(i+1,j) ^ matrix(i+1,j+1)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?=pre(i,j) ^ [pre(i,j) ^ matrix(i,j+1)] ^ [pre(i,j) ^ matrix(i+1,j)] ^?matrix(i+1,j+1)

即

用一個示意圖表示，即為

class Solution:def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:tmp=[]ret=[]tmp.append([matrix[0][0]])#異或模擬的數(shù)組ret.append(matrix[0][0])#每個坐標異或結果的數(shù)組for i in range(1,len(matrix)):tmp.append([tmp[i-1][0]^matrix[i][0]])ret.append(tmp[i-1][0]^matrix[i][0])for i in range(1,len(matrix[0])):tmp[0].append(tmp[0][i-1]^matrix[0][i])ret.append(tmp[0][i-1]^matrix[0][i])print(tmp)for i in range(1,len(matrix)):for j in range(1,len(matrix[0])):tmp[i].append(tmp[i][j-1]^tmp[i-1][j]^tmp[i-1][j-1]^matrix[i][j])ret.append(tmp[i][j-1]^tmp[i-1][j]^tmp[i-1][j-1]^matrix[i][j])ret.sort()return(ret[-k])

?

總結

以上是生活随笔為你收集整理的文巾解题1738. 找出第 K 大的异或坐标值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。