Day 99, ##, Fraction to Recurring Decimal, Majority Element, Majority Number II

Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,

• Given numerator = 1, denominator = 2, return "0.5".
• Given numerator = 2, denominator = 1, return "2".
• Given numerator = 2, denominator = 3, return "0.(6)".

---------------------------------------------
Map 里面记录是某一个数的开始的index
reference
注意正负号跟溢出，casting long long
27行，先存map，再乘10

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        string rt = "";
        
        if ((numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0)) {
            rt = "-";
        }
        
        long long dividend = abs((long long)numerator);
        long long divisor = abs((long long)denominator);
        rt += to_string(dividend / divisor);
        
        dividend %= divisor;
        if (dividend == 0) return rt;
        
        rt += '.';
        unordered_map<int,int> mapping;
        
        while (dividend != 0) {
            if (mapping.find(dividend) != mapping.end()) {
                rt.insert(mapping[dividend],"(");
                rt += ")";
                return rt;
            }
            mapping[dividend] = rt.size();
            dividend *= 10;
            rt += to_string(dividend / divisor);
            dividend %= divisor;
        }

        return rt;
    }
};

In Java, updated on Feb-13th-2019

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) return "0";
        StringBuilder sb = new StringBuilder();
        
        if ((numerator < 0 && denominator > 0) || (numerator > 0 && denominator < 0)) {
            sb.append("-");
        }
        
        long num = Math.abs((long)numerator);
        long den = Math.abs((long)denominator);
        
        sb.append(num / den);
        num %= den;
        if (num == 0) return sb.toString();
        sb.append(".");
        
        Map<Long, Integer> map = new HashMap<>();
        map.put(num, sb.length());
        
        while (num > 0) {
            num *= 10;
            sb.append(num / den);
            num %= den;
            if (map.containsKey(num)) {
                sb.insert(map.get(num),"(");
                sb.append(")");
                return sb.toString();
            }
            
            map.put(num, sb.length());
        }
        
        return sb.toString();
    }
}

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
-----------------------------------------------------
fact: we are given an array with a majority element in it.
每次都丢掉2个不同数，majority最后肯定会被留下来

class Solution {
public:
    int majorityElement(vector<int> &num) {
        int count = 1;
        int countElem = num[0];
        
        for (int i = 1; i < num.size(); i++) {
            if (count == 0) {
                countElem = num[i];
                count++;
                continue;
            }
            if (countElem == num[i]) {
                count++;
            }else {
                count--;
            }
            
        }
        
        return countElem;
    }
};

Majority Number II 

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.
Find it.

Note

There is only one majority number in the array

Example

For [1, 2, 1, 2, 1, 3, 3] return 1

-------------------------------------
每次都丢掉3个不同的数，最后超过1/3的肯定会被留下来
最后还要重新对留下来的2个数重新计数，因为超1/3的数可能会被过度消耗
举例：1，1，1，1，2，2，3，3，4，4，4

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: The majority number occurs more than 1/3.
     */
    int majorityNumber(vector<int> nums) {
        // write your code here
        int count_1 = 1, count_2 = 0;
        int cand_1 = nums[0], cand_2;
        
        for (int i = 1; i < nums.size(); i++) {
            if (count_1 == 0 && cand_2 != nums[i]) {
                count_1 = 1;
                cand_1 = nums[i];
                continue;
            }
            if (count_2 == 0 && cand_1 != nums[i]) {
                count_2 = 1;
                cand_2 = nums[i];
                continue;
            }
            
            if (nums[i] != cand_1 && nums[i] != cand_2) {
                count_1--;
                count_2--;
            }
            
            if (nums[i] == cand_1) {
                count_1++;
            }
            if (nums[i] == cand_2) {
                count_2++;
            }
        }
        
        count_1 = 0;
        count_2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == cand_1) count_1++;
            if (nums[i] == cand_2) count_2++;
        }
        
        if (count_1 > count_2) {
            return cand_1;
        }else {
            return cand_2;
        }
    }
};