- 博客(430)
- 收藏
- 关注
RSS订阅原创 LeetCode LCP 25. 古董键盘（dp + 组合数）
【题目】古董键盘【思路】令表示前 个小写字母组合成字符串的前 个长度的可能情况数目。易得临界值为前 个小写字母组合长度为0的情况只有一种就是不选，假设第个字母的个数为个，那么可以得到前个字母组成个长度的字符串的可能情况数目：题目给定最多被按 次，因此我们得到状态转移方程：表示组合数从a个里面选b个，临界值为递推式为，比较好理解，因为如果可选择的范围增加一个数，这个数可以被选或者不被选。【代码】class So...
2020-09-25 19:32:04
394
原创 LeetCode LCP 24. 数字游戏 （优先队列维护中位数）
【题目】数字游戏【思路】首先，我们知道，对于一个长度为n的数字序列nums，的最小代价，只会出现在这个数字序列的中位数（n为奇数）或者两个中位数（n为偶数）之间的位置。那么，我们就可以通过先把nums的每一项分别减去0,1,2,3...，转化成求的最小值问题。那么代价就是中位数右边的数字之和-中位数左边数字之和（即下面代码的sum2-sum1+中位数） 或者 右边中位数往右的数字和（包括中位数）-左边中位数往左的数字和（包括中位数）。【代码】class Solution...
2020-09-25 15:09:01
517
原创 C++ STL 中的 sort() 函数底层实现原理
数据量大时采用快速排序 Quick Sort，分段递归排序。一旦分段后的数据量小于某个阈值，为避免Quick Sort的递归调用带来过大的额外开销，就改用插入排序 Insertion Sort。如果递归层次过深，还会改用堆排序 Heap Sort。八大排序：冒泡排序、插入排序、希尔排序、选择排序、堆排序、归并排序、快速排序、基数排序...
2020-08-07 12:05:53
3584
原创 剑指Offer 从尾到头打印链表（三种方法）
从尾到头打印链表题目：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。思路：1.顺序加入列表，反转列表2.反转链表再加入链表3.递归代码：// 1.反转列表/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) :* val(x), next(NULL) {* }* }
2020-08-07 11:51:07
204
原创 剑指Offer 二维数组中的查找 + 替换空格
题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。思路：有序查找，很容易想到二分，那么复杂度就是O(nlogm)或者O(mlogn)，但是这样没有完全利用这个二维数组的性质。从左上角开始走，往右或者往下都是升序的，不好进行比较；如果从右上角开始走，往左是降序，往下是升序，我们可以利用这一点。做法：从右上角出发，如果当前位置的值＜target，说明
2020-08-07 11:02:11
225
原创 进程与线程的联系与区别
通常在一个进程中可以包含若干个线程，它们可以利用进程所拥有的资源。在引入线程的操作系统中，通常都是把进程作为分配资源的基本单位，而把线程作为独立运行和独立调度的基本单位。由于线程比进程更小，基本上不拥有系统资源，所以对它的调度要付出的开销就会小得多，能更高效的提高系统内多个程序间并发执行的程度。线程和进程的区别在于，子进程和父进程有不同的代码和数据空间，而多个线程则共享数据空间，每个线程有自己的执行堆栈和程序计数器为其执行上下文。进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动，进程是系
2020-08-07 09:50:43
297
原创 LeetCode 5. 最长回文子串（中心扩散法 or 动态规划 or 马拉车算法）
题目：给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。思路：1.中心扩散法：枚举每一个位置（两个位置）作为中心点的情况，向两边扩散，不断更新最大长度的答案。时间复杂度O(n^2)，空间复杂度O(1)。2.动态规划：定义状态dp[i][j]为区间[i,j]的s的子串是否为回文。假如dp[i][j]是回文，且s[i-1]==s[j+1]，那么dp[i-1][j+1]也是回文。在这个过程中不断更新最大长度的答案，最后输出这个最长的回文子串即可。时...
2020-07-22 16:00:37
414
原创 网易2020校招笔试- 运维工程师（正式批）编程题 吃葡萄
思路：一看数据这么大有1e18肯定是思维题，再一看答案具有单调性直接二分答案。二分的check函数这么写：如果最多的葡萄都可以被吃完，那么最少和次少一人负责一款直接解决就好了；如果两个人都吃不完最多的葡萄，那么这个肯定有得剩吃不完；否则轮流按优先吃最多、然后次少、判断剩下的能不能被最后一个人吃完。二分时间复杂度是logn级别的，因此这种写法的时间复杂度最多是log(1e18)也就是64，相当于常数级别看作O(1)。另一种解法：思维当 a,b,c都差不多大 或者 其中两个比较大的时候，我们..
2020-07-15 22:59:08
682
原创 计算机网络第七版谢希仁 - 第三章数据链路层 - 学习笔记
数据链路层使用的信道主要有以下两种类型：点对点信道。这种信道使用一对一的点对点通信方式。 广播信道。这种信道使用一对多的广播通信方式，过程比较复杂。本章最重要的内容数据链路层的点对点信道和广播信道的特点，以及这两种信道所使用的协议（PPP协议以及CSMA/CD协议）的特点。 数据链路层的三个基本问题：封装成帧、透明传输和差错检测。 以太网MAC层的硬件地址。 适配器、转发...
2020-05-08 15:11:50
1308
原创 计算机网络第七版谢希仁 - 第二章物理层 - 学习笔记
本章最重要的内容物理层的任务 几种常用的信道复用技术 几种常用的宽带接入技术主要是ADSL和FTTx2.1 物理层的基本概念物理层考虑的是怎样才能在连接各种计算机的传输媒体上传输数据比特流，而不是指具体的传输媒体。可以将物理层的主要任务描述为确定与传输媒体的接口有关的一些特性，即：机械特性：指明接口所用接线器的形状和尺寸、引脚数目和排列、固定和锁定装置等。平时...
2020-04-14 20:16:12
906
2
原创 计算机网络第七版谢希仁 - 第一章概述 - 学习笔记
目录本章重点内容（1）互联网边缘部分和核心部分的作用，其中包含分组交换的概念。（2）计算机网络的性能指标。（3）计算机网络分层次的体系结构，包含协议和服务的概念。建议：抽象的概念一下子难以掌握，但是对后面的内容有着指导作用，因此最好时常回顾本章中的基本概念，有利于掌握好整个计算机网络的概念。1.1 计算机网络在信息时代中的作用首先我们来讨论一下计算机网络在信...
2020-04-10 22:32:59
938
原创 操作系统 第一章引论 学习笔记
目录1.1 计算机系统组成1.2 操作系统的作用和定义1.3 操作系统的发展过程1.4 操作系统的分类1.5 操作系统的功能和特性1.6 操作系统的结构模型1.1 计算机系统组成计算机系统包括硬件系统和软件系统两部分，操作系统是配置在计算机硬件上的第一层软件，可以扩充硬件功能，提供软件运行环境，实现了应用软件和硬件设备的连接。硬件系统是指计算机的物理设备本身，如...
2020-04-09 20:52:41
259
原创 前端「HTML+CSS」零基础入门学习笔记（完整）
课程前导一般来说，所有与视觉和交互有关的工作都由前端工程师来完成，后端工程师主要负责研究如何更好地把数据传给前端。首先要掌握前端三大基础语言：HTML CSS JavaScript ，其次要学习：jQuery 网络 CSS3 H5 es6 webpack4.0 git 小程序 设计模式 VUE VUEX VUE源码 React Node.js Mongo DB数据库等等。H...
2020-02-16 23:26:14
6840
2
原创 2020牛客寒假算法基础集训营1 题解
目录【A-honoka和格点三角形】【B-kotori和bangdream】【C-umi和弓道】【D-hanayo和米饭】【E-rin和快速迭代】【F-maki和tree】【G-eli和字符串】【H-nozomi和字符串】【I-nico和niconiconi】【J-u's的影响力】【A-honoka和格点三角形】呕，花我时间最多的一道题，因为一...
2020-02-04 18:00:19
522
原创 2020 CCPC Wannafly Winter Camp 1 重现赛 H 最大公约数（思维）
【题目】【题解】对于给定的范围[1,n]内的k，要求我们判断是否正确，并输出最小的判断数字。首先我们根据样例来递推一下思路是否正确：Input ：10 1 Output：210假如k是正确的，那么gcd(k,k)=k；所以假如不正确，我们只需要考虑i在[1,n]范围内gcd(i,k)==k的数字。对于1来说，有2,3,4,5,6,7,8,9,10这几个数字gc...
2020-02-03 15:17:51
323
原创 AtCoder Contest 153 E - Crested Ibis vs Monster（完全背包）
【题目】E - Crested Ibis vs Monster【题解】将题目转化成选取一些物体，使得价值总和不小于h的所选物体的最小体积和这样一个完全背包问题，每个物体可以选择多次。临界值为什么可以是2e4呢？因为我们考虑最坏的情况，就是当h=1e4时，选择很划算的价值x为999的物品*2。临界值为什么不可以是h+h呢？因为考虑h很小而性价比最高的物体价值很大的情况，比...
2020-01-27 00:06:46
579
原创 求两直线的交点（C++）
假设两直线的式子分别为：求解过程:综上所述，交点的解为：则有解，否则两直线平行。补充：如果化成Y=kX+b的形式的话，得解为：例题：Audio给定三个不共线的点，要求输出一个点使得这个点到三个点的距离相同，输出保留三位小数。#include<bits/stdc++.h>using namespac...
2020-01-19 10:09:25
6023
原创 2019前端「HTML+CSS」零基础入门之 CSS学习笔记
目录2019前端「HTML+CSS」零基础入门 2019前端「HTML+CSS」零基础入门之 HTML学习笔记课时4css初级篇-css引入css基础选择器选择器权重课时5css复杂选择器，权重计算问题，css基础属性课时6css企业开发经验、习惯，盒子模型，层模型课后练习2019前端「HTML+CSS」零基础入门浏览器 = ...
2020-01-15 19:07:48
542
6
原创 2019前端「HTML+CSS」零基础入门之 HTML学习笔记
目录2019前端「HTML+CSS」零基础入门课时1 课程向导课时2 html 初级篇 - 基础标签课时3 html 进阶篇 - 高级标签2019前端「HTML+CSS」零基础入门之 CSS学习笔记2019前端「HTML+CSS」零基础入门课时1 课程向导前端三大基础语言：HTML CSS JavaScript其次要学习：jQuery 网络 CSS3 H5 ...
2019-12-30 17:28:15
779
原创 ZUST 2019111 悲伤数字（思维+二叉树）
【题意】用4,9按大小构造数字序列a[]为[4,9,44,49,94,99....]，定义499为1Z，输入k(1<=k<=1e8)，输出第kZ个数字。比如k=1，输出为第499个数字，99994944。【题解】因为只有4,9两个数字，我们很容易联想到0,1，从而想到二叉树。我们这样构造二叉树，结点X的左儿子的编号为0X，右儿子的编号为1X，以此类推，我们可以得到整棵树...
2019-12-18 20:23:13
657
原创 1151 LCA in a Binary Tree (30分)（中序求LCA）
【题意】给定一棵树的中序和前序，给出q个询问，每个询问两个点u,v，询问u,v的最近公共祖先。【题解】不需要建整颗树，在左根右这样的中序时，如果两个结点分别在根的左右(可包含根)，那么根即是LCA；如果两个结点同时在根的左边，那么我们继续遍历左子树；否则继续遍历右子树。【代码】#include <bits/stdc++.h>using namespace std...
2019-12-07 12:40:45
369
原创 PAT 甲级 1098 Insertion or Heap Sort (25 分)
【题意】给定一个序列的初始状态和经过某种排序几个步骤之后的结果，要求判断是插入排序还是堆排序，并输出执行下一个步骤之后的结果。【题解】不清楚插入排序和堆排序的请移步：八大排序首先，我们根据排序过程中得到的序列判断是哪种排序。怎么判断呢？如果能把序列分成两段，前一段是有序的，后一段是跟原序列相同的，这样就是插入排序；否则是堆排序。如果是插入排序，那么我们只需要将下一个元素加入到前一段...
2019-11-26 19:43:58
149
原创 甲级PAT 1026 Table Tennis (30 分)（模拟+三大坑点总结）
【题意】有一家乒乓球的店，营业时间为8:00-21:00。现在已知一天要接待的客户对数，每对客户的抵达时间、使用桌子时间和是否为VIP，然后是K张桌子，M张VIP桌和M张VIP桌的编号。要求按接待时间输出每对被服务的客户的抵达时间、开始服务时间和等待时间，然后输出每张桌子接待的客户的对数。【题解】需要注意的是：①所有的客户的抵达时间在8:00-21:00没错，但是只有当开始服务时间...
2019-11-25 21:06:20
760
原创 甲级PAT 1010 Radix (25 分)（考虑溢出）
【题意】给定两个数N1，N2（均不超过10位），和一个tag（1或2）和radix（表示几进制），要求判断当数是一个radix进制数时，是否存在一种进制使得另一个数等于这个数成立。【题解】一开始我们很容易会以为进制数只可能在【2，36】，所以可能会枚举或者二分，但是只会有部分正确，为什么呢？因为更大的进制数也有可能。虽然无法被全部表达，但是根据我们的N1或者N2和一个确定的更大的进...
2019-11-25 15:15:28
197
原创 甲级PAT 1069 The Black Hole of Numbers (20 分)（模拟）
【题意】给定一个n(0,1e4)，要求输出n的位数进行排列的 最大值-最小值=结果 ，直到出现黑洞数6174，或者一开始结果就为0.【题解】一直过不去的测试点的原因在于，我用while循环将数字转化成长度为4的整型数组时，有可能只覆盖到了前面几位(<4)，而后面几位本应该是0但是未被覆盖，于是答案错误。解决这个问题可以用for循环转化，也可以每次清空再while转化。【代...
2019-11-20 19:08:12
501
原创 甲级PAT 1016 Phone Bills (25 分)（模拟，注意输出格式）
【题意】给定一天24个时段每分钟的话费和一个指定月份的多个人的所有通话记录，要求算出每个人的月话费账单并按样例格式输出。【题解】呕，我吐啦，居然wa在最后的输出格式上，小数点后要不足两位补0啊啊啊，真·写题三分钟debug一小时思路：题目要求只有最近配对的on-off才能算是一次有效通话，且要求严格按姓名升序进行输出，所以我们在处理数据时按姓名为第一关键字时间为第二关键字升序排序即...
2019-11-13 19:45:44
171
原创 甲级PAT 1014 Waiting in Line (30 分)（模拟）
【题解】甲级凡是有问题，大多出在读题。题意：有n个窗口，每个窗口黄线内可以排长度为m个人的队，总共有k个客户，每个客户有一个解决时间ti，q个询问，每次询问编号为x的客户在几点办完事情。思路：我们看到，一天的工作时间是从8:00-17:00，共9个小时9*60=540分钟，数据比较小所以我们选择按时间枚举没有疑问。根据题目中的举例，我们可以看到，当黄线内没有满的时间，客户会优先选择队伍...
2019-11-12 15:39:12
182
原创 Codeforces Round #595 (Div. 3) C2. Good Numbers (hard version)（三进制）
【题解】题意：q次询问(500)，每次询问第一个>=n(n<=1e18)的由 3的不同幂次求和得到的值。思路：题意要求不同幂次，所以我们可以联系到三进制，每一位上是0或者1就是满足，否则考虑把最高位的2变成0并向高位进1，而低位全部变成0，这样的是最优的。3^38>=1e18，所以我们只要考虑38位就好了。为什么这样是最优的呢？因为我们很容易知道，10000是由022...
2019-11-06 14:38:50
206
原创 zcmu 1540: 第k大数（思维+二分）
【题解】n*m有1e10显然我们不可能直接对生成的序列做什么操作，所以我们考虑通过原始序列作出某种判断得出答案。询问的n*m个元素从大到小排序，这样的一个数组显然是具有单调性的，所以很容易想到用二分。但是想到怎么二分并且优化时间复杂度就不是特别容易了，要一点思维。我们知道，这个数组的最大值一定是a[0]*b[0]，最小值一定是a[n-1]*b[m-1]，所以我们可以先对两个数组进行...
2019-10-29 18:43:51
340
原创 Codeforces Round #594 (Div. 2) D1. The World Is Just a Programming Task (括号匹配)
【题解】恐怕这道题最大的难点在于....读题题意：给定一个长度为n的(n<=500)括号序列，给一个交换两个位置上元素的机会(不一定要不同)，询问平移不同长度(从后往前平移)使得整个序列成为一个完美序列(每个'('有一个对应的')')的最多可能长度数目。比如S：)(())()()(()1.(())(())()() 2.()(())(())() 3.()()(())(()...
2019-10-22 20:46:58
160
原创 2019牛客国庆集训派对day6 I：Substring Query（Bitset的妙用）
【题意】给定一个字符串s(1e5)，q(1e5)次操作，操作1给定位置i和字母c，把第i个元素替换为c；操作二先给一个0再给一个字符串t，查询字符串t在s中的出现次数。【题解】显然常规做法行不通，考虑STL中的Bitset 。bitset简介bitset存储二进制数位，从右往左依次为2^0,2^1,2^2,...for(int i=0;i<n;i++) B[s[i]...
2019-10-06 20:05:14
194
原创 2019牛客国庆集训派对day4 H：Highway（树形dp求树上最长路径）
【题意】给定一棵树，两个结点之间的距离为树上路径的长度，要求构造一棵树上所有边的权值和最大的树并输出权值。【题解】我们可以把这个问题转化成，求每个结点的树上最长路径再加入到新构造的树中，注意n个长度求和后要删去最长边，因为最长的路径被重复计数了而我们只需要n-1条边。那么树上最长路径怎么求呢？可以看出，离第i个结点最远的距离，是边（v,i）的长度（其中v是i 的父亲）加上第v个...
2019-10-05 11:37:50
252
原创 Codeforces Round #589 (Div. 2) C.Primes and Multiplication（质因数分解）
【题解】题意：定义为x的所有质因数的集合；定义为找到一个最大的整数使得n能被整除，；定义为，；给定x,n，要你输出。题解：x有1e9，n有1e18，我们首先考虑到1e9范围内的数字最多有不超过10个素因数，所以先跑出x的素因数集合。然后我们考虑到对于每个p，只有当p能整除n时才对答案是有影响的，他可能是，否则一定为1。具体怎么影响呢？我们举...
2019-09-30 08:12:37
373
原创 loj #162. 快速幂 2 （数论）
【题解】令，则 。【代码】#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll mod=998244352;const int S=31596;ll a[32000],b[32000];int main(){ ll x; int n; scanf("%...
2019-09-29 18:07:58
432
3
原创 2019CCPC秦皇岛赛区 F：Forest Program（并查集+LCA）
【题解】题意：输出删除不同边使得所有连通图上无环的所有可能情况并取模，每条边最多只存在于一个环中。思路：令环的个数为N，每个环内的边数为ai，总边数为m，则答案为 ，即累乘2^(每个环内的边数)-1再乘上2^(无影响的边的数目)。这个答案很好得到，但是我们要怎么实现计算出每个环内的边数呢？我们考虑到每条边最多只存在于一个环中，所以只要我们把一个环中的任意一条边删除并且记录下来，...
2019-09-28 19:59:48
358
原创 codeforces 1231C. Increasing Matrix（贪心）
【题解】题意：给定一个n*m的矩阵，0表示可更改为任意值，要求最后的矩形满足对于每一行从左到右，每一列从上到下的元素都是严格上升的，最后输出最大矩阵和。思路：由题面可知0不会出现在边界的行列，那么显然我们可以知道最大临界值，所以只要每次根据最大临界值(横、竖)选择可选最大值，非0情况判断是否符合要求即可构造出最优结果。有点类似动态规划的思想，找到临界状态，就可以根据要求写出转移方程进行转移...
2019-09-25 19:43:11
416
原创 Python学习笔记
【基本语法】首先，是一段求阶乘的代码。n=int(input()) //输入ans=1i=1//第一种，while循环while i<=n: //循环 ans*=i i+=1//第二种，for循环for i in range(1,n+1): ans*=iprint(ans) //输出1.输入输出input() //输入，prin...
2019-09-25 15:57:36
857
原创 hdu 1099 Lottery（数学期望）
【题解】想不到把我wa的死死的是输出格式..当然题目也不太好读题意：有无数张编号为1-n的彩票，问平均买多少张彩票才能拿到一副完整的1-n的彩票。思路：首先，以n=3为例，无论我们买到哪一张(1,2或者3)，都是我们所需要的，所以买到一张所需要的编号的彩票概率是1即3/3；接着我们买到第二张所需要的彩票(编号为剩下的两个中的任意一个即可)的概率是2/3；买到最后一张所需要的编号的彩票的...
2019-09-25 14:37:03
251
原创 牛客练习赛52 B：Galahad（树状数组维护区间不同元素和(个数)）
【题目】查询区间和，如果区间元素重复出现则计数一次。【题解】按区间的右端点建立树状数组，维护区间[1,R]的每个元素的最右位置。按查询区间的右端点排序，依次处理，每次更新当前值的最右位置即可。若要查询区间不同元素个数，把 for(;it<=q[i].R;it++){ if(vis[a[it]]) //这个数之前出现过 ...
2019-09-14 22:36:33
278
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人