# 543. 二叉树的直径

题目

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

示例 : 给定二叉树

      1
     / \
    2   3
   / \     
  4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意:两结点之间的路径长度是以它们之间边的数目表示。

思路

使用二叉树的遍历来完成。定义一个全局变量diameter,深度遍历二叉树的算法是:遍历左子树深度,遍历右子数深度,返回最大的那一个值作为当前节点深度。在次基础上,返回节点深度之前加一步:将左右节点相加与diameter比较,看是否更新

代码

class Solution {
public:
    int diameter = 0;
    int depth(TreeNode* root){
        if(root == NULL) return 0;
        int L = depth(root->left);
        int R = depth(root->right);
        diameter = max(diameter, L + R);
        return max(L, R) + 1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        depth(root);
        return diameter;
    }
};

# 1013. 将数组分成和相等的三个部分

给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。

形式上,如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。

示例 1

输出:[0,2,1,-6,6,-7,9,1,2,0,1] 输出:true 解释:0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例 2:

输入:[0,2,1,-6,6,7,9,-1,2,0,1] 输出:false

示例 3:

输入:[3,3,6,5,-2,2,5,1,-9,4] 输出:true 解释:3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

提示:

3 <= A.length <= 50000 -10^4 <= A[i] <= 10^4

思路:这题思路很简单,先取平均数,再累计求和判断。但是下面来看一段错误代码并且分析

//错误代码
class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& A) {
        int sum = accumulate(A.begin(), A.end(), 0);
        if(sum % 3 != 0) return false;
        int average = sum / 3, left = 0, right = A.size() - 1;
        int left_sum = 0, right_sum = 0;

        while(left < right) {
            if(left_sum != average) left_sum += A[left++];
            if(right_sum != average) right_sum += A[right--];
            if(left_sum == average && right_sum == average) 
                return true;
        }
        return false;
    }
};

我想用双指针从头尾分别开始遍历,以left < right作为临界。请考虑一种情况:[-3, 0, 3],会发现在第一次进入while时候,left_sumright_sum 就已经等于average了,不会进行累计操作。请看正确的代码:

代码:

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& A) {
        int sum = accumulate(A.begin(), A.end(), 0);
        if(sum % 3 != 0) return false;
        int target = sum / 3;
        int n = A.size(), i = 0, cur = 0;
        while (i < n) {
            cur += A[i];	//先累加再判断
            if (cur == target) {
                break;
            }
            ++i;
        }
        if (cur != target) {
            return false;
        }
        int j = i + 1;
        while (j + 1 < n) {  // 需要满足最后一个数组非空
            cur += A[j];
            if (cur == target * 2) {
                return true;
            }
            ++j;
        }
        return false;
    }
};

# 169.多数元素

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

输入: [3,2,3] 输出: 3

示例 2:

输入: [2,2,1,1,1,2,2] 输出: 2

思路

本题有个很有意思的算法,参考评论区xinchen的发言:

摩尔投票法:

核心就是对拼消耗。

玩一个诸侯争霸的游戏,假设你方人口超过总人口一半以上,并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗,最差所有人都联合起来对付你(对应你每次选择作为计数器的数都是众数),或者其他国家也会相互攻击(会选择其他数作为计数器的数),但是只要你们不要内斗,最后肯定你赢。

最后能剩下的必定是自己人。

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums[0], count = 1;
        for (int i = 1; i < nums.size(); i++) {
            //混战,如果是自己人count++,如果是敌人count--
            if (n == nums[i]) count++;
            else {
                count--;
                if(count == 0) {
                    n = nums[i + 1];
                }
            }
        }
        return n;
    }
};