leetcode 6366. 在网格图中访问一个格子的最少时间
题目描述leetcode 6366. 在网格图中访问一个格子的最少时间
给你一个 m x n 的矩阵 grid ,每个元素都为 非负 整数,其中 grid[row][col] 表示可以访问格子 (row, col) 的 最早 时间。也就是说当你访问格子 (row, col) 时,最少已经经过的时间为 grid[row][col] 。
你从 最左上角 出发,出发时刻为 0 ,你必须一直移动到上下左右相邻四个格子中的 任意 一个格子(即不能停留在格子上)。每次移动都需要花费 1 单位时间。
请你返回 最早 到达右下角格子的时间,如果你无法到达右下角的格子,请你返回 -1 。
示例 1:
输入:grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
输出:7
解释:一条可行的路径为:
- 时刻 t = 0 ,我们在格子 (0,0) 。
- 时刻 ...
leetcode 1798. 你能构造出连续值的最大数目
题目描述leetcode1798. 你能构造出连续值的最大数目
给你一个长度为 n 的整数数组 coins ,它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币,它们的和为 x ,那么称,你可以 构造 出 x 。
请返回从 0 开始(包括 0 ),你最多能 构造 出多少个连续整数。
你可能有多个相同值的硬币。
示例 1:
输入:coins = [1,3]
输出:2
解释:你可以得到以下这些值:
- 0:什么都不取 []
- 1:取 [1]
从 0 开始,你可以构造出 2 个连续整数。
示例 2:
输入:coins = [1,1,1,4]
输出:8
解释:你可以得到以下这些值:
- 0:什么都不取 []
- 1:取 [1]
- 2:取 [1,1]
- 3:取 [1,1,1]
- 4:取 [4]
- 5:取 [4, ...
QQ机器人DDBOT
搭建QQ机器人DDBOT最近在水群的时候看到一个机器人,可以推送直播、动态通知,还有一些自定义命令。感觉挺好玩的,正好云服务器闲着也是闲着(目前只跑了网站和code-server,没什么压力),索性搭个机器人玩玩。
下载与安装DDBOT的github页面:Sora233/DDBOT: 一个基于MiraiGO的QQ群推送框架。这个机器人是拆包即用的,所以完全不懂代码也没事,releases如下图,下载与机器对应的最新版本即可,比如在windows上就下载DDBOT-v1.0.9.2-windows-amd64.zip,我是搭在阿里云的CentOS上,所以下载DDBOT-v1.0.9.2-linux-amd64.tar.gz,可以在本地下载然后拖到云服务器上去(需要vscode页面),也可以直接wget,不过由于github的屏蔽问题,为了加快下载速度,最好找一个镜像站,网上一搜就有。
下载完后得到一个.tar.gz文件,这是一个压缩包,通过tar -zxvf 文件 解压,得到一个可执行文件DDBOT,将它放到一个单独的文件夹中,运行即可。
首次运行结果如下图:
进行扫码登录。 ...
leetcode 2514. 统计同位异构字符串数目
题目描述leetcode 2514. 统计同位异构字符串数目
给你一个字符串 s ,它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。
如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个 排列 ,那么我们称字符串 t 是字符串 s 的同位异构字符串。
比方说,"acb dfe" 是 "abc def" 的同位异构字符串,但是 "def cab" 和 "adc bef" 不是。
请你返回 s 的同位异构字符串的数目,由于答案可能很大,请你将它对 109 + 7 取余 后返回。
示例 1:
输入:s = "too hot"
输出:18
解释:输入字符串的一些同位异构字符串为 "too hot" ,"oot hot" ,"oto toh" ,"too toh" 以及 "too oht" 。 ...
总算在2022年拿到了心心念念的蓝牌子
竞赛分数更新了,终于拿到了Guardian。🥳🥳🥳八月三日拿到了Knight,当时也发帖留念了——刷题四月,用Knight为我的大一画上句号,那时觉得Guardian还很遥远,没想到一个学期过去,终于在2023年到来之前拿到了蓝牌子。
这五个月里有什么进步呢?
在算法上,主要就是系统地学习了一遍数据结构与算法。之前是遇到一道题不会,就去学那种算法,效率终究是比较低,而且没有形成完整的知识框架。这学期跟着老师学数据结构,从线性表、栈、队列学到树、图,有了比较完整的认识,在学习的过程中也把一些总结放到我的个人博客上。同时,也学到了很多新的算法,比如KMP算法、最小生成树、最短路、各种排序、并查集、贪心……这些稍难一点的算法可能就是Knight与Guardian之间的一些区别。当然,题量还是最关键的,拿到Knight时我通过了316题,而今天,已经有692题了,量变达到质变果真不假。
下学期好像就没有算法课了,希望还会坚持做下去leetcode。大家一起加油↖(^ω^)↗
数据结构与算法Week11&12——图
图与相关问题这两周学习了图,和一些图相关的问题。
基本概念图是一种非线性结构,与树相比,它可以是非连通的,也可以是有环的,所以图的问题要更为复杂。
图有很多术语,这里就不一一列举了,图的基本概念 - songguojun - 博客园这篇文章写得比较全面,可以去看看。
表示方法比较常用的有两种——邻接矩阵表示法和邻接表表示法。
邻接矩阵应当明确,我们要保存一张图,实际上就是要保存它的顶点和边,在不存在孤立点时,就相当于保存所有的边。而每两个顶点之间都可能有边。所以我们用一个二维矩阵G[n][n]来记录边的情况。G[i][j]=true代表有一条从i指向j的边,将G称为邻接矩阵。
邻接矩阵法的好处就是简单、直观,可以在O(1)的时间内检查两个顶点之间是否有边以及对边进行增删,而缺点就是空间浪费很大(尤其是对于稀疏图),且不易于增删节点。
邻接表邻接表表示法,是对每一个节点记录它指向的节点,每个节点指向的节点数目各异,所以不能用静态数组保存,在C语言中要用链表或者动态数组,而C++中则可以直接用vector,保存为vector<vector<int>> G(n),将G ...
leetcode 795. 区间子数组个数
题目描述leetcode795. 区间子数组个数
给你一个整数数组 nums 和两个整数:left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组,并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit 整数范围。
示例 1:
输入:nums = [2,1,4,3], left = 2, right = 3
输出:3
解释:满足条件的三个子数组:[2], [2, 1], [3]
示例 2:
输入:nums = [2,9,2,5,6], left = 2, right = 8
输出:7
提示:
1 <= nums.length <= 105
0 <= nums[i] <= 109
0 <= left <= right <= 109
题解——枚举右端点,寻找左端点范围思路根据滑动窗口的思想,我们希望对于每一个右端点,找出满足要求的左端点的范围。假如记为[lower,upper],那 ...
meet in the middle——折半搜索算法
meet in the middle——折半查找算法提出问题回溯法是一个很经典的算法了,也可以视为暴力搜索算法,一般时间复杂度会达到指数级甚至阶乘级,只能用于求解规模很小的问题。比如N皇后问题、迷宫问题、数独、0-1背包……当问题规模变大一些时,一般会考虑是否有重复搜索,尝试通过记忆化来剪枝,使其变为记忆化搜索,来减少子问题的重复搜索次数,比如爬台阶,这样的做法使时间复杂度达到与动态规划相同的量级,不过常数更大。
考虑这样一个问题:给定一个长度为n的数组,里面有正有负。现在想从表中选出任意多个数,使它们的和为0,问有多少种选法?
考虑退化问题,如果把要选出来的个数确定下来,比如为2、3、4……就变成经典问题——K数之和,暴力方法复杂度为O(N^k),通过排序+双指针可以达到O(N^(k-1))。然而一旦不确定,就变成了0-1背包,对每个数都要考虑选与不选,时间复杂度为O(2^N),才能找到所有组合。这一般能处理到N=20的情况,再大就无能为力了。
假如N=30,这种方法就完全不可行了吗?能否对上面的算法做一些优化呢?这就要用到本文说的meet in the middle算法了。
mee ...
在shell脚本中运行tmux&开机自动执行脚本
起因今天又收到了阿里云的邮件,说实例意外宕机然后又帮我重启了,让我去检查应用是否恢复。查看网站,倒是没有问题,然而code-server却登录不了。其实这也不出我所料,因为每次重启阿里云时,网站都会自动恢复,而code-server则要我去远程连接,重新敲命令来启动。
之前一直是这么干的,然而今天感觉太麻烦了,code-server能否也开机自启呢?经过一番周折,终于实现了。
第一步:用shell脚本启动code-server这一部分我很久之前就完成了,不过还是说一下。我将code-server的可执行文件放在家目录下,每次只要运行它就行了,不过还要指定访问端口,并且指定证书以支持https访问。编写的code-server.sh脚本如下,这倒没什么难的,不过是把手敲的命令放到文件里罢了。
1234567#! /bin/bash#设置密码export PASSWORD="******"#定位至文件夹cd ~/MyCode-server#运行code-server,指定ssl证书以及端口./code-server --cert **** --cert-key **** ...
leetcode 891. 子序列宽度之和
题目描述leetcode891. 子序列宽度之和
一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。
给你一个整数数组 nums ,返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大,请返回对 109 + 7 取余 后的结果。
子序列 定义为从一个数组里删除一些(或者不删除)元素,但不改变剩下元素的顺序得到的数组。例如,[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。
示例 1:
输入:nums = [2,1,3]
输出:6
解释:子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。
示例 2:
输入:nums = [2]
输出:0
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 105
题解——贪心,直观解释思路我们知道,一个数组有2^n-1个非空子序列,枚举显然是不 ...