讨论/题目交流/🐱 力扣第 9 场夜喵双周赛/
🐱 力扣第 9 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。
image.png

展开讨论
共 9 个讨论

菜鸡第一次时间内做完,纪念一下。
1.排序累加
2.BFS(不知道有没有公式,这个是我耗时最长的...)
3.建桶存每个数字出现的次数,找最小的出现次数等于数组数量的值
4.将街区排序,每次取时间最短的两个街区,合并成一个(加上split时间)再插回原来队列,直到只剩一个为止

4

第 2 题

广度优先搜索,同时配合一定的剪枝策略,否则算法将超时。

剪枝的关键在于定义一个合法区域,一旦骑士移动到合法区域之外,则剪除该搜索分支,可以极大地提高效率。

合法区域定义如下:在起点与终点所限定的矩形的基础上,向四边各扩展 2 格所构成的矩形区域。为什么要扩展 2 格?这个 2 是怎么来的?由骑士的最基本走法可知,骑士要到达一个特定的点,最多需要额外 2 格的腾挪空间。如果不扩展这 2 格,那么有些终点将无法到达。

from collections import deque

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        start = complex(0, 0)
        end = complex(abs(x), abs(y))
        # 借助复数进行运算,而不是二元组,使得代码更加简洁高效
        directions = (1+2j, 1-2j, -1+2j, -1-2j, 2+1j, 2-1j, -2+1j, -2-1j)
        
        visited = set()
        q = deque([(start, 0)])
        while q:
            pos, depth = q.popleft()
            if not (-2 <= pos.real <= end.real + 2 and -2 <= pos.imag <= end.imag + 2):
                continue
            if pos in visited:
                continue
            if pos == end:
                return depth
            visited.add(pos)
            q.extend([(pos + d, depth + 1) for d in directions])

第 3 题

使用一组集合来保存矩阵的每一行数据,然后依次判断第一行的每一个数是否在剩余的所有的集合中均出现过。

O(MN) 时间复杂度(M、N 分别为矩阵的行数和列数):

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        sets = [set(lst) for lst in mat]
        for x in mat[0]:
            if all(x in s for s in sets):
                return x
        return -1

第 4 题

注意:每个工人只能用一次,所以 N 个街区最终必然需要召唤出 N 个工人!

将任务放入堆中,每次取时间最短的两个,计算两者的总耗时(split + max(t1, t2))再放回堆中,直到只剩一个为止。

每次合并的两个任务其实分别代表两组任务,由于这两组任务的时间最接近,因此把这两组任务并行处理,重叠时间最多。

import heapq

class Solution:
    def minBuildTime(self, blocks: List[int], split: int) -> int:
        heapq.heapify(blocks)
        while len(blocks) > 1:
            t1 = heapq.heappop(blocks)
            t2 = heapq.heappop(blocks)
            heapq.heappush(blocks, split + max(t1, t2))
        return blocks[0]
2

发一下第三题的源码吧。感觉复杂度略高。

class Solution {
    public int smallestCommonElement(int[][] mat) {
        int rowNum = mat.length;
        if (rowNum==1)
            return mat[0][0];
        int colNum = mat[0].length;
        int[] ids = new int[rowNum];
        while (true) {
            int mId = findMax(mat, ids, rowNum);
            boolean same = true;
            int compare = mat[mId][ids[mId]];
            for (int i=0; i<rowNum; i++) {
                int j=ids[i];
                for (; j<colNum; j++) {
                    if (mat[i][j] == compare) {
                        ids[i] = j;
                        break;
                    } else if (mat[i][j] > compare) {
                        ids[i] = j;
                        same = false;
                        break;
                    }
                }
                if (j==colNum)
                    return -1;
            }
            if (same)
                return compare;
        }
    }
    
    private int findMax(int[][] mat, int[] ids, int len) {
        int maxId = 0;
        for (int i=0; i<len; i++) {
            if (mat[i][ids[i]] > mat[maxId][ids[maxId]]) {
                maxId = i;
            }
        }
        return maxId;
    }
}

有大佬能解释一下这里为什么只要是相等就一定是结果呢。知道unordered_map是无序的,但这也太巧合了吧。但是写的时候没在意。。

unordered_map<int, int> cnt; 
int i, j; 

for (i = 0; i < lenx; i++) { 
    cnt[mat[i][0]]++; 
    for (j = 1; j < leny; j++) { 
        if (mat[i][j] != mat[i][j - 1]) 
            cnt[mat[i][j]]++; 
    } 
} 
for (auto ele : cnt) { 
    if (ele.second == lenx) 
        re = ele.first; 
} 
return re;

第一次参加竞赛=,=
第二题BFS..单用例测试通过. 提交TLE.真实心累.
卡了超久多时间= =. 竞赛结束了才剪肢剪出来AC..也不知道是不是Python坑的我.
幸好还留了一点时间看第三题..不然就只有一题目AC了..

本人第一次参加比赛,刚刚开始学习算法,这是我做的第三题代码,提交通过了,但我觉得耗时有点久,问下各位大佬有没有更简单的方法
🙄🙄

class Solution {
public:
vector<int> fun(vector<int>a, vector<int> b) {
vector<int> ret;
for (int num : a) {
if (find(b.begin(), b.end(), num) != b.end())
ret.push_back(num);
}
return ret;
}
public:
int smallestCommonElement(vector<vector<int>>& mat) {
while (mat.size() > 1) {
vector<int>temp = fun(mat[0], mat[1]);
if (temp.size() == 0)
return -1;
mat.erase(mat.begin(),mat.begin()+2);
mat.insert(mat.end(), temp);
cout << temp.size() << endl;
}
return mat[0][0];
}
};

第三题,n^nlog(n)

#include <algorithm>
class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mtx) {
        int n = mtx.size();
        if(mtx.empty() || mtx[0].empty()) return -1;
        else if(mtx.size()==1 && mtx[0].size()==1) return mtx[0][0];
        vector<int>& fst = mtx[0];
        for(int i=0; i<fst.size(); i++) { //扫遍第一行
            int key = fst[i], k = 1;
            
            for(k=1; k<mtx.size(); k++) { //二分 剩下的[2, n]行
                vector<int>& v = mtx[k];
                
                int idx = -1, lef = 0, rig = v.size()-1, mid;
                while(lef <= rig) {
                    mid = (lef + rig) >> 1;
                    if(v[mid] == key) { idx = mid; break; }
                    else if(v[mid] < key) lef = mid + 1;
                    else rig = mid - 1;
                }
                if(idx == -1) break;
            }
            if(k == n) return key;
        }
        return -1;
    }
## };

没人吗

有人