- 博客(116)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 基础排序大赏
排序算法乃最基础算法，作为CSers的必备算法，往往也是面试官比较青睐的考点。常见有序表排序算法主要有以下几种编号 排序类型 排序名称 平均时间复杂度 最坏时间复杂度 最优时间复杂度 空间复杂度 稳定性 1 比较类排序 交换排序 冒泡排序 稳定 2 快速排序 不稳定 3 插入排序 简单插入排序
2020-12-01 18:53:24
170
原创 链表交点问题
链表交点问题也属公司青睐的专题之一，一般依靠双指针来解决，主要分为链表判环和链表相交两大专题。142.Linked List Cycle II题意：判断链表是否有环，若有环，则返回环入口节点。思路：这题就是典型的快慢指针问题，代码很简单，但具体理论证明却十分值得研究。首先先说解法， 分两部分，判环和寻找入口：判环部分，设置两个指针（快指针fa一次走两个节点，慢指针sl一次走一个节点），若快指针走到了链表尾即空节点则说明链表无环，否则在环中快慢指针必能相遇。寻找入口部分，慢指.
2020-10-09 12:34:50
399
原创 最大子区域问题
最大子区域问题也是笔试面试非常常见的问题，典型的就是数组的最大子串和矩阵的最大子矩阵，一般伴随着求和求积这类操作。下面我们就来研究一下。53.Maximum Subarray题意：最大子区域问题的最经典类型就是数组的最大子区间和问题思路：dp枚举每个位置，动态维护以当前元素为结尾的最大子区间和总最大子区间，转移只需要与前项比较即可代码：/*Author Owen_Q*/class Solution {public: int maxSubArray(vec.
2020-10-08 17:51:30
575
原创 单调栈专题练--下一个更大元素
单调栈，主要用于记录数组中每个元素的下一个更大值。为了在O（n）时间复杂度内完成这个目标，需要从后往前维护一个单调递增栈，栈中依次存储当前下一个位置到数组尾的下一个更大值。因此，对于每个位置的更新，只需要从栈中将小值出栈，直到寻找到比当前值大的值即可。话不多说直接看题1019. Next Greater Node In Linked List题意：给定一个链表， 对于每个节点，记录链表中下一个比当前节点大的节点值，最终结果用数组返回。思路：寻找下一个更大节点问题，典型的单调栈问题
2020-10-08 15:17:52
228
原创 最大01子矩阵问题（单调栈优化）
题目描述：顾名思义，给定n*m大小的01矩阵，要求找到1数量最多的全1子矩阵问题降阶：思考二维问题前，先将问题降阶，思考该问题在一维状况下的解决方式会是一个比较好的思路。题目链接：485.Max Consecutive Ones题意：在01数组中寻找最长连续1的长度思路：简单的dp，维护数组中每个位置作为结尾的最长连续1长度。代码：/*Author Owen_Q*/class Solution {public: int findMaxCons.
2020-10-08 15:15:22
1124
1
原创 递归法求解面试三大经典链表问题
最近参加了一堆笔试面试模拟试，发现链表题是很多公司面试官所喜欢亲爱的一类题目，手撕链表的题目随处可见。毕竟，链表作为数据结构的基础，十分重要。而链表又恰恰是写代码中很容易出bug的一种数据结构，断链，空指针等各种问题经常让人猝不及防。这里，我总结了常见的三种最常见的链表题：链表翻转，链表合并，以及基于二叉链表的二叉树翻转。偶然间发现，递归法简直是处理这类问题的一大利器。利用递归法，可以完美避开链表的各大坑点，那么就让我们来试试吧。二叉树翻转题意：轴对称翻转一个二叉树思路：这道题简直就
2020-08-19 02:36:35
729
原创 Bestcoder-889-1004-Civilization(HDU6746)
题目链接题目链接（可提交）题意：经营模拟类游戏，n*n地图（5e2*5e2），每个地点有一定生产力a[i][j]，初始位置在（x，y）建城市，初始居民1人第一阶段：移动城市，每天可以将城市移动到曼哈顿距离不超过2的地方。第二阶段：生产，在确保城市有人的前提下，多余的市民可以去离城市曼哈顿距离不超过3的地方生产第二阶段每天结算一次首先结算粮食，所有有居民的地点均可获得粮食a[i][j]，粮食汇总到城市再结算人口，若当前城市总粮食数达到8倍人口数平方(food>=8*p*p
2020-08-12 05:34:13
108
原创 Bestcoder-892-1002-Binary Addition(HDU6839)
题目链接题目链接（可提交）题意：两个长为n（1e5）的二进制串a、b，小地址为低位，现在提供两种操作（任意更改一位，或整串二进制加以），问最少多少步可以使a串变为b串思路：策略题首先需要分析两种不同策略的优劣以及应用场景对于操作一，显然是基本操作，按位变换，最暴力的做法而相比较而言，操作二就是用来优化的，在某些特殊场景下，操作二可以对串造成较大的变化。显然，若从最低位开始有连续多个1时，一次操作二可以将这一系列多个连续的1全都变成0，从而达到一步操作更改多位的效果。而又由
2020-08-12 03:16:34
164
原创 Bestcoder-892-1001-Battle for Wosneth(HDU6838)
题目链接题目链接（可提交）题意：回合制游戏，Alice和Bob两人轮流攻击。Alice先手，每次成功的攻击自己获得1分，并给Bob造成一点血量损失，攻击命中率为p%；Bob血量为m（1e9），当血量减为0时，游戏结束，每次成功的攻击扣去Alice积分1分，攻击命中率为q%。求游戏结束时Alice积分的期望，结果对998244353取模。思路：期望游戏完全可以利用等效思维去考虑，那么游戏即可等效为：Alice攻击力为p%，Bob攻击力为q%不难发现，Alice自己所增加的积分一定为Bo
2020-08-11 23:24:52
153
原创 LeetCode-143-Reorder List
题目链接题意：重构一个单链表，O（1）空间复杂度条件下将链表L1~L2~L3~……~Ln-1~Ln重构为L1~Ln~L2~Ln-1~L3……思路：看似是一个双指针的题，一头一尾两个指针向中间合并。然而题目中的单链表这一数据结构使得尾指针无法向前移动，题目难度瞬间增大。于是，只能利用链表操作来完成。思路也比较清晰，关键就是链表操作细节点很多。化整为零，可以通过三个小操作来实现这个任务：1.将单链表一分为二2.将后半部分链表翻转3.再将两段链表合并下面详细来说明这三部分1
2020-08-09 07:56:41
157
原创 剑指 Offer（力扣版）-59-II-队列的最大值
题目链接题意：定义一个新队列数据结构，可以快速O(1)查找队中最大值思路：在队列中添加一个链表，用于维护当前队列最大值，该链表指向该最大值出队后剩余列表的最大值对于该新队列的三个基本操作：入队：...
2020-08-09 07:56:36
215
原创 LeetCode-54-Spiral Matrix
题目链接题意：回形输出一个矩阵思路：将上下左右四条边作为四个不同的操作单独处理，并动态记录边界代码：/*Author Owen_Q*/class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { int M = matrix.size(); vector<int> re;
2020-08-08 01:01:55
134
原创 Bestcoder-889-1003-Dec(HDU6745)
题目链接题意：给定a（1e3），b（1e3）两个正整数，每回合选取一个大于1的数减1，直至两个数均变为1求过程中两个数互质的最少回合数，多组数据（1e6）思路：这题看似是个策略题，1e6的数据量把策略的复杂度限制到常数级别，极其困难于是想到改在线查询为离线查询，预处理好所有可能的结果并存储备用，研究一下复杂度为1e6，可行于是选择dp，从最终终止条件a=b=1开始逆向转移，每种状态均可由a或b减1转移来，若互质即结果加1代码：/*Author Owen_Q*/.
2020-07-22 05:37:37
167
原创 Bestcoder-889-1002-GPA(HDU6744)
题目链接题意：四门课考试，每课最高100分，最低0分，给定特定gpa换算算法已知最终百分制总分，求最高gpa绩点，多组数据（4e2）思路：最暴力的做法当然是暴力枚举四门课的所有可能百分制分数分配方案，貌似复杂度完全ok这里稍稍改进一下，选取3+1枚举方式，暴力枚举前三科，利用最后一课进行查询当然最优方案应为2+2枚举方式，思路与3+1枚举相同，这里以3+1枚举为例代码：/*Author Owen_Q*/#include <bits/stdc++.h>
2020-07-22 05:19:15
169
原创 Bestcoder-889-1001-Drink(HDOJ6743)
题目链接题意：有n（1e2）种不同无限数量饮料，每种饮料提供x[i]（1e2）水分，补充y[i]（1e2）卡路里。现在只选择一种饮料，整瓶整瓶喝，需要补充m（1e5）水分，并使得摄入卡路里最少。问卡路里的最低摄入值思路：这一题读题很关键。一定要注意是只选一种饮料一直喝！看清这个，一切就都很简单了，枚举每一种饮料，计算当补充满水分时所摄入的卡路里量，最后输出最小值即可。代码：/*Author Owen_Q*/#include <bits/stdc++.h&g
2020-07-22 05:07:17
152
原创 Codeforces Round #630 (Div. 2)
疫情当下，刷题或许能成为一种不错的缓解无聊的方式A. Exercising Walk题意：矩形区域内，给定一定数量上下左右四种行走操作数量，问是否能在规定区域能完成而不超届。思路：上下，左右每对对立的操作只需要考虑之间的差，然后判断是否超界即可。因为，每对操作可以相互抵消。最后考虑一种特殊情况，就是对立操作刚好数量相同，检测一下两边是否有至少一个空间来执行操作即可。代码...
2020-04-01 23:05:42
189
原创 Virtualbox Ubuntu 输入法
输入法的重要性当然不言而喻了，可不希望每次想输入中文的时候都依靠在线输入法。于是这个来安装一下搜狗输入法1.安装一下中文语言包在设置中找到语言选项选择简体中文，安装2.安装fcitx输入框架sudo apt-get install fcitx3.下载输入法进入搜狗官网下载输入法4.修改框架再返回刚刚安装语言包的界面，修改输入框架为fcitx...
2020-02-03 04:17:10
2480
2
原创 Virtualbox Ubuntu增强功能
增强功能可谓是virtualbox的一大特色全屏显示首先，对于过小的屏幕，无疑是使用时特别难受的一点。而安装增强功能即可解决屏幕过小的问题简单的一步小小的操作即可时间，按步骤安装即可共享文件夹当然，如何实现windows和虚拟机linux之间的文件传输，也是一个很重要的问题。而共享文件夹，使得windows和linux中都可以访问到这个文件夹，即可完美解决这个问题...
2020-02-03 03:33:06
1294
原创 LeetCodeGOGOGO刷题记07——备战Amazon（Online_Assessment前的终章）
1122.Relative Sort Array难度：Easy思路：给定一个array和一个set，保证set中的元素均在array中出现了，要求将array按照set中的顺序排序，对于未在set中出现的元素从小到大排在array末尾复杂排序，考虑到直接建立一个新数据结构专门进行排序，num表示该数数值，value表示该数在set中出现的位置，对于未在set中出现的元素，其v...
2020-01-21 23:43:46
450
原创 LeetCodeGOGOGO刷题记06——夯实基础（预处理）
994.Rotting Oranges难度：Easy思路：图论题，一个图中若干好橘子和若干坏橘子，每回合坏橘子周围的好橘子会坏掉，问第几回合后没有坏橘子。比较流行的思路就是bfs，以坏橘子作为起点，一层层搜，搜完即可得到回合数确实这种思维很好想，但比起bfs，普通按回合grow&check要好写多了简简单单才是真，踏踏实实按回合走，思路清晰好写，而且代码效率极...
2020-01-21 20:58:38
236
原创 LeetCodeGOGOGO刷题记05——备战Amazon（打表，dp，刷刷刷）
1.Two Sum难度：Easy思路：刷到了leetcode的第一道题，求两数和等于特定值的pair，考虑到题号和难度，直接双循环暴力，解决什么？哈希优化？还有啥啥啥优化？这种题还优化个啥？赶紧看下一题去，别在水题上浪费时间！代码：/*Author Owen_Q*/class Solution {public: vector<int> ...
2020-01-21 20:32:20
223
原创 LeetCodeGOGOGO刷题记04——代码优化（预处理）
第一次完整的在线模拟，总体感觉就是思路清晰很重要，做完题目回头来看难度并不大，但如果能利用预处理，使得整体思路更加清晰，就可以使得编码更加轻松高效836.Rectangle Overlap难度：Easy思路：给两个矩形，判断两个矩形是否重叠。显然是分类讨论。看似很复杂，会有很多不同情况的样子，然而仔细想清楚，情况也很简单。首先，确定下左侧的矩阵。右侧的矩阵若不重叠，只...
2020-01-19 23:41:36
193
原创 LeetCodeGOGOGO刷题记03——代码优化（利用字符串流和c++11新功能来处理字符串）
819.Most Common Word难度：Medium思路：字符串处理问题，预先排除一部分单词，组成单词库（banned），要求找出一篇文章中出现最多的非banned单词（大小写不敏感）。这题思路也十分清晰，首先处理文章，将其处理成一个一个单词，并全部转化为小写，然后依次插入unordered_map中，最后遍历map得到结果其实这题的难度不大，然而常规代码并不简单，...
2020-01-19 01:11:30
146
原创 LeetCodeGOGOGO刷题记02——体验Hard题型（BFS模拟）
在上次的刷题记中分别体验了easy和medium难度，感觉easy属于纯水题，medium属于技巧性。那么，这次当然要来体验一下hard难度675.Cut Off Trees for Golf Event难度：Hard思路：图论题，其实题意也十分清晰，在一个种满树的的矩阵中，按照树的高度从小到大依次砍树，求最短距离。图论最短距离的搜索当然要数bfs了，对于搜索顺序，对树预...
2020-01-18 23:30:06
159
原创 LeetCodeGOGOGO刷题记01——链表优化（哈希法实现按键值访问链表）
deadline是第一生产力，刚刚收到笔试通知的我到现在居然一道题还没来得及刷，赶紧开始LeetCode刷题记从回忆版的题入手，据说是今年amazon电面的题，have a try206.Reverse Linked List难度：Easy思路：就是个简单链表反转的水题，注意输入可能是空链表这种特殊情况代码：/*Author Owen_Q*//** ...
2020-01-16 00:43:42
220
原创 Virtualbox Ubuntu基础配置
1.安装Virtualbox要在windows系统上运行ubuntu，首先你得先有个虚拟机。比较热门的虚拟机就属VMware和virtualbox了，这里以virtualbox为例virtualbox可以直接去官网下载，然后根据步骤一步步安装就好啦2.下载ubuntu镜像接下来，需要有个镜像文件来运行ubuntu，同样是直接去官网下载最新版ubuntu桌面版，目前最新永久版本为...
2020-01-13 04:52:41
421
原创 2015 United Kingdom and Ireland Programming Contest (UKIEPC 2015)
2015年的icpc英国站，不到一百只过题队伍，可以算是icpc在英国刚起步的时候。Problem B Mountain Biking思路：作为本场的签到题，读懂题意之后，这题倒是更像一道数学题。给定n个坡面的角度，求解到达坡道底端的速度利用经典力学动力学公式即可直接求出./*Author Owen_Q*/#include <bits/stdc++.h>...
2019-10-10 08:01:34
2835
原创 Codeforces Round #591 (Div. 2, based on Technocup 2020 Elimination Round 1)
打cf的过程中遭受到了DDOS攻击，导致最终无法进行下去，也算是奇闻一件了A. CME思路：看似像个火柴游戏，实则只是个判断奇偶的水题/*Author Owen_Q*/#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e7+5;i...
2019-10-07 05:34:45
325
原创 AtCoder Grand Contest 039
再战atcoder，误入grand局，赛后才意识到。偶然间发现，一年多前自己也是通过grand局狂涨800+分，甚是巧合A - Connection and Disconnection思路：这题就是一个简单的字符串计算问题，子串复制多次后变换最少元素消除连续相同元素。对于连续元素，其实只需要向下取整相间消除即可完成，最后单独统计一下首尾，处理掉复制连接处，再考虑一下所有元素均相同的情况即可...
2019-10-06 00:35:10
372
原创 Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)
疲敝，这是一个月前的场A. XORinacci思路：异或运算的斐波那契数列，由于异或运算的循环性，这个数列其实只是一个以三为循环节的循环数列#include <bits/stdc++.h>using namespace std;int main(){ int T; scanf("%d",&T); while(T--) {...
2019-09-29 18:31:38
169
原创 Codeforces Round #582 (Div. 3)
完成essay后最大的感觉就是轻松，放假一般的酸爽，考试什么的都不管了，来一场cf试试手A. Chips Moving思路：聚拢筷子问题，所有筷子可以随意移动偶数步，但奇数步移动需要代价，于是将所有筷子移成两列，最后处理少的那列即可得到最小代价#include <bits/stdc++.h>using namespace std;int main(){ ...
2019-09-21 23:27:15
158
原创 AtCoder Beginner Contest 139
再战AtcoderA - Tenki思路：天气预报，判断正确个数，直接暴力#include <bits/stdc++.h>using namespace std;char a[5],b[5];int main(){ scanf("%s%s",a,b); //cout << a << "*" << b <...
2019-09-21 21:37:00
224
原创 Codeforces Round #587 (Div. 3)
最近临近开学，事情有点多，忙里偷闲来打打A. Prefixes思路：题意写着确保所有前缀ab均等，看起来挺高级的样子，说白了就是要求ab相见，模拟一下即可#include <iostream>using namespace std;int main(){ int n; string s; ios::sync_with_stdio(fals...
2019-09-21 20:57:55
139
原创 Japanese Student Championship 2019 Qualification
转战Atcoder，这场比赛的名字看起来就很有趣的样子，很盛大的感觉，那当然赶紧来玩玩A - Takahashi Calendar思路：定义新日历算法，求特定日子数典型的签到题，当然是直接在新日历上跑一遍即可#include <bits/stdc++.h>using namespace std;int main(){ int mm,dd; s...
2019-09-10 22:45:20
5023
原创 Educational Codeforces Round 71 (Rated for Div. 2)
回归之战第二场，选择了一场educational，由于老师的拖堂，直接在教室里开一场cf也算是独特的体验了A. There Are Two Types Of Burgers思路：制作汉堡分配题。不同的汉堡公用相同的馍，那么当然是将馍先提供给高价值的汉堡，模拟一下即可#include <bits/stdc++.h>using namespace std;int ma...
2019-09-10 22:01:06
148
原创 xdoj freshmen onsite 2018
不知不觉到了第二届新生赛，此时的我已经是退休老油条了，看着xdu-icpc队伍逐渐壮大，甚是欣慰。预祝即将到来的第三届新生赛顺利。Problem A Easy Problem思路：正奇数数列最大长度，打标找规律即可发现，答案即为输入的开方数#include <bits/stdc++.h> using namespace std; const double eps...
2019-09-04 23:34:54
244
原创 xdoj freshmen onsite 2017
回忆第一届新生赛，在前往icpc的途中和队友讨论如何出题“为难”新生，尔来已经两年的，不觉感慨时间飞逝。OJ上没有挂对应题目的题面，可以从这下载，然后去oj提交Problem A A + B problem思路：1000以内特定三数和组合，直接暴力前两数统计即可#include <bits/stdc++.h> using namespace std; int ...
2019-09-04 22:49:12
192
原创 xdoj水题练
长时间没码代码后，对题目明显变得生疏，还是需要找几道水题来练练手1129: An Old Problem思路：典型的矩阵交换行列的题，建立索引，利用交换索引替代直接对矩阵进行交换#include <bits/stdc++.h>using namespace std;const int maxn = 1e3+10;int a[maxn][maxn];i...
2019-09-04 07:40:47
549
原创 Codeforces Round #579 (Div. 3)
回归之旅，怎么能少了cf，从div3开始玩起，又是一年多没玩的游戏了，赶紧上手找找感觉，题目不难，最重要的就是自信与时间的把握，确实太久没做题了A. Circle of Students思路：简单判循环题，正反两下循环即可搞定，手太生了，连循环都不敢写了#include <bits/stdc++.h>using namespace std;#define ne (...
2019-09-03 01:12:07
137
原创 xdoj回归练
不知不觉距离自己上次写博客已经快有一年之久了，近一年没做题，感觉自己不觉生疏了很多。编程素养还是很重要的，不宜随意丢弃。正式回归，还是从xdoj开始1370 Fibonacci问题思路：普通迭代循环求大数斐波那契#include <bits/stdc++.h>using namespace std;long long fi[41];int main(){ ...
2019-09-03 00:30:17
329
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人