Math - Medium

Happy Number

覚えてるのはUnhappy Number.^^

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> s = new HashSet<Integer>();
        
        int cur = n;
        int val = 0;
        
        while (cur >= 10) {
            val += (cur%10) * (cur%10);
            cur = cur / 10;
        }
        
        val += cur * cur;
        
        if (val == 1) {
            return true;
        } else if (! s.add(val)) {
            return false;
        } else {
            return isHappy(val);
        }
    }
}

Time limit exceeded

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> list = new HashSet<Integer>();
        
        int start = n;
        int end = squared(n);
        
        while (end != 1 && start != end) {
            start = squared(start);
            end = squared(squared(end));
        }
        
        return end == 1;
    }
    
    private int squared(int n) {
        int val = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            val = val + d * d;
        }
        return val;
    }
}

Factorial Trailing Zeros

class Solution {
    public int trailingZeroes(int n) {
        int five = 0;
        
        while (n / 5 >= 1) {
            five += n / 5;
            n = n / 5;
        }
        
        return five; 
        
    }
}

見るからにファクトリーエッグなので5個まで数えました.

class Solution {
    public int trailingZeroes(int n) {
        int five = 0;
        int fiven = n;
        
        while (fiven / 5 >= 1) {
            five = five + fiven / 5;
            fiven = fiven / 5;
        }
        
        return five;
    }
}

前回も同じように解けたのかな…^^

Excel Sheet Column Number

class Solution {
    public int titleToNumber(String s) {
        
        int total = 0; 
        int pow = 1; 
        for (int i = s.length() - 1; i >= 0; i--) {
            
            int val = s.charAt(i) - 'A' + 1;
            total += val * pow;
            pow = pow * 26;
        }
        
        return total;
    }
}

わぁ~~~今日のはすぐ過ぎてよかった^^

class Solution {
    public int titleToNumber(String s) {
        int length = s.length();
        int total = 0;
        int multiple = 1;
        for (int i = s.length() - 1; i >= 0; i--) {
            total += (s.charAt(i) - 'A' + 1) * multiple;
            multiple = multiple * 26;
        }
        return total;
    }
}

解くように??変数名のみ変更します.

Pow(x, n)

class Solution {
    public double myPow(double x, int n) {
        //보자마자 binary 생각나는데.. 어떻게 해야할지 모르겠네요^^
        
        if (n < 0) {
            x = 1 / x;
            n = n * -1;
        }
        
        if (n == 0) {
            return 1;
        } else {
            double half = myPow(x, n/2);
            
            if (n%2 == 0) {
                return half * half;
            } else {
                return half * half * x;
            }
        }
    }
}

Overflow炊き込みご飯...ぼそぼそ

class Solution {
    public double myPow(double x, int n) {
        //보자마자 binary 생각나는데.. 어떻게 해야할지 모르겠네요^^
        
        if (n == 0) {
            return 1;
        } else {
            double half = myPow(x, n/2);
            
            if (n%2 == 0) {
                return half * half;
            } else {
                if (n > 0) {
                    return half * half * x;
                } else {
                    return half * half / x;
                }
            }
        }
    }
}

Overflowは極度に嫌悪しているので、解決策を参考にしてください...

class Solution {
    public double myPow(double x, int n) {
        
        if (n == 0) {
            return 1.0;
        }
        
        long N = n;
        
        if (N < 0) {
            x = 1 / x;
            N = -N; 
        }
        
        double result = 1; 
        

        
        double multiple = x; 
        while(N > 0) {
            if (N % 2 == 1) {
                result = result * multiple;
            }
            
            multiple = multiple * multiple; 
            
            N = N / 2;
        }
        
        return result; 
    }
}

以前はlongでオーバーフローを避けていました.

Sqrt(x)

class Solution {
  public int mySqrt(int x) {
    if (x < 2) return x;

    long num;
    int pivot, left = 2, right = x / 2;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      num = (long)pivot * pivot;
      if (num > x) right = pivot - 1;
      else if (num < x) left = pivot + 1;
      else return pivot;
    }

    return right;
  }
}

binary search

class Solution {
    public int mySqrt(int x) {
        if (x < 2) return x;
        
        double x0 = x;
        double x1 = (x0 + x / x0) / 2.0;
        
        while (Math.abs(x0 - x1) >= 1) {
            x0 = x1;
            x1 = (x0 + x / x0) / 2.0;
        }
        
        return (int)x1; 
    }
}

彼はこれが一番速いと言った.

class Solution:
    def mySqrt(self, x: int) -> int:
        return int(sqrt(x))
        

過去の私良心が真実?^^

Divide Two Integers

ああ

class Solution {
    private static int HALF_INT_MIN = -1073741824;// -2**30;

public int divide(int dividend, int divisor) {

    // Special case: overflow.
    if (dividend == Integer.MIN_VALUE && divisor == -1) {
        return Integer.MAX_VALUE;
    }

    /* We need to convert both numbers to negatives.
     * Also, we count the number of negatives signs. */
    int negatives = 2;
    if (dividend > 0) {
        negatives--;
        dividend = -dividend;
    }
    if (divisor > 0) {
        negatives--;
        divisor = -divisor;
    }

    ArrayList<Integer> doubles = new ArrayList<>();
    ArrayList<Integer> powersOfTwo = new ArrayList<>();

    /* Nothing too exciting here, we're just making a list of doubles of 1 and
     * the divisor. This is pretty much the same as Approach 2, except we're
     * actually storing the values this time. */
    int powerOfTwo = -1;
    while (divisor >= dividend) {
        doubles.add(divisor);
        powersOfTwo.add(powerOfTwo);
        // Prevent needless overflows from occurring...
        if (divisor < HALF_INT_MIN) {
            break;
        }
        divisor += divisor;
        powerOfTwo += powerOfTwo;
    }

    int quotient = 0;
    /* Go from largest double to smallest, checking if the current double fits.
     * into the remainder of the dividend. */
    for (int i = doubles.size() - 1; i >= 0; i--) {
        if (doubles.get(i) >= dividend) {
            // If it does fit, add the current powerOfTwo to the quotient.
            quotient += powersOfTwo.get(i);
            // Update dividend to take into account the bit we've now removed.
            dividend -= doubles.get(i);
        }
    }

    /* If there was originally one negative sign, then
     * the quotient remains negative. Otherwise, switch
     * it to positive. */
    if (negatives != 1) {
        return -quotient;
    }
    return quotient;
}
}

Fraction to Recurring Decimal

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) {
        return "0";
    }
    StringBuilder fraction = new StringBuilder();
    // If either one is negative (not both)
    if (numerator < 0 ^ denominator < 0) {
        fraction.append("-");
    }
    // Convert to Long or else abs(-2147483648) overflows
    long dividend = Math.abs(Long.valueOf(numerator));
    long divisor = Math.abs(Long.valueOf(denominator));
    fraction.append(String.valueOf(dividend / divisor));
    long remainder = dividend % divisor;
    if (remainder == 0) {
        return fraction.toString();
    }
    fraction.append(".");
    Map<Long, Integer> map = new HashMap<>();
    while (remainder != 0) {
        if (map.containsKey(remainder)) {
            fraction.insert(map.get(remainder), "(");
            fraction.append(")");
            break;
        }
        map.put(remainder, fraction.length());
        remainder *= 10;
        fraction.append(String.valueOf(remainder / divisor));
        remainder %= divisor;
    }
    return fraction.toString();
}
}

hfewkogewkqdgfewqkfdghqewkowdghewkoqedh