Daily LeetCode – day0016 1422. Maximum Score After Splitting a String

// 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,感觉找到了初中数学找函数规律的题目了。当然可以达到目的的函数有很多,但是最简单的要改就是这个了吧。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0015 0768. Max Chunks To Make Sorted II

// 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;
    }
}
学习笔记:
这是一道有趣的困难题。
一开始我想到的解法是从左往右贪心+局部排序。但这样时间复杂度真的爆表。后来看了提示说用栈,然后就写了一个栈的。但是不知道为什么速度就是偏慢,别人应该用的是其它的思路。我用了面向对象的思路,内存还是特别省的。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0014 1282. Group the People Given the Group Size They Belong To

// 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%的用户。
可能因为我是把所有的遍历了一遍,分了组,然后再装起来。但是这应该没速度上的影响才对。最近工作繁忙,得等有空了再研究了。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0013 1417. Reformat The String

// 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码的数字分别代表什么如果可以掌握得好,写起判断来就可以简单直接且快速,不需要用其它奇怪的接口。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0012 0640. Solve the Equation

// 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没有办法取反,这实在太麻烦了,很多巧妙的计算得走判断。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0011 1413. Minimum Value to Get Positive Step by Step Sum

// 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加到第一项,然后从第二项开始算。但后来发现没必要,直接算完最后处理结果才是最佳策略。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0010 0761. Special Binary String

// 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);}
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0009 0636. Exclusive Time of Functions

// 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是否一样,开关是否一样。在遇到各种情况需要怎么处理,是压栈还是出栈还是是结算,最后发现其实只有三条分支。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0008 1408. String Matching in an Array

// 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的内存。
接下来就是最巧妙的地方了,从前往后找和从后往前找,找到这个单词两次也就是索引不同,找到这个单词一次就是索引相同。
发表在 每日LeetCode | 留下评论

Daily LeetCode – day0007 0623. Add One Row to Tree

class Solution {
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            return new TreeNode(val, root, null);
        }
        Queue<TreeNode> upperFloor = new LinkedList<>();
        int layer = 0;
        upperFloor.add(root);
        while (++layer < depth - 1) {
            int queueSize = upperFloor.size();
            for (int i = 0; i < queueSize; ++i) {
                TreeNode peek = upperFloor.poll();
                if (peek.left != null) {
                    upperFloor.add(peek.left);
                }
                if (peek.right != null) {
                    upperFloor.add(peek.right);
                }
            }
        }
        for (TreeNode node : upperFloor) {
                node.left = new TreeNode(val, node.left, null);
                node.right = new TreeNode(val, null, node.right);
        }
        return root;
    }
}
学习笔记:
这是一道二叉树的题目,也是可以使用深度优先搜索和宽度优先搜索。
深度优先搜索写得代码会特别巧妙,解题的方法自己递归调用自己。
宽度优先搜索也比较符合直觉,把要插入的楼上一层找出来后插入一层。
发表在 每日LeetCode | 留下评论