1738. 找出第 K 大的异或坐标值

发表于 | 分类于
异或 + 堆 + 动态规划 的好题

用时 ： 参考了答案

看完题目首先是想到dp是跑不掉的

但是写出转化方程式需要一定的技巧

观察到 dp[1][1] = matrix[0][0] ^ matrix[0][1] ^ matrix[1][0] ^ matrix[1][1]

然后利用异或的性质

相同值异或为0，任何值与0异或为其本身

可以写成

dp[1][1] = matrix[0][0] ^ (matrix[0][1] ^ matrix[0][0]) ^ (matrix[1][0] ^ matrix[1][0]) ^ matrix[1][1]

进而得到

dp[i][j] = dp[i - 1][j - 1] ^ dp[i][j - 1] ^ dp[i - 1][j] ^ matrix[i][j]

（这我是我没有想到的技巧,如果能画图的话其实可以想明白
（1，1） （1，2）
（2，1） （2，2）

（1，2） 和 （2，1） 的区域 异或之后，重叠的部分被消除

而重叠的部分正好是（1，1）的区域，因此 可以再 异或（1，1） 来补偿

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
const swap = function (arr,i,j) {
    [arr[i],arr[j]] = [arr[j],arr[i]]
}

class MaxHeap {
    constructor() {
        this.count = 0
        this.data = new Array(this.count + 1)
    }
    shiftUp(k) {
        // 把新的元素往上排
        while(k>=1) {
            let father = Math.floor(k / 2)
            if (this.data[k] > this.data[father]) {
                swap(this.data,k,father)
                k = father
            } else {
                break
            }
        }
    }
    shiftDown(k) {
        while( k * 2  <= this.count) { // 表示k 有孩子
            let j = k
            if (k * 2 + 1 <= this.count && this.data[k * 2 + 1] > this.data[k] && this.data[k * 2 + 1] > this.data[k * 2]) {
                j = k * 2 + 1
            } else if (this.data[k * 2] > this.data[k]) {
                j = k * 2
            } else {
                break
            }
            swap(this.data,j,k)
            k = j
        }
    }
    size() {
        return this.count
    }
    isEmpty() {
        return this.count === 0
    }
    insert(item) {
        this.data[++this.count] = item 
        this.shiftUp(this.count)
    }
    extractMax() {
        if (this.count < 0) return 
        let ret = this.data[1]
        swap(this.data,1,this.count--)
        this.shiftDown(1)
        return ret
    }
}

var kthLargestValue = function(matrix, k) {
    var maxheap = new MaxHeap()
    var row = matrix.length
    var col = matrix[0].length
    var dp = [[matrix[0][0]]]
    maxheap.insert(matrix[0][0])
    for(let j = 1; j < col ; j ++) {
        dp[0][j] = dp[0][j - 1] ^ matrix[0][j]
        maxheap.insert(dp[0][j])
    }
    for(let i = 1 ; i < row ; i ++) {
        for(let j = 1 ; j < col; j ++) {
            if (!dp[i]) {
                dp[i] = []
                dp[i][0] = dp[i - 1][0] ^ matrix[i][0]
                maxheap.insert(dp[i][0])
            }
            dp[i][j] = dp[i - 1][j - 1] ^ dp[i][j - 1] ^ dp[i - 1][j] ^ matrix[i][j]
            maxheap.insert(dp[i][j])
        }
    }
    var res = ''
    while(k > 0) {
        res = maxheap.extractMax()
        k--
    } 
    return res
};

然后K大 应该用 最小堆来做，这边用了最大堆不过问题不大