4a级旅游网站建设的要求,网络空间服务商,目前好的推广平台,郑州做景区网站建设公司力扣169
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
示例 1#xff1a;
输入#xff1a;nums [3,2,3]
输出#xff1…力扣169
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1
输入nums [3,2,3]
输出3
示例 2
输入nums [2,2,1,1,1,2,2]
输出2提示
n nums.length1 n 5 * 104-109 nums[i] 109
进阶尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
思路
摩尔投票法。
因为最多的数字一定是大于n/2。所以不存在诸如3 3 2 4或者2 2 3 3这样的情况。也就是说符合题目要求的情况都类似于 2 1 21 1 1 1 2 2这样子。
那么我们只要把相同数量的数字互相抵消最后留下的就一定是最多的数字。
用ans记录当前哪个数字最多count用来投票遇到相同的1,遇到不同的-1当count0的时候更换ans并重置count1。
代码
class Solution {
public:int majorityElement(vectorint nums) {int ansnums[0];int count1;for(int i0;inums.size();i){if(ansnums[i])count;else if(--count0){ansnums[i];count1;}}return ans;}
};
力扣10
给你一个字符串 s 和一个字符规律 p请你来实现一个支持 . 和 * 的正则表达式匹配。
. 匹配任意单个字符* 匹配零个或多个前面的那一个元素
所谓匹配是要涵盖 整个 字符串 s的而不是部分字符串。
示例 1
输入s aa, p a
输出false
解释a 无法匹配 aa 整个字符串。示例 2:
输入s aa, p a*
输出true
解释因为 * 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 a。因此字符串 aa 可被视为 a 重复了一次。示例 3
输入s ab, p .*
输出true
解释.* 表示可匹配零个或多个*任意字符.。提示
1 s.length 201 p.length 30s 只包含从 a-z 的小写字母。p 只包含从 a-z 的小写字母以及字符 . 和 *。保证每次出现字符 * 时前面都匹配到有效的字符
思路
xx题目真的无语题目意思表达地乱七八糟全靠解答错误的答案去判断到底是什么意思。
代码
class Solution {
public:bool isMatch(string s, string p) {//if(p.length()s.length())return 0;bool dp[35][35];memset(dp,0,sizeof(dp));dp[0][0] true;//if(p[p.length()-1]!.p[p.length()-1]!*p[p[p.length()-1]!s[s.length()-1]])return 0;for (int j 1; j p.length() 1; j) {if (p[j - 1] *) dp[0][j] dp[0][j - 2];}for(int i1;is.length();i){for(int j1;jp.length();j){ if (s[i - 1] p[j - 1] || p[j - 1] .) {dp[i][j] dp[i - 1][j - 1];} else if (p[j - 1] *) {if (s[i - 1] p[j - 2] || p[j - 2] .) {dp[i][j] dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];} else {dp[i][j] dp[i][j - 2];}}/*if(p[j-1]*p[j-2].)dp[i][j]dp[i-1][j-1]1;else if(p[j-1]*p[j-2]s[i-1])dp[i][j]max(dp[i-1][j-1]1,dp[i-1][j]1);else if(p[j-1].||p[j-1]s[i-1])dp[i][j]max(dp[i-1][j-1]1,dp[i][j-1]);else dp[i][j]max(dp[i][j-1],dp[i-1][j-1]);*///coutdp[i][j] ;}//coutendl;}//coutdp[s.length()][p.length()] s.length()endl;return dp[s.length()][p.length()];}
};
力扣115
设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
示例 1:
输入
[MinStack,push,push,push,getMin,pop,top,getMin]
[[],[-2],[0],[-3],[],[],[],[]]输出
[null,null,null,null,-3,null,0,-2]解释
MinStack minStack new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); -- 返回 -3.
minStack.pop();
minStack.top(); -- 返回 0.
minStack.getMin(); -- 返回 -2.提示
-231 val 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次
思路
用栈每次存取一个pair结构pair的first是当前存入值pair的second每次更新当前最小值。因为是栈的原因每次存进来都在栈顶所以很好去更新最小值。就是在一个元素出栈的时候把总最小值变更为当前栈顶的second就好了。
代码
class MinStack {
public:stackpairint,int s;int mminINT_MAX;MinStack() {}void push(int val) {if(valmmin)mminval;s.push(pairint,int(val,mmin));}void pop() {s.pop();if(s.size()0)mminINT_MAX;else mmins.top().second;}int top() {return s.top().first;}int getMin() {return s.top().second;}
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj new MinStack();* obj-push(val);* obj-pop();* int param_3 obj-top();* int param_4 obj-getMin();*/
