Happy 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;
}
}똑같이 푼듯??? variable 이름만 바뀌고
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으로 해서 overflow를 피했네요
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
y