MrainW's Home

Mac kill process on certain port

Posted on 2022-04-01 In Mac , Skills
Symbols count in article: 181 Reading time ≈ 1 mins.

Look through certain port

lsof -i :port

or

lsof -i tcp:port

//replace the port with the number of port(eg:3000)

Kill the pid

kill -9 PID


//replace the PID with the number of PID(get the value from last step)

Transfer Hexo blog to Mac

Posted on 2022-03-27 In Mac , Skills
Symbols count in article: 432 Reading time ≈ 1 mins.

Prepare

Copy the files to your new MacBook

_config.yml
theme
source
.gitignore
package.json
scaffolds

Install

// install hexo
sudo npm install hexo-cli -g

//install packages from package.json
sudo npm install

//install other dependencies
sudo npm install hexo-deployer-git --save
sudo npm install hexo-generator-feed --save
sudo npm install hexo-generator-sitemap --save

local test

hexo clean
hexo g
hexo s

//available on localhost:4000

Deploy to github

hexo clean

hexo g

hexo d

Sort

Posted on 2021-11-02 In Leetcode , Sort
Symbols count in article: 3k Reading time ≈ 3 mins.

Quick sort

quick sort

<= p >=p

two part

11111111112，防止分布不均

average time complexity O(nlogn)

worst O(n^2)

space complexity O(1)

non stability

先整体有序，后局部有序

public class Solution {
    /**
     * @param A: an integer array
     * @return: nothing
     */
    public void sortIntegers(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        quickSort(A, 0, A.length - 1);
    }
    
    private void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }
        
        int left = start, right = end;
        int pivot = A[(start + end) / 2];
        //left <= right
        //32145, 不存在交集，否则不断循环
        //[12][2345]
        while (left <= right) {
            //1111111 A[left]<=pivot，全部归到左面，不均衡
            while (left <= right && A[left] < pivot) {
                left++;
            }
            while (left <= right && A[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                left++;
                right--;
            }
        }
        quickSort(A, start, right);
        quickSort(A, left, end);
    }
}

Merge sort

merge sort

worst O(nlogn)

space complexity O(n)

stability

先局部有序，后整体有序

public class Solution {
    public void sortIntegers(int[] A) {
        if (A == null || A.length == 0) {
            return;
        }
        int[] temp = new int[A.length];
        mergeSort(A, 0, A.length - 1, temp);
    }
    
    private void mergeSort(int[] A, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }
        mergeSort(A, start, (start + end) / 2, temp);
        mergeSort(A, (start + end) / 2 + 1, end, temp);
        merge(A, start, end, temp);
    }
    
    private void merge(int[] A, int start, int end, int[] temp) {
        int middle = (start + end) / 2;
        int leftIndex = start;
        int rightIndex = middle + 1;
        int index = start;
        while (leftIndex <= middle && rightIndex <= end) {
            if (A[leftIndex] <= A[rightIndex]) {
                temp[index++] = A[leftIndex++];
            } else {
                temp[index++] = A[rightIndex++];
            }
        }
        while (leftIndex <= middle) {
            temp[index++] = A[leftIndex++];
        }
        while (rightIndex <= end) {
            temp[index++] = A[rightIndex++];
        }
        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }
    }
}

Quick selection

kth largest element

O(n)

class Solution {
    /*
     * @param k : description of k
     * @param nums : array of nums
     * @return: description of return
     */
    public int kthLargestElement(int k, int[] nums) {
        if (nums == null || nums.length == 0 || k < 1 || k > nums.length){
            return -1;
        }
        return partition(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int partition(int[] nums, int start, int end, int k) {
        if (start >= end) {
            return nums[k];
        }
        
        int left = start, right = end;
        int pivot = nums[(start + end) / 2];
        
        while (left <= right) {
            while (left <= right && nums[left] < pivot) {
                left++;
            }
            while (left <= right && nums[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
        //start-right right-left left-end 三部分
        if (k <= right) {
            return partition(nums, start, right, k);
        }
        if (k >= left) {
            return partition(nums, left, end, k);
        }
        return nums[k];
    }    
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};

Two point

Posted on 2021-11-02 In Leetcode , Two point
Symbols count in article: 9k Reading time ≈ 8 mins.

Two sum

Two sum data structure design

public class TwoSum {
    private Map<Integer, Integer> counter;
    public TwoSum() {
        counter = new HashMap<Integer, Integer>;
    }
    public void add(int number) {
        counter.put(number, counter.getOrDefault(number, 0) + 1);
    } 
    public boolean find(int value) {
        for (Integer num1 : counter.keySet()) {
            int num2 = value - num1;
            //repeated number
            int desiredCount = num1 == num2 ? 2 : 1;
            if (counter.getOrDefault(num2, 0) >= desiredCount) {
                return true;
            }
        }
        return false;
    }
}

public class TwoSum {
    public List<Integer> nums;
    public TwoSum() {
        nums = new ArrayList<Integer>();
    }
    public void add(int number) {
        nums.add(number);
        int index = nums.size() - 1;
        while (index > 0 && nums.get(index - 1) > nums.get(index)) {
            int tmp = nums.get(index);
            nums.set(index, nums.get(index - 1));
            nums.set(index - 1, tmp);
            index--;
        }
    }
    public boolean find(int value) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int twoSum = nums.get(left) + nums.get(right);
            if (twoSum < value) {
                left++;
            } else if (twoSum > value) {
                right--;
            } else {
                return true;
            }
        }
        retuen false;
    }
}

Three sum

a+b+c=0

a + b = -c

降维

public List<List<Integer>> threeSum(int[] numbers) {
    Arrays.sort(numbers);
    List<List<Integer>> results = new ArrayList<>();
    for (int i = 0; i < numbers.length; i++) {
        if (i != 0 && numbers[i] == numbers[i - 1]) {
            continue;
        }
        findTwoSum(numbers, i, results);
    }
}
private void findTwoSum(int[] nums, int index, List<List<Integer>> results) {
    int left = index + 1, right = nums.length - 1;
    int target = -nums[index];
    while (left < right) {
        int twoSum = nums[left] + nums[right];
        if (twoSum < target) {
            left++;
        } else if (twoSum > target) {
            right--;
        } else {
            List<Integer> triple = new ArrayList();
            triple.add(nums[index]);
            triple.add(nums[left]);
            triple.add(nums[right]);
            results.add(triple);
            left++;
            right--;
            //113422
            while (left < right && nums[left] == nums[left - 1]) {
                left++;
            }
        }
    }
}

triangle count

a <= b <= c, a + b > c

public int triangleCount(int S[]) {
    int left = 0, right = S.length - 1;
    int ans = 0;
    Arrays.sort(S);
    for (int i = 0; i < S.length; i++) {
        left = 0;
        right = i - 1;
        while (left < right) {
            if (S[left] + S[right] > S[i]) {
                //left +1, left + 2 ,,, 都可以 a+b>c
                ans = ans + (right - left);
                right--;
            } else {
                left++;
            }
        }
    }
    return ans;
}

remove repeated number, O(n^3)

4sum from a array

a+b+c+d = target

fix a, b -> by for loop

public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        Arrays.sort(num);

        for (int i = 0; i < num.length - 3; i++) {
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }

            for (int j = i + 1; j < num.length - 2; j++) {
                if (j != i + 1 && num[j] == num[j - 1])
                    continue;

                int left = j + 1;
                int right = num.length - 1;
                while (left < right) {
                    int sum = num[i] + num[j] + num[left] + num[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        ArrayList<Integer> tmp = new ArrayList<Integer>();
                        tmp.add(num[i]);
                        tmp.add(num[j]);
                        tmp.add(num[left]);
                        tmp.add(num[right]);
                        rst.add(tmp);
                        left++;
                        right--;
                        while (left < right && num[left] == num[left - 1]) {
                            left++;
                        }
                        while (left < right && num[right] == num[right + 1]) {
                            right--;
                        }
                    }
                }
            }
        }

        return rst;
    }
}

4sum from a array

a+b=-(c+d)

public class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> counter = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                int sum = A[i] + B[j];
                counter.put(sum, counter.getOrDefault(sum, 0) + 1);
            }
        }
        
        int answer = 0;
        for (int i = 0; i < C.length; i++) {
            for (int j = 0; j < D.length; j++) {
                int sum = C[i] + D[j];
                answer += counter.getOrDefault(-sum, 0);
            }
        }
        return answer;
    }
}

k sum

DFS

Partition

partition array

给出一个整数数组 nums 和一个整数 k。划分数组（即移动数组 nums 中的元素），使得：

所有小于k的元素移到左边
所有大于等于k的元素移到右边

返回数组划分的位置，即数组中第一个位置 i，满足 nums[i] 大于等于 k。

    public int partitionArray(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        
        int left = 0, right = nums.length - 1;
        while (left <= right) {

            while (left <= right && nums[left] < k) {
                left++;
            }

            while (left <= right && nums[right] >= k) {
                right--;
            }

            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                
                left++;
                right--;
            }
        }
        return left;
    }
}

Interleaving Positive and Negative Numbers

给出一个含有正整数和负整数的数组，重新排列成一个正负数交错的数组。

public class Solution {
    public void rerange(int[] A) {
        int pos = 0, neg = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                pos++;
            } else {
                neg++;
            }
        }
        
        partition(A, pos > neg);
        interleave(A, pos == neg);
    }
    
    private void partition(int[] A, boolean startPositive) {
        int flag = startPositive ? 1 : -1;
        int left = 0, right = A.length - 1;
        while (left <= right) {
            while (left <= right && A[left] * flag > 0) {
                left++;
            }
            while (left <= right && A[right] * flag < 0) {
                right--;
            }
            
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                
                left++;
                right--;
            }
        }
    }
    
    private void interleave(int[] A, boolean has_same_length) {
        int left = 1, right = A.length - 1;
        if (has_same_length) {
            right = A.length - 2;
        }
        while (left < right) {
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
            
            left += 2;
            right -= 2;
        }
    }
}

sort colors

给定一个包含红，白，蓝且长度为 n 的数组，将数组元素进行分类使相同颜色的元素相邻，并按照红、白、蓝的顺序进行排序。

我们使用整数 0，1 和 2 分别代表红，白，蓝。

左右排完，剩下的也排完了

public class Solution {
    public void sortColors(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        
        //直到mid > right停止遍历
        while (mid <= right){
            if (nums[mid] == 0){
                swap(nums, mid, left);
                mid ++;
                left ++;
            }
            else if (nums[mid] == 2){
                swap(nums, mid, right);
                right --;
            }
            else{
                mid ++;
            }
        }
    }
    
    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

sort colors II

给定一个有n个对象（包括k种不同的颜色，并按照1到k进行编号）的数组，将对象进行分类使相同颜色的对象相邻，并按照1,2，…k的顺序进行排序。

class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */
    public void sortColors2(int[] colors, int k) {
        if (colors == null || colors.length == 0) {
            return;
        }
        rainbowSort(colors, 0, colors.length - 1, 1, k);
    }
    
    public void rainbowSort(int[] colors,
                            int left,
                            int right,
                            int colorFrom,
                            int colorTo) {
        if (colorFrom == colorTo) {
            return;
        }
        
        if (left >= right) {
            return;
        }
        
        int colorMid = (colorFrom + colorTo) / 2;
        int l = left, r = right;
        while (l <= r) {
            //数偏小，<=  3/2=1, 为了均分，没有重复才可以
            while (l <= r && colors[l] <= colorMid) {
                l++;
            }
            while (l <= r && colors[r] > colorMid) {
                r--;
            }
            if (l <= r) {
                int temp = colors[l];
                colors[l] = colors[r];
                colors[r] = temp;
                
                l++;
                r--;
            }
        }
        
        rainbowSort(colors, left, r, colorFrom, colorMid);
        rainbowSort(colors, l, right, colorMid + 1, colorTo);
    }
}

Move Zeroes

给一个数组 nums 写一个函数将 0 移动到数组的最后面，非零元素保持原数组的顺序

public class Solution {
    /**
     * @param nums: an integer array
     * @return: nothing
     */
    public void moveZeroes(int[] nums) {
        int left = 0, right = 0;
        while (right < nums.length) {
            if (nums[right] != 0) {
                if (left != right) {
                    nums[left] = nums[right];
                }
                left++;
            }
            right++;
        }
        while (left < nums.length) {
            if (nums[left] != 0) {
                nums[left] = 0;
            }
            left++;
        }
    }
}

reverse

Valid Palindrome

给定一个字符串，判断其是否为一个回文串。只考虑字母和数字，忽略大小写。

public class Solution {
    /**
     * @param s: A string
     * @return: Whether the string is a valid palindrome
     */
    public boolean isPalindrome(String s) {
        // write your code here
        if(s == null || s.length() == 0){
           return true;   
        }
        
        int left = 0;
        int right = s.length() - 1;

        while(left<right){
            while(left<right && !isValid(s.charAt(left))){
                left++;
            }
            
            while(left<right && !isValid(s.charAt(right))){
                right--;
            }
            
            if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))){
               return false;
            }
            
            left++;
            right--;
        }
        return true;
    }
    public boolean isValid(char c){
        return Character.isLetter(c) || Character.isDigit(c);
    }
    
}

Valid Palindrome II

给一个非空字符串 s，你最多可以删除一个字符。判断是否可以把它变成回文串。

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            left++;
            right--;
        }
        
        if (left >= right) {
            return true;
        }
        
        return isSubPalindrome(s, left + 1, right) || isSubPalindrome(s, left, right - 1);
    }
    
    private boolean isSubPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
}

Binary search

Posted on 2021-10-29 In Leetcode , Binary search
Symbols count in article: 7.4k Reading time ≈ 7 mins.

Template

private int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int start = 0, end = nums.length - 1;
    //adjent, [1,2] [3,4]
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] < target) {
            start = mid;
        } else if (nums[mid] == target) {
            end = mid;
        } else {
            end = mid;
        }
    }
    if (nums[start] == target) {
        return start;
    }
    if (nums[end] == target) {
        return end;
    }
    return -1;
}

Type

Random position of the target

public class Solution {
    public int findPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

First position of target

class Solution {
    public int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                end = mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

Last position of target

public class Solution {
    public int lastPosition(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                start = mid;
            } else if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[end] == target) {
            return end;
        } else if (nums[start] == target) {
            return start;
        } else {
            return -1;
        }
    }
}

Example

Search In a Big Sorted Array (Can not find the upper bound)

Exponential Backoff

Public int searchBigSortedArray(ArrayReader reader, int target) {
    int kth = 1;
    while (reader.get(kth - 1) < target) {
        kth = kth * 2;
    }
    int start = 0, end = kth - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (reader.get(mid) < targrt) {
            start = mid;
        } else {
            end = mid;
        }
        if (reader.get(start) == target) {
            return start;
        }
        if (reader.get(end) == target) {
            return end;
        }
        return -1;
    }
}

Find K Closest Elements

public int[] kClosestNumbers(int[] A, int[] target, int k) {
    //A[right] >= target, A[left] < target 
    int right = findUpperCloest(A, target);
    int left = right - 1;
    int[] results = new int[k];
    for (int i = 0; i < k; i++) {
        if (isLeftCloser(A, target, left, right)) {
            results[i] = A[left];
            left--;
        } else {
            results[i] = A[right];
            right++;
        }
    }
    return results;
}
private int findUpperCloest(int[] A, int target) {
    //the 1st number >= target
    int start = 0, end = A.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (A[mid] >= target) {
            end = mid;
        } else {
            start = mid;
        }
    }
    if (A[start] >= target) {
        return start;
    }
    if (A[end] >= target) {
        return end;
    }
    return A.length;
}
private boolean isLeftCloser(int[] A, int target, int left, int right) {
    //越界
    if (left < 0) {
        return false;
    }
    if (right >= A.length) {
        return true;
    }
    return (target - A[left] <= (A[right] - target));
}

Maximum Number in Mountain Sequence

12345654321

if have repeated number cannot use this method

public class Solution {
    public int mountainSequence(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
            
        // find first index i so that nums[i] > nums[i + 1]
        //OOOOOXXXX, find first X
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            // mid + 1 保证不会越界
            // 因为 start 和 end 是 start + 1 < end
            if (nums[mid] > nums[mid + 1]) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        return Math.max(nums[start], nums[end]);
    }
}

Find Minimum in Rotated Sorted Array

0 1 2 4 5 6 7 -> 4 5 6 7 0 1 2

-> 右边第一个位置

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0, end = nums.length - 1;
        //find first element <= target
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > nums[end]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        return Math.min(nums[start], nums[end]);
    }
}

follow up: [111111110111], repeated number O(n), can not be logn

Search in Rotated Sorted Array

Solution 1 : find minimum first(two binary search)

public int search(int[] A, int target) {
    if (A == null || A.length == 0) {
        return -1;
    }
    int index = findMinIndex(A);
    //the target in the right part
    if (A[index] <= target && target <= A[A.length - 1]) {
        return binarySearch(A, index, A.length - 1, target);
    }
    return binarySearch(A, 0, index - 1, target);
}
private int findMinIndex(int[] A) {
    int start = 0, end = A.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (A[mid] < A[end]) {
            end = mid;
        } else {
            start = mid;
        }
    }
    if (A[start] < A[end]) {
        return start;
    }
    return end;
}
private int binarySearch(int[] A, int start, int end, int target) {
    if (end < 0) {
        end += A.length;
    }
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (A[mid] < target) {
            start = mid;
        } else {
            end - mid;
        }
        if (A[start] == target) {
            return start;
        }
        if (A[end] == target) {
            return end;
        }
        return -1;
    }
}

Solution 2, directly cut

public int search(int[] A, int target) {
    if (A == null || A.length == 0) {
        return -1;
    }
    int start = 0, end = A.lenghth - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (A[mid] >= A[start]) {
            if (A[start] <= target && target <= A[mid]) {
                end = mid;
            } else {
                start = mid;
            }
        } else {
            if (A[mid] <= target && target <= A[end]) {
                start = mid;
            } else {
                end = mid;
            }
        }
    }
    if (A[start] == target) {
        return start;
    }
    if (A[end] == target) {
        return end;
    }
    return -1;
}

Non sorted array

Find peak element(any peak)

public int findPeak(int[] A) {
    int start = 1, end = A.length - 2;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        //left high go left
        if (A[mid] < A[mid - 1]) {
            end = mid;
        } else if (A[mid] < A[mid + 1]) { //right high go high
            start = mid;
        } else {
            return mid;
        }
    }
    if (A[start] < A[end]) {
        return end;
    } else {
        return start;
    }
}

wood cut

有一些原木，现在想把这些木头切割成一些长度相同的小段木头，需要得到的小段的数目至少为 k。给定L和k，你需要计算能够得到的小段木头的最大长度。

public int woodCut(int[] L, int k) {
    if (L == null || L.length == 0) {
        return 0;
    }
    long maxValue = 0, sumValue = 0;
    for (int i = 0; i < L.length; i++) {
        sumValue += L[i];
        maxValue = Math.max(maxValue, L[i]);
    }
    //log(min)
    int start = 1, end = (int)Math.min(maxValue, sumValue / k);
    if (start > end) {
        return 0;
    }
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (getPieces(L, mid) >= k) {
            start = mid;
        } else {
           end = mid;
        }
    }
    if (getPieces(L, end) >= k) {
        return end;
    }
    if (getPieces(L, start) >= k) {
        return start;
    }
    return 0;
}
//O(n)
private long getPieces(int[] L, int length) {
    long result = 0;
    for (int i = 0; i < L.length; i++) {
        result += L[i] / length;
    }
    return result;
}
//O(nlog(min))

Subarray_1

Posted on 2021-10-29 In Leetcode , Subarray
Symbols count in article: 3.9k Reading time ≈ 4 mins.

Question

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1. All the number is positive.

A subarray is a contiguous part of an array.

Example 1:

1 2	Input: nums = [1], k = 1 Output: 1

Example 2:

1 2	Input: nums = [1,2], k = 4 Output: -1

Example 3:

1 2	Input: nums = [2,1,2], k = 3 Output: 3

Constraints:

1 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5
1 <= k <= 10^9
Solution1 brute force

Step 1: analyze the question

[1, 2, 3, 4, 5, 6]

[start, end], sum -> time complexity: O(n^3) space complexity: O(1)

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
                int sumOfSubarray = 0;
                for (int i = 0; i <= end; i++) {
                    sumOfSubarray += nums[i];
                }
                //subarray 的加和的边界
                if (sumOfSubarray >= k) {
                    minLength = Math.min(minLength, end - start + 1);
                }
            }
        }
        if (minLength == Integer.MAX_VALUE) {
            return -1;
        }
        return minLength;
    }
}

Solution2 prefix sum

Step 1: analyze the question

[1, 2, 3, 4, 5, 6]

[0, 1, 2, 3, 4, 5, 6] sum from index 0 -> i, length = nums.length + 1

[start, end], sum -> prefixSum[end + 1] - prefixSum[start]

time complexity: O(n^2) space complexity: O(n)

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        int[] prefixSum = getPrefixSum(nums);
        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
                if (prefixSum[end + 1] - prefixSum[start] >= k) {
                    minLength = Math.min(minLength, end - start + 1);
                }
            }
        }
        if (minLength == Integer.MAX_VALUE) {
            return -1;
        }
        return minLength;
    }
    //prefixSum 的构建
    private int[] getPrefixSum(int[] nums) {
        int[] prefixSum = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        return prefixSum;
    }
}

Solution3 prefix sum + binary search(not work on this question, because the number could be negative)

Step 1: analyze the question

[1, 2, 3, 4, 5, 6]

[0, 1, 2, 3, 4, 5, 6] sum from index 0 -> i, length = nums.length + 1

[start, end], sum -> prefixSum[end + 1] - prefixSum[start]

fix start, use binary search to find end

time complexity: O(nlogn) space complexity: O(n)

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        int[] prefixSum = getPrefixSum(nums);
        for (int start = 0; start < n; start++) {
            int end = getEndOfSubarray(prefixSum, start, k);
            if (prefixSum[end + 1] - prefixSum[start] >= k) {
                minLength = Math.min(minLength, end - start + 1);
            }
        }
        if (minLength == Integer.MAX_VALUE) {
            return -1;
        }
        return minLength;
    }
    private int[] getPrefixSum(int[] nums) {
        int[] prefixSum = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        return prefixSum;
    }
    private int getEndOfSubarray(int[] prefixSum, int start, int k) {
        int left = start, right = prefixSum.length - 2;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid + 1] - prefixSum[start] >= k) {
                right = mid;
            }
            else {
                left = mid;
            }
        }
        if (prefixSum[left + 1] - prefixSum[start] >= k) {
            return left;
        }
        return right;
    }
}

Solution4 two point

Step 1: analyze the question

[1, 2, 3, 4, 5, 6]

i, j two point

i,j -> 0

j++ -> sum>=k

i++ until sum < k, minLength

time complexity: O(n) space complexity: O(1)

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        int sumOfSubarray = 0;
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j < n && sumOfSubarray < k) {
                sumOfSubarray += nums[j];
                j++;
            }
            if (sumOfSubarray >= k) {
                minLength = Math.min(minLength, j - i);
            }
            sumOfSubarray -= nums[i];
        }
        if (minLength == Integer.MAX_VALUE) {
            return -1;
        }
        return minLength;
    }
}

LeetCode 402. Remove K Digits

Posted on 2021-10-18 In Leetcode , Monotonic stack
Symbols count in article: 781 Reading time ≈ 1 mins.

Question

Given string num representing a non-negative integer num, and an integer k, return the smallest possible integer after removing k digits from num.

https://leetcode.com/problems/remove-k-digits/

class Solution {
    public String removeKdigits(String num, int k) {
        Stack<Character> stack = new Stack<>();
        for (char c : num.toCharArray()){
            while (!stack.isEmpty() && k > 0 && c < stack.peek()){
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        while (k-- > 0) stack.pop();
        StringBuilder sb = new StringBuilder();
        boolean zero = true;
        for (int element : stack){
            if (element == '0' && zero) continue;
            else zero = false;
            sb.append(element - '0');
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

Time complexity: O(n)

Space complexity: O(n)

LeetCode 1081. Smallest Subsequence of Distinct Characters

Posted on 2021-10-17 In Leetcode , Monotonic stack
Symbols count in article: 805 Reading time ≈ 1 mins.

Question

Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

class Solution {
    public String smallestSubsequence(String s) {
        Stack<Integer> stack = new Stack<>();
        int[] last = new int[128];
        Set<Integer> visited = new HashSet<>();
        for (int i = 0; i < s.length(); i++) last[s.charAt(i)] = i;
        for (int i = 0; i < s.length(); i++){
            int c = s.charAt(i);
            if (!visited.add(c)) continue;
            while (!stack.isEmpty() && c < stack.peek() && i < last[stack.peek()]) visited.remove(stack.pop());
            stack.push(c);
        }
        StringBuilder sb = new StringBuilder();
        for (int i : stack) sb.append((char)(i));
        return sb.toString();
    }
}

Time complexity: O(n)

Space complexity: O(n)

LeetCode 739. Daily Temperatures

Posted on 2021-10-16 In Leetcode , Monotonic stack
Symbols count in article: 709 Reading time ≈ 1 mins.

Question

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

https://leetcode.com/problems/daily-temperatures/

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length, res[] = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = n - 1; i >= 0; i--){
            while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) stack.pop();
            res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
            stack.push(i);
        }
        return res;
    }
}

Time complexity: O(n)

Space complexity: O(n)

LeetCode 1019. Next Greater Node In Linked List

Posted on 2021-10-15 In Leetcode , Monotonic stack
Symbols count in article: 917 Reading time ≈ 1 mins.

Question

You are given the head of a linked list with n nodes.

For each node in the list, find the value of the next greater node. That is, for each node, find the value of the first node that is next to it and has a strictly larger value than it.

Return an integer array answer where answer[i] is the value of the next greater node of the ith node (1-indexed). If the ith node does not have a next greater node, set answer[i] = 0.

https://leetcode.com/problems/next-greater-node-in-linked-list/

class Solution {
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        for (ListNode cur = head; cur != null; cur = cur.next) nums.add(cur.val);
        int n = nums.size();
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = n - 1; i >= 0; i--){
            while (!stack.isEmpty() && nums.get(i) >= stack.peek()) stack.pop();
            res[i] = stack.isEmpty() ? 0 : stack.peek();
            stack.push(nums.get(i));
        }
        return res;
    }
}

Time complexity: O(n)

Space complexity: O(n)