LeetCode(80) -- 48, 42, 46

P48. Rotate Image (Medium)

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Solution

public class P48_RotateImage {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[j][i];
                matrix[j][i] = matrix[i][j];
                matrix[i][j] = temp;
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = temp;
            }
        }
    }
}

class Solution {
  public void rotate(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < (n + 1) / 2; i ++) {
      for (int j = 0; j < n / 2; j++) {
        int temp = matrix[n - 1 - j][i];
        matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];
        matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 -i];
        matrix[j][n - 1 - i] = matrix[i][j];
        matrix[i][j] = temp;
      }
    }
  }
}

P42. Trapping Rain Water (Hard)

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The Best Solution

class Solution {
    public int trap(int[] height) {
        int i = 0, j = height.length - 1, ans = 0, bound = 0;
        while (i < j) {
            if (height[i] < height[j]) {
                if (height[i] > bound) {
                    bound = height[i++];
                } else {
                    ans += bound -  height[i++];
                }
            } else {
                if (height[j] > bound) {
                    bound = height[j--];
                } else {
                    ans += bound - height[j--];
                }
            }
        }
        return ans;
    }
}

P46. Permutations (Medium)

Given a collection of distinct integers, return all possible permutations.

Discuss

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backtrack(nums, new ArrayList<>());
        return ans;
    }
    
    private void backtrack(int[] nums, List<Integer> tempList) {
        if  (tempList.size() == nums.length) {
            ans.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (tempList.contains(nums[i])) {
                continue;
            }
            tempList.add(nums[i]);
            backtrack(nums, tempList);
            tempList.remove(tempList.size() - 1);
        }
    }
}

24%

The Best Solution

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if(nums.length==0)
            return result;
        
        permuteHelper(nums, nums.length, nums.length, result);
        return result;
    }

    public void permuteHelper(int[] nums, int size, int n, List<List<Integer>> result) {
        
        if(size==1) { // add combo in list
            List<Integer> combo = new LinkedList<Integer>();
            for(int i = 0; i < nums.length; i++) {
                combo.add(nums[i]);
            }
            result.add(combo);   
        }
        
        for(int i = 0; i < size; i++) {
            permuteHelper(nums, size-1, n, result);
            
            if(size%2==1) {
                int temp = nums[0];
                nums[0] = nums[size-1];
                nums[size-1] = temp;
            } else {
                int temp = nums[i];
                nums[i] = nums[size-1];
                nums[size-1] = temp;
            }
        }
    }

}

100%

Solution

class Solution {
  public void backtrack(int n,
                        ArrayList<Integer> nums,
                        List<List<Integer>> output,
                        int first) {
    // if all integers are used up
    if (first == n)
      output.add(new ArrayList<Integer>(nums));
    for (int i = first; i < n; i++) {
      // place i-th integer first 
      // in the current permutation
      Collections.swap(nums, first, i);
      // use next integers to complete the permutations
      backtrack(n, nums, output, first + 1);
      // backtrack
      Collections.swap(nums, first, i);
    }
  }

  public List<List<Integer>> permute(int[] nums) {
    // init output list
    List<List<Integer>> output = new LinkedList();

    // convert nums into list since the output is a list of lists
    ArrayList<Integer> nums_lst = new ArrayList<Integer>();
    for (int num : nums)
      nums_lst.add(num);

    int n = nums.length;
    backtrack(n, nums_lst, output, 0);
    return output;
  }
}