- 博客(273)
- 收藏
- 关注
RSS订阅
原创 一些常用的Latex公式。(更新中)
\sqrt[2]{x+y} []里面的数字表示几次方 x+y−−−−√2x+y2\sqrt[2]{x+y} \frac{2}{3} + 1 23+123+1\frac{2}{3} + 1 \sum_{1}^{3} ∑13∑13\sum_{1}^{3}\begin{matrix}1 & 2 & 3 \\4 & 5 & 6 \\7 &
2018-04-07 21:59:13
387
2
原创 关于C++中STL的一些东西和一些函数小技巧（不定期整理）
stringstream类 对于有些oj题目，可能未说明有多少个数组，只是一整行的数据。对于写，我们可以先把他们当做字符串直接读取，再利用stringstream类进行转化。如下#include<iostream>#include<sstream>#include<cstdio>#include<vector>#include<algorithm>#incl
2017-12-08 15:37:55
333
原创 一些数学几何知识和小技巧
发现自己几何sb，还是总结一下已知三点求圆心，但三点不能共线Point Getcir(Point A,Point B,Point C){//给予三个点，求圆心。 double a = 2*(B.x - A.x); double b = 2*(B.y - A.y); double c = (B.x*B.x+B.y*B.y) - (A.x*A.x+A.y*A.y);...
2017-11-12 14:40:29
509
原创 无用？
盖文王拘而演《周易》；仲尼厄而作《春秋》；屈原放逐，乃赋《离骚》；左丘失明，厥有《国语》；孙子膑脚，《兵法》修列；不韦迁蜀，世传《吕览》；韩非囚秦，《说难》《孤愤》；《诗》三百篇，大底圣贤发愤之所为作也。
2017-05-07 16:43:48
457
1
原创 leetcode 1739. 放置盒子 (数学，二分）
放置盒子有一个立方体房间，其长度、宽度和高度都等于 n 个单位。请你在房间里放置 n 个盒子，每个盒子都是一个单位边长的立方体。放置规则如下：你可以把盒子放在地板上的任何地方。如果盒子 x 需要放置在盒子 y 的顶部，那么盒子 y 竖直的四个侧面都 必须 与另一个盒子或墙相邻。给你一个整数 n ，返回接触地面的盒子的 最少 可能数量。示例 1：输入：n = 3输出：3解释：上图是 3 个盒子的摆放位置。这些盒子放在房间的一角，对应左侧位置。示例 2：输入：n = 4输出：3解释.
2021-01-26 01:24:23
643
3
原创 codeforces 1453 D. Checkpoints (构造+期望)
构造题目，需要想到一种构造方法，这个题目其实可以想到两种构造，用全为1进行构造，如1111这种，但她的期望公式是f[n] = 2*n，因为n最大是2000，所以显然不行，然后就是全为0进行构造，因为开头是1，所以就是后面补0来进行构造。考虑 f1 = 2;f2 = 6;f3 = 14,可以看出规律是f[n] = f[n-1]*2,根据这个规律就可以解决这道题目了，因为第一个位置必须是1，结合上面也可以看出，无论怎么构造，期望一定是偶数。可以得到代码如下：#include <bits/stdc++.
2020-12-08 01:23:26
461
原创 区间更新，单点查询的两种做法（树状数组和差分）
差分差分是一种和前缀和相对的策略，可以当做是求和的逆运算。定义为:f(n)={ai−ai−1,n>2ai,n=1f(n) =\begin{cases} a_i - a_{i-1}, &n>2\\a_i, &n = 1 \end{cases}f(n)={ai−ai−1,ai,n>2n=1它具有一下这些性质：bi的前缀和是ai的值。若在序列a的[l,r]区间增加一个数d,对b的表现为在b[l] +d,b[r+1]-d。（通过这个性质可以实现区间
2020-12-01 00:45:20
1079
原创 codeforces 1454 F. Array Partition
F. Array Partitiontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a consisting of n integers.Let min(l,r) be the minimum value among al,al+1,…,ar and max(l,r) be the maximum
2020-11-29 01:28:22
183
原创 codeforces problem 1452 D. Radio Towers
There are n+2 towns located on a coordinate line, numbered from 0 to n+1. The i-th town is located at the point i.You build a radio tower in each of the towns 1,2,…,n with probability 12 (these events are independent). After that, you want to set the sign
2020-11-24 01:14:29
261
原创 Codeforces Round #685 (Div. 2) D. Circle Game
Utkarsh is forced to play yet another one of Ashish’s games. The game progresses turn by turn and as usual, Ashish moves first.Consider the 2D plane. There is a token which is initially at (0,0). In one move a player must increase either the x coordinate
2020-11-23 02:00:09
173
原创 Educational Codeforces Round 97 (Rated for Div. 2)
A. Marketing Schemetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou got a job as a marketer in a pet shop, and your current task is to boost sales of cat food. One of the strategies is to sell ca
2020-11-21 01:34:00
395
原创 leetcode 974. 和可被 K 整除的子数组
给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。示例：输入：A = [4,5,0,-2,-3,1], K = 5输出：7解释：有 7 个子数组满足其元素之和可被 K = 5 整除：[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]提示：1 <= A.length <= 30000-10000 <= A[i] <= 100002
2020-05-28 00:09:21
179
原创 leetcode 41. First Missing Positive（思维)
First Missing PositiveHard2902741Add to ListShareGiven an unsorted integer array, find the smallest missing positive integer.Example 1:Input: [1,2,0]Output: 3Example 2:Input: [3,4,-1,1]Out...
2020-04-17 00:53:10
151
原创 leetcode 1320. Minimum Distance to Type a Word Using Two Fingers (dp O(N) Solution)
You have a keyboard layout as shown above in the XY plane, where each English uppercase letter is located at some coordinate, for example, the letter A is located at coordinate (0,0), the letter B is...
2020-01-31 00:26:49
818
原创 Leetcode 155. 最小栈 O(1)空间复杂度的做法
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。push(x) – 将元素 x 推入栈中。pop() – 删除栈顶的元素。top() – 获取栈顶元素。getMin() – 检索栈中的最小元素。示例:MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minS...
2020-01-10 01:43:58
766
原创 链表的归并排序 & leetcode 148. 排序链表
发现链表的归并排序要注意的点还真挺多。对元素的划分，即要把链表从中间断开，这个可以利用一个快指针每次走两步，一个慢指针一次走一步的做法来实现，并记录前半部分链表的最后一个节点。对链表的合并，这个我是利用递归，很容易理解与实现。代码实现如下:/** * Definition for singly-linked list. * struct ListNode { * int ...
2019-09-18 23:49:01
199
原创 C++ primer 内存管理 allocator类
当我们分配一大块内存时，我们通常计划再这块内存上按需构造对象，在次情况下，我们希望内存分配和对象构造分离。内存分配和对象构造组合在一起可能会导致不必要的浪费，比如数组等，有时我们并不需这么大的空间。allocator标准库allocator类定义在头文件memory中，它可以用来将内存分配和对象构造分离，它提供一种类型感知的内存分配方法，它分配的内存是原始的、未构造的。它也是一个模板对象，所...
2019-09-04 21:10:42
244
原创 C++ 智能指针 循环引用以及解决方案
今天面试碰到这个问题了，结果自己没有搞清楚是个是么问题。感觉面试官说的也不太清楚。。我理解成两个两个智能指针A = B B = A,A = B,这种了。。。我还说这种不会引计数器多++。。尴尬。。自己基础方面还是有点问题。。循环引用如下#include<bits/stdc++.h>using namespace std;class B;class A{public: ...
2019-08-16 16:04:15
715
原创 leetcode 334. 递增的三元子序列 (dp)
给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。数学表达式如下:如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。示例 1:输入: [1,...
2019-08-13 17:05:16
125
原创 Codeforces Round #578 (Div. 2) 题解报告
A. Hoteliersb模拟，直接按题意模拟就可以了。B. Block AdventureGildong is playing a video game called Block Adventure. In Block Adventure, there are n columns of blocks in a row, and the columns are numbered from 1...
2019-08-12 14:04:54
363
原创 C++ 智能指针
在C++中，动态内存的管理通过new 和 delete来进行。但却经常存在以下三个常见问题：忘记通过delete 释放内存，这在编程中经常发生，尤其在某个函数内申请的一块内存作为临时使用，但在函数结束后却没释放。这就会导致“内存泄露”问题。使用已经释放过的内存，当有多个指针指向同一块内存时，某个指针释放后，却仍旧使用其他指针，就会导致这种错误。通过释放内存后把指针置为空，可以解决这种情况。...
2019-08-07 20:14:31
624
原创 Codeforces Round #576 (Div. 2) 题解
7.30号的cf,很久没打cf了，决定打一下，果然掉了10分。。。幸好还是蓝名。。。打完第二天就发了高烧也是无语。。。吃药在宿舍躺尸两天，决定把题解写下。。A. City Day题目很简单，不过英文有点绕。就是找到第一个符合的点，这个点是前面x个的值都比它大，后面y个的值都比它大。相当于一个凹点。当然，前面x可以不存在，后面y个也可以有不存在的。代码如下:#include<bits/...
2019-08-02 20:27:57
479
2
原创 leetcode 995. K 连续位的最小翻转次数 (区间更新，单点查询)
在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。返回所需的 K 位翻转的次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。示例 1：输入：A = [0,1,0], K = 1输出：2解释：先翻转 A[0]，然后翻转 A[2]。示例 2：输入：A = [1,1,0],...
2019-07-30 21:27:35
484
原创 leetcoe 第 147 场周赛 题解
A题:1137. 第 N 个泰波那契数人尽皆知傻逼题,直接数组模拟。B题:1138. 字母板上的路径我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。在本题里，字母板为board = [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”].我们可以按下面的指令规则行动：如果方格存在，‘U’ 意味着将我...
2019-07-29 15:08:20
187
原创 leetcode 154. 寻找旋转排序数组中的最小值 II (二分)
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。注意数组中可能存在重复的元素。示例 1：输入: [1,3,5]输出: 1示例 2：输入: [2,2,2,0,1]输出: 0来源：力扣（LeetCode）链接：https://leetcode-cn.com/p...
2019-07-28 15:17:24
209
原创 僵尸进程以及消灭僵尸进程
进程：占用内存空间的正在运行的程序，是系统进行资源分配和调度的基本单位。进程在完成工作后应该被销毁，如果完成工作后，仍占用系统资源不被销毁，就会变为僵尸进程，给系统带来负担。僵尸进程的产生向exit函数传递参数值，或者是通过return语句返回的值都会传递给操作系统，而操作系统如果没有把这些值传递给产生该子进程的父进程，那么操作系统就不会销毁子进程.处于这种状态下的进程就是僵尸进程。下面是...
2019-07-25 17:46:16
574
1
原创 2019第十届蓝桥杯大赛C++B组 试题 B: 质数拆分
【问题描述】将 2019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？ 注意交换顺序视为同一种方法，例如 2 + 2017 = 2019 与 2017 + 2 = 2019 视为同一种方法。题目其实不难，自己比赛的时候也是想到做法了，结果算出来的数贼大，感觉自己算错了。。。哎。。做法：（可能不是最佳的做法）先获得2019内的所有素数，然后就是一个从N个数里面凑成M的个数的题目了...
2019-06-06 11:24:26
4094
2
原创 leetcode 442. 数组中重复的数据 (思维) &448
给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？示例：输入:[4,3,2,7,8,2,3,1]输出:[2,3]最开始毫无思路，结果发现每个数的范围都是[1,n],所以可以考虑这种做法，如果某个位置的数不属于这个位置，就把他交换到对应...
2019-05-14 09:16:51
126
原创 leetcode 494. 目标和 (动态规划)
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。示例 1:输入: nums: [1, 1, 1, 1, 1], S: 3输出: 5解释:-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1...
2019-05-13 13:29:33
530
原创 select函数实现I/O复用的回声服务器
select函数可以将多个文件描述符集中到一起统一监视。1.是否存在套接字接收数据2.是否传输无阻塞数据3.是否发生异常文件描述符集中到一起需要fd_set数据执行，该数组是存有0和1的数组。在fd_set里面注册或更改的操作都是由以下宏完成的。FD_ZERO(fd_set *fdset):将fd_set变量的所有位初始化为0.FD_SET(int fd,fd_set * fdset...
2019-05-11 19:05:02
332
原创 leetcode 101. 对称二叉树 递归和迭代两种写法
给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。1/ \2 2/ \ / \3 4 4 3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:1/ \2 2\ \3 3做法就是，判断 根左右遍历 和 根右左遍历 是否相同。注意用BFS获得每层的做法是不对的（话说我最开始想到的竟然...
2019-05-11 12:37:47
326
原创 通过socket实现网络文件传输
把Linux下文件传输和Linux做服务端以及windows做客户端的传输都实现了一遍。Linux下Server端Linux下打开文件的函数open(path,flag)打开模式有O_CREAT 必要时创建文件O_TRUNC 删除全部现有数据O_APPEND 维持现有数据，保存其后面O_RDONLY 以只读打开O_WRONLY 以只写打开O...
2019-05-01 23:23:41
520
原创 Linux 下server端和windows下client端通信
最近看了《TCP/IP网络编程》这本书。正好又租了台阿里云的服务器，发现把TCP端口全部打开后，就可以实现本地与云服务器的通信了。主要时利用socket进行通信，实现一个简单的计算功能。代码有点丑。。op_server.cpp#include<stdio.h>#include<stdlib.h>#include<string.h>#include&...
2019-04-30 19:47:42
284
原创 codeforces 1157 D. N Problems During K Days (二分+构造)
D. N Problems During K Daystime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputPolycarp has to solve exactly n problems to improve his programming...
2019-04-27 15:41:30
321
原创 设计模式-适配器模式 C++实现
适配器模式定义：将一个类的接口转化为客户希望的另外一个接口，是的原本由于接口不兼容而不能在一起工作的那些类能一起工作。特点：（1）客户端通过适配器可以透明的调用目标接口.（2）程序员不需要修改原有代码而重用现有的适配者类。（3）将目标类和适配者类解耦，解决了目标类和适配者类接口不一致的问题。主要角色 目标接口（Target),适配者类（Adaptee，被转换为的对象）适配器（Adapter）...
2019-04-26 21:17:59
209
原创 Codeforces Round #554 (Div. 2) C. Neko does Maths（数论）
C. Neko does Mathstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputNeko loves divisors. During the latest number theory lesson, he got an inter...
2019-04-25 23:20:46
471
2
原创 剑指offer - 滑动窗口最大值 （单调队列的使用）& POJ 2823 & leetcode 239. 滑动窗口最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， ...
2019-04-23 15:19:34
219
原创 设计模式-代理模式 C++实现
代理模式定义：由于某些原因给某个对象提供一个代理以控制该对象的访问。特点：（1）代理模式再客户端和目标对象之间起到一个中介的作用和保护目标对象的作用。（2）代理对象可以扩展目标对象的功能。（3）代理模式能将客户端和目标对象分离，一定程度上降低了系统的耦合度。主要角色 Subject,ConcreteSubject,Proxy具体应用的例子：比如你有一个生产玩偶的工厂，但你自己生产的不是很美...
2019-04-22 23:21:15
204
原创 设计模式-建造者模式 C++实现
建造者模式定义：将一个复杂对象的构造与他的表示分离，是同样的构造过程可以创建不同的表示。可以想象为先创建一个产品的骨架，再拼接他的零件。特点：（1）各个具体的建造者相互独立，有利于系统的扩展。（2）客户端不必知道产品内部的组成细节，便于控制细节风险。主要角色 Product,AbstractBuilder,Builder,DirectorC++实现Product.h#pragma on...
2019-04-15 23:30:55
189
原创 设计模式-工厂模式 C++实现
工厂模式定义:一个创建产品对象的工厂接口，将产品对象的实际创建工作推迟到具体子类工厂类中。特点：（1）用户只要知道具体工厂的名称就可以得到所需要的产品，无需知道产品创建的过程。（2）增加新产品时只需要添加具体产品类和对应的具体工厂，无需修改源代码，满足开闭原则。C++实现如下Product.h#pragma onceclass AbstractProduct {public: Ab...
2019-04-13 23:02:23
142
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人