MISC

• 比较两棵二叉树是否相同Same Tree
  Python版本：

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if p is None and q is None:
            return True
        
        if p is None or q is None:
            return False
        
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

C++ 版本：

class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode *q) {
        if ((p == NULL) && (q == NULL))
            return true;
        else if ((p == NULL) || (q == NULL))
            return false;
        else if (p->val != q->val)
            return false;
        else
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

• Find All Numbers Disappeared in an Array
  遍历两遍，第一遍标记哪些数出现过（对应index上的值变成负数），第二遍找未出现的数（即数组中为正的下标+1）

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (size_t i = 0; i < nums.size(); ++i) {
            size_t idx = abs(nums[i]) - 1;
            nums[idx] = nums[idx] > 0 ? -nums[idx] : nums[idx];
        }
        
        vector<int> res;
        for (size_t i = 0; i < nums.size(); ++i) {
            if (nums[i] > 0)
                res.push_back(i + 1);
        }
        return res;
    }
};

• Can Place Flowers
  0/1数组里，判断能否实现在0的位置不相邻地插入n个1，任意两个1不能连在一起

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        if (n == 0) return true;
        
        int plot_num = flowerbed.size();
        if (plot_num <= 0) return false;
        
        // 先找出1的位置
        vector<int> flower_index;
        for(int i=0; i < plot_num; ++i) {
            if (flowerbed[i])
                flower_index.push_back(i);
        }
        
        // 判断两个1之间的0，能插入多少个1
        int flower_num = flower_index.size();
        int max_available = 0;
        if (0 == flower_num) {
            max_available = (plot_num + 1) / 2;
        } else if (1 == flower_num) {
            max_available = flower_index[0] / 2 + (plot_num - flower_index[0] - 1) / 2;
        } else {
            max_available += flower_index[0] / 2;
            for (int i = 0; i < flower_num - 1; ++i) {
                int zero_n = flower_index[i+1] - flower_index[i] - 1;
                if (zero_n > 0) {
                    max_available += (zero_n - 1) / 2;
                }
            }
            max_available += (plot_num - flower_index[flower_num - 1] - 1) / 2;
        }
        
        return max_available >= n;
    }
};

• Degree of an Array

// 笨办法，后面再看看有没有好办法
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1) return n;
        
        map<int, int> count, start_idx, end_idx;
        int degree = -1;
        for (int i = 0; i < n; ++i) {
            int val = nums[i];
            if (count.find(val) == count.end()) {
                count.insert(make_pair(val, 1));
            } else {
                count[val] += 1;
            }
            
            if (start_idx.find(val) == start_idx.end()) {
                start_idx.insert(make_pair(val, i));
                end_idx.insert(make_pair(val, i));
            } else {
                end_idx[val] = i;
            }
            if (count[val] > degree)
                degree = count[val];
        }
        
        int minLen = n;
        for (map<int, int>::iterator it = count.begin(); it != count.end(); ++it) {
            int val = it->first;
            if (it->second == degree) {
                int curLen = end_idx[val] - start_idx[val] + 1;
                if (curLen < minLen)
                    minLen = curLen;
            }
        }
        
        return minLen;
    }
};