weekly-algorithm-no.1.md

2024-09-08

字数统计: 1.1k字 | 阅读时长≈ 5分

每周算法NO.1

1367. 二叉树中的链表

原题链接：1367. Linked List in Binary Tree

简要描述：

给定一个链表、一个二叉树，判断二叉树中是否存在链表路径。

解题思路：

找出所有与链表头节点想等的二叉树节点
从这些节点开始分别向下遍历，判断节点值与链表值是否想等

public class LinkedSubPath {
    // 1367. Linked List in Binary Tree
    public boolean isSubPath(ListNode head, TreeNode root) {
        List<TreeNode> treeNodes = new ArrayList<>();
        findHead(root, head.val, treeNodes);
        for (TreeNode treeNode : treeNodes) {
            boolean isSubPath = findListNodePath(head, treeNode);
            if(isSubPath) {
                return true;
            }
        }
        return false;
    }

    private boolean findListNodePath(ListNode head, TreeNode treeNode) {
        if (head == null) {
            return true;
        }
        if (head.val != treeNode.val) {
            return false;
        }
        return findListNodePath(head.next, treeNode.left) || findListNodePath(head.next, treeNode.right);
    }

    private void findHead(TreeNode root, int val, List<TreeNode> treeNodes) {
        if (root == null) {
            return;
        }
        if (root.val == val) {
            treeNodes.add(root);
        }
        if (root.left != null) {
            findHead(root.left, val, treeNodes);
        }
        if (root.right != null) {
            findHead(root.right, val, treeNodes);
        }
    }
}

874. 模拟行走机器人

原题链接：874. Walking Robot Simulation

题目简述：

平面无限大，机器人从原点(0，0)向北按指令移动，指令如下：

-2: 左转90度

-1: 右转90度

1<= k <= 9: 向当前方向移动k格

平面上存在障碍物，障碍物坐标列表obstacle，遇到障碍物会停留在障碍物的前一个网格方块上，并继续执行下一个命令。

求距离原点的最远距离的平方

note:

北 +y
东 +x
南 -y
西 -x
原点可能存在障碍物

解题思路：

模拟行走过程
通过 0， 1， 2， 3分别代表各个方向
行动时判断当前方向是否存在障碍物，确定最终行走位置

public class WalkRobot {
    public int robotSim(int[] commands, int[][] obstacles) {
        int distance = 0;
        int face = 1;
        int x = 0, y = 0;
        for (int command : commands) {
            if (command > 0) {
                int originX= x, originY = y;
                if (face == 0) {
                    // E
                    x += command;
                    for (int[] obstacle : obstacles) {
                        if (obstacle[1] == y && obstacle[0] > originX) {
                            x = Math.min(obstacle[0] - 1, x);
                        }
                    }
                } else if (face == 1) {
                    // N
                    y += command;
                    for (int[] obstacle : obstacles) {
                        if (obstacle[0] == x && obstacle[1] > originY) {
                            y = Math.min(obstacle[1] - 1, y);
                        }
                    }
                } else if (face == 2) {
                    // W
                    x -= command;
                    for (int[] obstacle : obstacles) {
                        if (obstacle[1] == y && obstacle[0] < originX) {
                            x = Math.max(obstacle[0] + 1, x);
                        }
                    }
                } else if (face == 3) {
                    // S
                    y -= command;
                    for (int[] obstacle : obstacles) {
                        if (obstacle[0] == x && obstacle[1] < originY) {
                            y = Math.max(obstacle[1] + 1, y);
                        }
                    }
                }
                distance = Math.max(distance, x * x + y * y);
            } else {
                face = turn(face, command);
            }
        }
        return distance;
    }

    public  int turn(int face, int command) {
        if (command == -1) {
            return  (face + 3) % 4;
        }
        if (command == -2) {
            return  (face + 1) % 4;
        }
        return 0;
    }
}

725. 分隔链表

原题链接：725. 分隔链表

题目简述：给定一个链表和数字k(1<=k<=50)，要求将链表均分为k个部分，每个部分长度差不超过1

解题思路：

求出链表的长度
计算各个部分的长度
遍历链表，获取每个部分的head
设置分隔，将分隔点的next设置为null

public class SplitLinkedList {
    // 725. Split Linked List in Parts
    // https://leetcode.com/problems/split-linked-list-in-parts/description/?envType=daily-question&envId=2024-09-08
    public ListNode[] splitListToParts(ListNode head, int k) {
        if (head == null) {
            return new ListNode[0];
        }
        ListNode p = head;
        int len = 0;
        while (p != null) {
            len++;
            p = p.next;
        }
        int avg = len / k;
        int mod = len % k;
        ListNode[] res = new ListNode[k];
        p = head;
        for (int turn = 0; turn < k; turn++) {
            ListNode damnHead = new ListNode();
            ListNode cur = damnHead;
            for (int n = 0; n < avg; n++) {
                cur.next = p;
                p = p.next;
                cur = cur.next;
            }
            if (mod > 0) {
                cur.next = p;
                p = p.next;
                cur = cur.next;
                cur.next = null;
                mod--;
            } else {
                cur.next = null;
            }
            res[turn] = damnHead.next;

        }
        return res;
    }
}

官方题解

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        int n = 0;
        ListNode temp = head;
        while (temp != null) {
            n++;
            temp = temp.next;
        }
        int quotient = n / k, remainder = n % k;

        ListNode[] parts = new ListNode[k];
        ListNode curr = head;
        for (int i = 0; i < k && curr != null; i++) {
            parts[i] = curr;
            int partSize = quotient + (i < remainder ? 1 : 0);
            for (int j = 1; j < partSize; j++) {
                curr = curr.next;
            }
            ListNode next = curr.next;
            curr.next = null;
            curr = next;
        }
        return parts;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/split-linked-list-in-parts/solutions/1010003/fen-ge-lian-biao-by-leetcode-solution-wevt/
来源：力扣（LeetCode）

本文作者： Naskete
本文链接： https://Naskete.github.io/2024/09/08/algorithm/weekly-algorithm-no.1/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！