LintCode 刷题

java python LintCode 计算机

1. A + B Problem

Write a function that add two numbers A and B.

1.1 Example

Given a=1 and b=2 return 3.

1.2 Challenge

Of course you can just return a + b to get accepted. But Can you challenge not do it like that?(You should not use + or any arithmetic operators.)

1.3 KeyKnowledge

在计算机中，数字是以补码的形式存在的，计算也是用补码来进行计算，计算后的结果也是补码，可以参考图解 Java 位运算。

1.4 Java Code

public class Solution {
    /**
     * @param a: An integer
     * @param b: An integer
     * @return: The sum of a and b 
     */
    public int aplusb(int a, int b) {
        // write your code here
        if(b==0){
            return a;
        }
        int xor = a ^ b;
        int carry = (a & b) << 1;
        return aplusb(xor, carry);
    }
}

1.5 Python Code

- Reference: [不用加减乘除做加法.py][2]
- 因为python整形无限大，所以导致不能直接用java魔改，不然会很慢很慢很慢
- Total runtime: 302ms

class Solution:
"""
@param a: An integer
@param b: An integer
@return: The sum of a and b 
"""
def aplusb(self, a, b):
    # write your code here
    while b != 0:
        xor = a ^ b
        b = (a & b) << 1
        a = xor & 0xFFFFFFFF
    return a if a >> 31 == 0 else a - 4294967296

2. Trailing zeros

Write an algorithm which computes the number of trailing zeros in n factorial.

2.1 Example

11! = 39916800, so the out should be 2

2.2 Challenge

O(log N) time

只有2和5碰在一起的时候，才会有0，而5的个数远比0少，只要计算有多少5

25/5 = 5，5/5 = 1；5+1=6

2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，21，22，23，24，25

2.3 JAVA Code

class Solution:
    """
    @param: n: An integer
    @return: An integer, denote the number of trailing zeros in n!
    """
    def trailingZeros(self, n):
        # write your code here, try to do it without arithmetic operators.
        if n == 0:
            return 0
        count = 0
        while n > 0:
            n /= 5
            count += n
        return count

2.4 Python Code

public class Solution {
    /*
     * @param n: An integer
     * @return: An integer, denote the number of trailing zeros in n!
     */
    public long trailingZeros(long n) {
        // write your code here, try to do it without arithmetic operators.
        if(n == 1) {
            return 0;
        }
        int five = 0;   // 2出现的频率永远低于5，所以只要计算5就行了，一个5配一个2，才能有0
        for(long i = 5; n / i > 0; i *= 5) {//2,4,5,6,8,10,12,14,15,20
            five += n / i;
        }
        return five;
    }
}

6. Merge Two Sorted Arrays

Merge two given sorted integer array A and B into a new sorted integer array.

6.1 Example

A=[1,2,3,4]
B=[2,4,5,6]
return [1,2,2,3,4,4,5,6]

6.2 Challenge

How can you optimize your algorithm if one array is very large and the other is very small?

6.3 JAVA Code

public class Solution {
    /**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
    public int[] mergeSortedArray(int[] A, int[] B) {
        // write your code here
        int[] merge = new int[A.length + B.length];
        System.arraycopy(A,0, merge, 0, A.length);
        System.arraycopy(B, 0, merge, A.length, B.length);
        Arrays.sort(merge);
        return merge;
    }
}

6.4 Python Code

class Solution:
    """
    @param A: sorted integer array A
    @param B: sorted integer array B
    @return: A new sorted integer array
    """
    def mergeSortedArray(self, A, B):
        # write your code here
        C = A + B
        list.sort(C)
        return C

8. Rotate String

Given a string and an offset, rotate string by offset. (rotate from left to right)

8.1 Example

Given "abcdefg".

offset=0 => "abcdefg"
offset=1 => "gabcdef"
offset=2 => "fgabcde"
offset=3 => "efgabcd"

8.2 Challenge

Rotate in-place with O(1) extra memory.

8.3 JAVA Code

public class Solution {
    /**
     * @param str: An array of char
     * @param offset: An integer
     * @return: nothing
     */
    public void rotateString(char[] str, int offset) {
        // write your code here
        if(offset != 0 && str.length != 0) {
            offset %= str.length;
            if(offset != 0) {
                char[] copy = str.clone();
                for (int i = 0; i < offset; i++) {
                    str[i] = copy[str.length - offset + i];
                }
                for (int i = offset; i < str.length; i++) {
                    str[i] = copy[i - offset];
                }
            }
        }
    }
}

8.4 Python Code

class Solution:
    """
    @param str: An array of char
    @param offset: An integer
    @return: nothing
    """
    def rotateString(self, str, offset):
        # write your code here
        if len(str) != 0:
            offset %= len(str)
            if offset != 0:
                a = str[:-offset]
                b = str[-offset:]
                c = b + a
                #str.replace(b+a)
                for i, item in enumerate(str):
                    str[i] = c[i]

37. Reverse 3-digit Integer

Reverse a 3-digit integer.

37.1 Example

Reverse 123 you will get 321.
Reverse 900 you will get 9.

37.2 Java Code

Running time: 757 ms

public class Solution {
    /**
     * @param number: A 3-digit number.
     * @return: Reversed number.
     */
    public int reverseInteger(int number) {
        // write your code here
        StringBuilder str = new StringBuilder();
        str.append(number);
        str = str.reverse();
        String result = String.valueOf(str);
        if(result.substring(0,1).equals("0")){
            result = result.substring(1,result.length());
        }
        return Integer.parseInt(result);
    }
}

37.3 Python Code

Running Time = 252ms

class Solution:
    """
    @param number: A 3-digit number.
    @return: Reversed number.
    """
    def reverseInteger(self, number):
        # write your code here
        temp = str(number)
        temp = temp[::-1]
        if temp[:1] == "0":
            temp = temp[2:]
        return int(temp)

145. Lowercase to Uppercase

Convert a lowercase character to uppercase.

145.1 Example

a -> A, b -> B ...

145.2 JAVA

Total runtime 3955 ms

public class Solution {
    /**
     * @param character: a character
     * @return: a character
     */
    public char lowercaseToUppercase(char character) {
        // write your code here
        return (char)(character - 'a' + 'A');
    }
}

145.3 Python

Total runtime 1310 ms

class Solution:
    """
    @param character: a character
    @return: a character
    """
    def lowercaseToUppercase(self, character):
        # write your code here
        return character.upper()