- 博客(67)
- 收藏
- 关注
RSS订阅原创 血泪教训，不要用python2运行os.rename
如果更改的名字已经存在，那么python2会直接删除这个已存在的文件，没有任何提示警告，这万恶的python2
2021-02-28 20:47:26
144
原创 Morris Traversal -Preorder & Inorder & Postorder
java versionimport java.util.ArrayList;public class Learn { public static void main(String[] args) { TreeNode root = new TreeNode(5); root.left = new TreeNode(2); root.left.left = new TreeNode(1); root.left.right = ne
2021-02-26 19:57:27
183
原创 记录一下，解决dash下载过慢
阅读各种语言的文档是刚需，一些文档有pdf下载，另一些只在网站上提供查询，因为墙的问题每次在线查慢的要死，因此想到了用dash把文档离线下来。Mac上可以用“可莱西x”（发音是这样，应该能懂得吧），proxy我用的agentneo，然后可莱西x上没找到配置rule的地方，直接设置global，找个快的节点，速度从20KB一下提升到11MB，起飞。...
2020-08-27 17:08:57
1153
原创 Rubik's Cube
题目POJ1955解法这题没什么含金量，纯考代码能力。除了枚举每一面的转法，还可以对每一个面抽象出一个统一的转法。旋转时需要转与这个面紧接的四个条状，以及这个面本身，用round数组存四个条状的指针，然后就可以统一处理了。#include <cstdio>char cube[6][3][3];char* round[6][4][3] = { { ...
2020-04-27 19:15:05
827
原创 求不存在重复元素的数组中逆序对的个数
问题：给定不存在重复元素的数列a[n]，问存在多少对(i, j)，满足 0<=i<j<n && a[i] > a[j]解法：归并排序数列的逆序对数 = 左半边逆序对数 + 右半边逆序对数 + merge过程中右半边元素放置在左半边元素前面的个数T(n)=2T(n2)+O(n)T(n) = 2T(\frac{n}{2}) + O(n)T(n)=2T...
2020-04-26 23:43:08
137
原创 n queens puzzle
N queens puzzleMath solutionThe solution is not unique, this method provide only one of them.DFS用四个数组记录位置可选的状态，每填一个点，其所导致失效的行、列、两个对角线必定是独一无二的，这样就方便在DFS中还原可选状态，比记录点[row][col]更好，因为同一点可能因多个点的填入被设为无效...
2020-04-22 18:17:00
114
原创 最小覆盖圆
问题给定一系列点，求最小的覆盖圆解法点类const double eps = 1e-8;const double pi = acos(-1.0);inline double sqr(double x){ return x*x;}//浮点数修正int cmp(double x){ if(fabs(x)<eps) return 0; if(x>...
2020-04-18 23:33:49
155
原创 3水杯倒水问题
问题：给出三个杯子的容量ABC ， 其中刚开始时C杯是满的，AB是空的。现在在保证不会有漏水的情况下进行如下操作：将一个杯子x的水倒到另一个杯子y中，如果x空了或者y满了就停止（满足其中一个条件才停下）现问C中水量有多少种可能性（A,B,C为非负整数）解法1：数论，扩展欧几里得待补充解法2：模拟倒水过程，BFS枚举所有情况只适用杯子容量不是很大的情况。#include <c...
2020-04-14 17:14:38
3629
原创 The longest zig-zag subsequence
类似于最长不降子序列。找到最长的大小相间的子序列。dp[k] 表示一个结构体，以k号结尾的最长zig-zag子序列长度，和期待下一个数是大还是小。struct node{ int len, state; //state, 0表示下一个数必须大，1表示必须小，2表示都可以}状态转移方程dp[k].len = max( num[k]能接到dp[i]后面 ? dp[i].len+1...
2020-04-12 18:07:35
146
原创 在字符串中找到第一个int范围内的数值 有限状态机
非0数字0或非数字遇到数字且结果未溢出遇到数字且结果溢出非数字数字非数字S0S1 开始计算数值S3S2 输出结果其中矩形是不接受状态，圆形是接受状态#include <cstdio>#include <cctype>void compute(char c, int &ans);int main(){ int state = 0, ans = 0...
2020-04-12 16:04:15
82
原创 用map实现并查集
一般并查集father都用数组，但在结点总数不知道，结点编号不连续的情况下不适用，可以用map#include <cstdio>#include <unordered_map>using namespace std;unordered_map<int, int> father;int findFather(int v);void unionSe...
2020-04-11 17:06:12
284
1
原创 将一个数组分为两个子数组，使分别的和最接近
ProblemSplit an array into two sub-arrays such that the absolute difference of two sums is minimal.Solution 1: EnumerationTo generate sub-array 1, we either include i’th element or don’t include. I...
2020-04-11 16:31:23
1408
原创 日期转换为星期 基姆拉尔森公式
方法1：基姆拉尔森公式(d + 2m + 3(m + 1) / 5 + y + y / 4 - y / 100 + y / 400 + 1) % 7d 为日期，范围是1-31m 为月份，范围是3-14，当年的1，2月需处理为上一年的13，14月。y为年份，当月份为1，2时，y需减一。结果为0-6，星期日用0表示，星期一为1，以此类推，星期六为6。方法2：每次加1天，加到目标日期#i...
2020-04-08 17:09:32
299
原创 质数（素数）
1. 判断一个数n是不是质数检查n能否被 [2, floor(sqrt(n))]整除，若都不行，则是质数。bool isPrime(int n){ if(n<=1) return false; int sqr = int(sqrt(n*1.0)); for(int i=2; i<=sqr; i++){ if(n%i==0) return fa...
2020-04-06 16:34:07
644
原创 Infix to Postfix & Evaluation of Postfix Expression
假设表达式中的数都是整数。#include <iostream>#include <string>#include <stack>#include <cctype>using namespace std;//假设所有的数都是整数void infixToPostfix(string &infix, string &po...
2020-04-02 17:01:10
299
原创 建立文件树，并打印
递归地建树，递归地打印#include <iostream>#include <string>#include <vector>using namespace std;struct node{ string name; vector<node*> child;};void insertTree(node* &...
2020-04-01 23:03:27
137
原创 无向图的连通，有向图的强连通，环
判断无向图是否连通DFS，BFS遍历图，是否所有顶点都能访问到。并查集。判断图中是否有环有向图：有向图中的环特指同向的环[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-hsVSlpDr-1584972787667)(http://note.youdao.com/noteshare?id=d98bba32026574ec204adac734ccdaf7&a...
2020-03-23 22:13:34
873
原创 leetcode72 edit distance
题目：Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.You have the following 3 operations permitted on a word:Insert a characterDelete a char...
2020-03-20 16:14:26
93
原创 leetcode4 O(logn)算法 the k^th smallest number in two sorted arrays
题目：There are two sorted arrays nums1 and nums2 of size m and n respectively.Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).You may assume nums1 and...
2020-03-19 17:12:26
120
原创 leetcode321 一次失败的动态规划尝试
题目：Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the sam...
2020-03-13 22:10:00
120
原创 括号配对
题目：最长连续有效括号序列。解法1：栈记录配对成功的括号下标，统计连续的最大长度。一对配对的括号，其内部一定全都配对了。解法2：只包含一个配对串的括号串有以下几种形态：(valid)))(valid)(())(valid)(((valid)(valid)(((valid)))任何一个给定的括号串一定是上面的组合，现在采取两种遍历方法，分别统计给定括号串中上述6种形态的...
2020-03-12 13:55:54
977
原创 leetcode10 动态规划实现简单正则匹配
题目：实现简单正则匹配解法：动态规划字符：.与 a~z。数量：*，与其前的字符是一个整体。a*结构具体实现几个a的作用规则非常复杂，不太可能直接if写，因此需要列举出所有的情况（0~n个a的作用），其中有一个匹配成功就算成功。选择状态dp[i][j]表示 s[0~i]与 p[0~j]是否匹配。状态转移方程dp[i][j]={dp[i−1][j−1]p[j]!=′∗′且chec...
2020-03-11 17:17:32
86
原创 leetcode740 动态规划
题目：Given an array nums of integers, you can perform operations on the array.In each operation, you pick any nums[i]and delete it to earn nums[i]points. After, you must delete every element equal to ...
2020-03-09 14:52:40
119
原创 leetcode312 重新思考动态规划
问题：Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get num...
2020-03-08 15:14:41
135
原创 leetcode1248
题目：给定一个整数数组，求有多少个连续的子序列，使其中恰有k个奇数。解法1：数学方法首先确定数组中所有奇数的位置，逐个枚举连续的k个奇数的位置(第i个~第j=i+k-1个)，那么包含这k个奇数的连续子序列的个数为：（第i个奇数与第i-1个奇数之间数字的个数+1）*（第j个奇数与第j+1个奇数之间数字的个数+1）其中+1的意思是加上一个也不选的情况。时间复杂度O(n)class So...
2020-03-06 20:43:37
153
原创 two sum问题
题目：给定一个包含重复元素(<10^5)的数组nums，其中和为k的两个数构成一个解，求解的个数。解法1：枚举法时间复杂度O(n^2)解法2：查询遍历每一个数nums[i]，查找数组中是否存在k-nums[i]。在查询问题上，如果逐个查找对比，最终复杂度依然是O(n^2)，但hash最终可以达到O(n)，速度最快。做法1：两次遍历。第一次先把所有元素入map，第二次再查询。...
2020-03-06 20:34:07
99
原创 pat甲级1057 在线查询/动态查询，空间换时间
查询无序数组中第M小的数，期间不断插入、删除，每次查询都排序一次的代价太大。以最大可能取值maxn为范围，将数字分成ceil(sqrt(maxn))组，每组floor(sqrt(maxn))个数,另外设置两个数组，一个统计每个数字出现的次数，另一个统计每个组中数字的个数。查询时，首先确定在哪个块，再在该块中找第M个。#include <cstdio>#include <s...
2020-03-05 16:22:13
98
原创 pat甲级1068 01背包问题，路径回溯，序列最小
dp数组的计算，路径回溯都有固定的写法，这题的难点在于如何保证回溯出来的路径序列最小，这是比较难想通的地方。序列最小的定义可以这样表述，即位置靠前的数其值越小，序列越小。而路径回溯是从“靠后”的数开始，回溯到“靠前”。因此可以想到这样的策略，把货币从大到小排列，这样回溯时是从小面值货币开始，这里关键的逻辑是，若在某点出现这个货币选与不选，dp值相等，那么选，而不是不选，只有这样才能保证序列最...
2020-03-04 17:33:12
225
原创 0-1背包问题，完全背包问题
0-1背包问题N个物品(编号1,2,…,N)，重量 int w[N+1]价值 int v[N+1]背包容量 int S具有重叠子问题具有最优子结构暴力解法每个物品选和不选，形成二叉树，再DFS动态规划递归写法：dp(i,x)表示从1~i号物品中选，背包剩余容量为x，此状态下能达到的最大价值。递推关系dp(i,x) = max{ dp(i-1,x), dp(i-1,...
2020-03-02 17:14:04
301
原创 ans
#include <iostream>#include <string>#include <vector>#include <map>using namespace std;struct node{ vector<double> w; vector<int> ind;};const int ...
2020-03-01 14:53:50
567
原创 pat甲级1040 最长回文子串
正确代码：#include <cstdio>#include <cstring>const int maxl = 1001;int main(){ char s[maxl]; fgets(s, maxl, stdin); int n; for(n=0; n<maxl; n++){ if(s[n]=='\n')...
2020-02-29 18:14:16
103
原创 最长回文子串 处理顺序
处理点（i, j）需保证点（i+1, j-1）状态已确定，即左下角的点那么有两种处理顺序，1、从左下角到右上角2、从左上角到右下角这种方式代码实现简单一些，代码1：int i=0, j=2;while(j-i<N){ int x=i, y=j; while(y<N){ //状态转移方程(x, y) x++; y++; } j++;}代码2：串...
2020-02-29 16:19:25
103
原创 pat甲级1045 最长不降子序列
怎样把【颜色的先后关系】用【数字大小关系】来体现，直接映射到从1开始递增的序列就好了。题目涉及到不需要的颜色，这类颜色全部映射到0，并在状态转移方程的执行过程中跳过，变向实现把stripe中不要的颜色事先全部删掉。#include <cstdio>int main(){ int N, M, L; scanf("%d%d", &N, &M); ...
2020-02-29 11:45:12
96
原创 pat甲级1007 最大子序列和 动态规划
选取状态：以某点i为结尾的最大子序列和另外多存储一个起始下标#include <cstdio>struct node{ int s, max_sum; //以i为尾，最大和子序列的开始下标与最大和};int main(){ int K; scanf("%d", &K); int seq[K]; bool negative =...
2020-02-28 14:45:56
145
原创 dijkstra算法、动态规划与贪心
我的答案：不属于。dijkstra算法解决的是单源最短路径问题，【问题描述】求起点 S 到某点 D 的 路径上边权和的最小值1、是否具有重叠子问题。是2、是否具有最优子结构。是【dijkstra算法的求解思路】设数组 d[] ，d[i] 表示 S 到 i 的 路径上边权和的最小值，初始化d[S]=0， 其他为无穷大。选取 状态：起点到某点 路径上边权之和的最小值。此状态具备无后效...
2020-02-28 00:28:43
3320
1
原创 pat甲级1087 多标准的dijkstra
首先用map解决城市名字到编号的映射。题目给了最优路径的三个判断标准：第一标准：边权累积最小。第二标准：点权累积最大。第三标准：平均点权最大。下面判断这三个标准能否用dijkstra算法处理，标准1：已知 S -> PATH1 -> B -> D是第一标准最优，证明 S -> PATH1 -> B 也是最优。假设存在 S -> PATH2 -&...
2020-02-27 21:38:18
186
原创 pat甲级1072 以多个顶点为起点，分别dijkstra
本题坑比较多，1、输入可能有 G1 G1 10。需要过滤掉2、输入可能有 G1 G2 10，G1 G2 1 这样的多条路。需保留最小值3、加油站的编号可能达到G10三位字母，居民楼编号可能达到1000四位字母，只看样例会误以为都只有一位数字。代码：#include <cstdio>#include <climits>#include <cstring&g...
2020-02-26 16:46:01
170
原创 多标准最优路径中，运用dijkstra算法的注意点
问题来自pat甲级1018，正确的做法是dijkstra+DFS，而我尝试只用dijkstra，在dijkstra过程中，同时实现对最优路径两个标准的判断，结合顶点之间lack与remain值的递推关系，写出下面的有逻辑错误的代码：#include <cstdio>#include <climits>#include <cmath>#include &l...
2020-02-25 16:55:48
246
1
原创 Bellman Ford算法，求解带负权值图的最短路径
给定一个V个顶点的图，至多进行V-1次循环声明数组d[V]，从起点到顶点 i 的最短距离为d[i]初始化为：distance0∞∞∞∞∞vertexSABCDE重复以下过程V-1次，若某次过程中未能进行优化，可以提前退出：逐个考察顶点，在其出边上，判断以其为中介，能否使到达目标顶点的距离变小，若是则更新表格。...
2020-02-24 15:33:34
281
原创 pat甲级1030 dijkstra算法，多标准的两种处理方法
1、dijkstra同时处理多个标准。#include <cstdio>#include <climits>#include <algorithm>#include <stack>using namespace std;struct edge{ int dis, price; edge(){ dis ...
2020-02-24 11:19:42
261
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人