- 博客(757)
- 收藏
- 关注
RSS订阅原创 No.293 - LeetCode[790] Domino and Tromino Tiling - 经典dp
/* * @lc app=leetcode id=790 lang=cpp * * [790] Domino and Tromino Tiling */// @lc code=startclass Solution {public: int numTilings(int n) { const int mod = 1000000007; vector<vector<long long>> dp(3, vector<long
2021-09-17 18:17:19
236
原创 No.292 - LeetCode[852] Peak Index in a Mountain Array - 二分山峰数组
/* * @lc app=leetcode id=852 lang=cpp * * [852] Peak Index in a Mountain Array */// @lc code=startclass Solution {public: void bsearch(int L, int R, vector<int>& arr, int& loc, int& mx){ if(L+1 >= R){ if
2021-09-17 17:51:47
227
原创 No.291 - LeetCode[932] Beautiful Array - 构造题
/* * @lc app=leetcode id=932 lang=cpp * * [932] Beautiful Array */// @lc code=startclass Solution {public: vector<int> beautifulArray(int n) { vector<int> ans = {1}; while(ans.size() < n) { vector<i
2021-09-17 11:39:40
238
原创 No.290 - LeetCode[870] Advantage Shuffle - 优先队列贪心
/* * @lc app=leetcode id=870 lang=cpp * * [870] Advantage Shuffle */// @lc code=startclass Solution {public: vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) { priority_queue<pair<int,in
2021-09-16 16:45:36
139
原创 No.289 - LeetCode[901] Online Stock Span - 单调栈
单调栈模拟就行。/* * @lc app=leetcode id=901 lang=cpp * * [901] Online Stock Span */// @lc code=startclass StockSpanner {public: stack<pair<int,int>> s; int cnt; StockSpanner() { cnt = 0; } int next(int price)
2021-09-16 15:18:24
109
原创 No.288 - LeetCode[950] Reveal Cards In Increasing Order - 双端队列构造
逆向模拟构造题使用双端队列数据结构。/* * @lc app=leetcode id=950 lang=cpp * * [950] Reveal Cards In Increasing Order */// @lc code=startclass Solution {public: vector<int> deckRevealedIncreasing(vector<int>& deck) { int N = deck.size();
2021-09-15 14:55:23
79
原创 No.282 - LeetCode[1009] Complement of Base 10 Integer -位运算
/* * @lc app=leetcode id=1009 lang=cpp * * [1009] Complement of Base 10 Integer */// @lc code=startclass Solution {public: int bitwiseComplement(int n) { if(n == 0) return 1; int ans = 0; int mask = 0; while(n &g
2021-09-15 11:29:31
90
原创 No.287 - LeetCode[958] Check Completeness of a Binary Tree - BFS
/* * @lc app=leetcode id=958 lang=cpp * * [958] Check Completeness of a Binary Tree */// @lc code=start/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() :
2021-09-14 16:10:32
77
原创 No.286 - LeetCode[978] Longest Turbulent Subarray - 简单动态规划
/* * @lc app=leetcode id=978 lang=cpp * * [978] Longest Turbulent Subarray */// @lc code=startclass Solution {public: int maxTurbulenceSize(vector<int>& arr) { int N = arr.size(); if(N<=1){ return N;
2021-09-14 15:55:29
102
原创 No.285 - LeetCode[982] Triples with Bitwise AND Equal To Zero - 哈希降维
/* * @lc app=leetcode id=982 lang=cpp * * [982] Triples with Bitwise AND Equal To Zero */// @lc code=startclass Solution {public: int countTriplets(vector<int>& nums) { unordered_map<int, int> mp; int N = nums.si
2021-09-14 15:25:34
82
原创 No.284 - LeetCode[987] Vertical Order Traversal of a Binary Tree - DFS
c++的set，multiset，map遍历是有序的。/* * @lc app=leetcode id=987 lang=cpp * * [987] Vertical Order Traversal of a Binary Tree */// @lc code=start/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * Tre
2021-09-13 17:56:25
82
原创 No.283 - LeetCode[991] Broken Calculator - 数学题
没有想出好的搜索方案。这是一道数学题，根据题目可以写成如下公式：2^a * x - (2^b + 2^c + ....) = y所以，从y往x去算，更直接。/* * @lc app=leetcode id=991 lang=cpp * * [991] Broken Calculator */// @lc code=startclass Solution {public: int brokenCalc(int startValue, int target) {
2021-09-13 16:49:45
76
原创 No.281 - LeetCode[1013] Partition Array Into Three Parts With Equal Sum - 三子串和相等
这题有个坑，就是如果采用L->R 单向统计和为sum/3的子串时会存在：A，B，C，D，E 5个子串和都为sum/3，看似是false，但是通过重新切分，可以变为AB1, B2CD1, D2E 来组合成三个子串和为sum/3，见case71./* * @lc app=leetcode id=1013 lang=cpp * * [1013] Partition Array Into Three Parts With Equal Sum */// @lc code=startclass
2021-09-12 17:21:36
101
原创 No.280 - LeetCode[1019] Next Greater Node In Linked List - 单调栈
/* * @lc app=leetcode id=1019 lang=cpp * * [1019] Next Greater Node In Linked List */// @lc code=start/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {}
2021-09-12 17:02:15
78
原创 No.279 - LeetCode[1020] Number of Enclaves - 经典DFS
/* * @lc app=leetcode id=1020 lang=cpp * * [1020] Number of Enclaves */// @lc code=startconst int dirx[] = {0, 1, 0, -1};const int diry[] = {-1, 0, 1, 0};class Solution {public: void dfs(int i, int j, vector<vector<int>>& G,
2021-09-12 15:40:56
112
原创 No.278 - LeetCode[1031] Maximum Sum of Two Non-Overlapping Subarrays - 前缀和
思路如下代码，可以进一步内存优化，取消dp数组，直接用sum即可。/* * @lc app=leetcode id=1031 lang=cpp * * [1031] Maximum Sum of Two Non-Overlapping Subarrays */// @lc code=startclass Solution {public: int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int se
2021-09-12 15:06:14
105
原创 No.277 - LeetCode[1041] Robot Bounded In Circle - 模拟题
/* * @lc app=leetcode id=1041 lang=cpp * * [1041] Robot Bounded In Circle */// @lc code=startclass Solution {public: bool isRobotBounded(string str) { int x = 0, y = 0; vector<int> dirx = {-1, 0, 1, 0}; vector<i
2021-09-10 18:56:50
80
原创 No.276 - LeetCode[1049] Last Stone Weight II - 最优二分配01背包
/* * @lc app=leetcode id=1049 lang=cpp * * [1049] Last Stone Weight II */// @lc code=startclass Solution {public: int lastStoneWeightII(vector<int>& stones) { bitset<1501> dp = {1}; int sum = 0; for(int v
2021-09-10 16:10:48
102
原创 No.275 - LeetCode[1096] Brace Expansion II - 复杂模拟题
写了两个小时，非常麻烦的一道模拟题。关键在于，缓存字符串，和缓存数组嵌套判断，没有 case，这题过不了????/* * @lc app=leetcode id=1096 lang=cpp * * [1096] Brace Expansion II */// @lc code=startclass Solution {public: vector<string> duplicate(vector<vector<string>>& v
2021-08-13 04:07:01
189
原创 No.274 - LeetCode[779] K-th Symbol in Grammar - 思维
首先发现个规律：1，在n增大过程中，前半部分是不变的。2，n为偶数，对折后值相反3，n为奇数，中轴对称直接想法，倒着计算即可。/* * @lc app=leetcode id=779 lang=cpp * * [779] K-th Symbol in Grammar */// @lc code=startclass Solution {public: int kthGrammar(int n, int k) { int ans = 0; wh
2021-08-05 20:58:45
90
原创 No.273 - LeetCode[951] Flip Equivalent Binary Trees - dfs
左右子树交换，直接dfs匹配/* * @lc app=leetcode id=951 lang=cpp * * [951] Flip Equivalent Binary Trees */// @lc code=start/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeN
2021-08-02 19:37:13
77
原创 No.272 - LeetCode[861] Score After Flipping Matrix - 贪心
贪心/* * @lc app=leetcode id=861 lang=cpp * * [861] Score After Flipping Matrix */// @lc code=startclass Solution {public: int calculate(vector<vector<int>>& grid) { int N = grid.size(); int M = grid[0].size();
2021-08-02 19:18:28
91
原创 No.271 - LeetCode[941] Valid Mountain Array - 暴力
严格递增和递减数列，注意边界/* * @lc app=leetcode id=941 lang=cpp * * [941] Valid Mountain Array */// @lc code=startclass Solution {public: bool validMountainArray(vector<int>& arr) { int N = arr.size(); if(N <= 2) return false;
2021-08-02 14:55:48
63
原创 No.270 - LeetCode[1016] Binary String With Substrings Representing 1 To N - 暴力
判断从n到n/2即可，小于n/2都包含在其中。暴力匹配即可/* * @lc app=leetcode id=1016 lang=cpp * * [1016] Binary String With Substrings Representing 1 To N */// @lc code=startclass Solution {public: bool match(string& s, int loc, int k){ int N = s.length();
2021-08-02 14:41:54
100
原创 No.269 - LeetCode[1071] Greatest Common Divisor of Strings - 暴力模拟
纯暴力/* * @lc app=leetcode id=1071 lang=cpp * * [1071] Greatest Common Divisor of Strings */// @lc code=startclass Solution {public: bool check(string str, int k){ int N = str.length(); for(int i=0;i<N/k;i++){ for(
2021-08-01 17:30:38
103
原创 No.268 - LeetCode[798] Smallest Rotation with Highest Score - 动态规划
求解最大得分，不需要计算每个k的实际得分，只需要计算差值就行。从k=1的状态到k=2的状态，会有以下两种计分变化：1，一定只加1分，从位置0到位置N-1的元素一定是得分的2，减分若干，当元素值等于下标正好是0分，往左移动一个会减分，之后不会再减。当k继续增大时，依次类推。解释：N-nums[i]+i+1 是 元素 nums[i] 从起始位置移动k步 到达 下标为nums[i]的左侧/* * @lc app=leetcode id=798 lang=cpp * * [798] Smalle
2021-08-01 16:26:41
108
原创 在RC和RR下innodb的锁
事务： 事务是数据库区别与文件系统的重要特性之一，锁为事务服务，实现事务的特性，先来简单回归一下事务的各种特性。事务的ACID特性：事务有四种特性来保证事务能够很好地为我们服务。原子性(atomicity)一个事务要么全部执行，要么全部失败一致性(consistency)事务将数据库从一种一致的状态转变为下一种一致的状态，数据库的完整性约束没有被破坏隔离性(isolation)不同的事务之间不应该相互干扰持久性(durability)事务一旦提交就
2021-06-29 12:07:10
754
1
原创 No.267 - LeetCode[1138] Alphabet Board Path
/* * @lc app=leetcode id=1138 lang=cpp * * [1138] Alphabet Board Path */// @lc code=startclass Solution {public: // a->b string getPath(int a,int b) { if(a == b) return "!"; string ans; string suffix; if(a
2021-06-03 20:26:09
104
原创 No.266 - [1139] Largest 1-Bordered Square - 前缀和
前缀和预处理/* * @lc app=leetcode id=1139 lang=cpp * * [1139] Largest 1-Bordered Square */// @lc code=startclass Solution {public: int largest1BorderedSquare(vector<vector<int>>& grid) { int N = grid.size(); int M = g
2021-06-01 20:21:08
109
原创 No.265 - [1145] Binary Tree Coloring Game - 树遍历
边界样例有点多/* * @lc app=leetcode id=1145 lang=cpp * * [1145] Binary Tree Coloring Game */// @lc code=start/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() :
2021-05-31 20:58:12
85
原创 No.264 - LeetCode[695] Max Area of Island - 裸的dfs
/* * @lc app=leetcode id=695 lang=cpp * * [695] Max Area of Island */// @lc code=startclass Solution {public: int dfs(int x,int y, vector<vector<int>>& color, vector<int>& dirx, vector<int>& diry, vector<v
2021-05-07 19:57:46
72
原创 No.263 - LeetCode[689] Maximum Sum of 3 Non-Overlapping Subarrays
思路：前缀和预处理+dp求最大和+回溯路径1、前缀和预处理后，退化成一道，求间距k的3个数最大和（经典dp）。2、经典3维dp求最大和。3、记录每次变更时的当前下标，以便回溯路径。难点：有很多边界处理/* * @lc app=leetcode id=689 lang=cpp * * [689] Maximum Sum of 3 Non-Overlapping Subarrays */// @lc code=startclass Solution {public: vec
2021-04-29 15:47:52
71
原创 No.262 - leetcode[670] Maximum Swap
/* * @lc app=leetcode id=670 lang=cpp * * [670] Maximum Swap */// @lc code=startclass Solution {public: struct Node { int v; int loc; Node(int a, int b): v(a), loc(b) {} }; static bool cmp(const Node & a, con
2021-04-29 12:41:59
63
原创 No.261- LeetCode[611] Valid Triangle Number - 前缀和
/* * @lc app=leetcode id=611 lang=cpp * * [611] Valid Triangle Number */// @lc code=startclass Solution {public: int triangleNumber(vector<int>& nums) { int N = nums.size(); if(N < 3) { return 0;
2021-03-08 10:11:24
111
原创 sql: 删除重复行
DELETE leads_relationFROM leads_relation, ( SELECT min(id) id, agent_uid, customer_uid FROM leads_relation GROUP BY agent_uid, customer_uid HAVING count(*) > 1 ) leads_t2WHERE leads_relation.agent_uid = leads_t2.agent
2021-03-02 22:13:45
544
原创 C++: 重定向freopen打开与关闭
printf("输出到终端");// 重定向到文件freopen("in.txt", "r", stdin);// 清空缓冲区，避免把之前写到终端的字符读进来fflush(stdin);// 读入文件字符while(~scanf("%s", &ch)){ // dosomething}// 重定向回终端freopen("/dev/tty", "w", stdout);//如果是windows用//freopen("CON", "w", stdout);printf
2021-03-02 15:51:34
2604
原创 Mac: tmux实用工具
参考： http://www.ruanyifeng.com/blog/2019/10/tmux.html安装：# Ubuntu 或 Debian$ sudo apt-get install tmux# CentOS 或 Fedora$ sudo yum install tmux# Mac$ brew install tmux常用命令：\red{常用命令：}常用命令：启动：tmux新建会话：tmux new -s <session-name>列出会话
2021-02-26 16:13:59
185
1
原创 服务端：cookie和session的机制
参考：https://www.jianshu.com/p/b5efddc433f5cookie:客户端记录身份信息在http头中两个key专门用于cookieSet-Cookie：服务端响应http头部会带上，指示客户端建立一个cookie，直到这个cookie过期。一种cookie会保存在内存中，浏览器关闭就会清楚，另一种cookie会存放在硬盘中。Cookie：session：服务端记录身份信息...
2021-02-26 10:33:25
116
原创 No.260 - LeetCode[605] Can Place Flowers - 非常有意思的一道数组相邻题
分为三块：左侧0个数右侧0个数中间0个数在最后判断一下数组中是否有1/* * @lc app=leetcode id=605 lang=cpp * * [605] Can Place Flowers */// @lc code=startclass Solution {public: bool canPlaceFlowers(vector<int>& flowerbed, int n) { int N = flowerbed.size()
2021-02-24 00:16:25
84
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人