309. Best Time to Buy and Sell Stock with Cooldownclass Solution { public:int maxProfit(vector<int>& prices) {if(prices.size() < 2) return 0;vector<int> buy(prices.size(), 0);vector<int> sell(prices.size(), 0);buy[0] = -prices[0];for(int ii = 1; ii < prices.size(); ii++) {buy[ii] = max(buy[ii-1], sell[max(0, ii-2)] - prices[ii]);sell[ii] = max(sell[ii-1], buy[ii-1] + prices[ii]);}return max(0, max...
999. 可以被一步捕获的棋子数(C++) 1 题目描述2 示例描述2.1 示例 22.2 示例 22.3 示例 3 3 解题提示4 解题思路5 源码详解(C++) 1 题目描述在一个 8 x 8 的棋盘上,有一个白色的车(Rook),用字符 ‘R’ 表示。棋盘上还可能存在空方块,白色的象(Bishop)以及黑色的卒(pawn),分别用字符 ‘.’,‘B’ 和 ‘p’ 表示。不难看出,大写字符表示的是白棋,小写字符表示的是黑棋。 车按国际象棋中的规则移动。东,西,南,北四...
139. Word Breakclass Solution { public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> DP(s.size()+1, false); // 动态规划,表示此前的串是否为真DP[0] = true;for(int ii = 0; ii < s.size(); ii++) {if(DP[ii]) {for(auto word : wordDict) {int jj = ii + word.size();if(jj <= s.size() && s.substr(ii, word.size()) == word) DP[jj] = true;}}}return DP[s.size()];} };
1.解答 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。 原题链接:https://leetcode-cn.com/problems/two-sum/ 下面是我写的代码: #include<iostream>void main() {/***********数据部分**************/int num[4] = { 2,6,7,8 };int target = 13;/**************处理部分**************/int output[2];//for (int i = 0; i < sizeof(num) / sizeof(num[...
198. House Robberclass Solution { public:int rob(vector<int>& nums) {int a = 0, b = 0;for(int ii = 0; ii < nums.size(); ii++) {int temp = b;b = max(nums[ii] + a, b);a = temp;}return b;} };class Solution { public:int rob(vector<int>& nums) {if(nums.size() == 0) return 0;if(nums.size() == 1) return nums[0];vector<int> DP(nums.size(), 0);DP[0] = nums[0];DP[1] = nums[1];if(nums.size() > 2) DP[2] = num...
995. K 连续位的最小翻转次数在仅包含 0 和 1 的数组 A 中,一次 K 位翻转包括选择一个长度为 K 的(连续)子数组,同时将子数组中的每个 0 更改为 1,而每个 1 更改为 0。 返回所需的 K 位翻转的最小次数,以便数组没有值为 0 的元素。如果不可能,返回 -1。 示例 1: 输入:A = [0,1,0], K = 1 输出:2 解释:先翻转 A[0],然后翻转 A[2]。示例 2: 输入:A = [1,1,0], K = 2 输出:-1 解释:无论我们怎样翻转大小为 2 的子数组...
跟435题一样,都是先排序。 class Solution { public:int removeCoveredIntervals(vector<vector<int>>& intervals) {int size=intervals.size();if(size<2) return 0;sort(intervals.begin(),intervals.end(),[] (const auto& u,const auto& v){if(u[0]==v[0])return u[1]>v[1];elsereturn u[0]<v[0];});auto it=intervals.begin();int res=0,second=(*it)[1];for(++it;it!=intervals.end();++it){if(second>=(*it)[1])++res;els...
95. 不同的二叉搜索树 II 难度中等776 给定一个整数 n,生成所有由 1 ... n 为节点所组成的 二叉搜索树 。 示例: 输入:3 输出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解释: 以上的输出对应以下 5 种不同结构的二叉搜索树:1 3 3 2 1\ / / / \ 3 2 1 1 3 2/ / \ 2 ...
都是用动态规划去做; 123题 class Solution { public:int maxProfit(vector<int>& prices) {int size=prices.size();int buy1=-prices[0],sell1=0,buy2=-prices[0],sell2=0;for(int i=1;i<size;++i){sell2=max(sell2,buy2+prices[i]);buy2=max(buy2,sell1-prices[i]);sell1=max(sell1,buy1+prices[i]);buy1=max(buy1,-prices[i]);}return sell2;} };188题 class Solution { public:int maxProfit(int k, vector<int>& prices) {if...
730. 统计不同回文子序列给定一个字符串 S,找出 S 中不同的非空回文子序列个数,并返回该数字与 10^9 + 7 的模。 通过从 S 中删除 0 个或多个字符来获得子序列。 如果一个字符序列与它反转后的字符序列一致,那么它是回文字符序列。 如果对于某个 i,A_i != B_i,那么 A_1, A_2, ... 和 B_1, B_2, ... 这两个字符序列是不同的。 示例 1: 输入: S = bccb 输出:6 解释: 6 个不同的非空回文子字符序列分别为:b, c, bb, cc, bc...
没什么好说的,滑就是了…… class Solution { public:vector<int> findAnagrams(string s, string p) {vector<int> res;vector<int> dic(26),window(26);for(char c:p)++dic[c-'a'];for(int pl=0,pr=0;pr<s.size();++pr){++window[s[pr]-'a'];while(pr+1>pl+p.size())--window[s[pl++]-'a'];if(window==dic)res.push_back(pl);}return res;} };
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转(例如, [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] )。 请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。 示例 1: 输入:nums = [4,5,6,7,0,1,2], target = 0 输出:4示例 2: 输入:nums = [4,5,6,7,0,1,2], target = 3 输出:-1示例 3: 输入:nums = [1], target = 0 输出:-1文字题解 二分查找 思路和算法 对于有序数...
C++描述 LeetCode 567. 字符串的排列??大家好,我叫亓官劼(q guān ji ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博主目前仅在CSDN中写博客,唯一博客更新的地址为:亓官劼的博客 ,同时正在尝试在B站中做一些内容分享,B站主页为: 亓官劼的B站主页本文原创为亓官劼,请大家支持原创,部分平台一直在恶意盗取博主的文章!!! 若需联系博主,可以联系本人微信:qiguanjie2015给定两个字符串 s1 和 s2,写一个函...
173. 二叉搜索树迭代器 难度中等322 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例:BSTIterator iterator = new BSTIterator(root); iterator.next(); // 返回 3 iterator.next(); // 返回 7 iterator.hasNext(); // 返回 true iterator.next(); // 返回 9 iterator.hasNext(); // 返回 true iterator.next(); // 返回 15 iterator....
145. 二叉树的后序遍历 难度中等515 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3] 12/3 输出: [3,2,1] 进阶: 递归算法很简单,你可以通过迭代算法完成吗?1、迭代 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(n...