- 博客(64)
- 资源 (8)
- 收藏
- 关注
RSS订阅原创 牛客编程巅峰赛S2第11场
链接：https://ac.nowcoder.com/acm/contest/10323/A牛牛现在在花园养了n棵树，按顺序从第1棵到第n棵排列着。牛牛每天会按照心情给其中某一个区间的树浇水。例如如果某一天浇水的区间为[2,4]，就是牛牛在这一天会给第2棵，第3棵和第4棵树浇水。树被浇水后就会成长，为了简化问题，我们假设在初始时所有树的高度为0cm。每过去一天树会自然成长1cm，每次树被浇水后当天会额外成长1cm。m天中牛牛每天都都会选一个区间[l,r]对这个区间内的树进行浇水，牛牛想知道m天后有多少棵.
2020-12-23 01:24:22
977
原创 牛客编程巅峰赛S2第8场
牛牛选物链接：https://ac.nowcoder.com/acm/contest/9887/A牛牛有现在有n个物品，每个物品有一个体积v[i]和重量g[i],他想选择其中总体积恰好为V的若干个物品，想使这若干个物品的总重量最大，他想知道最大总重量为多少。（如果不存在合法方案，返回-1）01背包，不过容量太大了，而物品数量却很小，所以用二进制枚举即可import java.util.*;public class Solution { /** * 代码中的类名、方
2020-12-11 22:23:43
802
原创 牛客编程巅峰赛S2第7场
牛牛爱喝酒链接：https://ac.nowcoder.com/acm/contest/9752/A题目描述牛牛是一个酒鬼，非常爱喝酒，一瓶酒m元钱，两个酒瓶可以换一瓶酒，四个瓶盖可以换一瓶酒，现在有 n 元钱，求最多可以喝多少瓶酒？（注：没有借贷功能，即最终不允许借一瓶酒、喝完后拿酒瓶兑换归还的操作）签到题：import java.util.*;public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，
2020-12-09 00:04:28
746
原创 牛客编程巅峰赛S2第6场
A:https://ac.nowcoder.com/acm/contest/9715/A牛牛想知道在[0,n]范围中，选取一个最大的数x，满足x%a=b，不过这个范围可能会很大，牛牛不知道该如何解决，所以他想请你帮忙。给定如上所述的a,b,n，返回满足条件的最大的x。签到题，代码：import java.util.*;public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 *
2020-12-05 21:33:35
736
原创 牛客编程巅峰赛S2第5场
怕npy的牛牛链接：https://ac.nowcoder.com/acm/contest/9556/B来源：牛客网题目描述牛牛非常怕他的女朋友，怕到了走火入魔的程度，以至于每当他看到一个字符串同时含有n,p,y三个字母他都害怕的不行。现在有一个长度为m的只包含小写字母‘a’-‘z’的字符串x，牛牛想知道能令他不害怕的最长子串的长度是多少。（对于字符串”abc”来说，”c”,”ab”都是原串的子串，但”ac”不是原串子串）基础题，滑动窗口即可解决import java.util..
2020-12-01 22:44:02
643
原创 位图法和布隆过滤器
大数据量的排序和判重，可以用位图法和布隆过滤器位图法:将数值按顺序分布于二进制位的空间实现位图法非常容易，只需要一些基本的位操作将要存储的数值转化到相应的数组位置上去基本操作是s.get(n) == ((arr[n/len] & (1<<(n%len))) != 0)，其中len表示使用的存储类型长度，比如int是32，byte是8arr[n/len]是定位到存储该数使用的二进制位值(1<<(n%len))表示该值的二进制表达位，相与就能确定该位是
2020-11-29 19:01:35
636
原创 牛客编程巅峰赛S2第4场
最小最大问题很明显是二分，枚举间隔即可，判断是否合法要点技巧import java.util.*;/* * public class Interval { * int start; * int end; * public Interval(int start, int end) { * this.start = start; * this.end = end; * } * } */public class Solution { /*..
2020-11-27 23:19:45
598
原创 归并排序
148. 排序链表给你链表的头结点head，请将其按 升序 排列并返回 排序后的链表 。进阶：你可以在O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？这里场景是链表排序，给了nlogn的时间复杂度，但需要常数级的空间nlogn的时间复杂度的排序有：归并排序、堆排序和快速排序但是空间上，这里使用堆排序和快排都要额外空间所以最适合的是原地进行归并排序O(1)空间复杂度就不能用递归了代码：class Solution { public...
2020-11-26 21:22:55
602
原创 基数排序
164. 最大间距给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。如果数组元素个数小于 2，则返回 0。示例1:输入: [3,6,9,1]输出: 3解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。示例2:输入: [10]输出: 0解释: 数组元素个数小于 2，因此返回 0。说明:你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。请尝试在线性时间复杂度和空间复杂度..
2020-11-26 21:09:35
639
原创 牛客编程巅峰赛S2第3场 - 青铜&白银&黄金
链接：https://ac.nowcoder.com/acm/contest/9246/A来源：牛客网牛牛在各个平台被各种传奇游戏的广告轰炸，所以他决定去玩一玩这类的游戏。这类游戏挂机就可以升级，所以牛牛每天都能变强。在第i天里，牛牛能杀死防御力小于等于i的怪物。但由于牛牛还要刷题，所以牛牛每天最多杀一只怪物。这个游戏共有n只怪物，每只怪物的防御力为DEF[i]，牛牛想知道最少要到第几天才能把这n只怪物都杀死。import java.util.*;public class Solutio.
2020-11-24 23:07:52
778
原创 交易保证幂等性
如果在以太坊中要为用户提交一笔交易或事物，服务器代理广播到网络中：1.广播成功，服务器返回交易成功结果给前端，如果因为网络问题返回交易成功的信息无法送达客户端呢？不恰当的处理可能会让用户误以为交易失败（实际上交易成功只是确认成功的消息在网络中丢了），再次发起交易造成损失。这就是在支付案例中的幂等性。幂等性指可以使用相同参数重复执行，并能获得相同结果的函数，这些函数不会影响系统状态，也不用担心重复执行会对系统造成改变。也就是相同参数一次请求和多次请求具有相同的状态结果。这个风险需要应用前端
2020-10-24 16:14:36
1541
原创 树形dp换根
树形dp即在树上进行动态规划模板题：834. 树中距离之和给定一个无向、连通的树。树中有 N 个标记为 0...N-1 的节点以及 N-1条边。第 i 条边连接节点edges[i][0] 和 edges[i][1]。返回一个表示节点 i 与其他所有节点距离之和的列表 ans。示例 1:输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]输出: [8,12,6,10,10,10]解释:如下为给定的树的示意图： 0/...
2020-10-06 17:37:12
695
原创 单调栈
单调栈中存放的数据是有序的，所以单调栈也分为单调递增栈和单调递减栈单调递增栈：栈中数据出栈的序列为单调递增序列 单调递减栈：栈中数据出栈的序列为单调递减序列例如有一组数10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。10入栈时，栈为空，直接入栈，栈内元素为10。3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。7入栈时，栈顶元素3比7小，则栈顶元素出
2020-09-23 23:30:25
706
原创 二叉搜索树
二叉搜索树中序遍历是递增序列二叉搜索树中序遍历是递增序列二叉搜索树中序遍历是递增序列直接上题 leetcode99. 恢复二叉搜索树二叉搜索树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。示例1:输入: [1,3,null,null,2] 1/3\ 2输出: [3,1,null,null,2] 3/1\ 2示例2:输入: [3,1,4,null,null,2] 3/ \1 ...
2020-09-21 17:09:59
632
原创 Morris 中序遍历
Morris 中序遍历是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为O(1)。如果 x无左孩子，先将 xx 的值加入答案数组，再访问 xx 的右孩子，即 x = x.\textit{right}x=x.right。 如果 xx 有左孩子，则找到 xx 左子树上最右的节点（即左子树中序遍历的最后一个节点，xx 在中序遍历中的前驱节点），我们记为 predecessor。根据 predecessor 的右孩子是否为空，进行如下操作。如果 predecessor 的右孩子为空，则将其右..
2020-09-14 10:10:53
896
原创 最小生成树Prim和Kruskal算法
生成树是对图遍历访问的一条无回路的遍历路径称为图的生成树，最小生成树是对带有权值的图,生成树路径中权值总和最小的路径,称为最小生成树.以leetcode5513. 连接所有点的最小费用为例给你一个points数组，表示 2D 平面上的一些点，其中points[i] = [xi, yi]。连接点[xi, yi] 和点[xj, yj]的费用为它们之间的 曼哈顿距离：|xi - xj| + |yi - yj|，其中|val|表示val的绝对值。请你返回将所有点连接的最小总...
2020-09-13 21:13:39
663
原创 有限状态机
剑指 Offer 20. 表示数值的字符串请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。将所有的状态转移存入map映射中代码：class Solution { public boolean isNumber(String s) { Map<Stat
2020-09-08 09:29:56
630
原创 二进制枚举
当需要对某一序列进行枚举取数时，可以使用二进制对是否取数进行标记。以leetcode491. 递增子序列为例给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。示例:输入: [4, 6, 7, 7]输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]说明:给定数组的长度不会超过15。数组中的整数范围是[-100,100]。给定数组中可..
2020-09-08 09:19:19
1586
原创 N皇后问题
n皇后问题研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。上图为 8 皇后问题的一种解法。给定一个整数 n，返回所有不同的n皇后问题的解决方案。每一种解法包含一个明确的n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。示例：输入：4输出：[[".Q..", // 解法 1 "...Q", "Q...", "..Q."],["..Q.", // 解法 2 "Q...", "....
2020-09-07 22:00:43
1039
原创 堆-堆中的路径
堆堆中的路径：将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。输入格式:每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。输出格式:对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。输入样例:5 346
2020-09-07 20:56:45
810
原创 逆康拓展开
康拓展开的基本原理源于以下公式：其中an表示序列的第i位在当前未出现的元素中是排在第几个以LeetCode60. 第k个排列为例：给出集合[1,2,3,…,n]，其所有元素共有n! 种排列。按大小顺序列出所有排列情况，并一一标记，当n = 3 时, 所有排列如下："123""132""213""231""312""321"给定n 和k，返回第k个排列。说明：给定 n的范围是 [1, 9]。给定 k的范围是[1, n!]。示例1:...
2020-09-05 21:15:31
221
原创 字符串哈希Rabin-Karp 算法
Rabin-Karp 字符串哈希算法可用于解决字符串匹配问题，通过比较字符串的哈希而不是内容来减少复杂度在该方法中，我们将字符串看成一个 base 进制的数，它对应的十进制值就是哈希值。显然，两个字符串的哈希值相等，当且仅当这两个字符串本身相同。然而如果字符串本身很长，其对应的十进制值在大多数语言中无法使用内置的整数类型进行存储。因此，我们会将十进制值对一个大质数 mod 进行取模。此时：如果两个字符串的哈希值在取模后不相等，那么这两个字符串本身一定不相同； 如果两个字符串的哈希值在取模后相等，.
2020-08-29 17:35:05
388
原创 欧拉回路Hierholzer 算法
定义通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。具有欧拉回路的无向图称为欧拉图。具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。判定1.图G是连通的，无孤立点。2.无向图奇点数为0或2，并且这两个奇点其中一个为起点另外一个为终点。有向图，可以存在两个点，其入度不等于出度，其中一个入度比出度大1，为路径的起点；另外一个出度比入度大1，为路径的终点。图中所有节点度为偶数，则一定存在欧拉回路Hierholz
2020-08-29 12:20:45
788
原创 位运算
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。示例 1:输入: [5,7]输出: 4示例 2:输入: [0,1]输出: 0此题的规律即找到m和n的公共前缀「Brian Kernighan 算法」，它用于清除二进制串中最右边的11。代码：class Solution { public int rangeBitwiseAnd(int m, ..
2020-08-23 18:51:26
138
原创 字典树
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。可以用指针或者静态数组实现指针实现：public class TrieNode { public int path; public int end; public TrieNode[] map; public Tri.
2020-08-06 18:10:30
104
原创 状态压缩动态规划
寻宝我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 'S' 表示），和唯一的宝藏地点（用 'T' 表示）。但是，宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点（用 'M' 表示），只有所有机关均被触发，才可以拿到宝藏。要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（用 'O' 表示），每个石堆都有无限个足够触发机关的重石。但是由于石头太重，我们一次只能搬一个石头到指定地点。迷宫中同
2020-07-31 18:04:19
127
原创 判断子序列动态规划
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。示例1:s = "abc", t = "ahbgdc"返回true.示例2:s = "axc", t =...
2020-07-27 17:39:09
202
原创 最长递增路径（多解）
给定一个整数矩阵，找出最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。示例 1:输入: nums =[ [9,9,4], [6,6,8], [2,1,1]]输出: 4解释: 最长递增路径为[1, 2, 6, 9]。示例 2:输入: nums =[ [3,4,5], [3,2,6], [2,2,1]]输出: 4解释: 最长递增路径是[3, 4, 5...
2020-07-26 10:17:31
460
原创 LeetCode（97. 交错字符串）字符串dp
给定三个字符串s1, s2, s3, 验证s3是否是由s1和s2 交错组成的。示例 1:输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"输出: true示例2:输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"输出: false代码：class Solution { public boolean isInterleave(String s1, S...
2020-07-18 09:33:36
114
转载 二分图
二分图二分图定义：二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于...
2020-07-16 11:00:44
164
转载 求一个序列中两个只出现一次的数
原文链接：http://www.cnblogs.com/grubbyskyer/p/3915261.html当然了，O(1)空间复杂度是必须的...先看一个简单版：求出一个序列中一个只出现一次的数COJ 1217 奇数个的那个数http://122.207.68.93/OnlineJudge/problem.php?id=1217我们知道任意两个相同的数 异或结果为0 任何数与0异或结果是其本身 异或运算满足交换律亦即：a^a=0 a^0=a (a^b)^(...
2020-07-11 17:51:22
115
原创 树状数组
树状数组1.什么是树状数组？顾名思义，就是用数组来模拟树形结构呗。那么衍生出一个问题，为什么不直接建树？答案是没必要，因为树状数组能处理的问题就没必要建树。和Trie树的构造方式有类似之处。2.树状数组可以解决什么问题可以解决大部分基于区间上的更新以及求和问题。3.树状数组和线段树的区别在哪里树状数组可以解决的问题都可以用线段树解决，这两者的区别在哪里呢？树状数组的系数要少很多，就比如字符串模拟大数可以解决大数问题，也可以解决1+1的问题，但没人会在1+1的问题上用大数模拟。4.
2020-07-11 17:01:46
202
原创 YOLO细节
YOLOv3采用了Faster RCNN的样本挖掘策略，将样本划分为3种状态，正样本、负样本、ignore。在检测器的训练过程，将非正样本与正样本进行IOU计算，如果非正样本与每一个正样本的IOU都不超过指定阈值(论文中设置为0.5)就设置为负样本状态，其他样本则成为ignore状态。对于正样本，YOLOv3和YOLO一样。YOLO划分网格本身就是一种先验辅助，正样本的中心落入哪一个格子里...
2020-03-14 16:08:32
181
原创 Springboot Security + JWT 请求验证
配置 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-security</artifactId> </dependenc...
2019-12-15 16:07:19
189
原创 vue发起跨域请求
使用axios跨域调试，在webpack配置跨域参数vue-cli下生成的config文件下的index.js中修改proxyTable配置 proxyTable: { "/api":{ target: 'http://localhost:8080', changeOrigin: true, pathRew...
2019-12-02 20:09:55
184
原创 快速排序
快排--不稳定排序，必备技能#include <bits/stdc++.h>using namespace std;int Partition(int a[], int low, int high){ int x = a[high];//将输入数组的最后一个数作为主元，用它来对数组进行划分 int i = low - 1;//i是最后一个小于主元的数的下标...
2019-11-09 19:42:55
98
原创 非递归汉诺塔
借助堆栈以非递归（循环）方式求解汉诺塔的问题（n, a, b, c），即将N个盘子从起始柱（标记为“a”）通过借助柱（标记为“b”）移动到目标柱（标记为“c”），并保证每个移动符合汉诺塔问题的要求。输入格式:输入为一个正整数N，即起始柱上的盘数。输出格式:每个操作（移动）占一行，按柱1 -> 柱2的格式输出。输入样例:3输出样例:a -> ca...
2019-08-21 17:11:06
207
原创 奶牛披萨--位标记/组合数
原题链接：https://ac.nowcoder.com/acm/contest/945/A题目描述有T种馅料，但有些馅料不能被放在一起。求选出一些馅料的方案数是多少。文件输入第一行为两个整数 T 和 N（T≤20,N≤52T≤20,N≤52），N表示接下来N行会有N个限制。接下来N行，每行的第一个数Z表示接下来数的个数：a1,a2......az，表示任意一种陷料中这z种馅料不能...
2019-07-05 18:52:30
160
原创 文本识别text-detection-ctpn环境搭建
最近做文本识别需要用到CTPN，window下搭建环境花了不少功夫，做个笔记项目GitHub地址简介CTPN在文本识别上表现优异，因为把RNN引入目标检测问题，加入了LSTM层，使其对连续文本的序列特征具有敏感性，增加了文本检测的精确度。环境搭建源码下载，python包环境就不多说，看requirements.txt就行只提一下遇到的几个问题1.import问题报错N...
2019-04-10 10:23:12
2357
9
原创 二进制补码是如何把减法转变为加法的
用一个例子来解释补码的原理：假设现在标准时间为4点整，而有一只表已经到7点了，为了校准时间，可以采用两种方法：一种是将时针退7-4=3格；二是将时针向前拨12-3=9格，这两种方法都可以校准到4点。摘自《计算机组成原理》p20 第2节这个例子的意思可以理解为将7变为4，在钟表环境（12进制）下可以表示为7-3和7+9意即钟表法则中7-3=7+9 （称为同余式）看了这个例子，...
2018-12-17 11:45:35
10251
机器学习实战教程（代码）
2020-07-15
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人