Moon

题目描述题目链接 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/‘ 开头），请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//‘）都被视为单个斜杠 ‘/‘ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。 请注意，返回的 规范路径 必须遵循下述格式： 始终以斜杠 ‘/‘ 开头。两个目录名之间必须只有一个斜杠 ‘/‘ 。最后一个目录名（如果存在）不能 以 ‘/‘ 结尾。此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘..’）。返回简化后得到的 规范路径 。 样例12345示例 1：输入：path = "/home/"输出："/home"解释：注意，最后一个目录名后面没有斜杠。 12345示例 2： ...

题目描述题目链接 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： “123”“132”“213”“231”“312”“321”给定 n 和 k，返回第 k 个排列。   样例1234示例 1：输入：n = 3, k = 3输出："213" 1234示例 2：输入：n = 4, k = 9输出："2314" 1234示例 3：输入：n = 3, k = 1输出："123" 1234提示：1 <= n <= 91 <= k <= n! 算法1(枚举) $O(n^2)$由于需要快速计算出从小到大第 k 位的排列值，那么我们可以考虑当确定了 i 位数字时，排列数目的变化； 首先，当任意一位数字都未确定时，总共排列的数目为 $n!$种 每确定一位数字， 剩余的排列数就会相应的变为 $(n - 1)!$种 那么，我们可以从小到大枚举尚未选择的最小数字，若当前第 k 个排列大于剩余的排列数 $(n - i ...

题目描述题目链接 已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。 给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。 你必须尽可能减少整个操作步骤。 样例12输入：nums = [2,5,6,0,0,1,2], target = 0输出：true 12输入：nums = [2,5,6,0,0,1,2], target = 3输出：false 算法1(暴力枚举) $O ...

题目描述整数数组的一个 排列  就是将其所有成员以序列或线性顺序排列。 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。给你一个整数数组 nums ，找出 nums 的下一个排列。 必须 原地 修改，只允许使用额外常数空间。 样例12输入：nums = [1,2,3]输出：[1,3,2] 算法1思路为了找到下一个排列，我 ...

题目描述给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例如图： 样例示例 1： 1234输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 算法1(线性扫描三次) $O(n)$对于每一个柱子来说，若他要能够接住雨水，那么必须满足在这根柱子的左右两边存在着高度高于他的其他柱子，这样才有可能形成凹槽接住雨水。 那么可以通过两次遍历整个数组，第一次遍历存储每个位置左侧的最高柱子，第二次遍历存储每个位置右侧的最高柱子 最终，预处理完左右两侧的柱子之后，我们可以最后遍历所有的柱子，根据每个柱子左右两侧的最大柱子计算以该柱子之上可以接住的雨水即可 C++ 代码123456789101112131415161718192021class Solution {public: int trap(vector<int>& height ...

JAVA复习——第一章1.1 计算机、程序和Java概述 计算机概述 计算机是存储 和 处理数据的电子设备 计算机包括硬件(Hardware) 和 软件(Software) 两部分 一般来说，硬件指计算机中可见的物理部分，即对于人类来说可以在现实世界中看到、触摸到的实体。通常来讲，计算机的硬件主要有如下几种： 中央处理器(CPU) 内存 存储设备(用来存储计算机中的数据) 输入设备(用来让人类想计算机中输入数据) 输出设备(用来展示计算机中的数据) 通信设备(用来与互联网、其他计算机连接) 上述计算机中的硬件借助总线(bus)实现互联 在一般计算机中，总线搭建在主板上，而主板是一块连接计算机各个部分的电路板 软件则是一些指令，用来操控计算机 硬件概述 中央处理器(Central Processing Unit, CPU)，是计算机的核心和大脑，负责从计算机内存获取并执行指令 关于时钟 CPU内部的时钟以固定的速度发射电子脉冲 电子脉冲用于控制和同步计算机各种操作的步调 时钟速度越快，表示在单位时间内执行的指令越多 时钟速度的计量单位是赫兹(hertz, Hz), 一赫兹相当 ...

Dijkstra: Dijkstra求最短路 I Dijkstra求最短路 II 朴素Dijkstra的算法思想: 123456789101112131415161718int dijkstra(){ memset(dist, 0x3f, sizeof dist); // 初始化，将图中所有的点距离初始为 负无穷，随后在 dijkstra 的算法过程中更新最短距离; dist[1] = 0; // 在这里将 标号为 1 的点距离初始为0， 表示 1 号点到 1 号点的距离为 0; st[1] = true; // 表示 for(int i = 0; i < n; i ++) { int t = -1; // 寻找当前集合中距离最小的点 /* 根据 dijkstra 的定义，很容易知道，第一次循环一定会找到 1 号点， 随后根据 1 号点的距离更新其余点的值 */ for(int j = 1; j <= n; j ++) ...

以阿里云 ECS 服务器，搭载 Ubuntu 20.04系统为例，分享我在使用服务器时的一些配置 添加子用户购买了阿里云服务之之后，系统会分配给我们 root 用户的权限。但是在开发过程中，可能出现误操作删除某些配置、系统文件而导致服务器崩溃的现象。 因此日常的代码开发应当在 子用户 中进行，防止误操作而删除某些关键文件。 配置子用户步骤如下： 以 root 用户登入服务器 终端中输入 adduser NewUsername 随后按照提示操作即可添加新的子用户 需要注意的是，此时添加的子用户并不具有 sudo 权限, 因此要给新加入的用户添加 sudo 权限 添加 sudo 权限： 首先输入 cd .. 回到根目录 在根目录中输入 cd etc/sudoers.d/ 进入 sudo 权限配置文档 使用 vim 命令创建文件，不需要加入后缀名 在新创建的文件中输入 Username ALL=(ALL) ALL 保存后退出 经过上述操作，成功在云服务器上添加了具有 sudo 权限的子用户，以后就不用登陆 root 用户进行开发了，直接在此处开发即可 配置 SSH 免密登录使用阿里云时， ...

DFS:排列数字n-皇后 深度优先搜索通常需要使用布尔值来记录某个元素是否被遍历过 深度优先搜索需要注意状态的回溯, 每当进入更深层的DFS时,需要在进入之前改变元素的遍历状态, 当从更深层DFS中弹出时, 需要将之前改变的元素状态复位; 对于n皇后之类的棋盘问题，可以考虑使用建立坐标系的方式构建直线来使用对角线、反对角线等辅助线来解题。 BFS:走迷宫八数码 广度优先遍历的通用模板:12345678while(队列不空){ auto t = 队头元素 遍历队头元素所能到达的元素，并加入队列中 并根据题目维护不同的额外信息}队列为空时，说明深度遍历已经结束 BFS中通常涉及到上下左右方向的枚举，可以直接使用两个数组dx dy来模拟 树和图的DFS:数的重心 树和图的BFS:图中点的层次 树和图的存储方式有邻接表和邻接矩阵两种，稀疏图可以使用邻接表，稠密图则需要使用邻接矩阵存储 邻接表模板:12345678int h[N], e[N], ne[N], idx;memset(h, -1, sizeof h);void ...

Trie 树:字符串统计最大异或对 并查集:合并集合连通块中点的数量食物链 堆:模拟堆 哈希:模拟散列表字符串哈希 并查集中可以维护额外的信息来解决题目 模拟堆需要对常规的堆实现任意位置的插入以及删除操作，需要使用额外的映射来维护插入点的顺序 模拟散列表常用的有两种方法，分别是拉链法与开放寻址法 拉链法:散列表中存放的是链表，出现冲突时在对应位置的链表中插入; 开放寻址法: 散列表为数据大小的2-3倍，当出现重复时，像其后位置依次寻找，若发现空位置则插入;