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 ---E

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

 

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.

Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.

 

Constraints:

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 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];
    }
};

------------------------第二遍----------------

class Solution {

public:

int minCostClimbingStairs(vector<int>& cost) {

int n = cost.size();

int pre=0, prepre = 0;

for(int i =0; i<n;i++){

int cur = cost[i] + min(pre, prepre);

prepre = pre;

pre = cur;

}

return min(pre, prepre);

}

};

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 好了。怎么办