334. Increasing Triplet Subsequence - M 看smart 解法

Q:

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

A:
----------------------先从后往前找到该位置后面的最大的值---------再从前往后， 看其之前有没有值比他小，而且他又比后面的值小--------------------但是O(n)  space，需要进一步优化------------

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if(n<3)
            return false;
        vector<int> largerV(n, 0);
        int largestSoFar = nums.back(); // will error if nums is empty
        for(int i = n-1;i >=0; --i)
        {
            largerV[i]=largestSoFar;
            largestSoFar = max(largestSoFar, nums[i]);
        }
        int minBefore = nums[0];
        for(int i = 1; i<n-1;i++)
        {
            if(nums[i] > minBefore and nums[i] < largerV[i])
            {
                return true;
            }
            minBefore = min(minBefore, nums[i]);
        }
        return false;
    }
};

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

第一编扫描： 先对每一个位置，确认有个value比他小。 做个标记

第二遍扫描： 确认之前比他小的value都被做了标记

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
        if(n < 3){
            return false;
        }
        vector<bool> hasPreI(n,false);
        int minPre = nums[0];
        
        int firstJ = -1;
        for(int i =1;i<n;++i){
            if(nums[i]>minPre){
                hasPreI[i] = true;
                if(firstJ < 0){
                    firstJ = i;
                }
            }
            minPre = min(minPre, nums[i]);
        }
        if(firstJ <0){
            return false;
        }
        // now go find the 2nd round
        int minJ = nums[firstJ];
        for(int k = firstJ ; k<n;++k){
            if( nums[k] > minJ){
                return true;
            }
            if(hasPreI[k]){
                minJ = min(minJ, nums[k]);
            }
        }
        return false;
    }
};

---------------- Greedy --------------------------
这个思路是使用两个指针m1和m2，初始化为整型最大值，我们遍历数组，
如果m1大于等于当前数字，则将当前数字赋给m1；
如果m1小于当前数字且m2大于等于当前数字，那么将当前数字赋给m2，
一旦m2被更新了，说明一定会有一个数小于m2，那么我们就成功的组成了一个长度为2的递增子序列，所以我们一旦遍历到比m2还大的数，我们直接返回ture。
如果我们遇到比m1小的数，还是要更新m1，有可能的话也要更新m2为更小的值，毕竟m2的值越小，能组成长度为3的递增序列的可能性越大，

------------------这里的关键点是， 要 <=  

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        int smallest = INT_MAX;// the smallest we see now
        int second_small = INT_MAX;//update when find value k==> m1 < k < m2 (but already bigger than the smallest--m1 )
        for(auto k : nums){
            if(k <= smallest){
                smallest = k;
            }else if(k<=second_small){
                second_small = k;
            }else{
                return true;
            }
        }
        return false;
    }
};

344. Reverse String E

Q:

Write a function that takes a string as input and returns the string reversed.

Example:
Given s = "hello", return "olleh".

A:

class Solution {
public:
    void reverseString(vector<char>& s) {
        int i =0, j = s.size()-1;
        while(i<j){
            swap(s[i],s[j]);
            ++i;
            --j;
        }
    }
};

337. House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.
A:
首先：就是遍历一遍。然后考虑2种情况。 取或者不取 node。
要防止多次（重复）遍历。 有个简单的方法，就是用hash. 这里，我们用hashMap来保存结果

/**
 * 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 rob(TreeNode* root) {
        if(not root)
            return 0;
        if(M.find(root) != M.end())
            return M[root];
        
        int withRoot = root->val + (root->left? rob(root->left->left) + rob(root->left->right) :0 )+ \
            (root->right ? rob(root->right->left) + rob(root->right->right) : 0);
        int noRoot = rob(root->left) + rob(root->right);
        M[root] = max(withRoot, noRoot);
        return M[root];
    }
private:
    unordered_map<TreeNode*, int> M;
};

Mistakes:
1：  withRoot 计算的时候， 三目运算符， 要括起来。  

338. Counting Bits - M

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

A:
 就是利用：每当一个bit 上赋值 1 之后。 是其前面的所有的重复。

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num+1,0);
        int end = 1; // end is exclusive
        while(end<=num)
        {
            for(int i = end; i< min(2*end, num+1); ++i)
                res[i] = 1+ res[i-end];
            end *= 2;
        }
        return res;
    }
};

Mistakes：

342. Power of Four

Q:

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

A:

********  use recursion ***************

public class Solution {
    public boolean isPowerOfFour(int num) {
        if(num<=0)
            return false;
        if(num == 1)
            return true;
        return num%4==0 && isPowerOfFour(num / 4);
    }
}

*******  Use Set  **********  but this is not smart enough *********

public class Solution {
    public boolean isPowerOfFour(int num) {
        Set<Integer> set = new HashSet();
        int a =1;
        for(int i =0; i<16;i++){
            set.add(a);
            a *= 4;
        }
        return set.contains(num);
    }
}

**********  借助了  power of two 的idea， 然后做了一层包装**************

public class Solution {
    public boolean isPowerOfFour(int num) {
        int mask = 0xAAAAAAAA;
        return (( mask & num )== 0 ) && isPowerofTwo(num);
    }
    public boolean isPowerofTwo(int n){
        return (n>0) && ( n == 1 || ( (n & (n-1)) ==0 ));
    }
}

Mistakes:
method 3 , 想mask，想了半天。一开始是对的，后来给搞错了。

343. Integer Break

Q:

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: you may assume that n is not less than 2.

A:


 就是按照3 来区分。 主要是 * 3 比  *2 要给出更多product。 而且sum里损失的也少。

public class Solution {
    public int integerBreak(int n) {
        return helper(n,true); 
    }
    public int helper(int n, boolean isMustDecode){
        if( n<=3 ){
            return isMustDecode? n-1 : n;
        }
        // we only care about 2 and 3 as potential decoposation
        if(n>4)
            return 3*helper(n-3, false);
        else if(n == 3 )
            return 3 ;
        else // n == 4 or 2 or 1
            return n;
    }
}