秋招刷题打卡

一天有空就多刷刷，大四明年毕业，JAVA为主

760 Find Anagram Mappings ---- Easy 用時4分鐘
用了兩個方法去解
1. Brute force
    public int[] anagramMappings(int[] A, int[] B) {
        int[] result = new int[A.length];
        for(int i = 0; i < A.length; i++){
            for(int j = 0; j < B.length; j++){
                if (B[j] == A[i]){
                    result[i] = j;
                }
            }
        }
        return result;
    }

2. HashMap
    public int[] anagramMappings(int[] A, int[] B) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < B.length; i++){
            map.put(B[i], i);
        }
        
        int[] result = new int[B.length];
        for(int i = 0; i < A.length;i++){
            result[i] = map.get(A[i]);
        }
        
        return result;
    }

657. Robot Return to Origin ---- Easy  Time : 4:37

1. For loop + swtich case / if else O(N)
    public boolean judgeCircle(String moves) {
        int x = 0;
        int y = 0;
        for(int i = 0; i < moves.length(); i++){
            switch(moves.charAt(i)){
                case('U'):
                    y += 1;
                    break;
                case('D'):
                    y -= 1;
                    break;
                case('L'):
                    x -= 1;
                    break;
                case('R'):
                    x += 1;
                    break;
                default:
                    break;
            }
        }
        return(x == 0 && y == 0);
    }

832. Flipping an Image --- Easy Time : 7:23

1. 想不到更好的方法 for loop走一遍, 第二個forloop換方向, 第三個forloop 10互換
    public int[][] flipAndInvertImage(int[][] A) {
        for(int i = 0; i < A.length; i++){
            for(int j = 0; j < A[i].length / 2; j++){
                int temp = A[i][j];
                A[i][j] = A[i][A[i].length - j - 1];
                A[i][A[i].length - j - 1] = temp;
            }
            for(int k = 0; k < A[i].length; k++){
                if(A[i][k] == 1){
                    A[i][k] = 0;
                }else{
                    A[i][k] = 1;
                }
            }
        }
        return A;
    }

617. Merge Two Binary Trees --- Easy

1. recursion to go through left side and right side.

    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        //BFS
        
        if(t1 == null){
            return t2;
        }
        if(t2 == null){
            return t1;
        }
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;

    }

700. Search in a Binary Search Tree   Easy

    public TreeNode searchBST(TreeNode root, int val) {
        while(root != null){
            if(root.val < val){
                root = root.right;
            }else if(root.val > val){
                root = root.left;
            }else{
                return root;
            }
        }
        return null;
    }

905. Sort Array By Parity

While loop + 2 pointers O(N)

    public int[] sortArrayByParity(int[] A) {
        int i = 0;
        int j = A.length - 1;
        int temp;
        while (i < j){
            if (A[i] % 2 == 1 && A[j] % 2 == 0) {
                temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                i += 1;
                j -= 1;
            } else if (A[i] % 2 == 0) {
                i += 1;
            } else if (A[j]%2 == 1) {
                j -= 1;
            }
        }
        return A;
    }