力扣每日一题（六月）

2022-06-01

力扣每日一题迁移至GitHub：

06-22 三晴

字母大小写全排列
一口气肝三题，爽

回溯

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.9 MB, 在所有 Java 提交中击败了68.82%的用户

class Solution {
    public List<String> letterCasePermutation(String s) {
        List<String> list = new ArrayList<>();
        char[] chars = s.toCharArray();
        backtracking(0, list, chars);
        return list;
    }
    public void backtracking(int start, List<String> list, char[] chars) {
        if (start == chars.length) {
            list.add(String.valueOf(chars));
            return;//一轮完成添加到结果集
        }
        backtracking(start + 1, list, chars);//自身先递归
        if (Character.isDigit(chars[start]))
            return;//为数字不用大小写转换
        //大小写转换
        char ch = chars[start];
        chars[start] = Character.isLowerCase(ch) ? Character.toUpperCase(ch) : Character.toLowerCase(ch);
        backtracking(start + 1, list, chars);
        ch = chars[start];
        chars[start] = Character.isLowerCase(ch) ? Character.toUpperCase(ch) : Character.toLowerCase(ch);
    }
}

全排列
趁热打铁，秒杀

回溯

执行用时：1 ms, 在所有 Java 提交中击败了80.87%的用户
内存消耗：41.7 MB, 在所有 Java 提交中击败了38.83%的用户

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Deque<Integer> deque = new ArrayDeque<>();
        backtracking(nums, list, deque);
        return list;
    }
    public void backtracking(int[] nums, List<List<Integer>> list, Deque<Integer> deque) {
        if (deque.size() == nums.length){
            list.add(new ArrayList<>(deque));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (deque.contains(nums[i]))
                continue;
            deque.offerLast(nums[i]);
            backtracking(nums, list, deque);
            deque.pollLast();
        }
    }
}

组合
今天学习了回溯算法，初步认识了回溯（虽然以前其实写过），明白经常看到的“剪枝”的意思了。

回溯算法

执行用时：15 ms, 在所有 Java 提交中击败了44.25%的用户
内存消耗：42.6 MB, 在所有 Java 提交中击败了52.73%的用户

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> ints = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtracking(1,0, n, k);//回溯
        return list;
    }

    public void backtracking(int start, int count, int n, int k) {
        if(count == k) {
            list.add(new ArrayList<>(ints));//为结果，添加到结果集
            return;
        }
        for (int j = start; j <= n; j++) {
            ints.add(j);//添加新的元素
            backtracking(j + 1, count + 1, n, k);//进行递归
            ints.remove(ints.size() - 1);//删去刚刚添加的元素，回溯
        }
    }
}

06-21 二雨

腐烂的橘子
早些时候做图论的题的时候就看到评论区有人提这题了，感觉是个经典例题，广搜很快搞定，试了下深搜，要稍微转变一下思路，在每个点上记录路径长度，然后取最大值作为所用时间，有迪杰斯特拉算法的感觉了。

深度优先搜索

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.2 MB, 在所有 Java 提交中击败了12.41%的用户

class Solution {
    int row, col;
    int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int orangesRotting(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if (grid[i][j] == 2)
                    dfs(grid, i, j, 2);//深搜计算路径
            }
        }
        int path = 0;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] == 1)
                    return -1;//有1的直接返回-1
                else
                    path = Math.max(path, grid[i][j]);//取最大值
            }
        }
        return path == 0 ? 0 : path - 2;//为0时返回0，否则要减去初始的2
    }
    public void dfs(int[][] grid, int x, int y, int path) {
        if (x < 0 || x > row - 1 || y < 0 || y > col - 1)
            return;//越界结束
        if (grid[x][y] != 1 && grid[x][y] < path)
            return;//若被标记过且比当前路径小的，也结束递归
        grid[x][y] = path++;//标记到当前坐标的路径
        for(int[] dir : direction) {
            dfs(grid, x + dir[0], y + dir[1], path);//上下左右深搜
        }
    }
}

广度优先搜索

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.9 MB, 在所有 Java 提交中击败了57.35%的用户

class Solution {
    public int orangesRotting(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        int[][] direction = {{-1,0}, {1, 0}, {0, -1}, {0, 1}};
        Queue<int []> queue = new LinkedList<>();
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if (grid[i][j] == 2)
                    queue.offer(new int[]{i, j});
            }
        }
        int time = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                int[] position = queue.poll();
                for(int[] dir : direction) {
                    int x = position[0] + dir[0];
                    int y = position[1] + dir[1];
                    if(x < 0 || x > row - 1 || y < 0 || y > col - 1 || grid[x][y] != 1)
                        continue;
                    queue.offer(new int[]{x, y});
                    grid[x][y] = 2;
                }
            }
            time++;
        }
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if (grid[i][j] == 1)
                    return -1;
            }
        }
        return time == 0 ? 0 : time - 1;
    }
}

06-20 一阴

今天下午考第一科Java程序设计，试卷直接把实验报告当大题，关键是那实验报告的例题又臭又长，不是简不简单的问题，题目描述的语文水平感觉比我还差，缺斤少两的，甚至老师在考试期间还和我们说题目里不完整的大家自己补充一下。我朋友的评价是：“自助式考试”
半小时写完了试卷，最后一题写了一小时，提前半小时交卷，大学的考试果然不敢维恭。
回来还早没到饭点，先刷一道题排解郁闷。

填充每个节点的下一个右侧节点指针

递归

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.4 MB, 在所有 Java 提交中击败了59.77%的用户

class Solution {
    public Node connect(Node root) {
        if (root == null || root.left == null)//为空或为叶子
            return root;
        root.left.next = root.right;//左连右
        if(root.next != null)//有兄弟节点
            root.right.next = root.next.left;//右连兄弟节点的左
        connect(root.left);//递归连接
        connect(root.right);
        return root;
    }
}

层序遍历

执行用时：2 ms, 在所有 Java 提交中击败了69.83%的用户
内存消耗：41.7 MB, 在所有 Java 提交中击败了23.63%的用户

class Solution {
    public Node connect(Node root) {
        if(root == null)
            return null;
        Node cur = root;
        Node pre;//上一个节点
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(cur);
        while(!queue.isEmpty()) {
            pre = null;
            int size = queue.size();
            while(size-- > 0) {
                cur = queue.poll();
                if(cur.left != null)
                    queue.offer(cur.left);
                if(cur.right != null)
                    queue.offer(cur.right);
                if(pre == null)//当前层第一个节点
                    pre = cur;
                else {//不为首节点则进行连接操作
                    pre.next = cur;
                    pre = pre.next;
                }
            }
        }
        return root;
    }
}

06-19 日阴

合并二叉树

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.8 MB, 在所有 Java 提交中击败了6.74%的用户

合并到树1

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null)
            return root2;
        if (root2 == null)
            return root1;
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

新建一棵树

代码重复率有点高了……应该可以优化一下

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return dfs(root1, root2);
    }
    public TreeNode dfs(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null)
            return null;
        TreeNode node = new TreeNode();
        if (root1 == null) {
            node.val += root2.val;
            node.left = dfs(null, root2.left);
            node.right = dfs(null, root2.right);
        }
        else if (root2 == null) {
            node.val += root1.val;
            node.left = dfs(root1.left, null);
            node.right = dfs(root1.right, null);
        }
        else {
            node.val = root1.val + root2.val;
            node.left = dfs(root1.left, root2.left);
            node.right = dfs(root1.right, root2.right);
        }

        return node;
    }
}

图像渲染
做过的题，用广搜写一遍，效率比深搜低呀，不过感觉手写简单广搜深搜没啥问题了

深度优先搜索

class Solution {
    int[][] direction = {{-1,0}, {1, 0}, {0, -1}, {0, 1}};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if (image[sr][sc] != color)
            dfs(image, sr, sc,image[sr][sc], color);
        return image;
    }
    public void dfs(int[][] image, int x, int y, int color, int newColor) {
        if(x < 0 || x > image.length - 1 || y < 0 || y > image[0].length - 1 || image[x][y] != color)
            return;
        image[x][y] = newColor;
        for(int[] dir : direction) {
            dfs(image, x + dir[0], y + dir[1] , color, newColor);
        }
    }
}

广度优先搜索

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if(image[sr][sc] == color)
            return image;
        int row = image.length, col = image[0].length;
        int[][] direction = {{-1,0}, {1, 0}, {0, -1}, {0, 1}};
        Queue<int []> queue = new LinkedList<>();
        queue.offer(new int[]{sr, sc});
        int target = image[sr][sc];
        image[sr][sc] = color;
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size-- > 0) {
                int[] position = queue.poll();
                for(int[] dir : direction) {
                    int x = position[0] + dir[0], y = position[1] + dir[1];
                    if(x < 0 || x > row - 1 || y < 0 || y > col - 1 || image[x][y] != target)
                        continue;
                    image[x][y] = color;
                    queue.offer(new int[]{x, y});
                }
            }
        }
        return image;
    }
}

06-18 六阴

字符串的排列

执行用时：5 ms, 在所有 Java 提交中击败了76.52%的用户
内存消耗：41.6 MB, 在所有 Java 提交中击败了15.75%的用户

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int l1 = s1.length(), l2 = s2.length();
        if(l1 > l2)
            return false;
        int[] map1 = new int[26];
        int[] map2 = new int[26];
        for (int i = 0; i < l1; i++) {
            map1[s1.charAt(i) - 'a']++;
            map2[s2.charAt(i) - 'a']++;
        }
        if(Arrays.equals(map1, map2))
                return true;
        for (int i = l1; i < l2; i++) {
            map2[s2.charAt(i - l1) - 'a']--;
            map2[s2.charAt(i) - 'a']++;
            if(Arrays.equals(map1, map2))
                return true;
        }
        return false;
    }
}

无重复字符的最长子串
做老题，感觉比以前好懂多了，很快搞明白了以前看得一脸懵逼的地方。

滑动窗口

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.6 MB, 在所有 Java 提交中击败了33.31%的用户

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] map = new int[127];//记录字符上一次出现的位置
        Arrays.fill(map, -1);
        int left = 0, maxLen = 0;//左臂和最大长度
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // if(map[ch] != -1){
            //     left = Math.max(left, map[ch] + 1);//不用加判断了，取了max效果是一样的
            // }
            left = Math.max(left, map[ch] + 1);
            map[ch] = i;
            maxLen = Math.max(maxLen, i - left + 1);
        }
        return maxLen;
    }
}

06-17 五雨

删除链表的倒数第 N 个结点
复习了离散，吃饭前做一道题，提交完发现是做过的……再次学习吧

快慢指针单遍历

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.5 MB, 在所有 Java 提交中击败了59.33%的用户

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow = head, fast = head;//快慢指针
        for(int i = 0; i < n; i++)
            fast = fast.next;//快指针先走n步
        if(fast == null)//若快指针走了n步后为null，说明删除的是头结点
            return head.next;//因此返回head.next即可
        while (fast.next != null) {//快指针走到最后一个节点为止
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;//删除慢指针的下一个节点
        return head;
    }
}

设置头结点 + 单指针计数双遍历

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.5 MB, 在所有 Java 提交中击败了59.33%的用户

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node = new ListNode();//设置头结点
        node.next = head;
        head = node;
        int count = 0;
        while(head.next != null) {
            head = head.next;
            count++;
        }
        head = node;
        while(count-- > n)
            head = head.next;
        head.next = head.next.next;
        return node.next;
    }
}

06-16 四阴

链表的中间结点
久违的链表题做简单题好舒服，写完继续复习离散

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.9 MB, 在所有 Java 提交中击败了50.77%的用户

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null){//或者直接保持快指针当前及下一个都不为空
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast != null) {
            fast =  fast.next;
            if (fast == null)
                break;
            slow = slow.next;//把这步放到if后面，避免奇偶个节点的繁琐问题
            fast = fast.next;
        }
        return slow;
    }
}

06-15 三阴

反转字符串中的单词 III

逐个原地翻转

转为字符数组（这里不算原地了），然后每次找空格的位置进行逐个单词的翻转

执行用时：3 ms, 在所有 Java 提交中击败了90.94%的用户
内存消耗：41.7 MB, 在所有 Java 提交中击败了66.38%的用户

class Solution {
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int length = s.length();
        int left = 0, right = s.indexOf(' ');
        while(left < right) {
            reverse(chars, left, right - 1);
            left = right + 1;
            right = s.indexOf(' ', left);
        }
        reverse(chars, left, length - 1);
        return new String(chars);
    }

    public void reverse(char[] chars, int left, int right) {
        while(left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }
}

StringBuilder拼接

执行用时：9 ms, 在所有 Java 提交中击败了39.32%的用户
内存消耗：42.3 MB, 在所有 Java 提交中击败了9.45%的用户

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        StringBuilder temp = new StringBuilder();
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch == ' ') {
                sb.append(temp.reverse() + " ");
                temp.delete(0, temp.length());
            }
            else
                temp.append(ch);

        }
        sb.append(temp.reverse());
        return sb.toString();
    }
}

06-14 二雨

对角线遍历
(´இ皿இ｀)模拟好痛苦……
今晚考了选修课的开卷观后感，写了一千二字感觉是上了大学后写最多的一次了（入党申请书时间充裕），手要断了！

模拟

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：43 MB, 在所有 Java 提交中击败了72.21%的用户

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int row = mat.length, col = mat[0].length;
        int[] result = new int[row * col];
        int count = 0;
        for(int i = 0; i < row + col - 1; i++){
            if(i % 2 == 0) {//为斜向上遍历
                int x = i < row ? i : row - 1;//取i值或者为边界值
                int y = i < row ? 0 : i - row + 1;//取0或者为边界值
                while (x >= 0 && y < col){
                    result[count++] = mat[x--][y++];
                }
            }
            else {//为斜向下遍历
                int x = i < col ? 0 : i - col + 1;//取0或者为边界值
                int y = i < col ? i : col - 1;//取i或者为边界值
                while (x < row && y >= 0){
                    result[count++] = mat[x++][y--];
                }
            }
        }
        return result;
    }
}

06-13 一阴

高度检查器
感谢老铁送来的简单题，开始复习高数~

排序检测

执行用时：1 ms, 在所有 Java 提交中击败了68.84%的用户
内存消耗：39.6 MB, 在所有 Java 提交中击败了5.24%的用户

class Solution {
    public int heightChecker(int[] heights) {
        int[] expected = heights.clone();
        Arrays.sort(expected);
        int count = 0;
        for(int i = 0; i < heights.length; i++){
            if(heights[i] != expected[i])
                count++;
        }
        return count;
    }
}

06-12 日阴

查找和替换模式
一眼打表，但是感觉挺多细节……

用map集合写慢一点

执行用时：2 ms, 在所有 Java 提交中击败了33.33%的用户
内存消耗：40.2 MB, 在所有 Java 提交中击败了90.38%的用户

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        List<String> list = new ArrayList<>();
        Map<Character, Character> map = new HashMap<>();
        for(int i = 0; i < words.length; i++){
            map.clear();
            boolean flag = true;//判断是否为正确映射
            for(int j = 0; j < pattern.length(); j++){
                char ch1 = words[i].charAt(j);//分别取两个字母
                char ch2 = pattern.charAt(j);
                if(!map.containsKey(ch1) && !map.containsValue(ch2)){//若当前字母未有映射 则添加映射
                    map.put(ch1, ch2);
                }
                else if((map.containsKey(ch1)  && map.get(ch1) != ch2) || (!map.containsKey(ch1) && map.containsValue(ch2))){//若映射不正确则标记并退出循环
                    flag = false;
                    break;
                }
            }
            if(flag)
                list.add(words[i]);
        }
        return list;
    }
}

构建映射关系

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.2 MB, 在所有 Java 提交中击败了90.38%的用户

class Solution {
    public List<String> findAndReplacePattern(String[] words, String pattern) {
        int[] flag = new int[26];//标记pattern中已建立映射的字母
        int[] map = new int[26];//记录words[i]中字母映射的对象值
        List<String> list = new ArrayList<>();
        for(int i = 0; i < words.length; i++){
            Arrays.fill(flag, 0);//每一轮标记初始化为0
            Arrays.fill(map, -1);//每一轮记录值初始化为-1
            boolean temp = true;//判断是否为正确映射
            for(int j = 0; j < pattern.length(); j++){
                int ch1 = words[i].charAt(j) - 'a';//分别取两个字母
                int ch2 = pattern.charAt(j) - 'a';
                if(map[ch1] == -1 && flag[ch2] == 0){//若当前字母未有映射 则添加映射
                    map[ch1] = ch2;
                    flag[ch2] = 1;
                }
                else if(map[ch1] != ch2){//若映射不正确则标记并退出循环
                    temp = false;
                    break;
                }
            }
            if(temp)
                list.add(words[i]);
        }
        return list;
    }
}

06-11 六阴

将字符串翻转到单调递增
很巧妙！

执行用时：11 ms, 在所有 Java 提交中击败了61.21%的用户
内存消耗：42.3 MB, 在所有 Java 提交中击败了33.48%的用户

class Solution {
    public int minFlipsMonoIncr(String s) {
        char[] chars = s.toCharArray();
        int count = 0, length = chars.length;
        for(int i = 0; i < length; i++) {
            if (chars[i] == '0')
                count++;
        }
        int min = count;
        for(int i = 0; i < length; i++){
            if(chars[i] == '0')
                count--;
            else
                count++;
            min = Math.min(min, count);
        }
        return min;
    }
}

06-10 五阴

找到需要补充粉笔的学生编号

前缀和

执行用时：1 ms, 在所有 Java 提交中击败了99.38%的用户
内存消耗：54.4 MB, 在所有 Java 提交中击败了6.48%的用户

class Solution {
    public int chalkReplacer(int[] chalk, int k) {
        long count = 0;
        for(int i : chalk)
            count += i;
        k %= count;
        for(int i = 0; i < chalk.length; i++){
            k -= chalk[i];
            if(k < 0)
                return i;
        }
        return -1;
    }
}

06-09 四阴

非重叠矩形中的随机点
呜呜呜好难，思路没错但细节太多了，取整边界问题和概率问题等等……

前缀和 + 二分查找

执行用时：52 ms, 在所有 Java 提交中击败46.60%的用户
内存消耗：48.1 MB, 在所有 Java 提交中击败了5.83%的用户

class Solution {
    int area;//面积总和
    int length;//数组长度
    int[] sum;//前缀和（每个矩形的面积概率）
    int[][] rects;//pick里用到
    Random random;//获取随机数
    public Solution(int[][] rects) {
        area = 0;
        length = rects.length;
        this.rects = rects;
        random = new Random();
        sum = new int[length];
        for(int i = 0; i < length; i++){
            sum[i] = (rects[i][19] - rects[i][0] + 1) * (rects[i][20] - rects[i][21] + 1) + area;
            area = sum[i];//统计前缀和，即计算面积分布情况
        }
    }

    public int[] pick() {
        int n = random.nextInt(area) + 1;//获取随机数，计算出面积的取值
        int left = 0, right = length - 1;
        while(left < right){//通过二分查找找到对应的矩形
            int mid = left + (right - left) / 2;
            if(sum[mid] >= n)
                right = mid;
            else
                left = mid + 1;
        }
        int x = random.nextInt(rects[right][22] - rects[right][0] + 1) + rects[right][0];//随机数获取x值
        int y = random.nextInt(rects[right][23] - rects[right][24] + 1) + rects[right][25];//随机数获取y值
        return new int[]{x, y};
    }
}

06-08 三阴

今天把数据结构与算法的大作业和课程设计都搞定了，算法过程的视频录制比较简单，有意思的是哈夫曼树的编码和解码，利用最小堆对节点的权值进行构建成一棵哈夫曼树。学到了挺多，构建树、遍历树、编码、解码、最小堆、哈希表等等……
不过也差不多该复习其他科目了，期末考……挺紧张的，这学期的课程都比较难，不能一直学自己想学的内容了。

有效的回旋镖

比较斜率

既然是不能三点共线的话，那取两个斜率进行比较是否相等即可，一开始想到极坐标（老高数人了），但在转换角度的时候其实和斜率一样，就是有个除以0的问题，想尝试通过分母+1位移来解决，但写来写去还是有问题，最后发觉……既然是比较a/b == c/d，分母不能为0，那我不要分母就可以了啊！干！直接ad == bc……死去的十字相乘突然攻击我！

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.8 MB, 在所有 Java 提交中击败了85.30%的用户

class Solution {
    public boolean isBoomerang(int[][] points) {
        int x1 = points[1][0] - points[0][0], y1 = points[1][27] - points[0][28];
        int x2 = points[2][0] - points[0][0], y2 = points[2][29] - points[0][30];
        return x1 * y2 != x2 * y1;
    }
}

06-07 二雨

爱吃香蕉的珂珂

二分查找取上界

思路是模拟出来了，但是一直不确定，二分题里第一次多写一个遍历的方法感觉怪怪的，但getTime方法必不可少。
另外在上下界和取中值上不是很清晰，为什么有的题左闭右开，有的题返回左臂，有的返回右臂，而有的返回中值呢……值得学习(ó﹏ò｡)

执行用时：6 ms, 在所有 Java 提交中击败了99.66%的用户
内存消耗：41.8 MB, 在所有 Java 提交中击败了97.96%的用户

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int left = 1, right = 1000000000;//定义上下边界（习惯性左右了）
        while(left < right){
            int speed = left + (right - left) / 2;//取中值为当前速度
            long time = getTime(piles, speed);//获取当前速度所需要的时间
            if(time > h)//时间过长说明慢了，下界提升
                left = speed + 1;
            else//否则上界降低
                right = speed;
        }
        return right;//返回上界
    }
    public long getTime(int[] piles, int k){
        int time = 0;
        for(int i = 0; i < piles.length; i++){
            time += (piles[i] + k - 1) / k;
        }
        return time;
    }
}

06-06 一雨

两数之和 II - 输入有序数组

以二数之和为二分判断的条件

不要被框住了思维，二分不一定是直接取中位作为查找条件。
因为这里给的是一定有答案的数组，所以直接求和然后和目标值对比即可，以二数之和作为左右臂移动的根据。

执行用时：1 ms, 在所有 Java 提交中击败了98.54%的用户
内存消耗：44 MB, 在所有 Java 提交中击败了62.93%的用户

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while(left < right){//直接普通二分
            int sum = numbers[left] + numbers[right];//不取中位为二分判断，而是直接求和然后与target比较
            if(sum < target)
                left++;
            else if(sum > target)
                right--;
            else
                return new int[]{left + 1, right + 1};
        }
        return new int[]{left + 1, right + 1};
    }
}

取一找一

太呆了，看到两数之和的标题，直接就思维定式地取定一个数然后二分找另一个数……通过后看到击败这么少才发觉不对劲

执行用时：4 ms, 在所有 Java 提交中击败了24.24%的用户
内存消耗：43.9 MB, 在所有 Java 提交中击败了83.76%的用户

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int length = numbers.length;
        int index1 = 0, index2 = length - 1;//两个下标
        while(index1 < length - 1){
            int left = index1 + 1, right = index2;
            int t = target - numbers[index1];//取index1的值，然后二分查找其与target的差值
            while(left <= right){//二分查找差值
                int mid = left + (right - left) / 2;
                if(numbers[mid] < t)
                    left = mid + 1;
                else if (numbers[mid] > t)
                    right = mid - 1;
                else
                    return new int[]{index1 + 1, mid + 1};
            }
            index1++;
        }
        return new int[]{0};
    }
}

06-05 日晴

在圆内随机生成点

生成随机数判断是否在圆内

执行用时：207 ms, 在所有 Java 提交中击败了99.61%的用户
内存消耗：49.9 MB, 在所有 Java 提交中击败了78.52%的用户

class Solution {
    double radius;
    double x_center;
    double y_center;
    Random random;
    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.x_center = x_center;
        this.y_center = y_center;
        random = new Random();
    }

    public double[] randPoint() {
        while(true){
            double x = random.nextDouble() * 2 * radius - radius;//生成x随机坐标（以原点为圆心，方便计算是否在圆内
            double y = random.nextDouble() * 2 * radius - radius;//生成y随机坐标
            if(x * x + y * y <= radius * radius)//若生成的x y在圆内
                return new double[]{x + x_center, y + y_center};//则返回该圆坐标（加上原坐标将圆心移动到原圆心）
        }
    }
}

极坐标方程

万万没想到算法题还能用高数的极坐标方程解……
这里要注意极坐标和直角坐标的概率问题，比如一半的半径取的面积是不一样大的，因此生成圆内随机半径时要先平方再开平方。

执行用时：227 ms, 在所有 Java 提交中击败了20.70%的用户
内存消耗：50.2 MB, 在所有 Java 提交中击败了40.23%的用户

class Solution {
    double radius;
    double x_center;
    double y_center;
    Random random;
    public Solution(double radius, double x_center, double y_center) {
        this.radius = radius;
        this.x_center = x_center;
        this.y_center = y_center;
        random = new Random();
    }

    public double[] randPoint() {
        double d = random.nextDouble() * 2 * Math.PI;//生成随机角度
        double r = Math.sqrt(random.nextDouble() * radius * radius);//生成随机半径
        double x = x_center + r * Math.cos(d);//x转为极坐标
        double y = y_center + r * Math.sin(d);//y转为极坐标
        return new double[]{x, y};
    }
}

06-04 五晴

独特的电子邮件地址

利用各种库函数

执行用时：7 ms, 在所有 Java 提交中击败了90.70%的用户
内存消耗：41.5 MB, 在所有 Java 提交中击败了71.34%的用户

class Solution {
    public int numUniqueEmails(String[] emails) {
        Set<String> set = new HashSet<>();
        int length = emails.length;
        for(int i = 0; i < length; i++){
            int indexAt = emails[i].indexOf("@");//获取@的下标
            int indexAdd = emails[i].indexOf("+");//获取+的下标，若没有则为-1
            String local = indexAdd == -1 ? emails[i].substring(0, indexAt) : emails[i].substring(0, indexAdd);//获取地址
            set.add(local.replace(".", "") + emails[i].substring(indexAt));//拼接邮箱并加到set集合中
        }
        return set.size();//返回set的大小
    }
}

模拟

执行用时：9 ms, 在所有 Java 提交中击败了76.85%的用户
内存消耗：41.6 MB, 在所有 Java 提交中击败了61.67%的用户

class Solution {
    public int numUniqueEmails(String[] emails) {
        Set<String> set = new HashSet<>();
        int length = emails.length;
        for(int i = 0; i < length; i++){
            String[] split = emails[i].split("@", 2);//将字符串按@切割为两份
            char[] chars = split[0].toCharArray();//第一份转为数组
            StringBuilder sb = new StringBuilder();//可变字符串
            for(int j = 0; j < chars.length; j++){
                if(chars[j] == '.')
                    continue;//为.时跳过
                else if (chars[j] == '+')
                    break;//为+时退出
                sb.append(chars[j]);//添加当前字符
            }
            sb.append("@" + split[1]);//拼接
            set.add(sb.toString());
        }
        return set.size();
    }
}

06-03 四雨

今天未打卡不过度过了更有意义的一天！

06-02 四云

今天上完下午的java课就出去和朋友吃肯德基啦，然后晚上不回学校直接去哥哥家住，明天等姐姐她们过来一块吃饭~

删除二叉搜索树中的节点
不知道第几次做这题了……但还是只记住个大概，这次重新写一遍还是和书上的有些偏差。
这次写的只判断了以有没有右子树为准，而最优解是以有没有同时为左右子树以及只有左或只有右子树为区分，会更标准一些。

标准写法

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null)
            return null;//为空返回
        if(root.val < key)//值大于节点值，去右子树删除
            root.right = deleteNode(root.right, key);
        else if(root.val > key)//值小于节点值，去左子树删除
            root.left = deleteNode(root.left, key);
        else {//当前节点为删除节点时，分三种情况
            if(root.left != null && root.right != null){//情况一：既有左子树又有右子树
                TreeNode post = root.right;
                while(post.left != null)//找到右子树最小的节点
                    post = post.left;
                root.val = post.val;//右子树最小节点顶替当前被删除节点
                root.right = deleteNode(root.right, root.val);//去将右子树最小节点给删掉
            }
            else {
                if(root.left != null)
                    root = root.left;//情况二：只有左子树
                else
                    root = root.right;//情况三：只有右子树或者没有子节点（当前节点为叶子结点）
            }
        }
        return root;//返回当前节点
    }
}

这次写的

差距在于只有右子树时也会把右子树最小的提上来，增加了没必要的遍历，而标准的是直接返回右子树即可，不过力扣判定的时间都是0ms就是了∠( ᐛ 」∠)＿

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.7 MB, 在所有 Java 提交中击败了47.62%的用户

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null)
            return null;
        if(root.val != key){
            if(key > root.val)
                root.right = deleteNode(root.right, key);
            else
                root.left = deleteNode(root.left, key);
        }
        else {
            if(root.right != null){//有右子树时，把右子树最小的节点提上来
                TreeNode temp = root.right;
                while(temp.left != null)
                    temp = temp.left;//找到右子树最小的节点
                root.val = temp.val;//顶替
                root.right = deleteNode(root.right, temp.val);//再把最小的节点删了
            }
            else
                root = root.left;//没有右子树的话就直接把左子树返回
        }
        return root;
    }
}

06-01 三雨

火柴拼正方形
六月的第一题

执行用时：51 ms, 在所有 Java 提交中击败了43.78%的用户
内存消耗：39 MB, 在所有 Java 提交中击败了78.58%的用户

class Solution {
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for(int i : matchsticks)
            sum += i;
        if(sum % 4 != 0)
            return false;
        Arrays.sort(matchsticks);
        int[] border = new int[4];
        return DFS(matchsticks.length - 1 ,matchsticks, border, sum / 4);
    }
    public boolean DFS(int index, int[] matchsticks, int[] border, int length){
        if(index == -1)
            return true;
        for(int i = 0; i < border.length; i++){
            border[i] += matchsticks[index];
            if(border[i] <= length && DFS(index - 1, matchsticks, border, length))
                return true;
            else
                border[i] -= matchsticks[index];
        }
        return false;
    }
}

本文为作者九日发布，未经允许禁止转载！

156

发表留言

力扣每日一题（六月）

扫描右侧二维码继续阅读

June 1, 2022

微风忆夏

力扣每日一题（六月）

06-22 三 晴

06-21 二 雨

06-20 一 阴

06-19 日 阴

06-18 六 阴

06-17 五 雨

06-16 四 阴

06-15 三 阴

06-14 二 雨

06-13 一 阴

06-12 日 阴

06-11 六 阴

06-10 五 阴

06-09 四 阴

06-08 三 阴

06-07 二 雨

06-06 一 雨

06-05 日 晴

06-04 五 晴

06-03 四 雨

06-02 四 云

06-01 三 雨

06-22 三晴

06-21 二雨

06-20 一阴

06-19 日阴

06-18 六阴

06-17 五雨

06-16 四阴

06-15 三阴

06-14 二雨

06-13 一阴

06-12 日阴

06-11 六阴

06-10 五阴

06-09 四阴

06-08 三阴

06-07 二雨

06-06 一雨

06-05 日晴

06-04 五晴

06-03 四雨

06-02 四云

06-01 三雨