樊轶群的个人网站

// 0817. Linked List Components
class Solution {
    public int numComponents(ListNode head, int[] nums) {
        boolean[] exist = new boolean[10001];
        for (int num : nums) exist[num] = true;
        ListNode node = head;
        int ans = 0;
        boolean continues = false;
        while (node != null) {
            if (exist[node.val]) {
                if (!continues) {
                    ++ans;
                }
                continues = true;
            } else {
                continues = false;
            }
            node = node.next;
        }
        return ans;
    }
}

学习笔记：
今天这是一道哈希表的题目，但是用哈希表6ms。
用数组只需要1ms就行了。
简单题，还是要根据实际用例的范围来分析，哈哈哈。

// 1790. Check if One String Swap Can Make Strings Equal
class Solution {
    public boolean areAlmostEqual(String s1, String s2) {
        int differences = 0;
        int first = -1;
        int second = -1;
        for (int i = 0; i < s1.length(); ++i) {
            if (s1.charAt(i) != s2.charAt(i)) {
                ++differences;
                if (differences > 2) {
                    return false;
                }
                if (differences == 2) {
                    second = i;
                } else {
                    first = i;
                }
            }
        }
        if (differences == 0) return true;
        if (differences == 1) return false;
        return s1.charAt(first) == s2.charAt(second) && s1.charAt(second) == s2.charAt(first);
    }
}

学习笔记：
这是一道简单题，字符串数组。
先找不同点，如果超过两个就不行，提前返回。
如果没有，就ok。如果有一个，就不行。
只有刚好两个，就需要进一步比较交换后是否可行。

// 0801. Minimum Swaps To Make Sequences Increasing
class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int currentNoSwap = 0;
        int currentSwap = 1;
        for (int i = 1; i < n; ++i) {
            int previousNoSwap = currentNoSwap;
            int previousSwap = currentSwap;
            currentNoSwap = 131072;
            currentSwap = 131072;
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                currentNoSwap = previousNoSwap;
                currentSwap = previousSwap + 1;
            }
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                currentNoSwap = Math.min(currentNoSwap, previousSwap);
                currentSwap = Math.min(currentSwap, previousNoSwap + 1);
            }
        }
        return Math.min(currentNoSwap, currentSwap);
    }
}

学习笔记：
这是一道动态规划的题目，有一点困难。
有三种情况，
第一种是可以换，换了也行，不换也行。
第二种是必须换，不换就不行了。
第三种是不能换，换了就不行了。
可以根据条件来计算换和不换最小交换次数。
说是不会大于100000，所以就写了个131072来比较，不知道2的幂次会不会快一点。

// 0856. Score of Parentheses
class Solution {
    public int scoreOfParentheses(String s) {
        char[] parentheses = s.toCharArray();
        int[] stack = new int[25];
        int pointer = -1;
        for (char c : parentheses) {
            if (c == '(') {
                ++pointer;
                stack[pointer] = 0;
            } else if (stack[pointer] == 0) {
                --pointer;
                if (pointer == -1 || stack[pointer] == 0) {
                    ++pointer;
                    stack[pointer] = 1;
                } else {
                    stack[pointer] = stack[pointer] + 1;
                }
            } else {
                int top = stack[pointer];
                --pointer;
                --pointer;
                if (pointer == -1 || stack[pointer] == 0) {
                    ++pointer;
                    stack[pointer] = top * 2;
                } else {
                    top = top * 2 + stack[pointer];
                    stack[pointer] = top;
                }
            }
        }
        return stack[0];
    }
}

学习笔记：
这是一道栈的题目，但是用stack就需要1ms。
刚好今天比较空闲，就再尝试了手写数组模拟的栈，这样只需要0ms。

import java.util.Arrays;

// 0870. Advantage Shuffle
class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int len = nums1.length;
        Integer[] indexNums2 = new Integer[len];
        for (int i = 0; i < len; ++i) indexNums2[i] = i;
        Arrays.sort(nums1);
        Arrays.sort(indexNums2, (i, j) -> nums2[j] - nums2[i]);
        int biggest = len - 1;
        int smallest = 0;
        int[] ans = new int[len];
        for (Integer i : indexNums2) {
            if (nums1[biggest] > nums2[i]) {
                ans[i] = nums1[biggest];
                --biggest;
            } else {
                ans[i] = nums1[smallest];
                ++smallest;
            }
        }
        return ans;
    }
}

学习笔记：
这道题就是需要将索引进行排序，排序的参考是原本数组中数值的大小。
接下来就是贪心算法了，能放就放，不能放就搞个最小的凑数，相当于田忌赛马。

// 1800. Maximum Ascending Subarray Sum
class Solution {
    public int maxAscendingSum(int[] nums) {
        int ans = nums[0];
        int current = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > nums[i - 1]) {
                current += nums[i];
            } else {
                current = nums[i];
            }
            if (current > ans) {
                ans = current;
            }
        }
        return ans;
    }
}

学习笔记：
这是一道简单的数组水题。

// 0927. Three Equal Parts
class Solution {
    public int[] threeEqualParts(int[] arr) {
        int sum = 0;
        for (int d : arr) sum += d;
        if (sum == 0) return new int[]{0, 2};
        int[] ans = new int[]{-1, -1};
        if (sum % 3 != 0) return ans;
        int oneThird = sum / 3;
        int first1Part3 = arr.length;
        int count1 = 0;
        while (count1 != oneThird) {
            --first1Part3;
            count1 += arr[first1Part3];
        }
        int lengthPart = arr.length - first1Part3;
        int first1Part1 = 0;
        while (arr[first1Part1] == 0) ++first1Part1;
        for (int i = 0; i < lengthPart; ++i) {
            if (arr[first1Part1 + i] != arr[first1Part3 + i]) return new int[]{-1, -1};
        }
        ans[0] = first1Part1 + lengthPart - 1;
        int first1Part2 = first1Part1 + lengthPart;
        while (arr[first1Part2] == 0) ++first1Part2;
        for (int i = 0; i < lengthPart; ++i) {
            if (arr[first1Part2 + i] != arr[first1Part3 + i]) return new int[]{-1, -1};
        }
        ans[1] = first1Part2 + lengthPart;
        return ans;
    }
}

学习笔记：
这是一道困难题，需要把数字变成三等分。
首先我们找到最后一段，因为最后一段可以保证后面的确定性，至于前导零就不考虑了。
然后根据最后一段的情况，来找第一段，先去掉前导零，然后试试看对不对得上。
如果第一段没问题，就再去掉前导零试试看找第二段。
全部都没问题就可以把两个下标找到返回了。

// 0811. Subdomain Visit Count
class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        HashMap<String, Integer> hashMap = new HashMap<>();
        for (String cpdomain : cpdomains) {
            String[] splitted = cpdomain.split(" ");
            int times = Integer.parseInt(splitted[0]);
            String domain = splitted[1];
            if (hashMap.containsKey(domain)) {
                hashMap.put(domain, hashMap.get(domain) + times);
            } else {
                hashMap.put(domain, times);
            }
            int len = domain.length();
            for (int i = 0; i < len; ++i) {
                if ('.' == domain.charAt(i)) {
                    String subdomain = domain.substring(i + 1, len);
                    if (hashMap.containsKey(subdomain)) {
                        hashMap.put(subdomain, hashMap.get(subdomain) + times);
                    } else {
                        hashMap.put(subdomain, times);
                    }
                }
            }
        }
        List<String> ans = new LinkedList<>();
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            StringBuilder sb = new StringBuilder();
            sb.append(entry.getValue()).append(' ').append(entry.getKey());
            ans.add(sb.toString());
        }
        return ans;
    }
}

学习笔记：
这道题是哈希表统计数量的题目，不难，但巧妙的地方在于如何进行字符串的切割。

// 0921. Minimum Add to Make Parentheses Valid
class Solution {
    public int minAddToMakeValid(String s) {
        char[] parentheses = s.toCharArray();
        int stack = 0;
        int ans = 0;
        for (char c : parentheses) {
            if (c == '(') {
                ++stack;
            } else if (stack != 0) {
                --stack;
            } else {
                ++ans;
            }
        }
        return ans + stack;
    }
}

学习笔记：
今天的每日一题是一道栈的题目，但是其实我们也不需要用到真正的栈。
拿一个整数来模拟栈里左括号的数量也就行了。