Excel Sheet Column Title, Excel Sheet Column Number, Number of Digit One, Count Primes, Perfect Squares, Ugly Number, Ugly Number II, Power of Two, Add Digits, Happy Number, Missing Number

Posted on 2015-10-15   |   In 刷题   |  

Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
1 -> A
2 -> B
3 -> C
…
26 -> Z
27 -> AA
28 -> AB

Solution

  • n— mod 26 gives the current last digit value
  • n— / 26 gives the number for substring(0,len-1)
1
2
3
4
5
6
7
8
9
public String convertToTitle(int n) {
    String res="";
    while(n!=0){
        n--;
        res=(char)('A'+n%26)+res;
        n/=26;
    }
    return res;
}

Excel Sheet Column Number

Related to question Excel Sheet Column Title
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28

Solution

1
2
3
4
5
6
7
public int titleToNumber(String s) {
    int n=0;
    for(int i=0; i<s.length();i++){
        n=n*26 + s.charAt(i)-'A' + 1;
    }
    return n;
}

Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Naive Solution

LTE

1
2
3
4
5
6
7
8
9
10
11
public int countDigitOne(int n) {
    int totalcount=0;
    for(int i=1;i<=n;i++){
        int cur=i;
        while(cur>0){
            if(cur%10==1) totalcount++;
            cur/=10;
        }
    }
    return totalcount;
}

Mathy Solution

  • Observation: looking at each digit, 1 appears 1 time on digit 1, 10 times on digit 2, 100 times on digit 3…
  • Three cases when counting 1 on digit 3 : for 1131, 11-31 we have 1100+31+1;for 1231, 12-31 we have (1+1)100; for 1031, 10-31 we have 1*100
1
2
3
4
5
6
7
8
9
public int countDigitOne(int n) {
    int totalcount=0;
    for(long i=1;i<=n;i*=10){
        long left=n/i; long right=n%i;
        totalcount+= (left+8)/10 * i;
        if(left%10==1) totalcount+=right+1;
    }
    return totalcount;
}

Count Primes

Description: Count the number of prime numbers less than a non-negative number, n.

Naive Solution

LTE

1
2
3
4
5
6
7
8
9
10
11
12
13
public int countPrimes(int n) {
    int count=0;
    for(int i=2;i<n;i++){
        if(checkprime(i)) count++;
    }
    return count;
}
public boolean checkprime(int x){
    for(int i=2;i<x;i++){
        if(x%i==0) return false;
    }
    return true;
}

DP solution

  • record dp[ij] as not prime for each i and ij pair less than n 
1
2
3
4
5
6
7
8
9
10
11
public int countPrimes(int n) {
    int count=0;
    boolean[] notPrime = new boolean[n];
    for(int i=2;i<n;i++){
        if(!notPrime[i]) count++;
        for(int j=2; i*j<n; j++){
            notPrime[i*j] = true;
        }
    }
    return count;
}

Perfect Square

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

DFS Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int numSquares(int n) {
    int uppernum = (int)Math.sqrt(n) + 1;
    int[] minlen= {Integer.MAX_VALUE};
    dfs(n, uppernum, 1, new ArrayList<Integer>(),minlen,0);
    return minlen[0];
}
public void dfs(int n, int uppernum, int start, ArrayList<Integer> list, int[] minlen, int cursum){
    if(list.size()>=minlen[0] || cursum>n){
        return;
    }
    if(cursum==n){
        minlen[0]=Math.min(minlen[0], list.size());
        return;
    }
    for(int i=start; i<=uppernum; i++){
        list.add(i);
        dfs(n, uppernum, i, list, minlen, cursum+i*i);
        list.remove(list.size()-1);
    }
}

DP Solution

  • dp[i] records the least number of squares used to sum to i
1
2
3
4
5
6
7
8
9
10
11
12
13
public int numSquares(int n) {
    int[] dp = new int[n+1];
    for(int i=1; i< dp.length; i++){
        dp[i]=Integer.MAX_VALUE;
    }
    dp[0]=0;
    for(int i=0; i<=n; i++){
        for(int j=1; (i+j*j) <= n ; j++){
            dp[i+j*j] = Math.min(dp[i]+1, dp[i+j*j]);
        }
    }
    return dp[n];
}

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.

Naive Solution

LTE

1
2
3
4
5
6
7
8
public boolean isUgly(int num) {
    if(num==1) return true;
    long n = Math.abs(num);
    for(int i=2; i<n; i++){
        if(n%i==0 && i!=2 && i!=3 && i!=5) return false;
    }
    return true;
}

DP Solution

1
2
3
4
5
6
7
8
public boolean isUgly(int num) {
    for(int i=2; i<6 &&num>0; i++){
        while(num%i==0){
            num/=i;
        }
    }
    return num==1;
}

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:
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.
An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
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.
Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 2, L2 3, L3 * 5).

Solution

  • //(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
  • //(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
  • //(3) 1×5, 2×5, 3×5, 4×5, 5×5, …
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int nthUglyNumber(int n) {
        int a=2, b=3, c=5;
        int pa=0, pb=0, pc=0;
        int[] dp=new int[n];
        dp[0]=1;
        for(int i=1; i<n; i++){
            dp[i]=Math.min(Math.min(a,b),c);
            if(dp[i]==a){
                pa++;
                a=2*dp[pa];
            }
            if(dp[i]==b){
                pb++;
                b=3*dp[pb];
            }
            if(dp[i]==c){
                pc++;
                c=5*dp[pc];
            }
        }
        return dp[n-1];
    }

Power of Two

Given an integer, write a function to determine if it is a power of two.

Solution

1
2
3
4
5
6
7
8
public boolean isPowerOfTwo(int n) {
    if(n==1) return true;
    while(n>1){
        if(n%2!=0) return false;
        n/=2;
    }
    return n==1;
}
1
2
3
public boolean isPowerOfTwo(int n) {
    return (n>0) &&  (n & (n-1))==0;
}

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:
A naive implementation of the above process is trivial. Could you come up with other methods?
What are all the possible results?
How do they occur, periodically or randomly?
You may find this Wikipedia article useful.

Solution

1
2
3
4
5
6
7
8
9
public int addDigits(int num) {
    if(num/10==0) return num;
    int cur=0;
    while(num>0){
        cur+=num%10;
        num/=10;
    }
    return addDigits(cur);
}

Or make the following observation:
Supposed the digit is 534 , it equals (5x100 + 3x 10 +4) ,when it % 9 ,that is (5x100 + 3x 10 +4) %9 = ( (5x100 ）%9+ (3x10)%9 +4%9)%9 = (5+3+4)%9 = (12)%9 = (1x10+2)%9 = (1+2)%9 = 3
Or…
in out in out
0 0 10 1
1 1 11 2
2 2 12 3
3 3 13 4
4 4 14 5
5 5 15 6
6 6 16 7
7 7 17 8
8 8 18 9
9 9 19 1
根据上面的列举，我们可以得出规律，每9个一循环，所有大于9的数的树根都是对9取余，那么小于等于9的数对9取余就是0了，为了得到其本身，而且同样也要对大于9的数适用，我们就用(n-1)%9+1这个表达式来包括所有的情况…
out = (num - 1) % 9 + 1

1
2
3
public int addDigits(int num) {
    return num>0 ? (num%9==0 ? 9 : num%9) : 0;
}

Happy Number

Write an algorithm to determine if a number is “happy”.
A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.
Example: 19 is a happy number
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean isHappy(int n) {
    HashSet<Integer> hs = new HashSet<Integer>();
    while(hs.add(n)){
        int cur = 0;
        while(n>0){
            cur+= Math.pow(n%10, 2);
            n/=10;
        }
        if(cur==1) return true;
        n=cur;
    }
    return false;
}

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?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int missingNumber(int[] nums) {
    for(int i=0; i<nums.length; i++){
        if(i!=nums[i] && nums[i]<nums.length){
            int tmp=nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = tmp;
            i--;
        }
    }   
    for(int i=0; i<nums.length; i++){
        if(i!=nums[i]) return i;
    }
    return nums.length;
}
#Math #String #Bit Manipulation
Divide Two Integers, Fraction to Recurring Decimal