Daily LeetCode – day0109 1710. Maximum Units on a Truck

import java.util.PriorityQueue;

// 1710. Maximum Units on a Truck
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        PriorityQueue<BoxInformation> priorityQueue = new PriorityQueue<>((bi1, bi2) -> bi2.numberOfUnitsPerBox - bi1.numberOfUnitsPerBox);
        for (int[] boxType : boxTypes) {
            priorityQueue.offer(new BoxInformation(boxType[0], boxType[1]));
        }
        int ans = 0;
        while (truckSize > 0) {
            BoxInformation best = priorityQueue.poll();
            if (best == null) return ans;
            if (truckSize > best.numberOfBoxes) {
                ans += best.numberOfBoxes * best.numberOfUnitsPerBox;
            } else {
                ans += truckSize * best.numberOfUnitsPerBox;
            }
            truckSize -= best.numberOfBoxes;
        }
        return ans;
    }
}

class BoxInformation {
    Integer numberOfBoxes;
    Integer numberOfUnitsPerBox;

    public BoxInformation(Integer numberOfBoxes, Integer numberOfUnitsPerBox) {
        this.numberOfBoxes = numberOfBoxes;
        this.numberOfUnitsPerBox = numberOfUnitsPerBox;
    }
}
// 1710. Maximum Units on a Truck
class Solution {
    public int maximumUnits(int[][] boxTypes, int truckSize) {
        int len = boxTypes.length;
        Arrays.sort(boxTypes, (int[] bi1, int[] bi2) -> bi2[1] - bi1[1]);
        int ans = 0;
        int i = 0;
        while (truckSize > 0) {
            if (i < len) {
                if (truckSize > boxTypes[i][0]) {
                    ans += boxTypes[i][0] * boxTypes[i][1];
                } else {
                    ans += truckSize * boxTypes[i][1];
                }
                truckSize -= boxTypes[i][0];
                ++i;
            } else {
                return ans;
            }
        }
        return ans;
    }
}
学习笔记:
这是一道简单题,可以使用排序二维数组。
使用了了优先队列+创建对象,可能是因为放进去之后拿出来的概率太高了,所以花了10ms。
使用ArrayList+创建对象,需要13ms。
使用LinkedList+创建对象,需要23ms。可以看出LinkedList的排序属实性能不行。
最后写了一版二维数组排序的,只需要8ms。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0108 0805. Split Array With Same Average

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

// 0805. Split Array With Same Average
class Solution {
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length;
        if (n == 1) return false;
        int mid = n / 2;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        for (int i = 0; i < n; ++i) {
            nums[i] = nums[i] * n - sum;
        }
        int leftCombinations = 1 << mid;
        int rightCombinations = 1 << n - mid;
        Set<Integer> leftSums = new HashSet<>();
        for (int i = 1; i < leftCombinations; ++i) {
            int total = 0;
            for (int j = 0; j < mid; ++j) {
                if ((i & (1 << j)) != 0) {
                    total += nums[j];
                }
            }
            if (total == 0) return true;
            leftSums.add(total);
        }
        for (int i = 1; i < rightCombinations - 1; ++i) {
            int total = 0;
            for (int j = mid; j < n; ++j) {
                if ((i & (1 << j - mid)) != 0) {
                    total += nums[j];
                }
            }
            if (total == 0) return true;
            if (leftSums.contains(total * -1)) return true;
        }
        return false;
    }
}
学习笔记:
这道是一道超级困难题。
如果使用深度优先搜索,需要2的30次方的时间,太离谱了。
所以我们要用折半搜索,先搜2的15次方,再搜2的15次方,然后拿左半去右半里面找有没有相反的数字。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0107 0791. Custom Sort String

// 0791. Custom Sort String
class Solution {
    public String customSortString(String order, String s) {
        int[] lettersQuantity = new int[123];
        for (char letter : s.toCharArray()) {
            ++lettersQuantity[letter];
        }
        StringBuilder sb = new StringBuilder();
        for (char letter : order.toCharArray()) {
            int quantity = lettersQuantity[letter];
            lettersQuantity[letter] = 0;
            for (int i = 0; i < quantity; ++i) {
                sb.append(letter);
            }
        }
        for (char c = 'a'; c <= 'z'; ++c) {
            int quantity = lettersQuantity[c];
            for (int i = 0; i < quantity; ++i) {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
学习笔记:
这是一道简单的字符串题。
说是字符串,其实考验的是排序和贪心的算法。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0106 0790. Domino and Tromino Tiling

// 0790. Domino and Tromino Tiling
class Solution {
    public int numTilings(int n) {
        if (n < 3) return n;
        final long MOD = 1000000007;
        long[] fullTiling = new long[n + 1];
        long[] partTiling = new long[n + 1];
        fullTiling[1] = 1;
        fullTiling[2] = 2;
        partTiling[1] = 0;
        partTiling[2] = 1;
        for (int i = 3; i <= n; ++i) {
            fullTiling[i] = (fullTiling[i - 1] + fullTiling[i - 2] + partTiling[i - 1] + partTiling[i - 1]) % MOD;
            partTiling[i] = (partTiling[i - 1] + fullTiling[i - 2]) % MOD;
        }
        return (int) fullTiling[n];
    }
}
学习笔记:
这是一道动态规划的题目,要仔细分析出四种不同的情况。
空的,上面凸出来的,下面凸出来的,满的。
也可以分为两种,部分完成和全部完成。
这两种思路都可以完成这道题目。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0105 1704. Determine if String Halves Are Alike

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;
    }
}
学习笔记:
这是一道字符串的简单题,用到的是哈希表。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0104 0864. Shortest Path to Get All Keys

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维数组比较费空间。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0103 0764. Largest Plus Sign

// 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语句的妙处还是很有滋味的。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0102 1684. Count the Number of Consistent Strings

// 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;
    }
}
学习笔记:
简单题,一道字符串遍历的水题。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0101 0816. Ambiguous Coordinates

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的情况。需要分类讨论。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0100 1678. Goal Parser Interpretation

// 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天,没想到自己真坚持了那么久了。
发表在 每日LeetCode | 留下评论