JR_Chan-CSDN博客

原创 Pytorch实现L1与L2正则化

关于Pytorch如何实现正则化在这篇博客《pytorch实现L2和L1正则化regularization的方法》其实已经给出了差不多正确的方法，但是这篇博客的代码在实现L2正则的时候是有一点小问题的。首先看一下L2正则的公式：Loss=CL+λ2∑wi2Loss = CL+\frac{\lambda}{2} \sum w_{i}^{2}Loss=CL+2λ∑wi2 其中CLCLCL就是正常的损失（比如交叉熵损失）。实际上在Pytorch中，当你使用SGD的时候，其中的一个参数weight

2020-12-04 16:55:32 6440 4

原创 leetcode--仅含1的子串数

题目是LeetCode第197场周赛的第二题，链接：1513. 仅含 1 的子串数。具体描述为：给你一个二进制字符串s（仅由'0'和'1'组成的字符串）。返回所有字符都为 1 的子字符串的数目。由于答案可能很大，请你将它对10^9 + 7取模后返回。示例1:输入：s = "0110111"输出：9解释：共有 9 个子字符串仅由 '1' 组成"1" -> 5 次"11" -> 3 次"111" -> 1 次示例2:输入：s = "101"输出：2解释：子字符串

2020-09-10 19:15:05 733

原创 leetcode--好数对的数目

题目是LeetCode第197场周赛的第一题，链接：1512. 好数对的数目。具体描述为：给你一个整数数组nums。如果一组数字(i,j)满足 nums[i] == nums[j]且i < j，就可以认为这是一组好数对。返回好数对的数目。示例1:输入：nums = [1,2,3,1,1,3]输出：4解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始示例2:输入：nums = [1,1,1,1]输出：6解释：数组中的每组数字都

2020-09-07 19:36:33 351

原创 leetcode--最多K次交换相邻数位后得到的最小整数

题目是LeetCode第196场周赛的第四题，链接：1505. 最多 K 次交换相邻数位后得到的最小整数。具体描述：给你一个字符串num和一个整数k。其中，num表示一个很大的整数，字符串中的每个字符依次对应整数上的各个数位。你可以交换这个整数相邻数位的数字最多k次。请你返回你能得到的最小整数，并以字符串形式返回。示例1：输入：num = "4321", k = 4输出："1342"解释：4321 通过 4 次交换相邻数位得到最小整数的步骤：4321-->3412-->3142--&

2020-09-02 23:11:11 1546

原创 leetcode--统计全 1 子矩形

题目是LeetCode第196场周赛的第三题，链接：1504. 统计全 1 子矩形。具体描述：给你一个只包含0和1的rows * columns矩阵mat，请你返回有多少个子矩形的元素全部都是1。示例1：输入：mat = [[1,0,1], [1,1,0], [1,1,0]]输出：13解释：有 6 个 1x1 的矩形。有 2 个 1x2 的矩形。有 3 个 2x1 的矩形。有 1 个 2x2 的矩形。有 1 个 3x1 的矩形。矩形数目

2020-07-19 22:48:15 321

原创 leetcode--所有蚂蚁掉下来前的最后一刻

题目是LeetCode第196场周赛的第二题，链接：1503. 所有蚂蚁掉下来前的最后一刻。具体描述见原题。这题其实是脑筋急转弯，想清楚逻辑之后就没啥难度了。因为两只蚂蚁相遇之后会同时改变移动方向并继续移动，所以如果在相遇之后把两只蚂蚁的角色调换一下，情况不就跟相遇之后啥都没发生一样了吗，所以直接按相遇不会发生任何事情来做就行了。也就是只需要找到向左走的蚂蚁中最靠右的位置leftMax ，那么其需要走的步数就是leftMax，同时找到向右走的蚂蚁中最靠左的位置rightMin，那么其需要走的步数就是n

2020-07-18 21:46:08 239

原创 leetcode-判断能否形成等差数列

题目是LeetCode第196场周赛的第一题，链接：1502. 判断能否形成等差数列。具体描述为：给你一个数字数组arr。如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为等差数列。如果可以重新排列数组形成等差数列，请返回true；否则，返回false。示例1:输入：arr = [3,5,1]输出：true解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。示例2:输入：arr = [1,2,4]

2020-07-18 17:27:07 811

原创 leetcode--找到最小生成树里的关键边和伪关键边

题目是LeetCode第194场周赛的第四题，链接：1489. 找到最小生成树里的关键边和伪关键边。具体描述见原题。这题关键在于怎么找最小生成树，只要怎么找，就可以先生成一棵最小生成树同时记录这个最小权重和。然后只要把某条边去掉再重新执行生成最小生成树的过程，如果此生成的最小生成树的权重和大于原先的最小权重和，那么就说明这条边为关键边，否则则为伪关键边。生成最小生成树的算法的话可以直接用kruskal算法，具体就是先对所有边根据权重进行排序，然后每次都取出最小权重的边加入最小生成树中去，判断是否会形成

2020-07-18 16:18:17 439

原创 leetcode--避免洪水泛滥

题目是LeetCode第194场周赛的第三题，链接：1488. 避免洪水泛滥。具体描述为：你的国家有无数个湖泊，所有湖泊一开始都是空的。当第n个湖泊下雨的时候，如果第n个湖泊是空的，那么它就会装满水，否则这个湖泊会发生洪水。你的目标是避免任意一个湖泊发生洪水。给你一个整数数组rains，其中：rains[i] > 0表示第i天时，第rains[i]个湖泊会下雨。rains[i] == 0表示第i天没有湖泊会下雨，你可以选择一个湖泊并抽干这个湖泊的水。请返回一个数组ans，满足：ans

2020-07-11 23:16:35 710

原创 leetcode--保证文件名唯一

题目是LeetCode第194场周赛的第二题，链接：1487. 保证文件名唯一。具体描述为：给你一个长度为n的字符串数组names。你将会在文件系统中创建n个文件夹：在第i分钟，新建名为names[i]的文件夹。由于两个文件不能共享相同的文件名，因此如果新建文件夹使用的文件名已经被占用，系统会以(k)的形式为新文件夹的文件名添加后缀，其中k是能保证文件名唯一的最小正整数。返回长度为n的字符串数组，其中ans[i]是创建第i个文件夹时系统分配给该文件夹的实际名称。示例1:输入：names = ["pe

2020-07-05 22:22:13 410

原创 leetcode--数组异或操作

题目是LeetCode第194场周赛的第一题，链接：1486. 数组异或操作。具体描述为：给你两个整数，n和start。数组nums定义为：nums[i] = start + 2*i（下标从0开始）且n == nums.length。请返回 nums 中所有元素按位异或（XOR）后得到的结果。示例1:输入：n = 5, start = 0输出：8解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。 "^" 为按位异或 XOR

2020-06-27 21:12:24 343

原创 leetcode--树节点的第 K 个祖先

题目是LeetCode第193场周赛的第四题，链接：1483. 树节点的第 K 个祖先。具体描述为：给你一棵树，树上有n个节点，按从0到n-1编号。树以父节点数组的形式给出，其中parent[i]是节点i的父节点。树的根节点是编号为0的节点。请你设计并实现getKthAncestor(int node, int k)函数，函数返回节点node的第k个祖先节点。如果不存在这样的祖先节点，返回-1。树节点的第k个祖先节点是从该节点到根节点路径上的第k个节点。示例:输入：["TreeAncestor",

2020-06-27 20:46:32 475

原创 leetcode--制作m束花所需的最少天数

题目是LeetCode第193场周赛的第三题，链接：1482. 制作 m 束花所需的最少天数。具体描述为：给你一个整数数组bloomDay，以及两个整数m和k。现需要制作m束花。制作花束时，需要使用花园中相邻的k朵花。花园中有n朵花，第i朵花会在bloomDay[i]时盛开，恰好可以用于一束花中。请你返回从花园中摘m束花需要等待的最少的天数。如果不能摘到m束花则返回-1。示例1:输入：bloomDay = [1,10,3,10,2], m = 3, k = 1输出：3解释：让我们一起观察这三天的

2020-06-21 21:37:36 398

原创 leetcode--不同整数的最少数目

题目是LeetCode第193场周赛的第二题，链接：1481. 不同整数的最少数目。具体描述为：给你一个整数数组arr和一个整数k。现需要从数组中恰好移除k个元素，请找出移除后数组中不同整数的最少数目。示例1:输入：arr = [5,5,4], k = 1输出：1解释：移除 1 个 4 ，数组中只剩下 5 一种整数。示例2:输入：arr = [4,3,1,1,3,3,2], k = 3输出：2解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，

2020-06-20 21:35:11 424

原创 leetcode--一维数组的动态和

题目是LeetCode第193场周赛的第一题，链接：1480. 一维数组的动态和。具体描述为：给你一个数组nums。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i])。请返回nums的动态和。示例1:输入：nums = [1,2,3,4]输出：[1,3,6,10]解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。示例2:输入：nums = [1,1,1,1,1]输出：[1,2,3,4,5]解释：动态和计算过程

2020-06-20 21:12:23 574

原创 leetcode--连续子数组的最大和

题目来自LeetCode，链接：面试题42. 连续子数组的最大和。具体描述为：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。示例：输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。很典型的动态规划问题，定义dp[i]表示以数组第i个元素为子数组最后一个元素时的子数组之和，则有dp[i]=max(dp[i-1],num

2020-06-14 21:22:34 454

原创 leetcode--给房子涂色III

题目是LeetCode第192场周赛的第四题，链接：1473. 给房子涂色 III。具体描述为：在一个小城市里，有m个房子排成一排，你需要给每个房子涂上n种颜色之一（颜色编号为1到n）。有的房子去年夏天已经涂过颜色了，所以这些房子不需要被重新涂色。我们将连续相同颜色尽可能多的房子称为一个街区。（比方说houses = [1,2,2,3,3,2,1,1]，它包含5个街区[{1}, {2,2}, {3,3}, {2}, {1,1}]。）给你一个数组houses，一个m * n的矩阵cost和一个整数targe

2020-06-13 21:13:13 616 2

原创 leetcode--设计浏览器历史记录

题目是LeetCode第192场周赛的第三题，链接：1472. 设计浏览器历史记录。具体描述为：你有一个只支持单个标签页的浏览器，最开始你浏览的网页是homepage，你可以访问其他的网站url，也可以在浏览历史中后退steps步或前进steps步。请你实现BrowserHistory类：BrowserHistory(string homepage)，用homepage初始化浏览器类。void visit(string url)从当前页跳转访问url对应的页面。执行此操作会把浏览历史前进的记录全部删

2020-06-11 21:38:11 408

原创 leetcode--数组中的 k 个最强值

题目是LeetCode第192场周赛的第二题，链接：1471. 数组中的 k 个最强值。具体描述为：给你一个整数数组arr和一个整数k。设m为数组的中位数，只要满足下述两个前提之一，就可以判定arr[i]的值比arr[j]的值更强：|arr[i] - m| > |arr[j] - m||arr[i] - m| == |arr[j] - m|，且arr[i] > arr[j]请返回由数组中最强的k个值组成的列表。答案可以以任意顺序返回。中位数是一个有序整数列表中处于中间位置的值。形

2020-06-10 20:02:57 272 1

原创 leetcode--重新排列数组

题目是LeetCode第192场周赛的第一题，链接：1470. 重新排列数组。具体描述为：给你一个数组nums，数组中有2n个元素，按[x1,x2,...,xn,y1,y2,...,yn]的格式排列。请你将数组按[x1,y1,x2,y2,...,xn,yn]格式重新排列，返回重排后的数组。示例1:输入：nums = [2,5,1,3,4,7], n = 3输出：[2,3,5,4,1,7] 解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5

2020-06-10 18:36:34 391

原创 leetcode--数据流中的中位数

题目来自LeetCode，链接：面试题41. 数据流中的中位数。具体描述为：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构：void addNum(int num) - 从数据流中添加一个整数到数据结构中。double

2020-06-09 20:31:26 798

原创 leetcode--数组中出现次数超过一半的数字

题目来自LeetCode，链接：面试题39. 数组中出现次数超过一半的数字。具体描述为：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例：输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2 一种比较容易想到的思路就是用一个map保存数字的出现次数，那么当出现一个数字的出现次数超过一半之后直接返回就行了。时间复杂度为O(N)O(N)O(N)，空间复杂度为O(N)O(N)O(N)。 JAVA版代码如下

2020-06-08 21:02:35 454

原创 leetcode--两个盒子中球的颜色数相同的概率

题目是LeetCode第191场周赛的第四题，链接：1467. 两个盒子中球的颜色数相同的概率。具体描述见原题。一种做法是我们先将所有的球都先放到右边盒子里，然后逐渐从右边盒子往左边盒子放球（拿0、1...balls[0]个第0种颜色的球，再拿0、1...balls[1]个第1种颜色的球…），当左右盒子的球的数量一样的时候，我们看此时两个盒子里球的颜色数是否一样，一样的话就可以计算一下当下这种左边右边各n个球且有相同颜色数的情况下的排列组合数，以左边为例，假设此时左边球的情况可以用数组L表示，则其可能

2020-06-07 21:00:17 1412

原创 leetcode--重新规划路线

题目是LeetCode第191场周赛的第三题，链接：1466. 重新规划路线。具体描述见原题。题目可以用BFS来解决，不过首先我们需要先建立两个邻接表toNext和reverse分别代表正常的邻接表和逆的邻接表（也就是边的方向反了过了）。然后套用BFS模板，先将0号节点入队，只要队列非空就执行以下循环：出队一个节点node，从toNext中获得node的邻接节点，只要未访问过则入队（同时这表明有一条路径需要进行反转），从reverse获得指向node的那些节点，只要未访问过，就入队（这种路径不用反

2020-06-04 21:31:48 400

原创 leetcode--切割后面积最大的蛋糕

题目是LeetCode第191场周赛的第二题，链接：1465. 切割后面积最大的蛋糕。具体描述见原题。题目其实还是蛮简单的，面积最大就意味着在长和宽方向上的边都是最大的，这样得到的面积才是最大的，所以我们就只需要找到长和宽方向上的最大边就行了。所以首先对两个代表了切割位置的数组进行排序，然后分别遍历，求出所有的边长（num[i]-num[i-1]就是了），然后将两个最大边长乘起来就得到了答案。时间复杂度为O(mlogm+nlogn)O(mlogm+nlogn)O(mlogm+nlogn)，空间复杂度为

2020-06-03 19:50:53 334

原创 leetcode--数组中两元素的最大乘积

题目是LeetCode第190场周赛的第一题，链接：1464. 数组中两元素的最大乘积。具体描述为：给你一个整数数组 nums，请你选择数组的两个不同下标i和j，使(nums[i]-1)*(nums[j]-1)取得最大值。请你计算并返回该式的最大值。2 <= nums.length <= 5001 <= nums[i] <= 10^3 示例1:输入：nums = [3,4,5,2]输出：12 解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大

2020-06-03 19:28:24 1027

原创 leetcode--字符串的排列

题目来自LeetCode，链接：面试题38. 字符串的排列。具体描述为：输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。示例：输入：s = "abc"输出：["abc","acb","bac","bca","cab","cba"] 这种全排列的题目其实就是典型的DFS+回溯，老套路了。这里用的是交换法，也就是对于第i个字符，我们都尝试将其跟后面的字符交换一下得到一个新的排列（因为不能有重复元素，所以后面的字符如果跟第i个字符一样的话就不

2020-06-02 20:14:16 383

原创 leetcode--序列化二叉树

题目来自LeetCode，链接：面试题37. 序列化二叉树。具体描述为：实现两个函数，分别用来序列化和反序列化二叉树。示例：你可以将以下二叉树： 1 / \ 2 3 / \ 4 5序列化为 "[1,2,3,null,null,4,5]" 可以按照示例的序列化方式（也可以用其他的方法，题目只是说可以用示例的方法而已），其实就是将层序遍历的结果输出为字符串，层序遍历直接套模板就好了：根节点入队列，非空节点数nodeCount加1只要非空节点数n

2020-06-01 21:16:10 421

原创 leetcode--二叉搜索树与双向链表

题目来自LeetCode，链接：面试题36. 二叉搜索树与双向链表。具体描述见原题。这道题目要把二叉搜索树转为排序的循环双向链表，那明显就需要中序遍历来保证有序，循环双向链表的就用两个指针分别指向前一个节点和当前节点，然后根据双向链表的要求操作这两个指针即可。时间复杂度是O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)。 JAVA版代码如下：/*// Definition for a Node.class Node { public int val; public

2020-05-31 19:55:22 218

原创 leetcode--复杂链表的复制

题目来自LeetCode，链接：面试题35. 复杂链表的复制。具体描述见原题。这道题目其实就是让我们实现深拷贝，每次复制一个节点的时候我们都不仅需要复制值val，还需要复制next和random指针，所以要求我们判断next和random指向的节点是否已经复制过了，是的话直接将指针指向复制过的节点，否则则需要拷贝。为了实现这一点，可以用一个map来保存原节点到复制节点的映射。时间复杂度是O(n)O(n)O(n)，空间复杂度为O(n)O(n)O(n)。 JAVA版代码如下："""# Definit

2020-05-30 20:52:44 234

原创 leetcode--两个子序列的最大点积

题目是LeetCode第190场周赛的第四题，链接：1458. 两个子序列的最大点积。具体描述为：给你两个数组nums1和nums2。请你返回nums1和nums2中两个长度相同的非空子序列的最大点积。数组的非空子序列是通过删除原数组中某些元素（可能一个也不删除）后剩余数字组成的序列，但不能改变数字间相对顺序。比方说，[2,3,5]是[1,2,3,4,5]的一个子序列而[1,5,3]不是。题目其实也不难，就是DFS+回溯的题目。这里判断是否伪回文路径的做法比较简单，直接判断路径上各个数字出现次数中为奇

2020-05-29 21:59:00 343

原创 leetcode--二叉树中的伪回文路径

题目是LeetCode第190场周赛的第三题，链接：1457. 二叉树中的伪回文路径。具体描述见原题。题目其实也不难，就是DFS+回溯的题目。这里判断是否伪回文路径的做法比较简单，直接判断路径上各个数字出现次数中为奇数的有多少个，只要超过两个就可以判定不是伪回文了，因为伪回文最多只有一个数字出现的次数为奇数（这个数刚好是中间位置的时候）。DFS的过程其实就是在记录（增加）各个数字的出现次数，回溯的过程则是恢复（减少）数字的出现次数。时间复杂度为O(n)O(n)O(n)，空间复杂度为O(n)O(n)O(

2020-05-28 20:20:15 313 1

原创 leetcode--定长子串中元音的最大数目

题目是LeetCode第190场周赛的第二题，链接：1456. 定长子串中元音的最大数目。具体描述为：给你字符串s和整数k。请返回字符串s中长度为k的单个子字符串中可能包含的最大元音字母数。英文中的元音字母为（a, e, i, o, u）。1 <= s.length <= 10^5s由小写英文字母组成1 <= k <= s.length 示例1:输入：s = "abciiidef", k = 3输出：3解释：子字符串 "iii" 包含 3 个元音字母。示例2

2020-05-27 20:22:16 592

原创 leetcode--检查单词是否为句中其他单词的前缀

题目是LeetCode第190场周赛的第一题，链接：1455. 检查单词是否为句中其他单词的前缀。具体描述为：给你一个字符串sentence作为句子并指定检索词为searchWord，其中句子由若干用单个空格分隔的单词组成。请你检查检索词searchWord是否为句子sentence中任意单词的前缀。如果searchWord是某一个单词的前缀，则返回句子sentence中该单词所对应的下标（下标从1开始）。如果searchWord是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。如果se

2020-05-27 19:36:13 493

空空如也

空空如也