樊轶群的个人网站

// 0670. Maximum Swap
class Solution {
    public int maximumSwap(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        int len = chars.length;
        int[] rightest = new int[]{-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
        for (int i = len - 1; i >= 0; --i) {
            if (rightest[chars[i] - 48] == -1) {
                rightest[chars[i] - 48] = i;
            }
        }
        for (int i = 0; i < len; ++i) {
            for (int j = 9; j > chars[i] - 48; --j) {
                if (rightest[j] > i) {
                    chars[rightest[j]] = chars[i];
                    chars[i] = (char) (j + 48);
                    return Integer.parseInt(String.valueOf(chars));
                }
            }
        }
        return num;
    }
}

学习笔记：
这是一道非常经典的题目，如果使用双重循环比较尝试的话，复杂度极高。
应该从右往左找出每个数字最右边的一个。
然后从左往右找出第一个需要替换的数字。

import java.util.Arrays;

// 1608. Special Array With X Elements Greater Than or Equal X
class Solution {
    public int specialArray(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        if (nums[0] >= len) return len;
        for (int i = 1; i < len; ++i) {
            if (nums[i] >= len - i) {
                if (nums[i - 1] >= len - i) {
                    return -1;
                }
                return len - i;
            }
        }
        return -1;
    }
}

学习笔记：
这道题就是找恰好有几个数大于几，总体来说就是排序，然后找一遍。
但是当中要注意的细节也不少，有些情况就是不存在的。

import java.util.Arrays;
import java.util.PriorityQueue;

// 0857. Minimum Cost to Hire K Workers
class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int len = quality.length;
        Worker[] workers = new Worker[len];
        for (int i = 0; i < len; ++i) {
            workers[i] = new Worker(quality[i], wage[i]);
        }
        Arrays.sort(workers, (Worker w1, Worker w2) -> (int) ((w1.costEffective - w2.costEffective) * 100000));
        PriorityQueue<Worker> pq = new PriorityQueue<>((Worker w1, Worker w2) -> w2.quality - w1.quality);
        long sumQuality = 0;
        for (int i = 0; i < k; ++i) {
            sumQuality += workers[i].quality;
            pq.offer(workers[i]);
        }
        double ans = sumQuality * workers[k - 1].costEffective;
        for (int i = k; i < len; ++i) {
            if (workers[i].quality < pq.peek().quality) {
                sumQuality -= pq.poll().quality;
                sumQuality += workers[i].quality;
                pq.offer(workers[i]);
                if (sumQuality * workers[i].costEffective < ans) {
                    ans = sumQuality * workers[i].costEffective;
                }
            }
        }
        return ans;
    }
}

class Worker {
    int quality;
    int wage;
    double costEffective;

    public Worker(int quality, int wage) {
        this.quality = quality;
        this.wage = wage;
        this.costEffective = wage * 1.0 / quality;
    }
}

学习笔记：
今天来当一个黑心资本家。
这是一道优先队列、排序的困难题。
先要进行排序，排序就是按照性价比的方式来排，然后维护一个优先队列，把干活多的放顶上，先踢出干活多的，然后看看能不能降低成本。

// 0669. Trim a Binary Search Tree
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val < low) return trimBST(root.right, low, high);
        if (root.val > high) return trimBST(root.left, low, high);
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

学习笔记：
这是一道二叉树相关的题目，不是很难，也不是特别简单。
主要就是用递归，不断递归。

// 1598. Crawler Log Folder
class Solution {
    public int minOperations(String[] logs) {
        int ans = 0;
        for (String log : logs) {
            if (log.equals("../")) {
                --ans;
                if (ans == -1) {
                    ans = 0;
                }
            } else if (log.equals("./")) {
            } else {
                ++ans;
            }
        }
        return ans;
    }
}

学习笔记：
这是一道简单题，就是简单的if语句，不过朋友圈发出去后梁亮提醒我equals尽量要把常量放前面。

// 0667. Beautiful Arrangement II
class Solution {
    public int[] constructArray(int n, int k) {
        int[] ans = new int[n];
        ans[0] = 1;
        int i = 1;
        boolean ascending = true;
        int low = 2;
        int high = n;
        while (k > 1) {
            if (ascending) {
                ans[i] = high;
                --high;
            } else {
                ans[i] = low;
                ++low;
            }
            ascending = !ascending;
            --k;
            ++i;
        }
        if (ascending) {
            while (i < n) {
                ans[i] = ans[i - 1] + 1;
                ++i;
            }
        } else {
            while (i < n) {
                ans[i] = ans[i - 1] - 1;
                ++i;
            }
        }
        return ans;
    }
}

学习笔记：
这是一道有趣的数组题目，一开始没思路。
后来拿出纸笔来举例子就有了。
比如要5个数字，4个变化。
那么就是1,5,2,4,3。
然后多一点，9个数字，8个变化。
1,9,2,8,3,7,4,6,5。低高低高交替
然后思考如果变化变少呢？
9个数字，3个变化。
1,9,2,3,4,5,6,7,8。
也就是低高低高交替，交替前3次，然后就一直持续+1或-1变化就不变了。
这道和之前某个做过的题目很像，我教过学生，但忘记具体是哪题了。

// 1592. Rearrange Spaces Between Words
class Solution {
    public String reorderSpaces(String text) {
        int spaceQuantity = 0;
        char[] chars = text.toCharArray();
        for (char c : chars) {
            if (c == ' ') {
                ++spaceQuantity;
            }
        }
        String[] strings = text.split("\\s+");
        ArrayList<String> arrayList = new ArrayList<>();
        for (String s : strings) {
            if (!s.equals("")) {
                arrayList.add(s);
            }
        }
        int wordQuantity = arrayList.size();
        StringBuilder spaces = new StringBuilder();
        StringBuilder ans = new StringBuilder();
        if (wordQuantity == 1) {
            ans.append(arrayList.get(0));
            for (int i = 0; i < spaceQuantity; ++i) {
                ans.append(' ');
            }
        } else {
            for (int i = 0; i < spaceQuantity / (wordQuantity - 1); ++i) {
                spaces.append(' ');
            }
            for (int i = 0; i < arrayList.size() - 1; ++i) {
                ans.append(arrayList.get(i));
                ans.append(spaces);
            }
            ans.append(arrayList.get(arrayList.size() - 1));
            for (int i = 0; i < spaceQuantity % (wordQuantity - 1); ++i) {
                ans.append(' ');
            }
        }
        return ans.toString();
    }
}

学习笔记：
这是一道简单的字符串题目。
这道题还是错了两次，如果只有一个单词的话，wordQuantity - 1就会变成0，会出现ZeroDivisionError，这个的确需要注意。

// 0828. Count Unique Characters of All Substrings of a Given String
class Solution {
    public int uniqueLetterString(String s) {
        ArrayList<ArrayList<Integer>> lettersPositions = new ArrayList<>();
        for (int i = 0; i < 26; ++i) lettersPositions.add(new ArrayList<>());
        char[] charArray = s.toCharArray();
        int length = charArray.length;
        for (int i = 0; i < length; ++i) lettersPositions.get(charArray[i] - 65).add(i);
        int ans = 0;
        for (ArrayList<Integer> letterPositions : lettersPositions) {
            int size = letterPositions.size();
            if (size != 0) {
                if (size == 1) {
                    ans += (letterPositions.get(0) + 1) * (length - letterPositions.get(0));
                } else {
                    ans += (letterPositions.get(0) + 1) * (letterPositions.get(1) - letterPositions.get(0));
                    for (int i = 1; i < size - 1; ++i) ans += (letterPositions.get(i) - letterPositions.get(i - 1)) * (letterPositions.get(i + 1) - letterPositions.get(i));
                    ans += (letterPositions.get(size - 1) - letterPositions.get(size - 2)) * (length - letterPositions.get(size - 1));
                }
            }
        }
        return ans;
    }
}

学习笔记：
这是一道困难题，难在想到要求出每一个字符的价值。
其实每个字符的价值就是上一次出现的差，还有下一次出现的差。如果没有出现，那就是-1和length。

// 0652. Find Duplicate Subtrees
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        HashMap<String, ArrayList<TreeNode>> hashMap = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();
        if (root.left != null) q.add(root.left);
        if (root.right != null) q.add(root.right);
        boolean hasNext = true;
        while (hasNext) {
            hasNext = false;
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode front = q.poll();
                String s = binaryTree2String(front);
                if (hashMap.containsKey(s)) {
                    hashMap.get(s).add(front);
                } else {
                    ArrayList<TreeNode> treeNodeArrayList = new ArrayList<>();
                    treeNodeArrayList.add(front);
                    hashMap.put(s, treeNodeArrayList);
                }
                if (front.left != null) {
                    q.offer(front.left);
                    hasNext = true;
                }
                if (front.right != null) {
                    q.offer(front.right);
                    hasNext = true;
                }
            }
        }
        List<TreeNode> ans = new ArrayList<>();
        for (Map.Entry<String, ArrayList<TreeNode>> e : hashMap.entrySet()) {
            if (e.getValue().size() > 1) {
                ans.add(e.getValue().get(0));
            }
        }
        return ans;
    }

    private String binaryTree2String(TreeNode node) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(node);
        boolean hasNext = true;
        while (hasNext) {
            hasNext = false;
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode front = q.poll();
                if (front == null) {
                    sb.append('n');
                } else {
                    sb.append('e');
                    sb.append(front.val);
                    if (front.left == null) {
                        sb.append('l');
                    } else {
                        q.offer(front.left);
                        hasNext = true;
                    }
                    if (front.right == null) {
                        sb.append('r');
                    } else {
                        q.offer(front.right);
                        hasNext = true;
                    }
                }
            }
        }
        return sb.toString();
    }
}

学习笔记：
这是一道有难度的二叉树题目，用到了二叉树的序列化。
我用的是宽度优先搜索来遍历结点，用宽度优先搜索来序列化。
其实效率上和深度优先搜索查的不多的。但是问题就在于还有更巧妙的方法。
不过想想也是，一个大子树如果有相同的，那么它下面的小子树肯定也有一堆相同了。
但是要怎么样不暴力的把他们都列出来，这就是很巧妙的问题了。
今天心浮气躁，不想做更深入的研究，就没继续做了。

// 1582. Special Positions in a Binary Matrix
class Solution {
    public int numSpecial(int[][] mat) {
        int[] rowSum = new int[mat.length];
        int[] colSum = new int[mat[0].length];
        for (int i = 0; i < mat.length; ++i) {
            for (int j = 0; j < mat[0].length; ++j) {
                if (mat[i][j] == 1) {
                    rowSum[i] += 1;
                    colSum[j] += 1;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < mat.length; ++i) {
            for (int j = 0; j < mat[0].length; ++j) {
                if (mat[i][j] == 1) {
                    if (rowSum[i] == 1 && colSum[j] == 1) {
                        ++ans;
                    }
                }
            }
        }
        return ans;
    }
}

学习笔记：
这是一道简单题，主要是矩阵的。
我发现了一个惊人的事情，那就是做if判断然后来决定加，和直接加0或1就直接加那个值。竟然if判断快很多。我一直以为不用if才是更快的更合理更巧妙的。