樊轶群的个人网站

import java.util.HashSet;
import java.util.Set;

// 1704. Determine if String Halves Are Alike
class Solution {
    public boolean halvesAreAlike(String s) {
        Set<Character> vowels = new HashSet<>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');
        vowels.add('A');
        vowels.add('E');
        vowels.add('I');
        vowels.add('O');
        vowels.add('U');
        int len = s.length();
        int leftVowels = 0;
        for (int i = 0; i < len / 2; ++i) {
            if (vowels.contains(s.charAt(i))) {
                ++leftVowels;
            }
        }
        int rightVowels = 0;
        for (int i = len / 2; i < len; ++i) {
            if (vowels.contains(s.charAt(i))) {
                ++rightVowels;
            }
        }
        return leftVowels == rightVowels;
    }
}

学习笔记：
这是一道字符串的简单题，用到的是哈希表。

import java.util.*;

// 0864. Shortest Path to Get All Keys
class Solution {
    public int shortestPathAllKeys(String[] grid) {
        int sx = -1;
        int sy = -1;
        int m = grid.length;
        int n = grid[0].length();
        int maxKey = -1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                char c = grid[i].charAt(j);
                if (c == '@') {
                    sx = i;
                    sy = j;
                }
                if (c >= 'a' && c <= 'f') {
                    maxKey = Math.max(c - 'a' + 1, maxKey);
                }
            }
        }
        State start = new State(0, sx, sy);
        Queue<State> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        visited.add(0 + " " + sx + " " + sy);
        queue.offer(start);
        int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                State cur = queue.poll();
                if (cur.keys == (1 << maxKey) - 1) {
                    return step;
                }
                for (int[] direction : directions) {
                    int nx = cur.x + direction[0];
                    int ny = cur.y + direction[1];
                    int keys = cur.keys;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        char c = grid[nx].charAt(ny);
                        if (c == '#') {
                            continue;
                        }
                        if (c >= 'a' && c <= 'f') {
                            keys |= 1 << (c - 'a');
                        }
                        if (c >= 'A' && c <= 'F' && ((keys >> (c - 'A')) & 1) == 0) {
                            continue;
                        }
                        if (!visited.contains(keys + " " + nx + " " + ny)) {
                            visited.add(keys + " " + nx + " " + ny);
                            queue.offer(new State(keys, nx, ny));
                        }
                    }
                }
            }
            ++step;
        }
        return -1;
    }
}

class State {
    int keys;
    int x;
    int y;

    State(int keys, int x, int y) {
        this.keys = keys;
        this.x = x;
        this.y = y;
    }
}

学习笔记：
这是一道超级困难题，用到了宽度优先搜索、状态压缩、位运算。
遍历过的点当时的状态可以用3维数组存储，也可以使用hashset。
其实用hashset更科学，3维数组比较费空间。

// 0764. Largest Plus Sign
class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        int[][] grid = new int[n][n];
        int[][] maxArm = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                grid[i][j] = 1;
            }
        }
        for (int[] mine : mines) {
            grid[mine[0]][mine[1]] = 0;
        }
        for (int i = 0; i < n; ++i) {
            int continuesOnes = 0;
            for (int j = 0; j < n; ++j) {
                continuesOnes = (continuesOnes + grid[i][j]) * grid[i][j];
                maxArm[i][j] = continuesOnes;
            }
            continuesOnes = 0;
            for (int j = n - 1; j >= 0; --j) {
                continuesOnes = (continuesOnes + grid[i][j]) * grid[i][j];
                maxArm[i][j] = Math.min(maxArm[i][j], continuesOnes);
            }
        }
        for (int j = 0; j < n; ++j) {
            int continuesOnes = 0;
            for (int i = 0; i < n; ++i) {
                continuesOnes = (continuesOnes + grid[i][j]) * grid[i][j];
                maxArm[i][j] = Math.min(maxArm[i][j], continuesOnes);
            }
            continuesOnes = 0;
            for (int i = n - 1; i >= 0; --i) {
                continuesOnes = (continuesOnes + grid[i][j]) * grid[i][j];
                maxArm[i][j] = Math.min(maxArm[i][j], continuesOnes);
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                ans = Math.max(ans, maxArm[i][j]);
            }
        }
        return ans;
    }
}

学习笔记：
这是一道说是动态规划但似乎又不是动态规划的题目。
因为动态规划应该是无后效性的，但他分四个方向推了四次。
这里代码用逻辑来写应该是
if (grid[i][j] == 1) {
    ++continuesOnes;
} else {
    continuesOnes = 0;
}
但是想不用愚蠢的if语句，可以先加1或0，然后再乘1或0。
continuesOnes = (continuesOnes + grid[i][j]) * grid[i][j];
用if语句24ms，直接计算25ms，反而是用了if语句更快，只能说现在的CPU可能在分支预判上做得不错了，导致不用if语句的优势反而失去了。
但不用if语句的妙处还是很有滋味的。

// 1684. Count the Number of Consistent Strings
class Solution {
    public int countConsistentStrings(String allowed, String[] words) {
        boolean[] forbiddenLetters = new boolean[123];
        for (int i = 97; i < 123; ++i) {
            forbiddenLetters[i] = true;
        }
        for (char c : allowed.toCharArray()) {
            forbiddenLetters[c] = false;
        }
        int ans = 0;
        OUTER:
        for (String word : words) {
            for (char letter : word.toCharArray()) {
                if (forbiddenLetters[letter]) {
                    continue OUTER;
                }
            }
            ++ans;
        }
        return ans;
    }
}

学习笔记：
简单题，一道字符串遍历的水题。

import java.util.LinkedList;
import java.util.List;

// 0816. Ambiguous Coordinates
class Solution {
    public List<String> ambiguousCoordinates(String s) {
        List<String> ans = new LinkedList<>();
        int len = s.length();
        for (int mid = 2; mid < len - 1; ++mid) {
            List<String> leftNumbers = generateValidNumbers(s.substring(1, mid));
            List<String> rightNumbers = generateValidNumbers(s.substring(mid, len - 1));
            for (String leftNumber : leftNumbers) {
                for (String rightNumber : rightNumbers) {
                    StringBuilder sb = new StringBuilder();
                    sb.append('(').append(leftNumber).append(',').append(' ').append(rightNumber).append(')');
                    ans.add(sb.toString());
                }
            }
        }
        return ans;
    }

    private List<String> generateValidNumbers(String number) {
        int len = number.length();
        List<String> ret = new LinkedList<>();
        if (number.charAt(0) == '0') {
            if (len == 1) {
                ret.add("0");
                return ret;
            } else if (number.charAt(len - 1) != '0') {
                ret.add("0." + number.substring(1, len));
            }
        } else {
            ret.add(number);
            if (number.charAt(len - 1) != '0') {
                for (int i = 1; i < len; ++i) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(number.substring(0, i)).append('.').append(number.substring(i, len));
                    ret.add(sb.toString());
                }
            }
        }
        return ret;
    }
}

学习笔记：
这是一道字符串的中等题，但我感觉已经挺复杂了。
首先是切分，切分完后左半段找出所有合法组合，右半段找出所有合法组合，然后拼起来。
最麻烦的就是前导零也就是第一位是0还有末尾多余0的情况。需要分类讨论。

// 1678. Goal Parser Interpretation
class Solution {
    public String interpret(String command) {
        char[] charArray = command.toCharArray();
        int len = charArray.length;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; ++i) {
            if (charArray[i] == 'G') {
                sb.append('G');
            } else if (charArray[i + 1] == ')') {
                ++i;
                sb.append('o');
            } else {
                i += 3;
                sb.append("al");
            }
        }
        return sb.toString();
    }
}

学习笔记：
这是一道水题，字符串拼接。
今天也是第100天，没想到自己真坚持了那么久了。

import java.util.Stack;

// 1106. Parsing A Boolean Expression
class Solution {
    public boolean parseBoolExpr(String expression) {
        Stack<Character> stack = new Stack<>();
        char[] charArray = expression.toCharArray();
        for (char c : charArray) {
            if (c == 't' || c == 'f' || c == '!' || c == '&' || c == '|') {
                stack.push(c);
            } else if (c == ')') {
                boolean hasTrue = false;
                boolean hasFalse = false;
                while (stack.peek() == 't' || stack.peek() == 'f') {
                    if (stack.pop() == 't') {
                        hasTrue = true;
                    } else {
                        hasFalse = true;
                    }
                }
                char operator = stack.pop();
                char preIn;
                if (operator == '!') {
                    preIn = hasTrue ? 'f' : 't';
                } else if (operator == '&') {
                    preIn = hasFalse ? 'f' : 't';
                } else {
                    preIn = hasTrue ? 't' : 'f';
                }
                stack.push(preIn);
            }
        }
        return stack.peek() == 't';
    }
}

学习笔记：
这是一道困难题，用到的是栈。
根据不同的字符来进行处理，先在纸上推演几遍，然后写成代码就可以一气呵成。

// 0754. Reach a Number
class Solution {
    public int reachNumber(int target) {
        int total = 0;
        int ans = 0;
        target = Math.abs(target);
        while (total < target || ((total - target) & 1) != 0) {
            ++ans;
            total += ans;
        }
        return ans;
    }
}

学习笔记：
这是一道贪心算法的题目。
目标肯定要能到，要大于或者等于。等于就方便，大于就要往回，一往回就必须是2的倍数。
不然得再加一个奇数，调整奇偶性。

// 1668. Maximum Repeating Substring
class Solution {
    public int maxRepeating(String sequence, String word) {
        String find = "";
        while (sequence.contains(find)) find = find + word;
        return find.length() / word.length() - 1;
    }
}

学习笔记：
这是一道比较水的字符串水题。
暴力解法就是每次多加一个，然后看看存不存在。然后返回一个答案。
不知道二分法是个什么情况，过段时间有空了写写看。

// 1620. Coordinate With Maximum Network Quality
class Solution {
    public int[] bestCoordinate(int[][] towers, int radius) {
        int[] ans = new int[2];
        int maxNetworkQuality = 0;
        int minX = 50;
        int maxX = 0;
        int minY = 50;
        int maxY = 0;
        for (int[] tower : towers) {
            if (tower[0] > maxX) maxX = tower[0];
            if (tower[0] < minX) minX = tower[0];
            if (tower[1] > maxY) maxY = tower[1];
            if (tower[1] < minY) minY = tower[1];
        }
        for (int x = minX; x <= maxX; ++x) {
            for (int y = minY; y <= maxY; ++y) {
                int networkQuality = 0;
                for (int[] tower : towers) {
                    double distance = (Math.sqrt(Math.pow(Math.abs(tower[0] - x), 2) + Math.pow(Math.abs(tower[1] - y), 2)));
                    if (distance <= radius) {
                        networkQuality += (int) (tower[2] / (1 + distance));
                    }
                }
                if (networkQuality > maxNetworkQuality) {
                    maxNetworkQuality = networkQuality;
                    ans[0] = x;
                    ans[1] = y;
                }
            }
        }
        return ans;
    }
}

学习笔记：
这是一道枚举算法的题目。
由于题目限制了x和y在50以内，所以只需要遍历这2601个点就可以了。
每一个点计算与所有基站距离，然后将信号强度加总，最后比较。