LeetCode(83) -- 78, 61, 59

P78. Subsets (Medium)

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

My Solution

public class P78_Subsets {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if (nums == null || nums.length == 0) {
            return ans;
        }
        ans.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                List<Integer> existing = ans.get(j);
                ArrayList<Integer> newList = new ArrayList<>(existing);
                newList.add(nums[i]);
                ans.add(newList);
            }
        }
        return ans;
    }
}

1ms 28%

The Best Solution

class Solution {
    
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        backTrack(list, new ArrayList<>(), nums, 0);
        return list;
    }
    
    public void backTrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
        list.add(new ArrayList<>(tempList));
        for(int i = start; i < nums.length; i++) {
            tempList.add(nums[i]);
            backTrack(list, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

P61. Rotate List (Medium)

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

My Solution

public class P61_RotateList {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail = head;
        int length = 1;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }
        tail.next = head;
        int steps = length - k % length - 1;
        ListNode newTail = head;
        for (int i = 0; i < steps; i++) {
            newTail = newTail.next;
        }
        ListNode ans = newTail.next;
        newTail.next = null;
        return ans;
    }
}

100%

P59. Spiral Matrix II (Medium)

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

My Solution

public class P59_SpiralMatrixII {
    public int[][] generateMatrix(int n) {
        int last = n * n, i = 0, j = 0, current = 1, round = 0, size = n, limit = size == 1 ? 1 : (size - 1) * 4;
        int[][] ans = new int[n][n];
        int[] di = {0, 1, 0, -1};
        int[] dj = {1, 0, -1, 0};
        while (current <= last) {
            while (i < (n + size) / 2 && j < (n + size) / 2 &&
                    i >= (n - size) / 2 && j >= (n - size) / 2 && current <= limit ) {
                ans[i][j] = current;
                current++;
                i += di[round % 4];
                j += dj[round % 4];
            }
            i -= di[round % 4];
            j -= dj[round % 4];
            round++;
            i += di[round % 4];
            j += dj[round % 4];
            if (round % 4 == 0) {
                size -= 2;
                limit += size == 1 ? 1 :(size - 1) * 4;
            }
        }
        return ans;
    }
}

100%

The Best Solution

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int iStart = 0, iEnd = n-1;
        int val = 1;
        while(iStart<iEnd){
            for(int i=iStart;i<iEnd;i++){
                res[iStart][i] = val;
                val++;
            }
            for(int i=iStart;i<iEnd;i++){
                res[i][iEnd] = val;
                val++;
            }
            for(int i=iEnd;i>iStart;i--){
                res[iEnd][i] = val;
                val++;
            }
            for(int i=iEnd;i>iStart;i--){
                res[i][iStart] = val;
                val++;
            }
            iStart++;
            iEnd--;
        }
        if(iStart==iEnd){
            res[iStart][iStart] = val;
        }
        return res;
    }
}