844. Backspace String Compare (easy)

Q:

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

1. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

A:

就是从后往前比较，  同时用一个指针记录位置  （比较tricky,多练几遍）

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int is = S.length()-1;
        int it = T.length()-1;
        int cc = 0;
        while(is>=0 || it>=0)  // using && will omit case of S= "a#" T=""
        {
            cc = 0;
            while(is>=0 && ( S[is]=='#' || cc>0))
            {
                if(S[is] =='#')
                {
                    cc++;
                }else{
                    cc--;
                }            
                is--;
            }

            cc = 0;
            while(it>=0 && ( T[it]=='#' || cc>0))
            {
                if(T[it] =='#')
                {
                    cc++;
                }else{
                    cc--;
                }        
                it--;    
            }
            // now both are valid, do compare now.
            if(is<0 && it<0)
                return true;
            if(is<0 || it<0)
                return false;
            if(S[is] != T[it])
                return false;
            is--;
            it--;        
        }
        return is<0 && it<0; // not both index are out of range
    }
};

896. Monotonic Array (easy)

Q:

An array is monotonic if it is either monotone increasing or monotone decreasing.

An array A is monotone increasing if for all i <= j, A[i] <= A[j].  An array A is monotone decreasing if for all i <= j, A[i] >= A[j].

Return true if and only if the given array A is monotonic.

Example 1:

Input: [1,2,2,3]
Output: true

Example 2:

Input: [6,5,4,4]
Output: true

Example 3:

Input: [1,3,2]
Output: false

Example 4:

Input: [1,2,4,5]
Output: true

Example 5:

Input: [1,1,1]
Output: true

Note:

1. 1 <= A.length <= 50000
2. -100000 <= A[i] <= 100000

A:

class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        int n = A.size();
        if(n==0)
            return true;
        if(A[0] <= A[n-1])
        {
            return checkIncrease(A);
        }else{
            return checkDecrease(A);
        }
    }
private:
    bool checkIncrease(vector<int> &A)
    {
        for(int i =0;i<A.size()-1;++i)
        {
            if(A[i]>A[i+1])   
                return false;
        }
        return true;
    }
    bool checkDecrease(vector<int> &A)
    {
        for(int i =0;i<A.size()-1;++i)
        {
            if(A[i]<A[i+1])
                return false;
        }
        return true;
    }
};

746. Min Cost Climbing Stairs (easy)

Q:

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

1. cost will have a length in the range [2, 1000].
2. Every cost[i] will be an integer in the range [0, 999].

A:

这个的主要的坑，就是一开始没有注意到， 最后一节也是要爬的，因为，目标是走上floor

-------------简单的 DP -----

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // at the last step, we need also climb,  fuck
        int n = cost.size();
        vector<int> vec(n+2, INT_MAX);  //extra as floor, as we need move last step
        vec[0] = 0;
        vec[1] = 0;
        // for each step, calculate the ones that it can reach        
        for(int i =0;i<n;i++)
        {
            vec[i+1] = min(vec[i+1], cost[i]+vec[i]);
            vec[i+2] = min(vec[i+2], cost[i]+vec[i]);
        }
        return vec[n];
    }
};

717. 1-bit and 2-bit Characters (easy)

Q:

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Example 1:

Input: 
bits = [1, 0, 0]
Output: True
Explanation: 
The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.

Example 2:

Input: 
bits = [1, 1, 1, 0]
Output: False
Explanation: 
The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.

Note:

1 <= len(bits) <= 1000.

bits[i] is always 0 or 1.

A:

本以为 需要DP， 结果不用。  

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        return helper(bits, 0);            
    }
private:
    bool helper(vector<int> &bits, int i)
    {
        int n = bits.size();
        if(i>=n)
            return false;
        if(i==n-1)
            return bits[i]==0;
        // we have at least two bits
        if(bits[i]==0){
            return helper(bits,i+1);
        }else{
            return helper(bits, i+2);
        }
    }
};

693. Binary Number with Alternating Bits (easy)

Q:

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Example 1:

Input: 5
Output: True
Explanation:
The binary representation of 5 is: 101

Example 2:

Input: 7
Output: False
Explanation:
The binary representation of 7 is: 111.

Example 3:

Input: 11
Output: False
Explanation:
The binary representation of 11 is: 1011.

Example 4:

Input: 10
Output: True
Explanation:
The binary representation of 10 is: 1010.

A:

记录前一个位置，并且每次对比

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int pre = (n&1)?0:1;
        while(n)
        {
            if(! (pre ^ (n&1)) ) 
            {
                return false;
            }
            pre = 1-pre;
            n = n>>1;
        }
        return true;
    }
};

记录前一个位置，并且每次对比

563. Binary Tree Tilt (easy)

Q:

Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes' tilt.

Example:

Input: 
         1
       /   \
      2     3
Output: 1
Explanation: 
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

Note:

1. The sum of node values in any subtree won't exceed the range of 32-bit integer.
2. All the tilt values won't exceed the range of 32-bit integer.

A:

思路就是，利用参数的传引用， 来返回两个数字 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int findTilt(TreeNode* root) {
        int s = 0;
        return helper(root, s);
    }
private:
    int helper(TreeNode* root, int & ss)
    {
        if(!root)
        {
            ss = 0;
            return 0;
        }
        int lsum = 0, rsum =0;
        int l = helper(root->left, lsum);
        int r = helper(root->right, rsum);
        ss = root->val + lsum + rsum;
        return l + r + abs(lsum-rsum);
    }
};

704. Binary Search (Easy)

Q:

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Note:

1. You may assume that all elements in nums are unique.
2. n will be in the range [1, 10000].
3. The value of each element in nums will be in the range [-9999, 9999].

A:

a,b is (a,b]   左闭开右开

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if(n==0)
            return -1;
        int a=0, b=n;
        while(a<b)
        {
            int mid = (a+b)/2;
            if(nums[mid] == target)
            {
                return mid;
            }else if(nums[mid] < target)
            {
                a = mid+1;
            }else
            {
                b = mid;
            }                
        }
        return -1;
        
    }
};

637. Average of Levels in Binary Tree

Q:

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Note:

1. The range of node's value is in the range of 32-bit signed integer.

A:

借用了两个数组，记录sum , and count;  

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        vector<int> count;
        helper(root, res, count, 1);
        for(int i =0;i<count.size(); i++)
        {
            res[i] /= count[i];
        }
        return res;
    }
private:
    void helper(TreeNode* root, vector<double> & res, vector<int> &count, int depth)
    {
        if(!root)
            return;
        if(res.size() < depth)
        {
            count.push_back(0);
            res.push_back(0);  // at most need one layer
        }
        res[depth-1] += root->val;
        count[depth-1] ++;
        helper(root->left, res, count, depth+1);
        helper(root->right, res,count, depth+1);
    }
};

借用了两个数组，记录sum , and count; 

581. Shortest Unsorted Continuous Subarray (easy)

Q:

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

1. Then length of the input array is in range [1, 10,000].
2. The input array may contain duplicates, so ascending order here means <=.

A:

首先找到左边和右边的不协调的地方。
然后在这个区间，找到最大最小的值。
然后再向两边扩展        （思路挺简单，可是就是写起来有点儿啰嗦）

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        int start = 0, end = n-1;
        // get the first that bigger than next
        bool isSorted = true;
        for(int i =0; i<n-1;++i){
            if(nums[i] > nums[i+1])
            {
                start = i;
                isSorted = false;
                break;
            }
        }
        if(isSorted)
            return 0;
        // count backward, get the first that smaller than previous one
        for(int i =n-1; i>0; --i){
            if(nums[i] < nums[i-1])
            {
                end = i;
                break;
            }
        }
        // get min and max value of that range
        int minn= nums[start]; // inclusive
        int maxx= minn;
        for(int i =start+1; i<=end; i++)
        {
            minn = min(minn, nums[i]);
            maxx = max(maxx, nums[i]);
        }        
        // now shrink        
        for(int i =start-1; i>=-1;--i)
        {
            if(i <0 || nums[i]<=minn)
            {
                start = i+1;
                break;
            }
        }
        for(int i = end+1; i<= n;++i)
        {
            if(i==n || nums[i] >= maxx)
            {
                end=i-1;
                break;
            }
        }
        return end-start +1;
    }
};

Mistakes:
   忘记检查如果全部已经sorted 好了。怎么办

437. Path Sum III (easy)

Q:

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

A:

这个是错的，具体是为什么呢？ 答案看最下方

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(!root)
            return 0;
        
        int endHere = sum == root->val? 1:0;
        return pathSum(root->left, sum-root->val) + 

               pathSum(root->right, sum-root->val) + 

               pathSum(root->left, sum) + 

               pathSum(root->right, sum) + endHere;
    }
};

my real solution:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(!root)
            return 0;
        
        return pathSum(root->left, sum) + 

               pathSum(root->right, sum) + 

               directSum(root,sum);
    }
private:
    int directSum(TreeNode* root, int sum)
    {
        if(!root)
            return 0;
        int endHere = sum==root->val?1:0;
        return directSum(root->left, sum-root->val) + directSum(root->right, sum-root->val) + endHere;
    }
};

为啥错呢？   因为在递归的时候，把一些路径计算了2次。

617. Merge Two Binary Trees (easy)

Q:

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input: 
 Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
      3
     / \
    4   5
   / \   \ 
  5   4   7

Note: The merging process must start from the root nodes of both trees.

A:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(!t1)
            return t2;
        if(!t2)
            return t1;
        auto l = mergeTrees(t1->left, t2->left);
        auto r = mergeTrees(t1->right, t2->right);
        auto *root = new TreeNode(t1->val + t2->val);
        root->left = l;
        root->right = r;
        return root;
    }
};

Mistakes:

        auto *root = new TreeNode(t1->val + t2->val);

这一句，一开始写的时候，错写成了
               TreeNode *root(t1->val + t2->val)
而且注意：这里的 new  是一定要写的。 否则，我们method

543. Diameter of Binary Tree

Q:

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

A:

 利用C++ 的参数reference type, 来完成 多个 返回值

看helper(     , int & maxDepth)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        // use reference to get the modified value from other function
        int dummy=0;
        return helper(root, dummy);
    }
private:
    int helper(TreeNode* root, int & maxDepth) // return the diameter of the tree
    {
        if(!root)
        {
            maxDepth = 0;
            return 0;
        }
        int leftDepth, rightDepth;
        int maxLeft = helper(root->left, leftDepth);
        int maxRight = helper(root->right, rightDepth);
        maxDepth = max(leftDepth, rightDepth) + 1;
        return max(maxLeft , max( maxRight, leftDepth + rightDepth) );        
    }
};