- 博客(57)
- 收藏
- 关注
RSS订阅原创 DL：overfitting
各个激活函数的优缺点过拟合：检测：train_loss下降，val_loss上升，val_loss最低的点就是最好的参数，test_data用来测试模型的好坏解决：
2021-08-28 13:44:40
129
原创 二维网格图上的DFS+回溯 LeetCode.79/1219
引言：在图（无论网格图还是什么图）上dfsdfsdfs遍历的时候，我们都需要给访问过的点设置标记，以免访问访问过的点（反复横跳、循环遍历一个环）。但是，有些情况下我们需要正确的遍历某一个特定的方向才能得到正确的答案（例：得到最大的值、拼成一个单词）。如果，我们先遍历了一个错误的方向，把一些点做上了标记。那么回溯到正确的点的正确的方向时，那些本应该是正确答案的点都访问不了了。所以我们回溯的时候需要状态重置，即访问完这个点a的可访问的邻接点的时候，我们需要将这个点的标记取消。这样当我们回溯到点aaa后面一.
2020-09-13 13:13:50
241
原创 LeetCode 301.删除无效的括号 DFS/BFS
题目链接：https://leetcode-cn.com/problems/remove-invalid-parentheses/首先，先说下这题很恶心，没给数据量。这道题感觉类似于什么括号匹配的题目（用右括号去匹配左括号），而且是最小，可能是贪心这类的，但是这道题要求的是所有可能的结果，多出来的可能是左括号、也可能是右括号，且删掉一个可能使前面kkk个字符满足了有效括号，后面的删除结果也要随之改变了。既然直接做会很麻烦，那么就暴力地去删除每一个字符，然后再对删除了一个的每一个串去删除第二个括号。.
2020-09-12 23:02:18
160
原创 LCP 19.秋叶收藏集 动态规划
题目链接：https://leetcode-cn.com/problems/UlBDOe/这道题拿到手上，直接懵了，感觉dp、贪心什么的都不对，因为题目好像不存在什么序的关系。但是，仔细想想，最后一个叶子必然为红色段（如果叶子本身为yyy，那么肯定要改成rrr），那么到最后一片叶子前面总共修改了几次，那么就看前n−1n-1n−1片叶子总共修改了几次（此时似乎出现了子结构），但是第n−1n-1n−1片叶子可以是处于阶段2（即yyy叶子段）、也可以是处于阶段3（即rrr叶子段）（此时似乎出现了决
2020-09-12 21:47:05
173
原创 归并排序 && 快速排序 时间复杂度分析 （基本递归时间复杂度分析）
归并排序归并排序：利用分治的思想，先排左边一半，再排右边一半，最后再将两边有序的合并起来。时间复杂度: 用T(n)T(n)T(n)表示排大小为nnn的数组的时间:T(n)=2T(n/2)+nT(1)=1T(n)=2T(n/2)+n T(1)=1T(n)=2T(n/2)+nT(1)=1关于如何解这个递归方程，这里介绍其中一种，我们假设n是2的幂:首先，我们递推关系式的两边同时除以n，得到:T(n)n=T(n/2)n/2+1\frac{T(n)} {n}=\frac{T(n/2)}{n/2}+1n
2020-09-11 13:47:14
1926
原创 LeetCode 1575 计数型动态规划（自底向上 + 自顶向下）
题目链接：https://leetcode-cn.com/problems/count-all-possible-routes/#define LL long longclass Solution {private: static constexpr LL MOD = 1e9 + 7; int dp[105][205], n; // dp：最优子结构 到达终点的方案数肯定由到达其他点的,不同油量的方案数求和 // 搜索：反过来 在第 i 个城市到达 fin 的方
2020-09-09 21:29:30
278
原创 LeetCode 1579 贪心 && 并查集 （隐式最小生成树）
首先要明确的是：只需要将这个图构造成一棵树，就可以遍历整个图。所以，我们需要通过边来生成一颗树（但是这棵树是没有权值的），生成一个无权无向无环图。同时，这道题还需要构造两棵树，因为对于Alice和Bob来说都需要连通。很明显，在这里贪心地先选择类型3的边来构造生成树，因为这里对A和B来说都能连通两个点。然后再选择类型2和类型1，这两个先后顺序随意，因为是分别对A和B来说。那么按照题意，我们需要删一些边，也就是选一些边来构造树的时候，有些边不需要选。那么很明显，当目前的这个边连通的两个点已经在一...
2020-09-09 16:51:00
83
原创 CrashCourse CS Note
3.布尔逻辑和逻辑门not, and, or, xor(异或)等布尔逻辑操作都是由晶体管并联（串联）组成的。4.二进制32-bit/64-bit代表计算机一块块处理数据，每块是32位或64位。浮点数的存储：第1位表示正负，后面八位是指数，最后23位是有效数字：-0.231*1023ASCII:二进制来表示字符Unicode:ASCII的超集GIF/MP3：用二进制编码图片和声音5.算术逻辑单元（ALU）算术单元：通过逻辑门实现算术单元，像加法就是异或Xor和And组成通过half-
2020-09-07 16:47:21
129
原创 如何使用Git？（关于本地、远程仓库、分支详解）
Git是分布式版本控制系统，客户端是把代码仓库完整地镜像下来。Git中的文件的三种状态：已修改、已暂存（对一个已修改文件的当前版本做标记，让它包含在下次快照中）、已提交（完成了一次快照）。这也对应了三个阶段：工作目录、暂存区域、Git仓库。本地Git仓库两种获取Git仓库的方式：1、将尚未进行版本控制的本地目录转化为Git仓库；首先cd进项目目录，然后git init初始化一个仓库，该命令创建了一个名为.git的子目录，这个子目录含有初始化的Git仓库中所有的必须文件。但是，此时项目里的文件.
2020-08-31 23:09:43
328
原创 快速得到某段区间的左端点和右端点
为了快速得到一段连续区间的左右端点：利用左端点，快速求得右端点；利用右端点，快速求得左端点。我们可以建立两个左右端点映射L,R。L[p]映射这段连续区间的左端点，R[p]映射这段连续区间的右端点：给区间[l,r], L[r]=l, R[l]=r。1. LeetCode 352传送门：https://leetcode-cn.com/problems/data-stream-as-disjoint-intervals/submissions/分析题意，直接可以分两种情况。1、val在某段区间里，.
2020-08-23 17:18:44
1445
原创 状态压缩dp例题+分析
牵扯到选不选，而且选择达到的目标给的范围很小的时候，多半可以压缩状态。AcWing 1243： https://www.acwing.com/problem/content/description/1245/#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<string>#in.
2020-08-19 16:43:22
220
原创 状态压缩：LeetCode 1542
题目链接：https://leetcode-cn.com/problems/find-longest-awesome-substring/这道题感觉和前缀和的巧妙运用这两个题目有点像，也是子串（子数组）满足某个条件，这里是子串里至多有一个数字出现过奇数次，其余都是偶数次，然后求符合这个条件的子串的最大长度。首先思考下暴力该怎么做：遍历每个数字，然后统计每个数字出现的次数，对于符合条件的子串必定是这样s[0...i−1]s[i...j]s[0...i-1]s[i...j]s[0...i−1]s[i.
2020-08-11 20:30:38
289
原创 前缀和的巧妙运用：LeetCode 560/1546
题目链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/class Solution {public: int subarraySum(vector<int>& nums, int k) { //2e4 unordered_map<int, int> rec; rec[0] = 1; int sum = 0, ans = 0; for .
2020-08-11 15:51:46
219
原创 LeetCode 632.最小区间
传送门：https://leetcode-cn.com/problems/smallest-range-covering-elements-from-k-lists/这道题一上来就蒙圈了，感觉没什么套路，模板。需要明确的是，答案必定是某个列表里的最小值，然后其他列表里都是取的第一个大于等于它的数。那么我们需要在迭代中更新答案，初始区间肯定是由每个列表里的最小值组成 （因为我们需要在相同大小区间里取左端点最小的，所以从小的开始更新）。那么，我们该如何更新呢？大概也就是去掉目前的最小值bi，而让第二.
2020-08-01 10:35:05
102
原创 C++11实现STL list以及内置迭代器
定义拷贝赋值 ：多利用公共操作，这里拷贝赋值的实现中选择利用定义好的拷贝构造一个rhs的副本，然后swap（必须是三次移动），利用这个副本是本地变量，离开作用域后自动析构的原因，节省了代码量。类里访问对象的私有成员 ：一个对象的私有成员在类外是不能通过对象用.运算符访问的，但是在类内例外，即使像拷贝赋值，依然可以使用形参对象的私有成员。将迭代器设置为（内嵌）类 ：返回类型不能都是引用 ：在begin()、end()这样的返回类型为迭代器的函数里，我们用tail(head)初始化了一个迭代器对象，但这.
2020-07-28 21:13:53
204
原创 LeetCode 5465/图论/dfs
传送门：https://leetcode-cn.com/problems/number-of-nodes-in-the-sub-tree-with-the-same-label/题意很清楚，一眼看过去就知道是dfs子树，然后到根节点的时候统计，并且这里都是小写字母，开个26大小的全局数组统计即可。但是，每个子树的字母出现个数都是相互独立的。因为是深度优先，假如我只开一个一维的全局统计数组，那么左子树的个数会影响到右子树的结点统计。所以，要为每个结点都开一个统计数组（所以cnt[][ ]），按照编号区.
2020-07-19 14:31:40
124
原创 C++中的虚函数(virtual)
class base{public: virtual void f(){cout << "base" << ends;}};class derived : public base{public: virtual void f(){cout << "derived" << ends;}};int main(void){ derived a; // a.f(); 静态类型 直接输出derived，什么类型就是什么类型
2020-07-15 11:44:03
130
原创 原地哈希/LeetCode [41/442/448]
这种原地哈希算法适用于和正整数有关，且数字范围和数组长度有关的题目里，映射之后能利用映射关系（下标和值一一对应）来找到解。1.题目链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/由于不能使用额外空间，哈希表等其他数据结构就无法使用了。我们采取一种特殊的原地哈希：f(nums[i]) = num[i] - 1,也就是将值为nums[i]的数字映射到nums[i]-1的下标位置，例：3映射到数.
2020-06-27 22:19:35
328
原创 LeetCode单调栈总结
1.LeetCode496.下一个更大元素Ⅰ这里我们需要找到右边第一大的元素，此时如果从左往右遍历每个数，维护一个数据结构时，每个元素相当于存在此数据结构里，等着右边大的数来找到它，而当右边大的数比栈顶元素大的时候，说明这个栈顶元素已经找到了右边第一个比它大的元素，那就将它pop掉，然后当前元素继续和栈顶元素比较直到空栈或者栈顶元素比其大的时候，然后再将这个元素放入栈中，等着右边的元素继续来找。整个操作其实是在维护一个从栈底到栈顶递减的栈。 int n = nums1.size();
2020-06-13 19:40:01
146
原创 [LeetCode 837]:动态规划
题目链接:https://leetcode-cn.com/problems/new-21-game/class Solution {public: double new21Game(int N, int K, int W) { double dp[K + W]; for(int i = 0;i <= W + K - 1;++i){ if(K <= i && i <= N) dp[i] =.
2020-06-03 23:28:09
414
原创 文档/代码编辑器实用快捷键
快速光标移动到行尾: End快速光标移动到行首: Home快速选中一行: Shift + Home (光标在行尾) Shift + End (光标在行首)快速操作网页布局: Win + 左方向键(网页显示在左半边) Win + 右方向键(网页显示在右半边) Win + 上方向键(网页全局显示) Win + 下方向键(网页不断缩小)剪切板: Win + V代码编辑器部分:注释: Ctrl + /前缩进: Ctrl + [后缩进: Ctrl + ]...
2020-06-02 11:59:30
432
原创 Uva 11181/条件概率
题目链接：https://vjudge.net/problem/UVA-11181设Ei为第i个人购买了产品，E为有r个人购买了。条件概率公式：P(Ei | E) = P(Ei E) / P(E)然后全排列算出所有r个人购买的概率累加就是分母，分子就是第i个人购买的时候概率累加，因此我们只需要设置一个数组，记录哪些分支里第i个人是否购买，然后到最后的时候判断一下，把第i个人购买的情况的概率做个累加就是分子了。#include<cstdio>#include<cstring&.
2020-05-30 18:58:46
140
原创 LeetCode 974/前缀和/哈希表/取模和取余
子数组串 -> 暴力+前缀和 -> TLE同余定理：这里使用同余定理：(a-b)/m为整数 -> a与b对模m同余对模m同余：当两个整数除以同一个正整数n，若得相同余数（正数），则…所以(pre[j]-pre[i - 1])modK==0 -> pre[j] mod K == pre[i - 1] mod K这样我们就不用管i的位置了，只要统计pre[i - 1] mod K这个结果在前面已经遍历过程中出现了几次就可以了，自然想到实现一个字典（以取模的结果为key，valu..
2020-05-27 13:44:26
354
原创 LRU/LeetCode 146
题目链接：https://leetcode-cn.com/problems/lru-cache/快速查找到这个元素不难想到：哈希表。关键是如何再设计一个数据结构去O(1)删除和插入，这样子的话很明显必须是个线性结构了（链表、栈、队列（这俩个只能在头尾）等），但是发现我们可能需要在线性结构中间删除某个元素（当key相同的时候，我们需要更新value），假如不会出现相同值的情况也只能用deque（因为头尾都需要可以进行操作），所以我们在这里选择链表。那么就很好办了，哈希映射链表中的位置（迭代器），因为
2020-05-25 16:25:04
119
原创 前序遍历/二叉树/LeetCode 5418
题目链接：https://leetcode-cn.com/problems/pseudo-palindromic-paths-in-a-binary-tree/要想排列成为回文，那么这个路径上出现过奇数次的数不能超过1个，不然无法构成回文。第一个想法，用一个集合在树上记录，如果集合出现了root->val，那么就erase，否则insert，这样到最后如果集合里的元素大于1个，说明不止一个数出现了偶数次。注意题目的细节：结点的值是从1~9，我们可以直接设置1至9的计数器，而不用选择集合。.
2020-05-24 14:22:12
68
原创 LeetCode 76/滑动窗口/双指针
设置两个字典（哈希表实现），因为这里相同字符可能出现多次，而s的子串必须出现同样多次的t中出现过的字符。总体思路：1.先不断移动右指针，当window里出现了全部need里的字符的时候（覆盖了t时）。2.这个时候开始不断移动左指针，同时更新最短窗口的起点和长度。一旦window里某个字符比need要少了，停止移动左指针，改为移动右指针。（因为答案可能是交叠出现的）class Solution {public: string minWindow(string s, string t) ..
2020-05-23 12:34:12
126
原创 位运算/LeetCode 260/LeetCode 136
题目链接:https://leetcode-cn.com/problems/single-number/TC:O(n),MC:O(1) 如此一来，暴力和利用哈希表(最坏情况是前面n/2都是出现了两次的数，这样所需要开辟的内存空间还是达到了O(n)级别)都不可以了。题目中有个信息很重要：n-1个数都出现了两次，联系到位运算中的异或：a^a=0,0^a=a,并且a^b^a=(a^a)^b=0^b=b，位运算是满足交换律和结合律的，自然题目就解决了，一开始用0去异或每一个数，这样最后异或完的必定是只出现一.
2020-05-22 12:30:12
144
原创 前序/中序遍历/树的重建/LeetCode 105
题目链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/首先，要明白preorder和inorder的关系，preorder中的第一个往往是那颗(子)树的根节点，在inorder中就可以把序列分为左右两半（左树、右树）。这里选择前序遍历构造树：也就是先构造根节点，再构造左子树和右子树。如何构造：首先我们知道preorder的第一个就是根节点，而不知道下一个结点究竟.
2020-05-22 10:58:03
83
原创 动态规划/LeetCode 5
递推顺序：dp(i+1,j-1) -> dp(i,j) ，也就是说当右下标枚举到j-1的时候，i+1的状态必须更新过，所以要把i放在里层循环。正着推的时候，j肯定在j-1后面更新。class Solution {public: string longestPalindrome(string s) { string ans; int n = s.size(); if(n < 2) return s; vector&l..
2020-05-21 23:42:38
115
原创 状态压缩/LeetCode 1371
暴力枚举起点i和终点j，同时还要预处理做前缀和，用pre(i,k)表示前i个字符第k个元音字符出现的次数。TC:O(n2)，TLE。解题关键在于偶数次，我们需要知道一个前提事实：偶数-偶数=偶数，奇数-奇数=偶数。也就是说当我们遍历到第j个字符时，这时五个元音的奇偶出现次数为一个状态，假如遍历到i个字符(i < j)，这时五个元音的奇偶出现次数和第j个是一样的话，j-i就是满足题意的一个子串的长度（所有元音都出现过偶数次）。也就是说我们要记录遍历到每个字符时，前面的所有元音的状态。然后不断更新..
2020-05-20 23:32:17
316
原创 拓扑排序/LeetCode 210
bfs利用入度来进行访问，将所有入度为0的都push进队列，因为那都有可能是起点。利用入度：class Solution {private: // 存储有向图 vector<vector<int>> edges; // 存储每个节点的入度 vector<int> indeg; // 存储答案 vector<int> result;public: vector<int> fin.
2020-05-17 15:27:01
137
原创 char和int
char本身其实就是一定范围的int，有符号范围为：-128~128，当我们给一个字符c赋值的时候，其实是把那个字符的对应的ASCII码给了那个变量。所以我们对char做位运算的时候，和对int做位运算一样的，都是转化为2进制，因为char也其实存的就是个十进制的数。char c = '2';//是把2的ASCII（10进制）码赋给了cchar c = 2; //是把ASCII码2给了cint main(void){ char a = 50; //储存了个ASCII码 pr.
2020-05-14 21:33:25
858
原创 多阶段决策/动态规划/Uva 116
回溯法中，每做一次决策，都会生成对于一个当前节点产生一颗子树，结点的层数就是“下一个待填充位置”cur。 ——刘佳汝dp不过就是回溯的返回值用一个表存储起来了，在这里每列都是解答树的一层，每层都要做出决策，而决策就是从前一列可移动过来的格子。很明显，dp(i,j)设为状态，代表(i,j)最小的转移cost。转移方程就是从可移动的三个位置取最小值，然后加上当前格子的cost。要注意的是：这题是环形矩阵，细节看代码。#include<iostream>#include<cs..
2020-05-08 23:28:09
149
原创 动态规划/最优子结构/LeetCode 221/LeetCode 1277
LeetCode 221 传送门这题，最开始想用搜索/暴力做，尝试过后，感觉实在麻烦。这题，关键还是要看出最优子结构，从而使用动态规划。每个为1的小方块，要想和大方块合并成为一个更大的方块，只能从 以左上、上方、左边的小方块为右下角的大方块那转移过来，而且只能从这四个里面选一个最小的，不然的话，无法保证其他两个边都有。定义状态：dp[i][j] 以 matrix[i][j] 为右下角的正方形的最大边长。（定义成面积虽然更直观，但是转移的时候很麻烦，要开更号求边长）递推方程：dp(i,j) = m.
2020-05-08 23:04:46
123
原创 泰勒展开式
一句话概括泰勒展开式：用多项式去无限逼近一个函数，就是将某个函数在一个点上泰勒展开。如何推导？不用管，记住公式就行了。蕴含的思想：某个点的变化掌握在一阶导数里，一阶导数的变化在二阶导数里，往后类推。为什么需要展开？（泰勒展开有什么用？）1.方便求一些函数值，因为泰勒展开是多项式，而多项式的值一般都很好求，只要代入变量，就可求出因变量。而很多函数的函数值很难求，例如si...
2020-05-08 17:00:37
1121
原创 LeetCode 572/前序遍历
主体思路就是，前序遍历这颗树，遇到值相同的，用另一个函数判断是否完全一致，不完全一致继续遍历（因为后面可能才出现子树相同的结构），否则返回true。判断函数，很多细节见代码。class Solution {public: bool isSubtree(TreeNode* s, TreeNode* t) { if(s == NULL) return false;...
2020-05-07 23:38:03
90
原创 递推/前缀和/Uva 12627
这题需要发现前一个时间段的图会成为后一个时间段的左上、右上、左下部分，而右下全是蓝色。假如题目需要的是在2k-1行前面的气球数，直接用上一张图这么多行的气球数×2就可以了。而如果需要2k-1行后面的，就需要上一张图里的前i-2k-1的，因为后面一张图的后半部分的气球数和以前一张图的是一样的（右下角都是蓝色）。这题还需要用到前缀和的思想，r1~r2的气球数，就用f(k,r2)-f(k,r1-...
2020-05-07 23:32:05
106
原创 使最大值最小化/Uva 714/二分/贪心
按照题目意思，我们需要找一个x，使得每组被分到的书的总页数都小于x，且这个x得最小。很明显，这个x的范围是：max~sum之间的，我们只需要从小到大枚举这么多数字，然后让检验是否满足前面一个条件即可。但是，分组的时候一定是贪心的分，即每个组被分到的书的总页数都尽量要贴近x，这样x才有可能是最小的，当需要的抄写员过多的时候，x一定小了，一定要抄写员等于所给的k的第一个x就是答案。降低时间复杂...
2020-05-07 23:17:59
219
原创 LeetCode 983最低票价/记忆化搜索/动态规划
此题来自：https://leetcode-cn.com/problems/minimum-cost-for-tickets/这道题刚开始打算用所给的天数直接搜索，即每一个要乘车的天数，都穷举选票策略，然后保留一个参数当作这个票的期限（剩下多少天可以继续乘车）。换个思路，当前第i天买哪个票最划算取决于买个这个票后的i+1/i+7/i+30天之后继续花的钱最少（这是一个贪心策略，很明显如果买了...
2020-05-06 12:17:26
151
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人