2021.1.24-2021.1.28 题解

2021.1.24-2021.1.28 题解

• 674.最长递增子序列 2021.1.24
  https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
  方法具体可以类比寻找最大值，只不过最大值变成了每个序列的递增长度，设置一个 curMax 和一个 max，如果序列一直在递增，就 curMax++，直到递减重置 curMax，然后根据 curMax 和 max 的大小对 max 进行更新。

  https://leetcode-cn.com/problems/add-two-numbers/
  
  两数相加，数字是倒序存储的，所以可以直接遍历两个链表，让两个节点的值相加，如果存在大于等于 10 的情况就进位，下两个节点计算加上进位，如果最后两个节点还存在进位，那就新建立一个节点存储该进位。
  
  https://leetcode-cn.com/problems/regions-cut-by-slashes/
  
  将 1x1 的格子扩大成为 3x3 的迷宫,扩大成为 6x6，然后把两种斜线写入迷宫计 1，然后计算最终有多少个区域即可
  
  https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs/
  
  对于 12，21 这种我们统一看成 12，并将 12 看成 key，value 看成有多少个组是 12，然后对 value 进行组合计算，求和得到最终的结果。
  
  https://leetcode-cn.com/problems/hamming-distance/
  
  汉明距离是求两个数字中，不同位的数字的个数。因此可以先进行异或，然后结果里边的所有的 1 就是最终结果。因此提供两种解法：第一种就是一位一位的移动，计算 1 的个数。第二种是叫做布赖恩·克尼根算法，他是可以直接计算 1，可以跳过 0。如图，让 x & (x-1)就可以去除掉 x 中的最后一个 1，以此类推，该操作的次数就是结果里边 1 的个数。
  
  
  https://leetcode-cn.com/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/
  
  这个题的主要思路有点类似于克鲁斯卡尔求最小生成树，但是不同的是这个图没有权重，因此可以按照边的顺序进行依次加边。而且判断连通也不是整个图连通，而是判断两个点是否连通，如果这两个点已经连通了，那么如果再对这两个点加边就是多余的，此时最终的答案 +1。然后具体判断两个点是否连通可以用并查集。
  
  https://leetcode-cn.com/problems/merge-two-binary-trees/
  
  这个题就正常做，遍历两棵树，计算相应的值作为新树的节点，然后新树的左子树为递归遍历两棵树的左子树。右子树同理
  
  https://leetcode-cn.com/problems/find-pivot-index/
  
  这题的思路也很明确，就是遍历每一个点，都尝试当做中心索引，然后是否左右相等。但是该题如果对每个中心节点的左右都计算一次太慢。我们只需要判断最后的条件，即 sum 左 + sum 右 + num[i] == total。然后 sum 左和 sum 右是相等的，因此直接 2 * sum 左 + num[i] == total 即可，然后 sum 左可以在遍历 num[i]的时候就计算出来。