Basic Question

Print Pascal

Link

void solution(int n){
    int[] preLevel = new int[]{1};
    printPascal(preLevel);

    for(int i=2; i<=n; i++){
        int[] level = new int[i];
        level[0] = 1;
        level[i-1] = 1;
        // i 為第幾層，有i個element
        // j 的長度判斷必須為上一個preLevel的長度
        for(int j=0; j<i-2; j++){
            level[j+1] = preLevel[j] + preLevel[j+1];
        }
        printPascal(level);
        preLevel = level;
    }
}

void printPascal(int[] level){
    StringBuilder sb = new StringBuilder();
    for(int n: level){
        sb.append(n).append(" ");
    }
    sb.append("\n");
    System.out.println(sb.toString());
}

48 Rotate Image

Explain

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).

• Swap by row (first_row++, last_row--)

• Swap elements by diagnals

/*
 * clockwise rotate
 * first reverse up to down, then swap the symmetry 
 * 1 2 3     7 8 9     7 4 1
 * 4 5 6  => 4 5 6  => 8 5 2
 * 7 8 9     1 2 3     9 6 3
*/

public void rotate(int[][] matrix) {
    int first = 0, last = matrix.length-1;
    // swap by row
    while(first < last){
        // swapRow(matrix[first++], matrix[last--]);
        int[] tmp = matrix[first];
        matrix[first] = matrix[last];
        matrix[last] = tmp;
        first++;
        last--;
    }

    // swap element in matrix by diagnal
    for(int i=0; i<matrix.length; i++){
        for(int j=0; j<i; j++){
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
            // swapElement(matrix[i][j], matrix[j][i]);
        }
    }

836 Rectangle Overlap

Given two rectangles, find if the given two rectangles overlap or not.

l1: Top Left coordinate of first rectangle. r1: Bottom Right coordinate of first rectangle. l2: Top Left coordinate of second rectangle. r2: Bottom Right coordinate of second rectangle.

l1 != r2 and l2 != r2

l1 _____
   |   |
   |___| r1
      l2 _____
         |   |
         |___| r2

public boolean doOverlap(Point l1, Point r1, Point l2, Point r2) {
    if (r2.x < l1.x || l2.x > r1.x){
        return false;
    }

    if (l2.y < r1.y || r2.y > l1.y){
        return false;
    }
    return true;
}

223. Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane. (A, B) is left bottom corner, (C, D) is right top corner

public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
    int rec1 = (C-A)*(D-B);
    int rec2 = (G-E)*(H-F);

     // 判斷左下角x軸max是超過右上角x軸min
    int left = Math.max(A,E);
    int right = Math.min(C,G);
    int bottom = Math.max(B,F);
    int top = Math.min(D,H);

    int overLap = 0;
    if(right > left && bottom < top){
        overLap = (left-right)*(top-bottom);
    }

    return rec1 + rec2 + overLap;
}

283 Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. Move in-space without using extra array.

Example:

Input: [0,1,0,3,12] Output: [1,3,12,0,0]

public void moveZeroes(int[] nums) {
    int notZero = 0;
    for(int i=0; i<nums.length; i++){
        if(nums[i] != 0){
            int tmp = nums[i];
            nums[i] = nums[notZero];
            nums[notZero] = tmp;
            notZero++;
        }
    }
}

246 Strobogrammatic Number

A strobogrammatic number is a number that looks the same when rotated 180 degrees. Write a function to determine if a number is strobogrammatic

• 頭尾i+j是否包含在"00 11 88 69 96"

public boolean isStrobogrammatic(String num) {
    int i=0, j=num.length()-1;
    while(i<=j){
        if(!"00 11 88 69 96".contains(num.charAt(i++)+""+num.charAt(j--)))
            return false;
    }
    return true;
}

247 Strobogrammatic Number II

Find all strobogrammatic numbers that are of length = n.

• Backtracking(n ,n): 第二個n用來判斷邊界是否要放0

public List<String> findStrobogrammatic(int n) {
    return helper(n, n);
}

private List<String> helper(int n, int m){
    // 偶數的base case
    if(n == 0) return new ArrayList(Arrays.asList(""));
    // 奇數的base case
    if(n == 1) return new ArrayList(Arrays.asList("0", "1", "8"));

    List<String> list = helper(n-2, m);
    List<String> ans = new ArrayList<>();

    for(String str: list){
        if(n != m) ans.add("0"+str+"0");
        ans.add("1"+str+"1");
        ans.add("6"+str+"9");
        ans.add("9"+str+"6");
        ans.add("8"+str+"8");
    }

    return ans;
}

Is Prime Number

def isPrime(self, num):
    # 1 並不是質數
    # 1 => False, 2 => True, others => False
    if num == 1 or num % 2 == 0: return num == 2
    for i in range(3, int(num**0.5)+1, 2):
        if num%i == 0: return False
    return True

進制轉換

public class AnyToDecimal {
    // 低到高位指數展開
    int toDecimal(String str, int base){
        int power = 1;
        int ans = 0;

        for(int i=str.length()-1; i>=0; i--){
            ans += realInt(str.charAt(i)) * power;
            power = power * base;
        }
        return ans;
    }

    int realInt(char c){
        if(Character.isDigit(c)) return c - '0';
        else return c - 'A' + 10;
    }

    // 除留取餘
    String decimalToAny(int num, int base){
        Stack<Character> s = new Stack<>();

        while(num > 0){
            s.push(realVal(num%base));
            num /= base;
        }

        StringBuilder sb = new StringBuilder();
        while(!s.isEmpty()){
            sb.append(s.pop());
        }
        return sb.toString();
    }

    char realVal(int num){
        if(num < 10){
            return (char)num;
        }else{
            return (char)('A' + num - 10);
        }
    }

    public static void main(String[] args) {
        AnyToDecimal a = new AnyToDecimal();
        System.out.println(a.toDecimal("1100", 2));
        System.out.println(a.toDecimal("FE0C", 16));
    }