讨论/题目交流/🐱 第 12 场夜喵双周赛/
🐱 第 12 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 数组变换
4 分 - 力扣排行榜
5 分 - 树的直径
7 分 - 删除回文子数组

展开讨论
共 12 个讨论

。。。兄弟们,抢头条了。。。

第一题:

看看数据范围,1<=playerId,K<=100001 <= playerId, K <= 10000 那是坑人的,最多 10001000 次函数调用,KK 还比当前人数小,KK 真实的范围应该是 K<=1000K <= 1000
这数据范围,直接暴力都行

class Leaderboard {
public:
    map<int, int> a;
    Leaderboard() {
        
    }
    
    void addScore(int playerId, int score) {
        a[playerId] += score;
    }
    
    int top(int K) {
        vector<int> data;
        for (auto it = a.begin(); it != a.end();it++) {
            data.push_back(it->second);
        }
        sort(data.begin(), data.end());
        int ret = 0;
        for (int i = 0;i < K;i++) {
            ret += data[data.size() - i - 1];
        }
        return ret;
    }
    
    void reset(int playerId) {
        a[playerId] = 0;
    }
};

如果这题的数据范围大一点,咋做?树状数组可以考虑一下


第二题:

根据题意暴力。。。

class Solution {
public:
    vector<int> transformArray(vector<int>& arr) {
        vector<int> a = arr;
        vector<int> b;
        int n = arr.size();
        while (1) {
            b = vector(n, 0);
            b[0] = a[0];
            b[n - 1] = a[n - 1];
            for (int i = 1;i < n - 1;i++) {
                if (a[i] < a[i - 1] && a[i] < a[i + 1]) {
                    b[i] = a[i] + 1;
                }
                else if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
                    b[i] = a[i] - 1;
                } else {
                    b[i] = a[i];
                }
            }
            if (a == b) {
                break;
            }
            a = b;
        }
        return a;
    }
};

第三题:

树的直径的解法,两次 BFS

  1. 任取一点 BFS,选择最长路径的节点,假设这个点为 aa
  2. aa 开始 BFS,最长路径就是树的直径

当然也可以选择用 DFS 做,不过这个题数据范围 n<=10000n<=10000,在 stack overflow 的边缘,保险一点,我还是不敢选择用 DFS 做

class Solution {
public:
    //写个注释,返回值第一维代表最远的点,第二维代表start跟最远点的距离
    pair<int, int> bfs(vector<vector<int>>& e, int start) {
        vector<int> d(e.size(), -1);
        
        queue<int> Q;
        Q.push(start);
        d[start] = 0;
        
        pair<int, int> ret;
        
        while (!Q.empty()) {
            int x = Q.front();
            Q.pop();
            ret.first = x;
            ret.second = d[x];
            for (auto& y : e[x]) {
                if (d[y] == -1) {
                    d[y] = d[x] + 1;
                    Q.push(y);
                }
            }
        }
        return ret;
    }
    
    int treeDiameter(vector<vector<int>>& edges) {
        int n = edges.size() + 1;
        vector<vector<int>> e(n, vector<int>());
        for (auto& edge: edges) {
            e[edge[0]].push_back(edge[1]);
            e[edge[1]].push_back(edge[0]);
        }
        
        pair<int, int> p;
        p = bfs(e, 0);
        p = bfs(e, p.first);
        
        return p.second;
    }
};

第四题:

这题使我联想到那个消消乐的题,消消乐是相同颜色的一起消除,这题是消除回文串

同样是典型的区间 dp

dp[left][right]dp[left][right] 表示区间 [left,right][left, right] 删除完的最少操作

那么我们考察 arr[left]arr[left] 这个元素,这个元素要么自己删除,要么跟另一个等于 arr[left]arr[left] 的元素一起删除

假设 arr[left]=arr[i]arr[left] = arr[i],那么 leftleft 可以跟 ii 一起删除,这时候的操作数就是 max(dp[left+1][i1],1)+dp[i+1][right]max(dp[left + 1][i - 1], 1) + dp[i + 1][right]

第二项好理解,第一项为啥是 max(dp[left+1][i1],1)max(dp[left + 1][i - 1], 1),因为 leftleftii 可以跟 [left+1,i1][left+1,i-1] 里面某个回文数一起删除,如果 [left+1,i1][left+1,i-1] 本身是个空集,那么 leftleftii 一起删除,就是一次操作

ok,dp[left][right]dp[left][right] 就是枚举所有的跟 arr[left]arr[left] 相等的 arr[i]arr[i],对每个i计算一个操作数,求最小即可

class Solution {
public:
    int dp[102][102];
    int getdp(vector<int>& arr, int left, int right) {
        if (left == right) {
            return 1;
        }
        if (left > right) {
            return 0;
        }
        if (left + 1 == right && arr[left] == arr[right]) {
            return 1;
        }
        if (left + 1 == right && arr[left] != arr[right]) {
            return 2;
        }
        if (dp[left][right] != -1) {
            return dp[left][right];
        }
        int ret = 0x3fffffff;
        
        for (int i = right;i >= left;i--) {
            if (arr[left] != arr[i]) {
                continue;
            }
            int t = getdp(arr, left + 1, i - 1);
            if (t == 0) {
                t = 1;
            }
            ret = min(ret, t + getdp(arr, i + 1, right));
        }
        return dp[left][right] = ret;
    }
    int minimumMoves(vector<int>& arr) {
        memset(dp, -1, sizeof(dp));
        return getdp(arr, 0, arr.size() - 1);
    }
};
21

大佬们可以献出优秀的题解了
我只能给个第二题的题解

class Solution{
	public:
		vector<int> transformArray(vector<int>& arr){
			vector<int> temp;
			temp.assign(arr.begin(),arr.end());
			
			bool flag=false;
			
			while(!flag)
			{
				flag=true;
				for(int i=1;i<arr.size()-1;++i)
				{
					if(arr[i]>arr[i-1] && arr[i]>arr[i+1])
					{
						--temp[i];
						flag=false;
					}
					else if(arr[i]<arr[i-1] && arr[i] < arr[i+1])
					{
						++temp[i];
						flag=false;
					}
				}
				
				arr.assign(temp.begin(),temp.end());
				
				flag=true;
				for(int i=1;i<temp.size()-1;++i)
				{
					if(temp[i]>temp[i-1] && temp[i]>temp[i+1])
					{
						--arr[i];
						flag=false;
					}
					else if(temp[i]<temp[i-1] && temp[i] < temp[i+1])
					{
						++arr[i];
						flag=false;
					}
				}
				temp.assign(arr.begin(),arr.end());
			}
			cout<<"[";
			for(int i=0;i<arr.size()-1;++i)
			{
				cout<<arr[i]<<",";
			}
			cout<<arr[arr.size()-1]<<"]"<<'\n';
			
			return arr;
		}
};
7

12 双周赛题解

5097. 力扣排行榜

由于数据范围:

1playerId,K1041 \leq playerId, K \leq 10^4

所以应该直接暴力就行。为了避免 Python 的坑,用优先队列优化了一下 topK 求和,用一个字典优化了存在性判断。

class Leaderboard:

    def __init__(self):
        self.heap = []
        self.hasId = {}

    def addScore(self, playerId: int, score: int) -> None:
        if self.hasId.get(playerId, False) == False:
            heapq.heappush(self.heap, (-score, playerId))
            self.hasId[playerId] = True
        else:
            for i, n in enumerate(self.heap):
                if n[1] == playerId:
                    self.heap[i] = (self.heap[i][0] - score, playerId)
        #print(self.heap)
        

    def top(self, K: int) -> int:
        topK = heapq.nsmallest(K, self.heap)
        res = 0
        for i in topK:
            res += -i[0]
        return res    
        

    def reset(self, playerId: int) -> None:
        for i, n in enumerate(self.heap):
            if n[1] == playerId:
                self.hasId[playerId] = False
                del self.heap[i]
                return None

5096. 数组变换

根据题目暴力就行

class Solution:
    def transformArray(self, arr: List[int]) -> List[int]:
        import copy
        while True:
            new = copy.deepcopy(arr)
            for ind, n in enumerate(arr):
                if ind == 0 or ind == len(new) - 1: 
                    continue
                if arr[ind] > arr[ind - 1] and arr[ind] > arr[ind + 1]:
                    new[ind] -= 1 
                elif arr[ind] < arr[ind - 1] and arr[ind] < arr[ind + 1]:
                    new[ind] += 1    
            if new == arr:
                return new
            arr = new
        return []    

5098. 树的直径

就是求一个图的最长路径,之前在 HDU 上有个收集糖果的题目类似,那个是求最长路径上的节点数,那其实就是 最长路径 + 1 ,而这题是裸题。为了避免 python 在写图论时候的坑,用 cpp 写了一版 dfs A 了:

class Solution {
public:
    vector<int> e[10004];
    int vis[10004] = {0};
    int ans = 0, now = 1;
    void dfs(int u,int dis){
        if(ans < dis) {
            ans = dis;
            now = u;
        }
        vis[u] = 1;
        for(int i = 0; i < e[u].size(); ++ i) {
            int v = e[u][i];
            if (!vis[v])
                dfs(v, dis + 1);
        }
    }

    int treeDiameter(vector<vector<int>>& edges) {
        for (int i = 0; i < edges.size(); ++ i) {
            int a = edges[i][0];
            int b = edges[i][1];
            e[a].push_back(b);
            e[b].push_back(a);
        }
        dfs(1, 0);
        ans = 0;
        memset(vis, 0, sizeof(vis));
        dfs(now, 0);
        return ans;
    }
};

5115. 删除回文子数组

比赛的时候没有做出来。看了这篇题解,发现就是一个区间 dp。

  1. dp[l][r] 代表 [l, r] 删除的操作数,所以我们枚举分隔点 k,然后 dp[l][r] 自然就从 dp[l][k] + dp[k + 1][r] 转移过来;
  2. 如果 arr[l] == arr[r],那么其实就从 dp[l + 1][r - 1] 转移而来,因为范围 [l + 1, r - 1] 里面不管怎么删除,lr 位置的字母具有回文性,删除里面的串,外部就可以通过一步干掉。

时间复杂度 O(n^3)。另外,相同思路代码用 Python 可能会 TLE,不解为什么。

class Solution {
public:
    int n, dp[105][105];
    int minimumMoves(vector<int>& arr) {
        n = (int)arr.size();
        for (int i = 1; i <= n; ++ i) 
            dp[i][i] = 1;
        
        for (int i = 1; i < n; ++ i) 
            dp[i][i + 1] = arr[i - 1] == arr[i] ? 1 : 2;
        
        for (int len = 3; len <= n; ++ len) {
            for (int i = 1; i + len - 1 <= n; ++ i) {
                int j = i + len - 1;
                dp[i][j] = j - i + 1;
                for (int k = i; k < j; ++ k) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
                if (arr[i - 1] == arr[j - 1]) {
                    dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
                }
            }
        }
        return dp[1][n];
    }
};


最后,欢迎大家关注我的微信公众号,算法 + iOS 移动开发,全是干货!

image.png

4

第三题 一次 BFSBFS

不断去掉叶子,每去掉一层叶子,最长路径 +2+2,最后剩余一个节点的话,说明共有偶数条边,即是最长路径,如果最后剩余两个节点,这两个节点之间一定有一条边相边,此时最长路径 +1+1(参考 310 最小高度树

class Solution:
    def treeDiameter(self, edges: List[List[int]]) -> int:
        from collections import defaultdict
        if not edges:
            return 0
        graph = defaultdict(list)
        for x, y in edges:
            graph[x].append(y)
            graph[y].append(x)
        n = len(graph)
        ans = 0
        # 叶子节点
        leaves = [i for i in graph if len(graph[i]) == 1]
        while n > 2:
            ans +=2
            n -= len(leaves)
            nxt_leaves = []
            for leave in leaves:
                # 与叶子节点相连的点找到
                tmp = graph[leave].pop()
                # 相连的点删去这个叶子节点
                graph[tmp].remove(leave)
                if len(graph[tmp]) == 1:
                    nxt_leaves.append(tmp)
            leaves = nxt_leaves
        if len(leaves) == 2:
            ans += 1
        return ans
3

第一题 Design A Leaderboard

这道题如果光从比赛的角度说,暴力就行了。但是更进一步,我们可以找到更好的办法。利用hashMap<play_id, score>保存用户分数,剩下的需要一个数据结构,它要既能够方便地插入数据,同时又能够有序地遍历内部的元素。最简单的就是BST,key是score,value保存有几个这样的score,比如tree[100]=3,表示得分为100的人3人。然后topK就可以以O(k)的时间复杂度算得。进而,我想到了SBT,size-balanced-tree。可以logN的时间查询出第K大,每个节点除了维护size还可以多维护一个所有子树的和,这样可以做到插入和查询都是O(logN)。但是,由于不想写,还是只用了标准库的BTree,思路是一样的,实际上比BST还快一点点。

use std::collections::{HashMap, BTreeMap};
use std::cmp::Reverse;

struct Leaderboard {
    user_score: HashMap<i32, i32>,
    rank: BTreeMap<Reverse<i32>, i32>,
}

impl Leaderboard {

    fn new() -> Self {
        Self{
            user_score: HashMap::new(),
            rank: BTreeMap::new(),
        }
    }

    fn add_score(&mut self, player_id: i32, score: i32) {
        if score == 0 {
            return;
        }
        let mut before = None;
        if let Some(&v) = self.user_score.get(&player_id) {
            before = Some(v);
        }
        let p = self.user_score.entry(player_id).or_insert(0);
        *p += score;
        if let Some(v) = before {
            if let Some(t) = self.rank.get_mut(&Reverse(v)) {
                *t -= 1;
            }
        }
        *self.rank.entry(Reverse(*p)).or_insert(0) += 1;
    }

    fn top(&self, k: i32) -> i32 {
        let mut count = 0;
        let mut n = k;
        for (k,&v) in self.rank.iter() {
           if n >= v {
               count += k.0 * v;
               n -= v;
           } else {
               count += k.0 * n;
               n = 0;
           }
            if n == 0 {
                break;
            }
        }
        count
    }

    fn reset(&mut self, player_id: i32) {
        if let Some(v) = self.user_score.get_mut(&player_id) {
            let t = *v;
            *v = 0;
            if t > 0 {
                *self.rank.get_mut(&Reverse(t)).unwrap() -= 1;
            }
        }
    }
}

第二题 Array Transformation

这道题是个easy,其实就是模拟这个过程就行了。为了节约空间可以用01滚动。

impl Solution {
    pub fn transform_array(arr: Vec<i32>) -> Vec<i32> {
        let n = arr.len();
        if n <= 2 {
            return arr;
        }
        let mut darr = [arr, vec![0; n]];
        darr[1][0] = darr[0][0];
        darr[1][n-1] = darr[0][n-1];
        let mut pos = 0;
        loop {
            let mut change = false;
            let np = pos ^ 1;
            for i in 1..n-1 {
                if darr[pos][i] > darr[pos][i-1] && darr[pos][i] > darr[pos][i+1] {
                    change = true;
                    darr[np][i] = darr[pos][i]-1;
                } else if darr[pos][i] < darr[pos][i-1] && darr[pos][i] < darr[pos][i+1] {
                    change = true;
                    darr[np][i] = darr[pos][i]+1;
                } else {
                    darr[np][i] = darr[pos][i];
                }
            }
            if !change {
                break;
            }
            pos = np;
        }
        darr[pos].clone()
    }
}

第三题 Tree Diameter

两次BFS,第一次任选一个点作为起点(比如0点),进行一次BFS,找到离0最远的点T。然后从T开始再进行一次BFS,找到离T最远的点,这个点到T的距离就是树的直径。
那么问题来了,为什么呢?下面给出证明:

设树的直径的左端点为S,右端点为T。随机选择一点P作为起点,分两种情况讨论:

假设P恰好在直径上

SP+PT=ST。那么离P最远的点必然是T(或者S)。为什么?
可以利用反证法,假设离P最远的点是W,不是T。此时可以推出:
SP+PW > SP+PT => SP+PW > ST。而由于SP是直径,树中没有任何路径能大于它,因此不存在这样的W点。
由此可得,当P点恰好在直径上,离他最远的点必然是直径的两个端点之一。

假设P是直径外一点

设,存在一个点W,使得PW > PT
设PW和直径ST相交于点X(必然相交,这个太简单就不证了),由此可得:
PX+XW > PX+XT(因为我们假设W离P最远),同理可得
PX+XW > PX+XS
两式相加可得:
2PX+2XW > 2PX+ST即:

XW > ST/2

我们继续分情况讨论:

  • 假如X恰好是ST的中点,则有: ST/2=SX=ST,而XW>ST/2=SX,因此:

SX+XW > ST,由于ST是直径,所以不存在这样的点W。

  • 假如X离S更近离T更远,即SX<XT, XT>ST/2

因此,XT+XW > SX+XT = ST。而ST是直径,所以不存在这样的点W。

综上可得,离树上任意点最远的点,必然是树的直径的两个端点之一。

use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn tree_diameter(edges: Vec<Vec<i32>>) -> i32 {
        if edges.is_empty() {
            return 0;
        }
        if edges.len() == 1 {
            return 1;
        }
        let mut graph = HashMap::new();
        for edge in edges {
            let (a,b) = (edge[0], edge[1]);
            graph.entry(a).or_insert(HashSet::new()).insert(b);
            graph.entry(b).or_insert(HashSet::new()).insert(a);
        }
        let (t, _) = Self::bfs(&graph, 0);
        let (_, ans) = Self::bfs(&graph, t);
        ans
    }
    fn bfs(graph: &HashMap<i32, HashSet<i32>>, start: i32) -> (i32, i32) {
        let mut visited = HashSet::new();
        let mut q = vec![];
        let mut s = 0;
        let mut ans = 0;
        q.push((start, 0));
        visited.insert(start);
        while !q.is_empty() {
            let (cur, dist) = q.pop().unwrap();
            if ans < dist {
                ans = dist;
                s = cur;
            }
            if let Some(nodes) = graph.get(&cur) {
                for &node in nodes.iter() {
                    if !visited.contains(&node) {
                        visited.insert(node);
                        q.push((node, dist+1));
                    }
                }
            }
        }
        (s, ans)
    }
}

第四题 Palindrome Removal

这道题是一道比较经典的区间DP。一般来说这种题都是一个套路,对大区间操作有一定规则,且需要把内部小区间先操作了。

这道题同样。我们用f[i][j]表示把区间i..j全部删除的最少次数。由于这道题要求删除的必须是回文串,因此分情况讨论:
删除整个区间有两种可能,第一是先删i..k,再删k+1..j,第二是把i+1..j-1先删,最后和i&j一起删。

  • s[i] == s[j],那么把它俩放到任何一个回文串两边,都能组成一个新的回文串。也就意味着i+1..j-1这个区间不论怎么删,最后一次删除的时候,都可以把s[i]s[j]带上一起删。因此:
    f[i][j] = max(f[i+1][j-1], 1)。和1取max是因为整个区间删除至少需要一次,如果i..j本来就是回文串,这样递归下去我们会得到0

当然,我们也可以把si和sj分成两个部分删,先删si..sk,再删sk+1..sj

use std::cmp::{min, max};

impl Solution {
    pub fn minimum_moves(arr: Vec<i32>) -> i32 {
        if arr.is_empty() {
            return 0;
        }
        let n = arr.len();
        if n == 1 {
            return 1;
        }
        let mut f = vec![vec![0; n]; n];
        Self::dfs(0, n-1, &arr, &mut f)
    }
    fn dfs(l: usize, r: usize, arr: &Vec<i32>, f: &mut Vec<Vec<i32>>) -> i32 {
        if l > r {
            return 0;
        }
        if l == r {
            return 1;
        }
        if f[l][r] > 0 {
            return f[l][r];
        }
        let mut ans = (r-l+1) as i32;
        for i in l..=r {
            if l == i {
                ans = min(ans, 1+Self::dfs(i+1, r, arr, f));
            } else {
                if arr[l] == arr[i] {
                    ans = min(ans, max(Self::dfs(l+1, i-1, arr, f), 1)+Self::dfs(i+1, r, arr, f));
                } else {
                    ans = min(ans, Self::dfs(l+1, i-1, arr, f)+2+Self::dfs(i+1, r, arr, f));
                }
            }
        }
        f[l][r] = ans;
        ans
    }
}
1

手速&思考速度还是不够orz

3

被第二题题意绊倒了,因为题意卡了 11 个小时也是醉了。。。。。。。。
分享一下自己会写的几道题的题解。

第一题

按照题意模拟即可,所有人的分数用 multiset存一下即可省的排序

const int MAXN = 1e4 + 10;
class Leaderboard {
    int board[MAXN];
    multiset<int> s;
    multiset<int> :: iterator ite;
   public:
    Leaderboard() {
        memset(board, 0, sizeof(board));
        s.clear();
    }
    void addScore(int playerId, int score) {
       if(board[playerId]) s.erase(s.find(-board[playerId]));
       board[playerId] += score;
       s.insert(-board[playerId]);
    }

    int top(int K) {
        int sum = 0;
        for(ite = s.begin(); K--; ite++) 
            sum += *ite;
        return -sum;
    }

    void reset(int playerId) {
        s.erase(s.find(board[playerId]));
        board[playerId] = 0;
    }
};

第二题

仔细读题暴力即可

class Solution {
   public:
    vector<int> transformArray(vector<int>& arr) {
        if(arr.size() <= 2) return arr;
        bool flag = false;
        while(!flag) {
            bool flag1 = true;
            vector<int> temp = arr;
            for(int i = 1; i < arr.size() - 1; i++) {
                if(arr[i] < temp[i - 1] && arr[i] < temp[i + 1]){
                    arr[i] += 1;
                    flag1 = false;
                }
                if(arr[i] > temp[i - 1] && arr[i] > temp[i + 1]) {
                    arr[i] -= 1;
                    flag1 = false;
                }
            }
            if(flag1) flag = true;
        }
        return arr;
    }
};

第三题

树的直径裸题,用两边 BFS,第一遍从起点 BFS 找到最远的点,第二遍从最远的点 BFS 找到最长的距离

const int MAXN = 100010;
int len, point, top;  //记录直径,最远点
struct node {
    int to, next, w;
} edge[MAXN];
int dis[MAXN];  //记录距离
bool vis[MAXN];
int head[MAXN];

class Solution {
   public:
    void addEdge(int u, int v, int z) {
        edge[top].to = v;
        edge[top].w = z;
        edge[top].next = head[u];
        head[u] = top++;
    }
    void BFS(int s) {
        queue<int> qu;
        memset(dis, 0, sizeof(dis));
        vis[s] = 1;
        qu.push(s);
        while (!qu.empty()) {
            int x = qu.front();
            qu.pop();
            for (int i = head[x]; i != -1; i = edge[i].next) {
                int y = edge[i].to;
                if (!vis[y]) {
                    dis[y] = dis[x] + edge[i].w;
                    if (len < dis[y]) {
                        len = dis[y];
                        point = y;
                    }
                    vis[y] = 1;
                    qu.push(y);
                }
            }
        }
    }
    int treeDiameter(vector<vector<int>>& edges) {
        memset(head, -1, sizeof(head));
        for (auto e : edges) {
            addEdge(e[0], e[1], 1);
            addEdge(e[1], e[0], 1);
        }
        len = 0;
        memset(vis, 0, sizeof(vis));
        BFS(0);
        len = 0;
        memset(vis, 0, sizeof(vis));
        BFS(point);
        return len;
    }
};

第四题

太菜了,第四题不会。。。。。。

2

第四题的简单解释

要计算数组的最少删除次数,等价于计算数组变成回文数组的最少删除次数+1。
求数组的回文所需次数很简单,首先对于最后一个数,他要么被删除,要么不被删除。
如果被删除,原问题就是规模为n-1的子问题的结果+1。
如果不被删除,,他肯定和前面某个数相同,为了方便描述记为k,那么k前面的数都不能保留都要被删除,那么删除k之前的数组所需要的次数显然是一个规模更小的子问题,同时k之后的数组要计算变成回文数组的最少次数也是个规模更小的子问题。
那么状态转移方程就很自然的知道了。

1

历经一个多小时,到最后也只做出来一道啊(;´Д`)

vector<vector<int> >tree(10005);
int dist[10005];
bool mark[10005];
class Solution {
public:
    pair<int, int> bfs(int start){//bfs最大深度的所在叶子节点及最大深度
        memset(dist, 0, sizeof(dist));//重置
        memset(mark, false, sizeof(mark));
        queue<int>que;
        que.push(start);
        mark[start] = true;
        int maxDis = 0, res = 0;
        int frt;
        while(!que.empty()){
            frt = que.front();
            que.pop();
            if(frt == start){
                for(int i = 0; i < tree[frt].size(); ++i){
                    dist[tree[frt][i]] = 1;
                    que.push(tree[frt][i]);
                    mark[tree[frt][i]] = true;
                }
            }
            else{
                bool flag = true;
                for(int i = 0; i < tree[frt].size(); ++i){
                    if(!mark[tree[frt][i]]){
                        dist[tree[frt][i]] = dist[frt] + 1;
                        que.push(tree[frt][i]);
                        mark[tree[frt][i]] = true;
                        flag = false;
                    }
                }
                if(flag && dist[frt] > maxDis){
                    res = frt;
                    maxDis = dist[frt];
                }
            }
        }
        return make_pair(res, maxDis);
    }
    int treeDiameter(vector<vector<int>>& edges) {
        int len = edges.size(), start;
        for(int i = 0; i < len; ++i){
            tree[edges[i][0]].push_back(edges[i][1]);
            tree[edges[i][1]].push_back(edges[i][0]);
        }
        int newSta = bfs(0).first;
        cout << newSta << endl;
        return bfs(newSta).second;
    }
};

这个是树的直径我的提交,但是在输入[[0,1],[1,2],[0,3],[3,4],[2,5],[3,6]]时,本地测试为5是正确的,但提交上去就是2,提示我是错的,很是疑惑,求哪位大佬可以解释一样,想了半天没想通,这是不是bug。