2215. Find the Difference of Two Arrays
Posted Updated LeetCode / Simple2 minutes read (About 225 words)

2215. Find the Difference of Two Arrays

Question

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

  • answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
  • answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

Read more
2215. Find the Difference of Two Arrays
Posted Updated LeetCode / Simplea few seconds read (About 107 words)

2215. Find the Difference of Two Arrays

Question

There is a function signFunc(x) that returns:

  • 1 if x is positive.
  • -1 if x is negative.
  • 0 if x is equal to 0.

You are given an integer array nums. Let product be the product of all values in the array nums.

Return signFunc(product).

Solution

遍历并检查当前元素的正负性，如果为负值则改变符号。

如果为0则返回0。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int arraySign(int[] nums) {
        int res = 1;

        for(int i = 0; i < nums.length; i++){
            if(nums[i] < 0){
                res = -res;
            }
            else if(nums[i] == 0){
                return 0;
            }
        }
        return res;
    }
}
1491-Average-Salary-Excluding-the-Minimum-and-Maximum-Salary
26. Remove Duplicates from Sorted Array
Posted Updated LeetCode / Easy2 minutes read (About 300 words)

26. Remove Duplicates from Sorted Array

Question

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k* after placing the final result in the first k slots of *nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Solution

由于数组本身已经排序，只要比较当前nums中的元素是否大于上一个保存的数值就可以决定是否保留。
创建一个k记录遍历的位置，每次比较nums[k]与nums[i]的位置元素的大小，如果当前的nums[i]大于nums[k]，则将k位置向后移动1，并将下一个位置记录为nums[i]。

最后返回k+1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[k] < nums[i]){
                k++;
                nums[k] = nums[i];
            }
        }
        return k + 1;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 150 words)

713. Subarray Product Less Than K

Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

滑动窗口，维护一个窗口内的乘积。
当乘积小于目标值时，窗口右侧向右移动。每加入一个新数值，可以增加(j-i+1)个组合。
当乘积大于目标时，窗口左侧向右移动。

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 numSubarrayProductLessThanK(int[] nums, int k) {
        int i = 0;
        int j = 0;
        int product = nums[0];
        int count = 0;
        
        while(i < nums.length && j < nums.length){
            if(product < k){
                count += (j - i) + 1;
                j++;
                if(j < nums.length ) product *= nums[j];
            }
            else{
                product /= nums[i];
                i++;
            }   
        }
        return count;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 451 words)

209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

滑动窗口，先取最左侧数字。记录窗口的最小值。
如果小于目标值，则右侧窗口向右移动，扩大窗口。更新窗口内的值。
如果大于等于目标值，则左侧窗口向右移动，缩小窗口。更新窗口内的值。
同时如果窗口大小小于最小值则更新窗口最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = nums[0];
        while(right < nums.length){
            if(sum >= target){
                min = Math.min(min, right - left + 1);
                sum -= nums[left];
                left++;
            }
            else{
                right++;
                if(right < nums.length) sum += nums[right];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

计算前缀和。
前缀和[j]与前缀和的[i]的差就是i+1到j的和。
因此需要找到sum[j] - sum[i] >= k。
暴力枚举的话需要O(n^2^)的时间复杂度。

由于前缀和是有序的，因此我们可以采用二分搜索。
寻找sum[j] - k >= sum[i]。
Arrays.binarySearch方法可以返回查找到的目录。
如果没有该值，方法会返回一个负数，其取反（x取反相当于[-(x+1)]）的值就是应该插入的目录。
将ans设置为无限大，如果(index - i)小于最小值则更新到ans。

时间复杂度O(nlogn)。

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 minSubArrayLen(int target, int[] nums) {
        int[] sum = new int[nums.length+1];
        for(int i = 1; i <= nums.length; i++){
            sum[i] = sum[i-1] + nums[i-1];
        }
        
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < sum.length; i++){
            int search = sum[i] + target;
            int index = Arrays.binarySearch(sum, search);
            if(index < 0){
                index = ~index;
            }
            if(index < sum.length){
                ans = Math.min(ans, index - i);
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 243 words)

560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

对于数组中每个数字，计算其前缀的和。
前缀[i]减去前缀[j]的差，等于[j]-[i]之间数字的和。（类似一种DP，数组可以用一个变量代替。）

因此，原题目等于寻找找 前缀[i]-前缀[j] = k。
用哈希表储存已经遍历过的前缀和出现的次数。
每次遍历时先查看哈希表内是否有当前[前缀和-k]的键在。
如果有则加入到count中。
（哈希表中需要提前放入一个0键，值等于1，为了计算[前缀和-k]等于0的情况。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int subarraySum(int[] nums, int k) {
        
        int[] sum = new int[nums.length + 1];
        HashMap<Integer, Integer> map = new HashMap();
        int count = 0;
        map.put(0, 1);
        
        for(int i = 1; i <= nums.length; i++){
            sum[i] = sum[i-1] + nums[i-1];
            count += map.getOrDefault(sum[i]-k, 0);
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }
        
        return count;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 258 words)

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

当前数字之外的积等于左边所有数字的积乘以右边所有数字的积。
因此可以维护两个数组，分别计算从左到右的乘积，和从右到左的乘积。

由于返回答案不算占用空间，因此可以将左侧乘积的数组保存在答案数组上。
然后在遍历时，从右至左遍历，使用一个变量储存右边的乘积，直接将两者的乘积更新在答案数组上。
此时空间复杂度为O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        ans[0] = 1;
        
        for(int i = 1; i < nums.length; i++){
            ans[i] = ans[i-1] * nums[i-1];
        }
        
        int rightProduct = 1;
        
        for(int j = nums.length-1; j >=0; j--){
            ans[j] = ans[j] * rightProduct;
            rightProduct *= nums[j];
        }
        return ans;   
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 511 words)

334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

贪心算法。
将first与second初始化为最大值。
first保存遍历过的最小值。
second保存遍历过的大于之前最小值的最小值。

遍历数组。
条件一：如果数字小于现在第一个值，则更新第一个值。
（此时一定不满足条件二，因此可以安全地更新更小的数字。）
条件二：如果数字大于第一个值，且小于第二个值，则更新第二个值。
（此时第一个值已经被更新过了，满足第一个值小于第二个值。）
条件三：如果数字大于第二个值，则返回true。
（此时两个值一定都被更新过了，满足第一个值小于第二个值小于第三个值。）

注意：
更新first后，second不会更新，但是second的存在可以确保曾经存在first小于second。
如果此时数字大于second，则数组中存在Triplet Subsequence。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;
        
        for(int num : nums){
            if(num < first){
                first = num;
            }
            else if(num > first && num < second){
                second = num;
            }
            else if(num > second){
                return true;
            }   
        }
        return false;
    }
}

双向遍历，逐渐收紧搜索窗口。设置i，k两个指针分别在头尾。
当nums[j] <= nums[i]，则更新i指针为j。
当nums[j] >= nums[k]，则更新k指针为j。
如果找到符合条件的nums[i] < nums[j] < nums[k]则返回。

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
class Solution {
    public boolean increasingTriplet(int[] nums) {
        boolean flag = true;
        int i = 0;
        int k = nums.length -1 ;
        int j;
        int count = 1;
        
        while(i < k && i + count < k){
            if(flag){
                j = i + count;
                if(nums[i] >= nums[j]){
                    i = j;
                    count = 1;
                    flag = true;
                    continue;
                }
                else if(nums[j] < nums[k]){
                    return true;
                }
                flag = !flag;
            }
            else{
                j = k - count;
                if(nums[k] <= nums[j]){
                    k = j;
                    count = 1;
                    flag = true;
                    continue;
                }
                else if(nums[j] > nums[i]){
                    return true;
                }
                else{
                    count++;
                }
                flag = !flag;
            }
        }
        return false;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 303 words)

33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

二分搜索，二分后将会形成两个区间，一个区间是顺序的，另一个是无序的。
如果target等于中间值则返回。
分别处理两种情况下移动指针的方式。
当顺序区间在左半边时：
当target在顺序区间内，则更新右指针的位置。
否则更新左指针位置。
当顺序区间在右半边时：
当target在顺序区间内，则更新左指针的位置。
否则更新右指针位置。

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
class Solution {
    public int search(int[] nums, int target) {

        int left = 0;
        int right = nums.length-1;
        
        while(left <= right){
            int mid = (right - left) / 2 + left;
            if(nums[mid] == target){
                return mid;
            }
            
            if( nums[mid] >= nums[0] ){
                if(target >= nums[0] && target < nums[mid] ){
                    right = mid - 1;
                }
                else{
                    left = mid + 1;
                }
            }
            else{
                if(target > nums[mid] && target <= nums[nums.length-1]){
                    left = mid + 1;
                }
                else{
                    right = mid -1;
                }
            }

        }
        return -1;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 355 words)

15. 3Sum

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.

三数之和，重点是如何遍历后去除重复的数组。
首先对数组进行排序。
遍历数组，三个数中最小的数字为nums[i]。
此时需要去除重复的nums[i]。如重复则继续下一次循环。
此时设置双指针left和right，分别在nums[i]右侧的子数组的首尾。

  • 当nums[i] + nums[left] + nums[right] > 0时，后两个数的和需要减小，right指针向左移动。
  • 当nums[i] + nums[left] + nums[right] < 0时，后两个数的和需要增大，left指针向右移动。
  • 当nums[i] + nums[left] + nums[right] = 0时，找到一个组合。
    此时需要去除重复的nums[left]和nums[right]。如重复则更新left或right的指针。
  • 将组合添加到返回列表。

最后返回列表。

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length; i++){
            int left = i+1;
            int right = nums.length-1;
            if(i>0 && nums[i] == nums[i-1]){
                continue;   
            }
            
            while(left < right){
                if(nums[i]+nums[left]+nums[right]==0){
                    while(left+1 < nums.length && nums[left] == nums[left+1]){
                        left++;
                    }
                    while(right-1 > i && nums[right] == nums[right-1]){
                        right--;
                    }
                    List<Integer> list = new ArrayList();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    ans.add(list);
                    
                    left++;
                    right--;
                }
                else if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return ans;
    }
}
Posted Updated LeetCode / Easy2 minutes read (About 243 words)

682. Baseball Game

问题
You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds’ scores.

At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following:

  1. An integer x - Record a new score of x.
  2. “+” - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores.
  3. “D” - Record a new score that is double the previous score. It is guaranteed there will always be a previous score.
  4. “C” - Invalidate the previous score, removing it from the record. It is guaranteed there will always be a previous score.

Return the sum of all the scores on the record.

遍历选项，根据内容决定对ArrayList的操作。
然后遍历将ArrayList加和，返回。

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
class Solution {
    public int calPoints(String[] ops) {
        int ans = 0;
        List<Integer> records = new ArrayList();
        
        for (String op : ops){
            switch(op){
                case "+":
                    records.add(records.get(records.size()-1)+records.get(records.size()-2));
                    break;
                case "D":
                    records.add(records.get(records.size()-1)*2);
                    break;
                case "C":
                    records.remove(records.size()-1);
                    break;
                default:
                    records.add(Integer.parseInt(op));
            }
        }
        
        for (int record : records){
            ans += record;
        }                 
        return ans;
    }
}
Follow

Recents

Archives

Links

×