樊轶群的个人网站

// 0641. Design Circular Deque
class MyCircularDeque {

    private final int[] values;
    private final int capacity;
    private int size;
    private int f;
    private int r;

    public MyCircularDeque(int k) {
        values = new int[k];
        capacity = k;
        size = 0;
        f = 0;
        r = 0;
    }

    public boolean insertFront(int value) {
        if (size == capacity) return false;
        if (size != 0) f = (f + 1) % capacity;
        values[f] = value;
        ++size;
        return true;
    }

    public boolean insertLast(int value) {
        if (size == capacity) return false;
        if (size != 0) r = (r + capacity - 1) % capacity;
        values[r] = value;
        ++size;
        return true;
    }

    public boolean deleteFront() {
        if (size == 0) return false;
        if (size != 1) f = (f + capacity - 1) % capacity;
        --size;
        return true;
    }

    public boolean deleteLast() {
        if (size == 0) return false;
        if (size != 1) r = (r + 1) % capacity;
        --size;
        return true;
    }

    public int getFront() {
        if (size == 0) return -1;
        return values[f];
    }

    public int getRear() {
        if (size == 0) return -1;
        return values[r];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }
}

学习笔记：
和之前循环队列差的不多，可以先把图在iPad上画出来，然后推演各种情况。
但是还是有不少的bug，所以细心真的很重要，我这跑了很多很多遍才全部跑通。

// 1422. Maximum Score After Splitting a String
class Solution {
    public int maxScore(String s) {
        char[] chars = s.toCharArray();
        int score = 0;
        for (char c : chars) {
            score += c - 48;
        }
        score += 97 - chars[0] * 2;
        int maxScore = score;
        for (int i = 1; i < chars.length - 1; ++i) {
            score += 97 - chars[i] * 2;
            if (score > maxScore) {
                maxScore = score;
            }
        }
        return maxScore;
    }
}

学习笔记：
这是一道简单的字符串题目。
将所有能去掉的if语句全部去掉，尽全力加速。
但其实还是1ms并没有到0ms，要到0ms必须将s转成char，可能是因为charAt需要判断越界啥的属实太慢了吧。
不使用if语句的难点不在于一开始的c-48，而在于后面，如果将'0'映射到+1而'1'映射到-1。
我是分两步走，先将两个数字的差距从1调整到2，然后再用合适的数字进行一波加减。最终得出的就是97 - chars[i] * 2，感觉找到了初中数学找函数规律的题目了。当然可以达到目的的函数有很多，但是最简单的要改就是这个了吧。

// 0768. Max Chunks To Make Sorted II
class Solution {
    public int maxChunksToSorted(int[] arr) {
        Stack<Block> stack = new Stack<>();
        stack.push(new Block(arr[0], arr[0]));
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i] >= stack.peek().maxNum) {
                stack.push(new Block(arr[i], arr[i]));
            } else if (arr[i] < stack.peek().minNum) {
                Block insert = new Block(arr[i], stack.peek().maxNum);
                while (!stack.empty() && insert.minNum < stack.peek().maxNum) {
                    Block top = stack.pop();
                    if (insert.minNum > top.minNum) {
                        insert.minNum = top.minNum;
                    }
                }
                stack.push(insert);
            }
        }
        return stack.size();
    }
}

class Block {
    int minNum;
    int maxNum;

    Block(int minNum, int maxNum) {
        this.minNum = minNum;
        this.maxNum = maxNum;
    }
}

学习笔记：
这是一道有趣的困难题。
一开始我想到的解法是从左往右贪心+局部排序。但这样时间复杂度真的爆表。后来看了提示说用栈，然后就写了一个栈的。但是不知道为什么速度就是偏慢，别人应该用的是其它的思路。我用了面向对象的思路，内存还是特别省的。

// 1282. Group the People Given the Group Size They Belong To
class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        HashMap<Integer, ArrayList<Integer>> hashMap = new HashMap<>();
        for (int i = 0; i < groupSizes.length; ++i) {
            if (!hashMap.containsKey(groupSizes[i])) {
                hashMap.put(groupSizes[i], new ArrayList<>());
            }
            hashMap.get(groupSizes[i]).add(i);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (Map.Entry<Integer, ArrayList<Integer>> e : hashMap.entrySet()) {
            int i = 0;
            int listSize = e.getValue().size();
            while (i < listSize) {
                ans.add(new ArrayList<>());
                for (int j = 0; j < e.getKey(); ++i, ++j) {
                    ans.get(ans.size() - 1).add(e.getValue().get(i));
                }
            }
        }
        return ans;
    }
}

学习笔记：
这是一道用到哈希表的题目，我写得特别顺利，而且高效，但是不知道为什么速度是8ms，只击败了20%的用户。
可能因为我是把所有的遍历了一遍，分了组，然后再装起来。但是这应该没速度上的影响才对。最近工作繁忙，得等有空了再研究了。

// 1417. Reformat The String
class Solution {
    public String reformat(String s) {
        int letterQuantity = 0;
        for (char c : s.toCharArray()) {
            letterQuantity += c / 97;
        }
        boolean fillDigit;
        if (letterQuantity * 2 + 1 == s.length()) {
            fillDigit = true;
        } else if (letterQuantity * 2 - 1 == s.length()) {
            fillDigit = false;
        } else if (letterQuantity * 2 == s.length()) {
            fillDigit = true;
        } else {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        int indexDigit = 0;
        int indexLetter = 0;
        while (sb.length() < s.length()) {
            if (fillDigit) {
                while (s.charAt(indexDigit) > 96) {
                    ++indexDigit;
                }
                sb.append(s.charAt(indexDigit));
                ++indexDigit;
            } else {
                while (s.charAt(indexLetter) < 59) {
                    ++indexLetter;
                }
                sb.append(s.charAt(indexLetter));
                ++indexLetter;
            }
            fillDigit = !fillDigit;
        }
        return sb.toString();
    }
}

学习笔记：
这是一道字符串的简单题。
ascii码的数字分别代表什么如果可以掌握得好，写起判断来就可以简单直接且快速，不需要用其它奇怪的接口。

// 0640. Solve the Equation
class Solution {
    public String solveEquation(String equation) {
        equation += '+';
        boolean beforeEqualSign = true;
        boolean positive = true;
        boolean isConstant = true;
        int totalCoefficients = 0;
        int totalConstants = 0;
        int num = 0;
        for (int i = 0; i < equation.length(); ++i) {
            char charAtI = equation.charAt(i);
            if (charAtI == '+' || charAtI == '-' || charAtI == '=') {
                if (!positive) {
                    num *= -1;
                }
                if (isConstant) {
                    totalConstants += num;
                } else {
                    totalCoefficients += num;
                }
                if (charAtI == '+') {
                    positive = beforeEqualSign;
                } else if (charAtI == '-') {
                    positive = !beforeEqualSign;
                } else {
                    positive = false;
                    beforeEqualSign = false;
                }
                isConstant = true;
                num = 0;
            } else if (charAtI == 'x') {
                isConstant = false;
                if (i == 0 || equation.charAt(i - 1) == '+' || equation.charAt(i - 1) == '=' || equation.charAt(i - 1) == '-') {
                    num = 1;
                }
            } else {
                num = num * 10 + charAtI - 48;
            }
        }
        totalConstants *= -1;
        if (totalCoefficients == 0) {
            if (totalConstants == 0) {
                return "Infinite solutions";
            } else {
                return "No solution";
            }
        }
        return "x=" + totalConstants / totalCoefficients;
    }
}

学习笔记：
这道题就是简单的字符串题，也用到了基础的数学。
做这类简单等式，就是需要移项整理，把x移到左边，把常数项移到右边。
那这里为了方便就先都放左边，然后最后算完乘以-1。
这里有个小技巧就是在最后加一个符号，让最后的一个数字也可以正常计算。
特别要注意的是x如果没有系数，那系数可不是0，但是本身系数是0也有可能。
然后我还发现了java的基本数据类型里面boolean无法直接转化为int，int没有办法取反，这实在太麻烦了，很多巧妙的计算得走判断。

// 1413. Minimum Value to Get Positive Step by Step Sum
class Solution {
    public int minStartValue(int[] nums) {
        int prefixSum = 0;
        int minPrefixSum = Integer.MAX_VALUE;
        for (int num : nums) {
            prefixSum += num;
            if (prefixSum < minPrefixSum) {
                minPrefixSum = prefixSum;
            }
        }
        return Math.max((minPrefixSum - 1) * -1, 1);
    }
}

学习笔记：
这是一道前缀和的简单题。
我一开始是把-1加到第一项，然后从第二项开始算。但后来发现没必要，直接算完最后处理结果才是最佳策略。

// 0761. Special Binary String
class Solution {
    public String makeLargestSpecial(String s) {
        if (s.length() < 3) {
            return s;
        }
        int prefixSum = 0;
        int processed = 0;
        PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '1') {
                ++prefixSum;
            } else {
                --prefixSum;
                if (prefixSum == 0) {
                    pq.offer("1" + makeLargestSpecial(s.substring(processed + 1, i)) + "0");
                    processed = i + 1;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            sb.append(pq.poll());
        }
        return sb.toString();
    }
}

学习笔记：
这是一道很困难的字符串题，需要用到分治思想递归调用。
找到每一个最大的1和0包的部分，再内部排序，排完序之后整体排序。
看完后会发觉这道题目的精妙。
一开始我用了List和Collections.sort()，String.join()来返回，这样时间是3ms。
我觉得可能是排序消耗比较花时间吧，就改用了PriorityQueue，用了之后就报错了，这里有一个坑，就是使用 增强for循环 和 迭代器遍历 是不可以按正确顺序遍历PriorityQueue的，所以得用记录size后的普通for循环 或者 while循环来遍历。
这道题的PriorityQueue是个最大堆，可以使用Comparator，也可以使用lambda表达式。
(o1, o2) -> {return o2.compareTo(o1);}

// 0636. Exclusive Time of Functions
class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] ans = new int[n];
        Stack<LogObject> stack = new Stack<>();
        for (String log : logs) {
            LogObject logObject = new LogObject(log);
            if (stack.empty()) {
                stack.push(logObject);
            } else if (logObject.isStart) {
                ans[stack.peek().functionId] += logObject.timestamp - stack.peek().timestamp;
                stack.push(logObject);
            } else {
                ans[stack.peek().functionId] += logObject.timestamp - stack.peek().timestamp + 1;
                stack.pop();
                if (!stack.empty()) {
                    stack.peek().timestamp = logObject.timestamp + 1;
                }
            }
        }
        return ans;
    }
}

class LogObject {
    int functionId;
    boolean isStart;
    int timestamp;

    LogObject(String s) {
        this.functionId = Integer.parseInt(s.substring(0, s.indexOf(':')));
        this.isStart = s.substring(s.indexOf(':') + 1, s.lastIndexOf(':')).equals("start");
        this.timestamp = Integer.parseInt(s.substring(s.lastIndexOf(':') + 1));
    }
}

学习笔记：
这是一道栈的题目，也用到了切割字符串。
这里我选择使用了创建类和转化成对象的思路来做，本来以为会导致时间和空间升高，没想到
执行用时：9 ms, 在所有 Java 提交中击败了95.92%的用户
内存消耗：41.7 MB, 在所有 Java 提交中击败了96.55%
这样写出来代码又好看又好懂真是太妙了。
这道题的难点是用栈后的五种情况，栈是不是空了，id是否一样，开关是否一样。在遇到各种情况需要怎么处理，是压栈还是出栈还是是结算，最后发现其实只有三条分支。

// 1408. String Matching in an Array
class Solution {
    public List<String> stringMatching(String[] words) {
        List<String> ans = new ArrayList<>();
        String allWords = String.join(",", words);
        for (String word : words) {
            if (allWords.indexOf(word) != allWords.lastIndexOf(word)) {
                ans.add(word);
            }
        }
        return ans;
    }
}

学习笔记：
这里使用的是一个String.join()函数，传入分隔符后可以传入数组或者迭代器。
这种方式比用StringBuilder再转回String还剩了1.3M的内存。
接下来就是最巧妙的地方了，从前往后找和从后往前找，找到这个单词两次也就是索引不同，找到这个单词一次就是索引相同。