Leetcode record - March 2023

March 21, 2023

Binary Search

Find left bound/right bound

public int[] searchRange(int[] nums, int target) {
    return new int[]{helper(nums, target, true), helper(nums, target, false)};
}

public int helper(int[] nums, int target,boolean trueIfSearchLeftBound){
    int l = 0;
    int r = nums.length-1;
    int res = -1;
    while (l<=r){
        int midl = (l+r)/2;
        if (nums[midl]>target){
            r = midl-1;
        }else if(nums[midl]<target){
            l = midl+1;
        }else{
            res = midl;
            if (trueIfSearchLeftBound){
                r = midl-1;
            }else{
                l = midl+1;
            }
        }
    }
    System.out.println(res);
    return res;
}

Find minimal value

public static int findMin(int[] nums) {
        int len = nums.length;
        int low = 0;
        int high = len-1;

//        二分查找
        while(low < high){
//            取中间值
            int mid = (high+low)/2;
//            如果中间值小于最大值，则最大值减小
//            疑问：为什么 high = mid;而不是 high = mid-1;
//            解答：{4,5,1,2,3}，如果high=mid-1，则丢失了最小值1
            if (nums[mid] < nums[high]) {
                high = mid;
            } else {
//                如果中间值大于最大值，则最小值变大
//                疑问：为什么 low = mid+1;而不是 low = mid;
//                解答：{4,5,6,1,2,3}，nums[mid]=6，low=mid+1,刚好nums[low]=1
//                继续疑问：上边的解释太牵强了，难道没有可能low=mid+1,正好错过了最小值
//                继续解答：不会错过!!! 如果nums[mid]是最小值的话，则其一定小于nums[high],走if，就不会走else了
                low = mid+1;
            }
        }
//        疑问：为什么while的条件是low<high,而不是low<=high呢
//        解答：low<high，假如最后循环到{*,10,1,*}的这种情况时，nums[low]=10,nums[high]=1,nums[mid]=10,low=mid+1,
//             直接可以跳出循环了,所以low<high,此时low指向的就是最小值的下标;
//             如果low<=high的话，low=high，还会再不必要的循环一次，此时最后一次循环的时候会发生low==high==mid，
//             则nums[mid]==nums[high]，则会走一次else语句，则low=mid+1,此时low指向的是最小值的下一个下标，
//             则需要return[low-1]
        return nums[low];
    }

String Input

How to input String:

public static void main(String[] args) {
    Scanner sc = newScanner(System.in);
    String str = sc.nextLine().toString();
    int[] dis =getIntArr(str);
    str = sc.nextLine().toString();
    int[] eng =getIntArr(str);
    int maxDis = sc.nextInt();
}
static int[] getIntArr(String str){
    String[] arr  = str.split(" ");
    int[] b = new int[arr.length];
    for(int j = 0; j<b.length;j++) {
        b[j] = Integer.parseInt(arr[j]);
    }
    return b;
}

ByteDance Spring recruit

1.万万没想到之聪明的编辑

三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello
两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello
上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC

输入例子： 2 helloo wooooooow

输出例子： hello woow

感悟：队列+枚举。在很难一次遍历完全时可以牺牲空间换取更便利的写法。四个一组分类讨论，不一定要一次就分出来

import java.util.*;

public class Main {
    public static String repair(String s) {
        List<Character> queue = new ArrayList<>();
        StringBuilder res = new StringBuilder();
        for (char c : s.toCharArray()) {
            queue.add(c);
            if (queue.size() == 4) {
                if(queue.get(0)==queue.get(1) && queue.get(1)==queue.get(2)&& queue.get(3)==queue.get(2)){
                    queue.remove(3);
                    queue.remove(2);
                }else if(queue.get(0)==queue.get(1) && queue.get(1)==queue.get(2)){
                    queue.remove(2);
                }else if(queue.get(1)==queue.get(2) && queue.get(2)==queue.get(3)){
                    queue.remove(3);
                }else if(queue.get(0)==queue.get(1) && queue.get(2)==queue.get(3)){
                    queue.remove(3);
                }else{
                    res.append(queue.remove(0));
                }
            }
        }
        for(char c: queue){
            res.append(c);
        }
        return res.toString();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();//处理读int剩下的Enter
        for (int i = 0; i < n; i++) {
            String s = sc.nextLine();
            System.out.println(repair(s));
        }
    }
}

3.雀魂启动！

小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。

于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：

总共有36张牌，每张牌是1~9。每个数字4张牌。
你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌

14张牌中有2张相同数字的牌，称为雀头。
除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如111,777）

public class Main {
    private static int[]arr= new int[13];
    private static int[]count;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

				count= new int[9];
        for (int i = 0; i <arr.length; i++) {
						arr[i] = scanner.nextInt();
            ++count[arr[i]-1];
        }
        int winCount = 0;
        // 选择1到9中的一个作为第14张牌，然后判断是否胡牌
        for (int i = 1 ; i <= 9; i++) {
            if(count[i-1]<4){
                ++count[i-1];
                if(win()){
                    ++winCount;
                    System.out.print(i);
                    System.out.print(" ");
                }
                --count[i-1];
            }
        }
        if(winCount==0){
            System.out.println(0);
        }
    }
    public static boolean win(){
        // 从1到9 中选择一个作为雀头, 然后判断剩余的牌是否构成4对
        for (int i = 1; i <= 9; i++) {
            if(count[i-1]<2){
                continue;
            }
						count[i-1]-=2;
            if(hasTriples(4)){
								count[i-1]+=2;
                return true;
            }
						count[i-1]+=2;
        }
        return false;
    }

    public static boolean hasTriples(int n){
        if(n==0){
            return true;
        }
        // 1到9，每一张牌尝试三张或顺子
        for (int i = 1; i <= 9; i++) {
            if(count[i-1]>=3){
								count[i-1]-=3;
                boolean subHashTriples =hasTriples(n-1);
								count[i-1]+=3;
                if(subHashTriples){
                    return true;
                }
            }
            if(i<=7  &&count[i-1]>0 &&count[i] > 0 &&count[i+1]>0){
                --count[i-1];
                --count[i];
                --count[i+1];
                boolean subHasTriples =hasTriples(n-1);

                ++count[i-1];
                ++count[i];
                ++count[i+1];
                if(subHasTriples){
                    return true;
                }
            }
        }
        return false;
    }
}

Sliding window

Template：

void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char r = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新,准备判断条件
        ...

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char l = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新，更新判断条件
            ...
        }
    }
}
需要变化的地方

1、右指针右移之后窗口数据更新
2、判断窗口是否要收缩
3、左指针右移之后窗口数据更新
4、根据题意计算结果

1. Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.

The testcases will be generated such that the answer is unique.

Example 1:

Input: s = “ADOBECODEBANC”, t = “ABC” Output: “BANC” Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.

public String minWindow(String s, String t) {
    //s = "ADOBECODEBANC", t = "ABC"
    int left = 0;
    int right = 0;
    // 窗口调整前暂存原窗口边界
    int start = 0;
    int end = 0;
    int count = 0;
    int minValue = Integer.MAX_VALUE;
    int []need = new int[128]; //{A:1, B:1, C:1}
    int []window = new int[128];//{A:2,B:2,C:2, D:...}
    for(char c: t.toCharArray()){
        need[c]++;//count appear times
    }
    while (right<s.length()){
        char r = s.charAt(right);
        if (window[r]<need[r]){
            count++;
        }
        window[r]++;
        right++;
        while (count==t.length()){
            if (right-left<minValue){
                minValue = right-left;
                start = left;
                end = right;
            }
            char l = s.charAt(left);
            if (window[l]==need[l] && need[l]!=0){
                count--;
            }
            left++;
            window[l]--;
        }
    }
    return s.substring(start,end);
}

82. Remove Duplicates from Sorted List II

class Solution {//Better to modify the pointer instead of create a new LinkedList
        public ListNode deleteDuplicates(ListNode head) {
            ListNode pre = new ListNode(0,head);
            ListNode cur = pre;
        while(cur.next != null && cur.next.next != null) {
            if(cur.next.val == cur.next.next.val) {
                int val = cur.next.val;
                while(cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return pre.next;
        }
}

120. Triangle

/*
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

*/
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int n = triangle.size();
        int[][] dp = new int[n][n];
        // Initialize the last row of DP array with the last row of the triangle
        for (int i = 0; i < n; i++) {
            dp[n-1][i] = triangle.get(n - 1).get(i);
        }
        // Start from the second last row and work your way up
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // For each element in the row, find the minimum sum path
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i+1][j], dp[i+1][j + 1]);
            }
        }

        return dp[0][0];
    }
}

技术