MrainW's Home

All things come to those who wait!

0%

Posted on In ,
Symbols count in article: 839 Reading time ≈ 1 mins.

Question

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

https://leetcode.com/problems/container-with-most-water/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length < 2) return 0;
        int area = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            area = Math.max(area, (right - left) * Math.min(height[left], height[right]));
            if (height[left] > height[right]) right--;
            else if (height[left] < height[right]) left++;
            //left = right
            else {
                left++;
                right--;
            }
        }
        return area;
    }
}

Complexity:

Time complexity: O( n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 812 Reading time ≈ 1 mins.

Question

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

https://leetcode.com/problems/3sum-closest/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length == 0) return target;
        Arrays.sort(nums);
        int delta = nums[0] + nums[1] + nums[2] - target;
        for (int i = 0; i < nums.length - 2; i++){
            int start = i + 1;
            int end = nums.length - 1;
            while (start < end) {
                int newDelta = nums[i] + nums[start] + nums[end] - target;
                if (newDelta == 0) return target;
                if (Math.abs(newDelta) < Math.abs(delta)) delta = newDelta;
                if (newDelta < 0) start++;
                else end--;
            }
        }
        return target + delta;
    }
}

Complexity:

Time complexity: O( n^2)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.4k Reading time ≈ 1 mins.

Question

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

https://leetcode.com/problems/3sum/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length <= 2) return res;
        int n = nums.length;
        int i = 0;
        Arrays.sort(nums);
        while (i < n - 2) {
            int base = nums[i];
            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = base + nums[left] + nums[right];
                if (sum == 0) {
                    List<Integer> list = new LinkedList<>();
                    list.add(base);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    left = moveRight(nums, left + 1);
                    right = moveLeft(nums, right - 1);
                } else if (sum > 0) {
                    right = moveLeft(nums, right - 1);
                } else {
                    left = moveRight(nums, left + 1);
                }
            }
            i = moveRight(nums, i + 1);
        }
        return res;
    }
    private int moveLeft(int[] nums, int right) {
        while (right == nums.length - 1 || (right >= 0 && nums[right] == nums[right + 1])) {
            right--;
        }
        return right;
    }
     private int moveRight(int[] nums, int left) {
        while (left == 0 || (left < nums.length && nums[left] == nums[left - 1])) {
            left++;
        }
        return left;
    }
}

Complexity:

Time complexity: O( n^2)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 851 Reading time ≈ 1 mins.

Question

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

https://leetcode.com/problems/first-bad-version/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (!isBadVersion(mid)) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}

Complexity:

Time complexity: O(logn)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 872 Reading time ≈ 1 mins.

Question

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

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

https://leetcode.com/problems/rotate-image/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null) return;
        if (matrix.length == 0 || matrix[0].length == 0) return;
        int top = 0;
        int left = 0;
        int right = matrix.length - 1;
        int bottom = matrix.length - 1;
        int n = matrix.length;
        while (n > 1) {
            for (int i = 0; i < n - 1; i++) {
                int tmp = matrix[top][left + i];
                matrix[top][left + i] = matrix[bottom - i][left];
                matrix[bottom - i][left] = matrix[bottom][right - i];
                matrix[bottom][right - i] = matrix[top + i][right];
                matrix[top + i][right] = tmp;
            }
            top++;
            bottom--;
            left++;
            right--;
            n -= 2;
        }
    }
}

Complexity:

Time complexity: O(n^2)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 797 Reading time ≈ 1 mins.

Question

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

https://leetcode.com/problems/first-missing-positiv

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) return 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0){
                nums[i] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            //3142
            //31-42
            int num = Math.abs(nums[i]);
            //3642
            //最大是5，不需要操作，两个重要的点
            if (num <= nums.length) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 916 Reading time ≈ 1 mins.

Question

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

https://leetcode.com/problems/group-anagrams/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        ArrayList<List<String>> res = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) return res;
        HashMap<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] curr = strs[i].toCharArray();
            Arrays.sort(curr);
            String key = String.valueOf(curr);
            if (!map.containsKey(key))
                map.put(key, new ArrayList<String>());
            map.get(key).add(strs[i]);
        }
        res = new ArrayList<List<String>>(map.values());
        return res;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 975 Reading time ≈ 1 mins.

Question

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

https://leetcode.com/problems/next-permutation/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int replace = nums.length - 2;
        //后面的数确定是倒序排列的
        while (replace >= 0) {
            if (nums[replace] < nums[replace + 1]) break;
            replace--;
        }
        if (replace < 0) {
            Arrays.sort(nums);
            return;
        }
        int lgrIdx = replace + 1;
        //while 找到的是最接近的比replace位大的数的下一位
        while (lgrIdx < nums.length && nums[lgrIdx] > nums[replace]) {
            lgrIdx++;
        }
        int tmp = nums[replace];
        nums[replace] = nums[lgrIdx - 1];
        nums[lgrIdx - 1] = tmp;
        //nums.length不参加排序
        Arrays.sort(nums, replace + 1, nums.length);
    }
}

Complexity:

Time complexity: O(nlogn)

Space complexity: O(1)

Posted on In ,
Symbols count in article: 701 Reading time ≈ 1 mins.

Question

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

https://leetcode.com/problems/spiral-matrix-ii/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        if (n <= 0) return res;
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int k = 1;
        while (top < bottom && left < right) {
            for (int i = left; i < right; i++) res[top][i] = k++;
            for (int i = top; i < bottom; i++) res[i][right] = k++;
            for (int i = right; i > left; i--) res[bottom][i] = k++;
            for (int i = bottom; i > top; i--) res[i][left] = k++;
            top++;
            bottom--;
            left++;
            right--;
        }
        if (n %2 != 0) res[n / 2][n / 2] = k;
        return res;
    }
}

Complexity:

Time complexity: O(mn)

Space complexity: O(mn)

Posted on In ,
Symbols count in article: 965 Reading time ≈ 1 mins.

Question

Given an m x n matrix, return all elements of the matrix in spiral order.

https://leetcode.com/problems/spiral-matrix/

  • Solution1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new LinkedList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return res;
        int left = 0, right = matrix[0].length - 1;
        int top = 0, bottom = matrix.length - 1;
        while (left < right && top < bottom) {
            for (int i = left; i < right; i++) res.add(matrix[top][i]);
            for (int i = top; i < bottom; i++) res.add(matrix[i][right]);
            for (int i = right; i > left; i--) res.add(matrix[bottom][i]);
            for (int i = bottom; i > top; i--) res.add(matrix[i][left]);
            left++;
            right--;
            top++;
            bottom--;
        }
        if (left == right) {
            for (int i = top; i <= bottom; i++) res.add(matrix[i][left]);
        } else if (top == bottom) {
            for (int i = left; i <= right; i++) res.add(matrix[top][i]);
        }
        return res;
    }
}

Complexity:

Time complexity: O(mn)

Space complexity: O(mn)