异或的三道题目整理:Leetcode1738:找出第 K 大的异或坐标值

2021.5.19
  最近Leetcode官方连续推荐了3天的异或题目,不把我异或教会不罢休啊,不多说了直接上代码,详细看 Leetcode官方题解吧。
  异或运算满足结合律和交换律,且任意数异或自身等于 0
  上式可化简为整体思路还是秉持着使用异或的性质结合前缀和~~~~ 两个相同的数异或结果是0 ,0和任何数异或结果都是它本身,即对一个数做两次重复异或运算。 这个数就会消失。
   之前的两道异或题目可以参考:
1. Leecode421:数组中两个数的最大异或值
2. Leetcode1442:形成两个异或相等数组的三元组数目

class Solution {
public:
    int kthLargestValue(vector<vector<int>>& matrix, int k) {
    //只能是暴力异或,但是要使用前缀和! 二维前缀和,前缀和就是我就算暴力也要知道咋暴力
    //就是暴力的结果来自之前的积累
    int m=matrix.size(); int n=matrix[0].size();
    vector<int> results; 
    vector<vector<int>> pre(m+1,vector<int>(n+1,0));
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
          pre[i][j]=pre[i-1][j]^pre[i][j-1]^pre[i-1][j-1]^matrix[i-1][j-1];
          results.push_back(pre[i][j]);
        }
    }

    sort(results.begin(),results.end(),greater<int>()); //greater<int>() 让程序从升序变成降序
    return results[k-1];
    }
};

这道题目进一步地优化时间复杂度,可以围绕排序来展开,用可以更快地实现排序:

上一篇:根据项目实战深度理解Mybatis@Results、@Result,@Many一对多的关系


下一篇:python实现杨辉三角