讨论两道gg的高频题

第一题是:给定一个棋盘,里面有一些棋子。你能移走这个棋子,当且仅当这个棋子的同行同列有其它棋子。要求最多能移走多少棋子。
目前我看到的解法是把这个想成一个图,用横竖union find来做,可是想了好久也没法理解union find怎么运用到这个题目中,是把每个格子看成node吗?
那把什么看成edge呢?

第二题是实现带有expire功能的map, 我觉得最简单的做法是把timestamp存到hashMap里面,这样每次get的时候可以check要不要expire,
至于clean所有expired的,就把map扫一遍。
如果要improve,我想到的使用linked list把所有结果按顺序存起来,这样clean up的时候,就从linked list头部开始往后扫,扫到不要expire为止。
还有别的更好的做法吗?如果用treeMap的话,是不是只能用timestamp做key,这样没法update了吧。

多谢各位了

第一题我没准备到,同行同列之间是且还是或啊,如果是或的话用unionfind就很好理解了,因为每个set你总有方法移除到只剩一个,所以用unionfind来找set个数就好了,不过既然是静态的图寻找set,我觉得dfs就好了吧

第二题有很蛮种做法的,空间时间复杂度各不相同,地里都有,有些总结甚至连code都写出来了,可以再好好看下

那你的意思是说,找到了set的个数以后,用总共的棋子数减去set的个数,就是我们想要的答案?

没错紫薯紫薯紫薯紫薯紫薯紫薯紫薯紫薯紫薯紫薯紫薯紫薯

不好意思,我还是没有完全理解怎么做,在做union的时候,具体是怎么union呢,多谢了

我目前的想法是这样的,可能不太对

unordered_map<int,int> parents;
int find(int a){
    if(parents[a] == a){
        return a;
    }
    return parents[a] = find(parents[a]);
}
void connect(int a, int b){
    int root_a = find(a);
    int root_b = find(b);

    parents[root_b] = root_a;
}

int chess(vector<vector<int>> chessBoard){
    int m = chessBoard.size();
    int n = chessBoard[0].size();

    unordered_map<int,vector<int>> rows;
    unordered_map<int,vector<int>> columns;
    int sum = 0;
    for(int i = 0 ; i < m; i++){
        for(int j = 0; j < n; j++){
            if(chessBoard[j] == 1){
                parents[i * n +j] = i * n + j;
                rows.push_back(j);
                columns[j].push_back(i);
                sum ++;
            }
        }
    }

    for(int i = 0; i < m; i++){
        for(int j = 1; j < rows.size(); j++){
            connect(i * n + rows[0], i *n + rows[j]);
        }
    }

    for(int j = 0; j < n; j++){
        for(int i = 1; i < columns[j].size(); i++){
            connect(columns[j][0] * n + j, columns[j] * n + j);
        }
    }

    unordered_set<int> S;
    for(auto element: parents){
        int temp = find(element.first);
        S.insert(temp);
    }
    return sum - S.size();
}

最后一题可以用一个特殊的数据结构,叫skip list。但是这玩意儿咋说呢,结合heap写的话就是一个大悲剧,你要是装比被要求写一个出来当场直接就能被拍死。除非说面试你的人也不太懂这玩意儿。那可能能唬一下。另外expired map最核心的点不是如何高效删除,而是高效并发。真想装逼就记住两点,一,clear()用DaemonTrhead,这样可以减少call到的次数。二,用concurrentHashMap,减少被lock的block,加快访问速度。

这些都不太会额,有简单一点的做法吗?

这些都是吹比用的,到最后一步基本上也不会写什么code了