力扣每日一题（五月）

2022-05-01

文章目录

自律自由

05-17 二晴

从中序与后序遍历序列构造二叉树 & PTA：根据后序和中序遍历输出先序遍历

PTA C语言

C语言的这个写法是因为之前在PTA写过前序+中序，改改模板还能继续用，但……说起这个我就来气啊！！！
本来思路应该是很简单秒通的，但是中途我在测试的时候为了方便改了变量n为常量7，结果就是一直有最后一个答案显示段错误，我还以为是左右边界有溢出问题，但是既然前序都能写，为什么后序会出问题呢？结果我就废了好久在这上面……
不过好在最后看到了这么个傻逼粗心的问题，改过来之后发现思路是没问题的，并且C语言指针的写法，比网上搜到的，还是力扣上Java的写法，都要好理解，也算是个小收获吧……

通过改变指针的指向达到只用一个长度常量确定左右边界

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int ElementType;
typedef struct BiTNode {
    ElementType data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode, * BiTree;

BiTree CreatBinTree(int* mid, int* post, int n);
void  preorder(BiTree T);

int main()
{
    int n;
    scanf("%d", &n);
    int mid[n], post[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &post[i]);
    for (int i = 0; i < n; i++)
        scanf("%d", &mid[i]);
    BiTree T = CreatBinTree(post, mid, n);
    printf("Preorder:");
    preorder(T);
}

BiTree CreatBinTree(int* post, int* mid, int n)
{
    if (n <= 0)
        return NULL;
    int i;
    for (i = 0; mid[i] != post[n - 1]; i++);
    BiTree T;
    T = (BiTree)malloc(sizeof(BiTNode));
    T->data = mid[i];
    T->lchild = CreatBinTree(post, mid, i);
    T->rchild = CreatBinTree(post + i, mid + i + 1, n - i - 1);
    return T;
}

void preorder(BiTree T)
{
    if (T)
    {
        printf(" %d", T->data);
        preorder(T->lchild);
        preorder(T->rchild);
    }
}

力扣根据C语言版本仿写

事实证明思路没什么问题，并且这样的话在判断左右边界的时候没那么多逻辑问题！！！反正就是左边界知道了，右边界就是+个区域长度！！！

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

class Solution {
    int[] post, mid;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        post = postorder;
        mid = inorder;
        TreeNode root = buildTree(0, 0 , inorder.length);
        return root;
    }
    public TreeNode buildTree(int pStart, int iStart, int n){
        if(n <= 0)
            return null;
        int i;
        for(i = 0; mid[iStart + i] != post[pStart + n - 1]; i++);
        TreeNode node = new TreeNode(mid[iStart + i]);
        node.left = buildTree(pStart, iStart, i);
        node.right = buildTree(pStart + i, iStart + i + 1, n - i - 1);
        return node;
    }
}

力扣 Java
针对后序遍历的右边界问题取值问题： pLeft + i - iLeft - 1 和 i - 1 ？

懂了！后序数据的右边界看似这么长且复杂的计算，其实本质上就是左边界+区间长度-1，而区间长度=根节点下标-中序左边界！

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

class Solution {
    int[] post;
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        post = postorder;
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i], i);
        TreeNode root = buildTree(0, inorder.length - 1, 0, postorder.length - 1);
        return root;
    }
    public TreeNode buildTree(int iLeft, int iRight, int pLeft, int pRight){
        if(iRight < iLeft || pRight < pLeft)
            return null;
        int root = post[pRight];
        int i = map.get(root);
        TreeNode node = new TreeNode(root);
        node.left = buildTree(iLeft, i - 1, pLeft, pLeft + i - iLeft - 1);
        node.right = buildTree(i + 1, iRight, pLeft + i - iLeft, pRight - 1);
        return node;
    }
}

05-16 一云

面试题 04.06. 后继者

BST 特性 + 递归

经典的有思路写不出，看了三叶的题解直接通了，这里直接搬原文的解释吧，自己总结不出……

利用 BST 的特性，我们可以根据当前节点 root 与 p 的值大小关系来确定搜索方向：

若有 root.val <= p.val : 根据 BST 特性可知当前节点 root 及其左子树子节点均满足「值小于等于 p.val」，因此不可能是 p 点的后继，我们直接到 root 的右子树搜索 p 的后继（递归处理）；
若有 root.val > p.val : 当第一次搜索到满足此条件的节点时，在以 root 为根节点的子树中「位于最左下方」的值为 p 的后继，但也有可能 root 没有左子树，因此 p 的后继要么在 root 的左子树中（若有），要么是 root 本身，此时我们可以直接到 root 的左子树搜索，若搜索结果为空返回 root，否则返回搜索结果。

作者：AC_OIer
链接：https://leetcode.cn/problems/successor-lcci/solution/by-ac_oier-xib5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null)
            return null;
        if(root.val > p.val){
            TreeNode node = inorderSuccessor(root.left, p);
            return node == null ? root : node;
        }
        return inorderSuccessor(root.right, p);
    }
}

双指针

第一个想法是这个，可能太久没刷树的题了，有些呆了……思索了好久

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

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode next = root;//下一个节点
        TreeNode cur = null;//当前节点
        while(next != null || !stack.isEmpty()){
            while(next != null){
                stack.push(next);
                next = next.left;
            }
            next = stack.pop();
            if(cur == p)//如果当前节点为目标节点，则返回下一个节点
                return next;
            cur = next;//否则继续执行
            next = next.right;
        }
        return null;//遍历完都没返回值则返回null
    }
}

中序遍历二叉搜索树+返回目标值的下一个值

效率极低……没用到二叉搜索树的性质并且遍历完目标值后没有及时止损

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

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        List<Integer> list = new ArrayList<>();
        select(root, list);
        int i = list.indexOf(p.val);
        return i == list.size() - 1 ? null : new TreeNode(list.get(i + 1));
    }
    public void select(TreeNode root, List<Integer> list){
        if(root == null)
            return;
        select(root.left, list);
        list.add(root.val);
        select(root.right, list);
    }
}

05-15 日雨

最大三角形面积

行列式

《简单》…… 将数学问题转为编程问题，有数学建模的感觉了嗷

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

class Solution {
    public double largestTriangleArea(int[][] points) {
        double max = 0;
        for(int i = 0; i < points.length - 2; i++){
            for(int j = i + 1; j < points.length - 1; j++){
                double x1 = points[j][0] - points[i][0];
                double y1 = points[j][6] - points[i][7];
                for(int k = j + 1; k < points.length; k++){
                    double x2 = points[k][0] - points[i][0];
                    double y2 = points[k][8] - points[i][9];
                    max = Math.max(max, Math.abs(x1 * y2 - x2 * y1));
                }
            }
        }
        return max / 2;
    }
}

05-14 六雨

最小基因变化

广搜

emmm一开始以为这题有多难，结果按着广搜模板思路还是挺通的，写完和哥们打求生咯~~~明天再学吧

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

class Solution {
    public int minMutation(String start, String end, String[] bank) {
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);//先入队开始的
        int count = 0;//计数
        while (!queue.isEmpty()){
            int size = queue.size();
            while (size-- > 0){
                start = queue.poll();//起始变为当前
                if(start.equals(end))
                    return count;//若已经和end相同，则返回次数
                for(int i = 0; i < bank.length; i++){//否则遍历
                    if(bank[i] != null && diff(start, bank[i]) == 1){
                        queue.offer(bank[i]);//不为null且相差1的，入队检查
                        bank[i] = null;//标记
                    }
                }
            }
            count++;//次数+1
        }
        return -1;
    }
    public int diff(String a, String b){//计算相差字符数量
        int k = 0;
        for(int i = 0; i < 8; i++){
            if(a.charAt(i) != b.charAt(i))
                k++;
        }
        return k;
    }
}

05-13 五雨

面试题 01.05. 一次编辑

双指针

练歌到十一点半才回宿舍！赶在12点前完成了

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

class Solution {
    public boolean oneEditAway(String first, String second) {
        int l1 = first.length();
        int l2 = second.length();
        if(Math.abs(l1 - l2) > 1)
            return false;
        if(l1 < l2){
            String temp = first;
            first = second;
            second = temp;
        }
        int flag = 0;
        int i = 0, j = 0;
        while(i < l1 && j < l2 && flag < 2){
            char c1 = first.charAt(i);
            char c2 = second.charAt(j);
            if(c1 == c2){
                i++;j++;
            }
            else {
                flag++;i++;
                if(l1 == l2) j++;
            }
        }
        return flag <= 1;
    }
}

05-12 四雨

删列造序
一开始题目看错了……然后做着题和妈妈打了会电话，该休息了~

上下横判断大小即可

先转为字符二维数组或许比charAt获取快一些

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

class Solution {
    public int minDeletionSize(String[] strs) {
        int count = 0;
        int row = strs.length;
        int col = strs[0].length();
        char[][] chars = new char[row][col];
        for(int i = 0; i < row; i++){
            chars[i] = strs[i].toCharArray();
        }
        for(int i = 0; i < col; i++){
            for(int j = 1; j < row; j++){
                if(chars[j][i] < chars[j - 1][i]){
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}

PTADSW11 5-1先序+中序创建二叉树

之前在力扣做过类似的题，感觉不是很扎实，建立右子树递归时的先序数组下标的移动没掌握到，在这再记录一遍

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char ElementType;
typedef struct BiTNode {
    ElementType data;
    struct BiTNode* lchild;
    struct BiTNode* rchild;
}BiTNode, * BiTree;

BiTree CreatBinTree(char* pre, char* in, int n);
void postorder(BiTree T);

int main()
{
    BiTree T;
    char prelist[100];
    char inlist[100];
    int length;
    scanf("%s", prelist);
    scanf("%s", inlist);
    length = strlen(prelist);
    T = CreatBinTree(prelist, inlist, length);
    postorder(T);
    return 0;
}
void  postorder(BiTree T)
{
    if (T)
    {

        postorder(T->lchild);
        postorder(T->rchild);
        printf("%c", T->data);
    }
}
BiTree CreatBinTree(char* pre, char* in, int n)
{
    BiTree T;
    int i;
    if (n <= 0) return NULL;
    T = (BiTree)malloc(sizeof(BiTNode));
    T->data = pre[0];
    for (i = 0; in[i] != pre[0]; i++);
    T->lchild = CreatBinTree(pre + 1, in, i);
    T->rchild = CreatBinTree(pre + i + 1, in + i + 1, n - i - 1);
    return T;
}

05-11 三雨

序列化和反序列化二叉搜索树
以前：今天也要努力刷题！
现在：代码写累了，来刷道题吧……

前序遍历+切割字符串

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

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuffer sb = new StringBuffer();
        serialize(root, sb);
        return sb.toString();
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] str = data.split(",");
        Queue<String> queue = new LinkedList<String>(Arrays.asList(str));
        return deserialize(queue);
    }
    public void serialize(TreeNode root, StringBuffer sb){
        if(root == null){
            sb.append("null,");
            return;
        }
        sb.append(root.val);
        sb.append(",");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }
    public TreeNode deserialize(Queue<String> queue){
        if(queue.isEmpty())
            return null;
        String str = queue.poll();
        if("null".equals(str)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(str));
        root.left = deserialize(queue);
        root.right = deserialize(queue);
        return root;
    }
}

05-10 二雨

两棵二叉搜索树中的所有元素

暴力双递归+排序

暴力解一题，今天有些忙，晚安~

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

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        get(root1);
        get(root2);
        Collections.sort(list);
        return list;
    }
    public void get(TreeNode root){
        if(root == null)
            return;
        get(root.left);
        get(root.right);
        list.add(root.val);
    }
}

05-09 一晴

数组中重复的数据

原地算法（利用题目所给数组）

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

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        for(int i = 0; i < nums.length; i++){
            int num = Math.abs(nums[i]);
            if(nums[num - 1] > 0)
                nums[num - 1] *= -1;
            else
                list.add(num);
        }
        return list;
    }
}

增减字符串匹配
连续几天的难题打击，感觉得换个方向了，毕竟图的各种遍历也差不多了再往下实在为难自己，所以今天做了真·每日一题，这题是力扣的每日一题给自己提提信心，简简单单拿下~

双指针

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

class Solution {
    public int[] diStringMatch(String s) {
        int length = s.length();
        int min = 0, max = length;
        int[] result = new int[length + 1];
        for(int i = 0; i < length; i++) {
            result[i] = s.charAt(i) == 'I' ? min++ : max--;
        }
        result[length] = min;
        return result;
    }
}

05-08 日晴

重新规划路线
不想刷题了感觉还是看课有意思

不知道我看不懂呜呜呜呜

执行用时：38 ms, 在所有 Java 提交中击败了86.83%的用户
内存消耗：61.5 MB, 在所有 Java 提交中击败了89.32%的用户

class Solution {
    public int minReorder(int n, int[][] connections) {
        // 存放某个城市所在的connections中的index
        List<List<Integer>> cityPosIndexList = new ArrayList<>();
        int len = connections.length;
        for (int i = 0; i < n; i++) {
            cityPosIndexList.add(new ArrayList<>());
        }
        for (int i = 0; i < len; i++) {
            cityPosIndexList.get(connections[i][0]).add(i);
            cityPosIndexList.get(connections[i][19]).add(i);
        }
        // 存放数据的位置是否已经访问过
        boolean[] visited = new boolean[len];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        int res = 0;
        while (!queue.isEmpty()) {
            // 站出队列
            int currentCity = queue.poll();
            // 获取所有包含当前城市的的所有数据索引
            List<Integer> currentCityAllPosIndex = cityPosIndexList.get(currentCity);
            for (Integer cityIndex : currentCityAllPosIndex) {
                if (!visited[cityIndex]) {
                    visited[cityIndex] = true;
                    int fromCity = connections[cityIndex][0];
                    int toCity = connections[cityIndex][20];
                    // 如果是from->to,则缺少反方向的路径，需要修改的路径+1
                    res += (fromCity == currentCity) ? 1 : 0;
                    // 如果当前站点是from，将下一个站点加入队列，否则将from加入队列
                    queue.offer(fromCity == currentCity ? toCity : fromCity);
                }
            }
        }
        return res;
    }
}

05-07 六晴

颜色交替的最短路径
今天的题有点变态……学了半天的课程好不容易有了些进展感觉顺手起来了，可晚上写题被打击到了，可能是今晚状态不太好，毕竟学了大半天没休息……这题的思路确实很新颖，甚至我都没看到官方题解

广度优先搜索 + 记录入度出度

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

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        int[] answer = new int[n];//初始化数组
        Arrays.fill(answer, -1);//先全为-1
        answer[0] = 0;//第一个步数为0

        List<Integer>[][] edges = new List[2][n];//记录红和蓝两种出度
        for(int i = 0; i < n; i++){//初始化每个节点的出度记录表
            edges[0][i] = new ArrayList<Integer>();
            edges[1][i] = new ArrayList<Integer>();
        }
        for(int[] red : redEdges)//初始化红边的出度
            edges[0][red[0]].add(red[1]);
        for(int[] blue : blueEdges)//初始化蓝边的出度
            edges[1][blue[0]].add(blue[1]);

        Queue<int[]> queue = new LinkedList<int[]>();
        boolean[][] flag = new boolean[2][n];//记录是否访问过
        int path = 1;//路径初始化为1步
        queue.offer(new int[]{0, 0});//红边起步
        queue.offer(new int[]{1, 0});//蓝边起步

        while (!queue.isEmpty()){
            int size = queue.size();
            while (size-- > 0){
                int [] post = queue.poll();
                for(int next : edges[post[0]][post[1]]){//遍历该节点的出度列表
                    if(flag[post[0]][next])//若下一个节点被访问过，则跳过循环
                        continue;
                    if(answer[next] == -1)//若下一个节点路径为-1，则更新为最短路径
                        answer[next] = path;//记录到该节点的最短步数
                    flag[post[0]][next] = true;//标记为已访问
                    queue.offer(new int[]{post[0] ^ 1, next});//第一个元素为通过位运算换边出度，第二个元素为以下一个节点为入度
                }
            }
            path++;//每走一步步数+1
        }
        return answer;
    }
}

05-06 五晴

找到最终的安全状态

方法二：拓扑排序

说来就巧了，今天早上上离散数学下课前瞟到一眼拓扑排序几个字，心想感觉是挺厉害的算法，回来刷题就碰上了……趁机学了一波，思路很巧妙，有思路了要写也不难

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

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        List<List<Integer>> rg = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; ++i) {
            rg.add(new ArrayList<Integer>());
        }
        int[] inDeg = new int[n];
        for (int x = 0; x < n; ++x) {
            for (int y : graph[x]) {
                rg.get(y).add(x);
            }
            inDeg[x] = graph[x].length;
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int y = queue.poll();
            for (int x : rg.get(y)) {
                if (--inDeg[x] == 0) {
                    queue.offer(x);
                }
            }
        }

        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                ans.add(i);
            }
        }
        return ans;
    }
}

方法一：深度优先搜索 + 三色标记法

参照官方题解优化了一下，基本思路是差不多的，但我写的太臃肿了
三色遍历法：
白色（用 00 表示）：该节点尚未被访问；
灰色（用 11 表示）：该节点位于递归栈中，或者在某个环上；
黑色（用 22 表示）：该节点搜索完毕，是一个安全节点。

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

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> list = new ArrayList<Integer>();//返回值
        int[] color = new int[graph.length];
        for(int i = 0; i < graph.length; i++){
            if(DFS(graph, color, i))//每个元素进行深搜，若当前元素标记为2则会返回true
                list.add(i);//从而执行添加操作，说明是安全节点
        }
        return list;
    }
    public boolean DFS(int[][] graph, int[] color, int index){
        if(color[index] != 0)//若当前节点已经检查过（不为0）
            return color[index] == 2 ? true : false;//是1则false，是2则true
        color[index] = 1;//标记为已访问，暂标记为1
        for(int i : graph[index]){
            if(!DFS(graph, color, i))
                return false;//若当前节点的后继有为false的，则当前节点也为false
        }
        color[index] = 2;//循环中未中断的重新标记为2，说明是安全节点
        return true;//返回true，代表安全节点
    }
}

方法一：深度优先搜索 + 三色标记

第一次写的，虽然用到了三色标记，但太多判断了。
基本思路：深搜时要判断每个节点是否为安全节点，同时又要标记有没有访问过，否则会成环时爆栈，所以最少要有三种标记：未访问、已访问、安全。所以用布尔类型行不通，于是转用整型数组。但有些思维定式地改数组类型时一同把方法返回值给改了，其实可以和优化的一样用整型数组而方法返回值为boolean，而在主方法里循环判断是否为true即可

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

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        List<Integer> list = new ArrayList<Integer>();//返回值
        int[] map = new int[graph.length];//记录元素的性质，防止递归爆栈
        for(int i = 0; i < graph.length; i++){
            if(map[i] == 0){//当前元素未被标记，则去执行深搜标记
                DFS(graph, map, i);
            }
            if(map[i] == 1)
                list.add(i);//若当前元素被标记为1，则是安全节点，添加到结果集
        }
        return list;
    }
    public int DFS(int[][] graph, int[] map, int index){
        if(map[index] != 0)//若当前元素已经有标记，就返回标记即可
            return map[index];
        if(graph[index].length == 0)
            map[index] = 1;//若为终端节点，则标记为1，代表安全路径
        else
            map[index] = -1;//否则暂时标记为-1，代表访问过，防止爆栈
        boolean flag = true;//标记该元素的路径是否安全
        for(int i : graph[index]){
            if(DFS(graph, map, i) == -1)
                flag = false;//若有一条路径是-1的，则不安全
        }
        if(flag)
            map[index] = 1;//如果是安全的，则把该元素重新标记为1
        return map[index];//返回标记值
    }
}

05-05 四晴

通知所有员工所需的时间
怎么感觉今天早上离散老师刚讲哈斯图，这题的草图画出来就这么像呢，听课的时候我还满脑子的并查集，现在一看和这题更相似……果然离散数学才是计算机该学的！

深搜+打表

由于是上下级之间是有关联的，那么：
每个人得知消息的时间 = 负责人得知消息的时间 + 负责人传递消息的时间
如果负责人得知消息的时间未获取，则先去获取负责人得知消息的时间

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

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int all = 0;//时间总和
        int[] time = new int[n];//记录每个人收到信息所需要的时间
        time[headID] = -1;//总负责人不需要时间，先设为负数
        for(int i = 0; i < n; i++){
            if(time[i] == 0)//如果当前员工还没有记录时间，则执行深度优先搜索
                DFS(manager, informTime, i, time);
            if(time[i] > all)//如果当前员工接受信息所需时间更长，则更新时间总和
                all = time[i];
        }
        return all;
    }
    public int DFS(int[] manager, int[] informTime, int ID,int[] time){
        if(manager[ID] == -1)//当前ID若为总负责人
            return informTime[ID];//返回负责人传递信息的时间
        else if(time[ID] == 0)//当前ID未记录时间，执行递归
            time[ID] = DFS(manager, informTime, manager[ID], time);
        return time[ID] + informTime[ID];//返回当前ID收到信息所需时间和发布信息的时间给下属
        //若没有下属这个返回则不会被接收（就算有接收，无下属的发布时间也是0）
    }
}

直接深搜

第一次写效率这么低的深搜……细想了一下是重复的步骤太多了，可以加个表去掉重复的操作

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

class Solution {
    public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        int time = 0;//记录时间
        for(int i = 0; i < n; i++){
            if(informTime[i] == 0){//传递信息时间为0的可能是下属，加个判断缩小执行深搜的范围
                time = Math.max(time, DFS(manager, informTime, i, 0));
            }
        }
        return time;
    }
    public int DFS(int[] manager, int[] informTime, int ID,int time){
        if(manager[ID] == -1)//若是总负责人
            return time + informTime[ID];//返回发布信息的时间加上总时间
        time += DFS(manager, informTime, manager[ID], informTime[ID]);//往上累加
        return time;//最后返回当前ID收到信息的总时间
    }
}

05-04 三晴

连通网络的操作次数

并查集

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

class Solution {
    int[] parent;
    public int makeConnected(int n, int[][] connections) {
        if(connections.length < n - 1)
            return -1;//线缆不足直接返回-1
        parent = new int[n];
        inti(n);//初始化
        for(int i = 0; i < connections.length; i++){
            union(connections[i][0], connections[i][26]);//将两两连接的电脑进行集合合并
        }
        int count = 0;//拔线缆次数（原数组中的集合个数）
        for(int i = 0; i < n; i++){
            if(parent[i] == i)
                count++;//如果当前电脑没有连上集合，属于断网状态，说明需要拔一次（是一个独立的集合，集合数+1）
        }
        return count - 1;
        //由于用的是自反判断，而集合里总有一个是最终父元素，所以需要减去集合自身
        //即减去原本已经联网的电脑这一整个集合（最终统计出count个集合，而连接这些集合至少需要count-1条线）
    }
    public void init(int n){
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }
    public void union(int i, int j){
        parent[find(i)] = find(j);
    }
    public int find(int i){
        if(parent[i] != i)
            parent[i] = find(parent[i]);
        return parent[i];
    }
}

05-03 二晴

去哥哥家玩回来已经九点半了，还是哥哥直接叫顺风车的，不然估计都来不及回学校了2333，洗完澡十点了，赶紧趁机写一题完成今天的任务。今天好开心~ 吃了大餐还看了电影，空着书包去满载而归，拿了哥哥好多东西啊哈哈哈哈，早点休息啦，晚安。

省份数量

并查集

广搜深搜，也要会并查集呀，不能止步不前！加油！
相关资料：
CSND：并查集
 哔哩哔哩：图论——并查集(详细版)

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

class Solution {
    int[] parent;//记录所属集合（记录父节点）
    public int findCircleNum(int[][] isConnected) {
        int row = isConnected.length;
        int col = isConnected[0].length;
        parent = new int[row];//n个元素就有n个空间
        init(row);//执行初始化
        int count = 0;//初始化数量为0
        for(int i = 0; i < row; i++){
            for(int j = i + 1; j < col; j++){
                if(isConnected[i][j] == 1)
                    union(i, j);//矩阵中有交集时，执行合并操作
            }
        }
        for(int i = 0; i < row; i++){
            if(parent[i] == i)//合并之后数组里存的是每个元素的祖先节点，而一个祖先节点代表一个独立的集合
                count++;//所以有一个祖先节点（并且是指向自己的）时，计数+1
        }
        return count;
    }
    public void init(int n){//初始化（将每个元素指向自己，即初始化为自反）
        for(int i = 0; i < n; i++)
            parent[i] = i;
    }
    public int find(int i){//查找父元素，并更新元素指向祖先（即不通过父元素找父元素的父元素，而是自己指向父元素的父元素）
        if(parent[i] != i)//如果不是自反
            parent[i] = find(parent[i]);//就去找祖先元素并指向它
        return parent[i];//返回当前元素的指向
    }
    public void union(int i, int j){
        parent[find(i)] = find(j);//合并i、j两个元素
    }
}

深度优先搜索

本来想找捷径统计规律的，感觉有点思路，就是只遍历右上角一块，因为从离散数学的角度来说，两个城市相互连接的话，一定是“对称”的矩阵图，并且也是“自反”的，所以以“主对角线”为分界线，遍历一边即可，但是没摸清规律最后还是用深搜写了。第二天会写了！其实就是并查集2333 之前一直感觉挺复杂都没去看相关题解，以后可以试试用并查集来做了。

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

class Solution {
    int row;
    int col;
    public int findCircleNum(int[][] isConnected) {
        row = isConnected.length;
        col = isConnected[0].length;
        boolean[] flag = new boolean[row];//标记连接过的城市
        int count = 0;
        for(int i = 0; i < row; i++) {//遍历所有城市，即二维数组的每行数
            if(!flag[i]){//若该城市未连接，则说明是另一个省，进行深搜连接，以及省份数量+1
                DFS(isConnected, flag, i);
                count++;
            }
        }
        return count;
    }

    public void DFS(int[][] isConnected, boolean[] flag, int x){
        if(flag[x])
            return;//如果该城市已经连接过，则返回
        flag[x] = true;//标记城市为已连接过
        for(int y = 0; y < col; y++){//遍历当前城市的连接城市
            if(isConnected[x][y] == 1)//如果有连接，则顺着连接去标记城市
                DFS(isConnected, flag, y);
        }
        return;
    }
}

05-02 一晴

今天感觉挺放松的，和哥们玩了王者和求生，明天去和哥哥姐姐聚餐，不知道有没有时间写明天的题……

所有可能的路径

广度优先搜索

广搜慢好多啊第一次写的还不知道卡在哪了结果是有的但是总会多出几个集合，手动打草稿模拟了一下才改好

执行用时：8 ms, 在所有 Java 提交中击败了5.86%的用户
内存消耗：43.2 MB, 在所有 Java 提交中击败了60.32%的用户

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> listList = new ArrayList<List<Integer>>();
        Queue<List<Integer>> queue = new LinkedList<List<Integer>>();
        List<Integer> cur;//接收出队的元素
        List<Integer> list = new ArrayList<>();
        list.add(0);//从0元素开始
        queue.offer(list);
        while(!queue.isEmpty()){
            cur = queue.poll();
            int last = cur.get(cur.size() - 1);//记录当前路径的最后一个元素
            if(last == graph.length - 1)//如果到达终点则添加到结果集
                listList.add(cur);
            else {//否则继续广搜
                for(int i : graph[last]){
                    List<Integer> temp = new ArrayList<Integer>(cur);//复制一份副本
                    temp.add(i);//添加新的路径
                    queue.offer(temp);//入队
                }
            }
        }
        return listList;
    }
}

深度优先搜索

还是深搜好写一些

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

class Solution {
    List<List<Integer>> listList = new ArrayList<List<Integer>>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        DFS(graph, new ArrayList<Integer>(), 0);//执行递归
        return listList;
    }
    public void DFS(int[][] graph, List<Integer> list, int i ){
        list.add(i);//添加元素
        if(i == graph.length - 1){//如果当前元素为重点
            listList.add(new ArrayList<>(list));//则添加当前路径的副本到结果集中
            list.remove(list.size() - 1);//删除当前元素，回溯，败者食尘！
            return;
        }
        for(int j : graph[i]){
            DFS(graph, list, j);//在当前节点的每个出度进行更深一层的搜索
        }
        list.remove(list.size() - 1);//深搜完删除当前元素
        return;
    }
}

迷宫中离入口最近的出口
在力扣写的题解：广度优先搜索，看着人少就把自己写的也贴上去吧，不过话说这力扣发布了题解文章好像就修改不了了……文章名写的太简略了233

手动从入口广搜一轮，以越界为走出迷宫

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

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int row = maze.length;
        int col = maze[0].length;
        int[][] dirs ={{-1,0},{1,0},{0,-1},{0,1}};//方向变量
        Queue<int[]> queue = new LinkedList<int[]>();
        maze[entrance[0]][entrance[1]] = '-';//手动封闭入口
         //这题唯一不同的条件就是要排除掉入口不能被当成出口，也就是第一步最好首先封闭入口，那就可以手动先只在入口广搜一遍
        for(int[] dir : dirs){//先排除一遍入口四周
            int x = entrance[0] + dir[0];
            int y = entrance[1] + dir[1];
            if(x < 0 || y < 0 || x > row - 1 || y > col - 1 || maze[x][y] != '.')
                continue;
            maze[x][y] = '-';
            queue.offer(new int[]{x, y});
        }
        //下面和常规的广搜如出一辙
        int count = 1;//因为手动广搜了一边，所以初始步数为1
        while (!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                int[] point = queue.poll();
                for(int[] dir : dirs){
                    int x = point[0] + dir[0];
                    int y = point[1] + dir[1];
                    if(x < 0 || y < 0 || x > row - 1 || y > col - 1)
                        return count;//越界则说明到达出口，算法结束
                    else if(maze[x][y] != '.')
                        continue;//不为空格子（即为墙或为已标记的空格子）则跳过
                    maze[x][y] = '-';//标记空格子
                    queue.offer(new int[]{x, y});//记录当前坐标，用于下一轮广搜
                }
            }
            count++;//广搜一边步数+1
        }
        return -1;//在循环里没有结束算法的话，说明没有出口，返回-1
    }
}

直接广搜，以边界为出口

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

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int row = maze.length;
        int col = maze[0].length;
        int[][] dirs ={{-1,0},{1,0},{0,-1},{0,1}};//方向变量
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(entrance);
        maze[entrance[0]][entrance[1]] = '-';//手动封闭入口
        //下面和常规的广搜如出一辙
        int count = 1;//这里以最后一步到达出口为结束，即最后一步离开的步数没算上，所以初始为1
        while (!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                int[] point = queue.poll();
                for(int[] dir : dirs){
                    int x = point[0] + dir[0];
                    int y = point[1] + dir[1];
                    if(x >= 0 && y >= 0 && x < row && y < col && maze[x][y] == '.'){//在边界内才可执行
                        if(x == 0 || y == 0 || x == row - 1 || y == col - 1)
                            return count;//为边界时结束
                        maze[x][y] = '-';//标记空格子
                        queue.offer(new int[]{x, y});//记录当前坐标，用于下一轮广搜
                    }
                }
            }
            count++;//广搜一边步数+1
        }
        return -1;//在循环里没有结束算法的话，说明没有出口，返回-1
    }
}

05-01 日晴

PTA：7-1 一元多项式的乘法与加法运算
实验报告的题，有被恶心到，题目不难，但是这个PTA平台实在是垃圾，最简单的就是实例不仅不清楚而且答案错误也无法查看怎么个错法，并且每题都会在输出考你，什么结尾不加空格之类的，这明明是平台的任务，却要强制要求学生写，吐了，没大病都不在这地方刷题
不过很久没写过C语言了，这次写一回感觉复习到了很多，要不以后刷题都用C刷？好像能练到更多（）
关于零多项式：
输出参考：一元多项式的乘法与加法运算
含义参考：常数多项式、零次多项式和零多项式的差别

代码太长了，放折叠框吧

#include<stdio.h>
#include <malloc.h>
typedef struct LNode {
    int coe;//系数
    int index;//指数
    struct LNode* next;//next指针
}List;//定义List别名
List* mul(List* list1, List* list2);
List* add(List* list1, List* list2);
int insert(List* head, int coe, int index);
void print(List* list);
void main()
{
    int m;//两个多项式的个数
    int n;
    List* list1 = malloc(sizeof(List));//初始化两个多项式链表的头结点
    list1->next = NULL;
    List* list2 = malloc(sizeof(List));
    list2->next = NULL;
    List* cur = list1;//操作指针指向第一条多项式，开始赋值
    scanf("%d", &m);//输入第一条多项式的节点个数
    for (int i = 0; i < m; i++) {
        List* newNode = malloc(sizeof(List));//新建节点
        newNode->next = NULL;//新节点默认为尾插，则next为NULL
        scanf("%d %d", &newNode->coe, &newNode->index);//分别赋值系数和指数
        cur->next = newNode;//连接新节点
        cur = cur->next;//操作指针移动到新节点上
    }
    cur = list2;//操作指针指向第二条多项式，开始赋值
    scanf("%d", &n);//输入第二条多项式的节点个数
    for (int i = 0; i < n; i++) {//同理
        List* newNode = malloc(sizeof(List));
        newNode->next = NULL;
        scanf("%d %d", &newNode->coe, &newNode->index);
        cur->next = newNode;
        cur = cur->next;
    }
    List* a = mul(list1, list2);//两条多项式的乘积
    if(a->next != NULL)
        print(a);//不为零多项式则进行正常输出
    else
        printf("0 0");//为零多项式则直接输出0 0
    printf("\n");
    List* b = add(list1, list2);//两条多项式的合并
    if (b->next != NULL)
        print(b);
    else
        printf("0 0");
}

List* mul (List* list1, List* list2) {
    List* head = malloc(sizeof(List));//新建乘积链表的头结点
    head->next = NULL;//尾空
    List* post = list1;//记录一条多项式的头节点
    while (list2->next != NULL) {
        list2 = list2->next;
        list1 = post;//内循环开始前更新指针指回头结点
        while (list1->next != NULL) {
            list1 = list1->next;
            int coe = list1->coe * list2->coe;//系数相乘
            int index = list1->index + list2->index;//指数相加
            insert(head, coe, index);//调用插入函数
        }
    }
    return head;//返回头结点
}

List* add(List* list1, List* list2) {
    List* head = malloc(sizeof(List));//新建相加合并的多项式头结点
    head->next = NULL;
    while (list1->next != NULL) {
        list1 = list1->next;//第一条多项式每个节点都调用插入函数
        insert(head, list1->coe, list1->index);
    }
    while (list2->next != NULL) {
        list2 = list2->next;//第二条多项式每个节点都调用插入函数
        insert(head, list2->coe, list2->index);
    }
    return head;//返回头结点
}

int insert(List* head, int coe, int index) {
    while (head->next != NULL) {//寻找插入位置
        if (head->next == NULL || head->next->index < index) {
            break;
            //1、如果下一节点为空，则当前指针指向最后一个节点
            //2、如果下一节点的指数比目标指数小，说明需要新建节点插入
        }
        if (head->next->index == index) {//若原链表中存在目标指数的节点
            int tempCoe = head->next->coe + coe;
            if (tempCoe == 0) {//若合并后系数为0，则删除该节点
                List* post = head->next;
                head->next = post->next;
                free(post);
            }
            else {//系数不为零则正常合并相加
                head->next->coe = tempCoe;
            }
            return 0;
        }
        head = head->next;
    }
    List* newNode = malloc(sizeof(List));//新建插入节点
    newNode->next = NULL;//尾空
    newNode->coe = coe;//系数赋值
    newNode->index = index;//指数赋值
    newNode->next = head->next;//节点连接
    head->next = newNode;
    return 1;
}

void print(List* list) {
    while (list->next) {
        list = list->next;
        printf("%d %d", list->coe, list->index);
        if (list->next) {//最后一个不打印空格
            printf(" ");
        }
    }
}

最短的桥
五月的第一道题

DFS标记第一座岛 + BFS扩张第二座岛

看这题人挺少的，而且好像思路正确效果也还行，就写一篇题解吧2333

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

class Solution {
    int[][] dirs ={{-1,0},{1,0},{0,-1},{0,1}};
    int row;
    int col;
    public int shortestBridge(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        Queue<int []> queue = new LinkedList<int []>();
        boolean flag = false;//判断是否进行了一次深度优先搜索
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 1){
                    if(!flag) {//是第一次遇到1，也就是第一座岛
                        DFS(grid, i, j);//进行深度优先搜索吧将该岛屿都标记为2
                        flag = true;//更改标记为已深搜
                    }
                    else
                        queue.offer(new int[]{i, j});//记录第二座岛的坐标
                }
            }
        }
        int count = 0;//桥的单元格数
        while(!queue.isEmpty()){
            int size = queue.size();//第二座岛（包括搭好的桥）中需要向外扩张的单元格数量
            while(size-- > 0){
                int[] point = queue.poll();
                for (int[] dir : dirs){
                    int x = point[0] + dir[0];
                    int y = point[1] + dir[1];
                    if(x < 0 || y < 0 || x > row - 1 || y > col - 1 || grid[x][y] == 1)
                        continue;//越界或为岛屿时跳过循环
                    else if(grid[x][y] == 2)
                        return count;//桥搭建到了第一座岛则返回count
                    grid[x][y] = 1;//标记为第二座岛在这里搭过桥
                    queue.offer(new int[]{x, y});
                }
            }
            count++;//扩张一步桥的长度+1
        }
        return count;
    }
    public void DFS(int[][] grid, int i, int j){
        grid[i][j] = 2;//将第一座岛屿都标记为2
        for (int[] dir : dirs){
            int x = i + dir[0];
            int y = j + dir[1];
            if(x < 0 || y < 0 || x > row - 1 || y > col - 1 || grid[x][y] != 1)
                continue;//越界或为已标记的岛屿时跳过循环
            DFS(grid,x, y);//上下左右深搜
        }
    }
}

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

242

发表留言

安和

13天前

抱大腿

九日作者

12天前

(/ω＼)安和好久不见

安和

12天前

我也要高考啦

九日作者

12天前

啊差点以为咱们同届了，想起来小一届来着，加油啊哈哈哈哈，只剩最后一个月了，冲冲冲！尽自己最大的努力！

安和

12天前

疫情啦，现在二模都是线上在考，两个星期没去学校已经失忆了（

九日作者

11天前

23333失忆了可太真实唉疫情搞的，当时我在家也是学不下去，网课害人不浅（虽然现在感觉网课是真的香）

安和

11天前

胖虎同学

18天前

这五月还没开始呢就有页面了

九日作者

17天前

提前开个页面嘛，明天就能写了

力扣每日一题（五月）

扫描右侧二维码继续阅读

May 1, 2022

微风忆夏

力扣每日一题（五月）

05-17 二 晴

05-16 一 云

05-15 日 雨

05-14 六 雨

05-13 五 雨

05-12 四 雨

05-11 三 雨

05-10 二 雨

05-09 一 晴

05-08 日 晴

05-07 六 晴

05-06 五 晴

05-05 四 晴

05-04 三 晴

05-03 二 晴

05-02 一 晴

05-01 日 晴

05-17 二晴

05-16 一云

05-15 日雨

05-14 六雨

05-13 五雨

05-12 四雨

05-11 三雨

05-10 二雨

05-09 一晴

05-08 日晴

05-07 六晴

05-06 五晴

05-05 四晴

05-04 三晴

05-03 二晴

05-02 一晴

05-01 日晴