- 博客(101)
- 收藏
- 关注
RSS订阅原创 摆动排序leetcode324
给你一个整数数组nums，将它重新排列成nums[0] < nums[1] > nums[2] < nums[3]...的顺序。你可以假设所有输入数组都可以得到满足题目要求的结果。示例 1：输入：nums = [1,5,1,1,6,4]输出：[1,6,1,5,1,4]解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。示例 2：输入：nums = [1,3,2,2,3,1]输出：[2,3,1,3,1,2]提示：1 &l...
2021-07-17 14:18:43
189
1
原创 任务调度器leetcode621
问题(来自LeetCode)：给你一个用字符数组tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的 最短时间 。示例 1：输入：tasks = ..
2021-07-13 12:05:34
314
1
原创 C++ 使用bind方法，在类里面使用带有非静态cmp函数的sort
#include <iostream>#include <algorithm>#include <functional>using std::placeholders::_1;using std::placeholders::_2;class A {public: bool cmp(int x, int y) { ... } void test() { auto bound_cmp=bind(&.
2021-07-12 14:28:02
224
原创 灯泡开关问题
初始时有n个灯泡处于关闭状态。对某个灯泡切换开关意味着：如果灯泡状态为关闭，那该灯泡就会被开启；而灯泡状态为开启，那该灯泡就会被关闭。第 1 轮，每隔个灯泡切换一次开关。即，打开所有的灯泡。第 2 轮，每隔两个灯泡切换一次开关。 即，每两个灯泡关闭一个。第 3 轮，每隔三个灯泡切换一次开关。第i 轮，每i个灯泡切换一次开关。 而第n轮，你只切换最后一个灯泡的开关。找出n轮后有多少个亮着的灯泡。来源：力扣（LeetCode）链接：https://leetc...
2021-05-25 10:22:17
438
原创 Classifying dynamic textures via spatiotemporal fractal analysis（许教授）
提出了：dynamic fractal spectrum (动态分形谱) 来处理动态纹理序列模型由两个部分组成：volumetric dynamic fractal spectrum component (V-DFS 三维动态分形谱)、multi-slice dynamic fractal spectrum(S-DFS 多层动态分形谱)V-DFS：把DT序列堆叠起来，成为立体数据，然后捕获其随机自相似性S-DFS：对沿三维体的不同视觉方向的二维切片上重复DT图案的分形结构进行编码..
2021-04-10 17:01:20
201
原创 Leetcode (396 旋转函数)
问题：给定一个长度为 n 的整数数组A。假设Bk是数组A顺时针旋转 k 个位置后的数组，我们定义A的“旋转函数”F为：F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]。计算F(0), F(1), ..., F(n-1)中的最大值。注意:可以认为 n 的值小于 105。示例:A = [4, 3, 2, 6]F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6)...
2021-04-09 13:38:39
99
原创 leetcode 665(是否能通过修改数组一个元素，达到非严格递增)
Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).
2021-04-08 10:56:15
194
原创 最小子矩阵(前缀和+矩阵压缩+双指针)
题目描述一个N*M的矩阵，找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵（矩阵中元素个数为矩阵面积）输入描述:每个案例第一行三个正整数N,M<=100，表示矩阵大小，和一个整数K接下来N行，每行M个数，表示矩阵每个元素的值输出描述:输出最小面积的值。如果出现任意矩阵的和都小于K，直接输出-1。示例1输入4 4 101 2 3 45 6 7 89 10 11 1213 14 15 16输出1牛客网思路：任选两列，把这两列间.
2021-03-21 12:39:22
786
原创 最小邮票数（01背包）
题目描述 有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。 如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。输入描述: 有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。输出描述: 对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。示例1输入复制...
2021-03-19 10:26:16
174
原创 在线查询第K个元素
分块思想（参考算法笔记）：假设数组大小为N，那么我们把数组分成 block_num = sqrt(N)个块【向上取整】，每个块的范围是block_size= sqrt(N)【向下取整】，用block[i]记录第 i 块的元素个数，然后再开一个数组 table[i] 记录数值为 i 的元素个数添加元素 x 的时候，计算元素对应的块号为idx =x / block_size ，然后令 block[idx]+=1 , table[x] +=1删除元素 x 的时候，计算元素对应的块号为...
2021-03-07 10:50:23
106
原创 Find More Coins（记录背包的选择）
1068 Find More Coins (30 point(s))Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special
2021-03-05 13:45:08
161
原创 最大子矩阵（降维处理）
题目描述已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。比如，如下4 * 4的矩阵0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2的最大子矩阵是9 2-4 1-1 8这个子矩阵的大小是15。输入输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵..
2021-03-04 15:32:22
193
1
原创 毕业BG（01背包问题）
题目描述每 年毕业的季节都会有大量毕业生发起狂欢，好朋友们相约吃散伙饭，网络上称为“bg”。参加不同团体的bg会有不同的感觉，我们可以用一个非负整数为每个 bg定义一个“快乐度”。现给定一个bg列表，上面列出每个bg的快乐度、持续长度、bg发起人的离校时间，请你安排一系列bg的时间使得自己可以获得最 大的快乐度。例如有4场bg：第1场快乐度为5，持续1小时，发起人必须在1小时后离开；第2场快乐度为10，持续2小时，发起人必须在3小时后离开；第3场快乐度为6，持续1小时，发起人必须在2小时后离开；
2021-03-04 14:38:34
159
1
原创 放苹果（求组合数）
问题：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？注意：假如有3个盘子，那么 5，1，1 和 1，5，1 与 1，1，5 都是同一种分法。这种求放物品的组合数问题，可以通过这样的完备思路来构造递归公式：假设有n个盘子 ，那么1、至少有一个盘子不放苹果2、n个盘子都放苹果，这两种放法是完备的。所以求出两种放法的方案数，加起来就能得出结果接下来详细利用这个思路：假设 DP(M,N)记录M个苹果放在N个的盘子的总方案数苹果数M<盘子数N，那..
2021-03-04 14:28:00
394
原创 合唱队形（递增再递减的最长子序列）
题目描述N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。问
2021-03-04 13:56:09
731
1
原创 问题 A: 第二题（划分一个集合为差值最小的两个子集合）
题目描述一个数组中有若干正整数，将此数组划分为两个子数组，使得两个子数组各元素之和a,b的差最小，对于非法输入应该输出ERROR。输入数组中的元素输出降序输出两个子数组的元素和样例输入10 20 30 10 1010 20 abc 10 10样例输出40 40ERROR思路：令sum为集合中所有的元素之和，当子集合的和接近 sum/2 时，两个子集合的和相差最小用DP的背包思想来考虑这个问题：把 sum/2 看作是背包的容量V，把元素的数值看...
2021-03-04 13:40:49
977
2
原创 背包思想计算方案的总数（货币系统）
问题：已知V种不同面值的硬币，假设每种硬币的数量无限，求支付N元有多少种不同的方案？例：现在有3种货币：1元、2元、5元，需要向别人支付10元。完全背包思路：从左到右依次考虑每种货币，有两种操作：1.选 2.不选，同一种货币可以选择多次。令货币的价值=占用背包的空间，支付总价钱作为背包的容量，那么背包的容量等价于物品的价值，也就是我得到价值为K的物品，背包容量就减少了K。如果取得最大价值时，背包恰好装满，就代表放进背包的货币刚刚好能凑出支付的总价钱（容量为V的背包能取得的最大...
2021-03-04 11:40:30
158
1
原创 多阶段DP问题
多阶段DP问题的定义：一个问题可以分成多个阶段，每个阶段有多个状态，且每个阶段的状态只与上一阶段的状态有关。这类问题，题目一般会给出多个对象各自的属性和一个限制的条件，然后计算如何操作这些对象获得最优值我们可以用 dp[阶段][限制条件(状态)] 来记录某个阶段中某个状态的最优解然后找到dp[i][cur]与上一阶段的状态有什么联系，从有联系的状态中找出最优解例如01背包问题对象：物品；属性：重量、价值限制条件：背包容量vdp[i][v] 记录前i个物品(阶段i)，剩下容
2021-03-01 15:01:00
199
原创 最长不下降子序列（推广问题）
最长不下降子序列问题的定义：在一个序列中，找到一个最长的子序列，其中这个序列是非递减的我们可以把这个非递减推广，其实非递减就是一种顺序，那么我们可以把定义推广到：给出一个顺序序列、目标序列中，在目标序列中找到一个最长的子序列，其中这个子序列是符合给出顺序的子序列解决这个推广的问题，我们可以把这个顺序序列的每一个元素映射到一个递增序列假设顺序序列为X、Y、Z，那么我们可以把它映射到 0、1、2（用Hash表实现）然后目标序列为 XYXXZXYZ，我们从上面的Hash表中找到它对应的序列为.
2021-03-01 11:24:11
120
原创 Jugs (BFS解决方法)
JugsTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1449Accepted Submission(s): 480Problem DescriptionIn the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the ...
2021-02-19 10:25:16
303
原创 codeup:问题 D: 最短路径
题目描述有n个城市m条道路（n<1000, m<10000)，每条道路有个长度，请找到从起点s到终点t的最短距离和经过的城市名。输入输入包含多组测试数据。每组第一行输入四个数，分别为n，m，s，t。接下来m行，每行三个数，分别为两个城市名和距离。输出每组输出占两行。第一行输出起点到终点的最短距离。第二行输出最短路径上经过的城市名，如果有多条最短路径，输出字典序最小的那条。若不存在从起点到终点的路径，则输出“can't arrive”。样例输入3 3
2021-02-19 10:18:59
294
原创 迷宫问题输出超限反思
做了一题简单的迷宫题，但是OJ一直显示“输出超限”，一直找不到哪里出错后来发现，原来，我的习惯是：先判断合法性、设置标志，再进入下一层DFS，但是！！！在main函数进入DFS的第一层的时候，我忘记设置“标志”，这就违反了我上面“先标志，后进入”的原则，导致迷宫路径计算出错#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<algorithm>#include<string>#incl.
2021-02-01 18:56:49
152
1
原创 PAT 1074 Reversing Linked List
1074Reversing Linked List(25point(s))Given a constantKand a singly linked listL, you are supposed to reverse the links of everyKelements onL. For example, givenLbeing 1→2→3→4→5→6, ifK=3, then you must output 3→2→1→6→5→4; ifK=4, you must outpu...
2021-01-28 21:23:46
70
原创 PAT 1056 Mice and Rice (25point(s))(队列的使用)
1056Mice and Rice(25point(s))Mice and Riceis the name of a programming contest in which each programmer must write a piece of code to control the movements of a mouse in a given map. The goal of each mouse is to eat as much rice as possible in order t...
2021-01-28 17:47:41
77
原创 cin、getline的坑
cin、scanf 读取一个数据后，会遗留一个‘\n’在后面如果我们接着使用getline，就会把上面cin、scanf遗留下来的‘\n’读入。因为getline遇到‘\n’会读入结束，所以会读到一个空字符串如果我们需要在cin、scanf紧接着用getline，那么我们需要在cin、scanf后面加上一个getchar()，吃掉'\n'cin>>n;getchar();getline(cin,str);在循环使用getline的时候，不需要使用getchar()，因为ge
2021-01-25 13:24:28
327
原创 C++字符串数组排序技巧
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<algorithm>#include<vector>#include<map>#include<unordered_map>#include<string>#include<unordered_set>#include<iterator>#include<sstream&g.
2021-01-25 11:11:07
5559
1
原创 把浮点型数值用科学计数法输出
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<algorithm>#include<string>using namespace std;struct SCINUM { // 科学计数法结构体 string valid_num; //有效位 int pow;//指数 SCINUM() { pow = 0; }};SCINUM str2Sci(string num,int .
2021-01-21 13:37:52
1664
原创 求n!中含有质因子p的个数
定理：中含有质因子p的个数为,其中int cal(int n, int p) { int ans = 0; while (n != 0) { ans += n / p; n /= p; //相当与分母多乘一个p } return ans;}
2021-01-19 13:58:13
878
原创 大整数运算(必记)
大整数运算结构体struct bign { int d[maxn];//d的低位就是数值N的低位 int len;//大整数长度 //int symbol; bign() { memset(d, 0, sizeof(d)); len = 0; //symbol = 1; }};字符串转化为大整数型bign str2bign(char str[]) { bign num; int len = strlen(str); if (str[0] == '-')num.s
2021-01-19 13:24:47
194
原创 因子(约数)的个数
假设N = p * q ，那么p与q都是N的约数显然有,在1，2，... k ()中，如果N%k==0 ，那么就能找到N的一个或者两个约数当时，找到N的两个约数，k与n/k当时，找到N的一个约数，k#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>#include<algorithm>#include<string.h>#include<...
2021-01-18 22:09:24
93
原创 质因子分解
以下思路参考《算法笔记》质因子分解：把一个正整数n写成一个或多个质数相乘的形式例如 6=2✖️3 ，180=2✖️2✖️3✖️3✖️5先说如何判断一个数n，是否在[2,n) 中存在它的因子：假设这个n存在因子为k[2,n)，那么nmod k=0假设这个n存在因子为 k [2,n) ，那么n\mod k=0假设这个n存在因子为k[2,n)，那么nmodk=0由于n×nk=n，所以nmod nk=0，所以k与nk都是n的因子，且min(k,nk)<n由于 n\times\frac{n}{k}
2021-01-16 16:51:39
280
原创 PAT计算出2～N所有素数
#define maxn 405000int prime[maxn]; //保存素数的数组bool flag[maxn]; //记录是否为素数int cnt;void getPrime(int n) { memset(flag, 0, sizeof(bool)*maxn); cnt = 0; for (int num = 2; num <= n; num++){ if (flag[num] == false) { //如果num是素数 prime[++cnt] = num;/.
2021-01-15 19:53:06
79
原创 C语言的分数运算(简单版)
#define _CRT_SECURE_NO_WARNINGS#include<iostream>#include<cstdio>using namespace std;typedef long long ll;class Fraction {public: ll up, down;// up、down分别是分子、分母 Fraction(ll x = 0, ll y = 1) { up = x; down = y; this->reduction.
2021-01-15 15:04:57
4672
原创 1049 Counting Ones
1049Counting Ones(30point(s))The task is simple: given any positive integerN, you are supposed to count the total number of 1's in the decimal form of the integers from 1 toN. For example, givenNbeing 12, there are five 1's in 1, 10, 11, and 12.I...
2021-01-13 20:19:31
74
原创 C语言float、double、longlong的输入输出格式
float : scanf("%f,&b); printf("%f", a);double ： scanf("%lf", &a) ;printf("%f", a);long long :scanf("%lld",&a);printf("%lld",a);
2021-01-13 16:53:40
9800
原创 1003 我要通过！ (20point(s))
1003我要通过！(20point(s))“答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。得到“答案正确”的条件是：字符串中必须仅有P、A、T这三种字符，不可以包含其它字符； 任意形如xPATx的字符串都可以获得“答案正确”，其中x或者是空字符串，或者是仅由字母A组成的字符串； 如果aPbTc是正确的，那么aPbATca也是正确的，其中a...
2021-01-13 14:24:24
203
原创 离散化--个人总结
使用离散化的一般情况：1⃣️ 数据的值的范围太大，但数据的量并不多2⃣️ 值的大小不重要，重要的是值之间的大小关系离散化一般方法：1⃣️ 排序2⃣️ 去重3⃣️ 形成新的映射例子：https://www.cnblogs.com/farewell-farewell/p/5330429.html常用到的STL库函数：unique(start,end...
2019-11-16 20:48:15
150
原创 在有序数字中寻找和为k的两个数 O(n)
思路：分别在有序数字串的两头向中间遍历 bool findTarget(vector<int> &nums,int k) { for(i=0,j=nums.size()-1;i<j;){ if(nums[i]+nums[j]==k)return true; (nums[i]+nums[j]&...
2019-05-19 21:54:36
453
原创 865. Smallest Subtree with all the Deepest Nodes(‘找小弟’思想)
problem：Given a binary tree rooted atroot, thedepthof each node is the shortest distance to the root.A node isdeepestif it has the largest depth possible amongany node in theentire tree....
2019-05-19 21:46:39
125
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人