Day 121, #264, #263, #242, #257, #258, #268, #260 Ugly Number II, Ugly Number, Valid Anagram, Binary Tree Paths, Add Digits, Missing Number, Single Number III

Ugly Number II  

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:

1. The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
2. An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
3. The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
4. Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).

----------------------------------------------------
ref: http://www.geeksforgeeks.org/ugly-numbers/
COME_BACK
1 * 2, 2 * 2, 3 * 2, 4 * 2, 5 * 2, 6 * 2, 8 * 2...
1 * 3, 2 * 3, 3 * 3, 4 * 3, 5 * 3, 6 * 3, 8 * 3...
1 * 5, 2 * 5, 3 * 5, 4 * 5, 5 * 5, 6 * 5, 8 * 5...
这题要点在把上面3个list排序，而且上面的序号也是根据ugly number来增加，并不是每次都+ 1，所以要用一个vector来记录出现过的ugly number
p2, p3, p5分别指向3个list

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> ugly(n);
        ugly[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        
        for (int i = 1; i < n; i++) {
            int nextUgly = min(ugly[p2] * 2,min(ugly[p3] * 3,ugly[p5] * 5));
            
            if (nextUgly == ugly[p2] * 2) {
                p2++;
            }
            if (nextUgly == ugly[p3] * 3) {
                p3++;
            }
            if (nextUgly == ugly[p5] * 5) {
                p5++;
            }
            ugly[i] = nextUgly;
        }
        
        return ugly[n - 1];
    }
};

Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

------------------------------------------------

class Solution {
public:
    bool isUgly(int num) {
        if (num == 1) return true;
        while (true) {
            int t = num;
            if (num % 2 == 0) {
                num /= 2;
            }
            if (num % 3 == 0) {
                num /= 3;
            }
            if (num % 5 == 0) {
                num /= 5;
            }
            if (num == t) return false;
            if (num == 1) return true;
        }
    }
};

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

--------------------------------------------------------------

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;
        vector<int> dp(256,0);
        for (int i = 0; i < s.length(); i++) {
            dp[s[i]]++;
        }
        
        for (int i = 0; i < t.length(); i++) {
            if (dp[t[i]] == 0) return false;
            dp[t[i]]--;
        }
        
        return true;
    }
};

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

-------------------------------------------------------

/**
 * 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:
    void helper(vector<string> &rt, TreeNode *root, string path) {
        if (root->left == NULL && root->right == NULL) {
            rt.push_back(path + to_string(root->val));
        }
        if (root->left != NULL) {
            helper(rt,root->left,path + to_string(root->val) + "->");
        }
        if (root->right != NULL) {
            helper(rt,root->right,path + to_string(root->val) + "->");
        }
    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> rt;
        if (root == NULL) return rt;
        
        helper(rt,root,"");
        return rt;
    }
};

Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Hint:

1. A naive implementation of the above process is trivial. Could you come up with other methods?
2. What are all the possible results?
3. How do they occur, periodically or randomly?
4. You may find this Wikipedia article useful.

--------------------------------------------------------

class Solution {
public:
    int addDigits(int num) {
        if (num == 0) return 0;
        return num - (num - 1) / 9 * 9;
    }
};

Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

---------------------------------------------------------
类似first missing positive

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            int target = nums[i];
            while (target >= 0 && target < nums.size() && nums[target] != target) {
                swap(nums[i],nums[target]);
                target = nums[i];
            }
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (i != nums[i]) return i;
        }
        return nums.size();
    }
};

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

---------------------------------------------------------------
ref：https://leetcode.com/discuss/52351/accepted-java-space-easy-solution-with-detail-explanations
一路xor下来，最后结果肯定是2个不同数的xor结果，所以2进制上肯定包含1
任意取一位1，根据此1将array里的数划分为2半，每一半各包含一个只出现一次的数

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> rt(2,0);
        int xorNum = 0;
        for (int i = 0; i < nums.size(); i++) {
            xorNum ^= nums[i];
        }
        xorNum &= -xorNum;
        for (int i = 0; i < nums.size(); i++) {
            if ((xorNum & nums[i]) == 0) {
                rt[0] ^= nums[i];
            }else {
                rt[1] ^= nums[i];
            }
        }
        
        return rt;
    }
};