- 博客(129)
- 收藏
- 关注
RSS订阅原创 股票买卖 6题：
121-只允许买卖一次n * 2 空间的dp表：class Solution {public: int maxProfit(vector<int>& prices) { const int n = prices.size(); if (n == 0) return 0; // 初始化第0天的情况 vector<vector<int>> dp(n, vector<int>
2020-07-27 02:10:01
255
原创 剑指Offer 38：字符串的全排列
解法一：完全按照之前回溯法专题总结中，有重复元素数组的全排列方法来做，string也可以看做是一种数组（因为一开始陷入了对未排序 string 进行回溯+剪枝的思路，尝试了引入set等方法都半途折戟。最后还是要排序）class Solution {public: vector<string> permutation(string s) { sort(...
2020-05-06 16:40:43
152
原创 LeetCode 543：二叉树的直径
class Solution {public: int ans = 0; int diameterOfBinaryTree(TreeNode* root) { //ans = 1; dfs(root); return ans; } int dfs(TreeNode* root) { if(!ro...
2020-05-06 16:40:29
182
原创 LeetCode 31 数组的下一个排列
class Solution {public: void nextPermutation(vector<int>& nums) { int i = nums.size() - 2; while(i >= 0 && nums[i+1] <= nums[i]) { i--; ...
2020-05-06 16:32:05
118
原创 数据结构实现系列
一、两个栈实现一个队列class CQueue {public: CQueue() { } stack<int> s1, s2; void appendTail(int value) { s1.push(value); } int deleteHead() { if(!s2.em...
2020-05-06 15:55:14
118
原创 剑指Offer 68：二叉树的最近公共祖先
68-1 二叉搜索树的最近公共祖先循环搜索： 当节点 root 为空时跳出；当 p, q都在 root 的 右子树 中，则遍历至 root.right ；否则，当 p, q 都在 root 的 左子树 中，则遍历至 root.left ；否则，说明找到了 最近公共祖先 ，跳出。返回值： 最近公共祖先 root 。 TreeNode* lowestCommonAncesto...
2020-05-02 21:47:42
107
原创 LeetCode 8：字符串转换成整数
需要考虑各种特殊情况特殊处理： int strToInt(string str) { int len = str.length(); int i = 0; long long num = 0; while(str[i] == ' ') { i++; } bool f...
2020-05-02 21:22:08
119
原创 算法题总结3：二分查找专题
剑指Offer 53-1原始版本：找到左右边界，再返回。（缺点：容易出错，比较麻烦）class Solution {public: int search(vector<int>& nums, int target) { const int n = nums.size(); int left = 0, right = n - ...
2020-04-28 23:13:34
303
原创 LeetCode 72：编辑距离
一维动态规划：爬楼梯二维动态规划：编辑距离第一次根据思路写程序，在字符串如何切片，取[1:]被卡住了：class Solution {public: int minDistance(string word1, string word2) { }private: int minDistanceRecu(string word1, str...
2020-04-07 15:52:50
106
原创 回溯法系列：全排列系列问题、N皇后问题、矩阵中的路径、机器人的运动范围
class Solution {public: vector<vector<string>> solveNQueens(int n) { //vector<vector<string>> ans; vector<string> board(n, string(n, '.')); //初始化n*n...
2020-04-06 23:33:49
252
原创 接雨水两题：LeetCode 42/407
42 接雨水-一维动态编程，存储每个位置向左与向右的最大值，实现O(n)的时间复杂度。有一个容易出错的地方：计算向左/右的最大高度时，要把自己本身的高度也计算进去。（但是我感觉不应该包括。。。）一开始不通过的代码：class Solution {public: int trap(vector<int>& height) { const...
2020-04-06 15:41:04
128
原创 剑指Offer 16：简单快速幂|板子题
第一种写法：递归形式、二分思想class Solution {public: double myPow(double x, int n) { if(n == 0) return 1; if(n == 1) return x; if(n == -1) return 1/x; if(n % 2 == 0) { ...
2020-04-04 23:00:07
82
原创 面试题14：剪绳子
14-1：DP做法，思路比较好class Solution {public: int cuttingRope(int n) { if(n <= 1) return 0; vector<int> dp(n+1, 1); for(int i = 2; i <= n;...
2020-03-27 16:56:50
140
原创 LeetCode 999：车的可用捕获量
这道题只需要模拟题意即可。分方向讨论时也有一些基本的编程经验，如dx, dy方向数组分开设置比较方便。class Solution {public: int numRookCaptures(vector<vector<char>>& board) { if(board.size() != board[0].size()) return...
2020-03-27 00:05:34
93
原创 回文串/回文序列系列题：647回文子串个数/ 5最长回文子串/ 516最长回文子序列
647. 回文子串：计数字符串中回文子串的个数1、中心延展法：中心可以取为字母，或两个字母的间隙。class Solution {public: int countSubstrings(string s) { const int n = s.length(); int ans = 0; for(int i = 0; i < ...
2020-03-26 23:25:59
206
原创 贪心算法系列：435 无重叠区间 452 用最少数量的箭引爆气球
参考：https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/tan-xin-suan-fa-zhi-qu-jian-tiao-du-wen-ti贪心算法求解区间调度问题： 正确的思路其实很简单，可以分为以下三步： 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。...
2020-03-23 17:26:48
143
原创 DFS/BFS 系列：LC 365 水壶问题
方法1：BFS，C++版本写起来很繁琐，Python很简洁using PII = pair<int, int>; //分别是x, y中的水量，作为状态量class Solution {public: PII op(int index, const PII& cur, int x, int y) { switch (index) { ...
2020-03-22 21:37:04
414
原创 LeetCode 2：两数相加
一个不起眼的Bug来源：循环中再次定义的变量，会在本循环中覆盖之前的同名变量，而且每次循环之后会释放该变量。引发不能进位、错误进位两种错误。class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode dummy(0); List...
2020-03-21 23:34:22
87
原创 LeetCode : 股票买卖进阶4道题
123：限制买卖次数为2Bug：变量命名用的不好引起了低级错误！不要用k表示常亮，容易在之后写错。class Solution {public: int maxProfit(vector<int>& prices) { const int n = prices.size(); if(n <= 1) return 0;...
2020-03-21 11:47:48
175
转载 pip使用国内镜像源快速安装
pip源更改至清华、阿里镜像，可以提高安装速度以及成功率临时使用：可以在使用pip的时候加参数：-ihttps://pypi.tuna.tsinghua.edu.cn/simple例如：pip install -ihttps://pypi.tuna.tsinghua.edu.cn/simplesklearn，这样就会从清华这边的镜像去安装sklearn库。阿里源地址为：htt...
2020-03-12 21:06:30
2615
原创 双系统下win10安装第二个版本的cuda因为默认安装引起的系统重启失败崩溃和解决之路
一、问题描述 3.8号中午1点多，我准备在win10系统下安装第二个版本的cuda，以支持PyTorch1.2 GPU版本的顺利运行。原来的cuda版本是9.0，现在需要安装9.2的。简单搜了两篇博客，尤其其中一篇：https://blog.csdn.net/zsc201825/article/details/91149550，给我带来了很大的误导。。。。。当时看完觉得没什么要特...
2020-03-10 01:16:56
2664
原创 剑指Offer 64：滑动窗口的最大值
这道题一个月之前在LeetCode上做过https://blog.csdn.net/chengda321/article/details/104150828然而在思路上卡了2个地方(想到用单调队列，想到队列存放索引而不是数值)在实现上也出现了好几处漏洞：初始化第一个窗口之后就要把第一个窗口的结果保存，之后的遍历从第二个窗口开始就可以了。以及窗口的更新：比较的是新加入的最后一个元素，而...
2020-03-07 12:33:30
77
原创 LeetCode 994：腐烂的橘子
多源+BFS，代码也因此可以分为两阶段。Bug1 ：注意边界case：如果一开始全是腐烂橘子，直接就是返回0而不应该是-1，因此引入变量ansBug2：基本语法问题，循环里定义的变量在循环结束后都释放了，因此ans定义在循环外class Solution {private: int cnt = 0; //网格中剩余1的个数,初始化为0 int dist[10][10...
2020-03-06 16:59:03
119
原创 LeetCode ：95/96 不同的二叉搜索树 (二叉搜索树组合的个数)
参考力扣上官方的题解，采用动态规划法，关键点在于：1、状态转移公式的推导；2、边界的处理：dp[0]也初始化为1，因为+=的存在，dp除0,1之外，后面的都要初始化为0class Solution {public: int numTrees(int n) { if(n <= 1) return n; vector<int>...
2020-02-28 21:44:57
190
原创 LeetCode： 91 解码方法
这道题一开始以为是简单的递归问题，按照从前往后的顺序递归，总是在“10”这个输入上报错。按照从后向前的方法递归，应对短序列没有问题，但是面对长序列，因为存在大量重复计算，所以超时。如果用递归来做，应该用记忆化递归！class Solution {public: int numDecodings(string s) { //if(s == "0" || s =...
2020-02-27 23:59:08
722
原创 LeetCode：516 最长回文子序列
典型的动态规划题，可以用递归、迭代两种形式来解。首先引用一篇讲子序列问题的好文章：子序列问题通用思路|最长回文子序列以下内容引自上文：子序列问题是常见的算法问题，而且并不好解决。首先，子序列问题本身就相对子串、子数组更困难一些，因为前者是不连续的序列，而后两者是连续的，就算穷举你都不一定会，更别说求解相关的算法问题了。而且，子序列问题很可能涉及到两个字符串，比如前文「最长...
2020-02-27 22:53:08
150
原创 LeetCode：1143 最长公共子序列 583 两个字符串的删除操作
因为处理边界的不方便，自己想出了用Padding技巧来做，注意在 if 语句中 i, j 要减一class Solution {public: int longestCommonSubsequence(string text1, string text2) { int m = text1.length(), n = text2.length(); ...
2020-02-27 22:32:49
172
原创 LeetCode：5 最长回文子串
这道题与516题有一定的相似，只是一个是回文子序列，返回的是长度。一个是回文子串，返回的是字符串。一个比较好的解法汇总：动态规划、Manacher 算法一开始看了别人的思路，但是自己怎么写都不通过，后来发现原因在于：dp[i][j] = len==1 || len==2 || dp[i+1][j-1] && (s[i] == s[j]); 没有加括号，导致的后果：...
2020-02-27 17:51:36
95
原创 LeetCode 198：打家劫舍
简单的DP问题，因为状态转移方程仅仅和当前元素的前几个节点有关，因此不需要维护一个dp一维数组，和跳台阶问题一样，仅仅需要维护几个元素即可。class Solution {public: int rob(vector<int>& nums) { if(nums.empty()) return 0; int n...
2020-02-26 17:25:00
92
原创 LeetCode：300 最长上升子序列 (最优方法是：动态规划 + 二分法)
第一种简单粗暴地解法：递归求解状态转移方程，属于Up-Down方法，因为子问题的重复求解，导致时间复杂度O(2^n)一个语法点：想用全局变量，可以直接设置类的成员变量，不应该像 java 那样用 static 静态变量！这一点很容易被忽视！class Solution {private: int max; int f(vector<int>&a...
2020-02-26 16:08:37
200
1
原创 Win10/Ubuntu16.04 双系统下在Ubuntu系统安装CUDA10.1 cudnn7.6 PyTorch1.4
是一次花费了不少精力的安装，看了很多博文和经验贴，以下方法在我的笔记本上可用硬件配置：惠普暗影精灵4，GTX1060显卡一、安装cuda1.1 选择cuda版本 安装cuda之前要先确认自己的GPU是否支持cuda，安装开始我自己陷入了一个误区，以为不同型号的GPU支持的cuda版本有限，而疲于搜索1060显卡对应的cuda版本，实际上nvidia官网上列出来的支持cu...
2020-02-25 00:28:12
1177
1
原创 LeetCode：第177场周赛 1361
class Solution {public: bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) { deque<int> q; q.push_back(0); ...
2020-02-23 15:47:16
88
原创 LeetCode：215 数组中第K大的数
class Solution {public: int findKthLargest(vector<int>& nums, int k) { if(nums.size() < k || k < 1) return -1; int left = 0, right = nums.size()-1; while(...
2020-02-22 16:36:18
210
原创 LeetCode 147：对链表进行插入排序
指针的操作比较繁琐复杂，需要捋清楚再写，中间犯了3个错误：class Solution {public: ListNode* insertionSortList(ListNode* head) { if(!head || !head->next) return head; //Bug2:不应该是nullptr，应该是head ListNod...
2020-02-22 12:20:49
140
1
原创 LeetCode：212 单词搜索Ⅱ
这道题是DFS+前缀树，是一道标准的模板题这里面的Tire类的定义写的方法与之前的208略有不同，但基本上一样。只是单独定义了一下TireNode节点类。//定义节点，类/结构体class TireNode {public: TireNode(){ } bool isEnd = false; vector<TireNode*> next...
2020-02-19 14:53:28
113
原创 LeetCode：208 实现字典树
基础的数据结构，实现方法完全可以根据思路背下来。class Trie {private: bool isEnd; Trie* next[26];public: /** Initialize your data structure here. */ Trie() { isEnd = false; memset(next, 0...
2020-02-18 13:05:29
103
原创 剑指Offer：52 正则表达式的匹配
1、递归的灵活运用，尤其是多种情况下如何递归返回2、字符串的基本性质：char* str 向后移动不能str++，必须str+13、各种情况考虑必须严谨，不然很容易漏掉一些可能通过的匹配模式，比如：（1）'*'前字符相同也可以跳过不匹配；（2）pattern为'.'时要匹配还需要此时str不为'\0'class Solution {public: bool match...
2020-02-12 12:38:56
105
原创 剑指Offer：37 二叉树的序列化
这道题是今天做的5道二叉树习题中最难的一道了，主要因为对C++/C中的几种字符串的操作不熟悉，花了很多时间理清楚语法基础：C++ 字符串与字符数组 详解/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : ...
2020-02-12 00:27:53
94
原创 剑指Offer ：63 数据流中的中位数
很经典的一道题，书上的思路解析也非常好。面对这样的数据流问题，首先需要建立容器存储数据流：（1）数组、链表排序数组：插入时间复杂度为 O(n)，查找为O(1)；无序数组：插入时间复杂度 O(1)，查找为O(n)排序链表：插入时间复杂度 O(n)，查找为O(1)（2）二叉搜索树 BST平均情况下(左右子树比较平衡)，插入为O(logn)，查找中位数也是O(logn)最差的情...
2020-02-11 21:48:52
85
原创 LeetCode：62 二叉搜索树第K小的节点
这道题不久前在LeetCode上做过，二叉搜索树的中序遍历序列就是单调递增的。解法：递归的中序遍历，遍历到第k个节点结束递归返回；结果也作为参数列表的一部分：这是递归调用不知道如何返回结果时的一种变通的做法。注意 result 初始化为 nullptr，这样不足k个节点时，会返回nullptr。class Solution {public: TreeNode* KthNode...
2020-02-11 18:20:34
111
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人