题目链接

关键词

  • 数组
  • 归纳

解析

  • 从题目看,grid是一个n个队伍比赛结果的二维矩阵,其中
    • grid[i][j] == 1:表示i胜利
    • grid[i][j] == 0:表示j胜利
    • i ≠ j:自己跟自己不能比
  • 解法一:
    • 统计每一场比赛的胜利方,并将其胜利次数记录下来
    • 最后遍历找出胜利次数最多的胜利发,即为冠军
  • 解法二:
    • 由于比赛只有胜负两种情况,没有打平等情况,且由于不能和自己比赛,此时一个队伍能胜利的最多场次为 n-1,所以,可以做以下分析:
      • 冠军有败绩:此时冠军的胜场次数最大为n-2,意味着有其他队伍比冠军还强,此时n-2必定不是冠军的获胜次数
      • 冠军没败绩:冠军全胜,获胜场数为n-1
    • 经过上面的分析,冠军的获胜场数一定是n-1,反过来,获胜场数为n-1的队伍,一定为冠军
    • 对于每个队伍,都统计其获胜,如果获胜场数为n-1,意味着找到了冠军,直接返回
  • 解法三:
    • 根据解法二的分析,冠军一定不会有败绩,且队伍强弱之前是有传递关系的,这意味着当grid[i][j] = 1, grid[j][k] = 1时,一定有grid[i][k] = 1
    • 所以,可以从一个获胜方champion开始,一路往上找能战胜champion的队伍,最后的胜利者就是冠军

代码

暴力统计

统计冠军

冠军不会失败

Note图形信息标注——需求分析Leetcode1026. 节点与其祖先之间的最大差值