力扣169
给定一个大小为 n
的数组 nums
,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋
的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
输入:nums = [3,2,3] 输出:3
示例 2:
输入:nums = [2,2,1,1,1,2,2] 输出:2
提示:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
进阶:尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
思路:
摩尔投票法。
因为最多的数字一定是大于n/2。所以不存在诸如3 3 2 4或者2 2 3 3这样的情况。也就是说,符合题目要求的情况都类似于 2 1 2,1 1 1 1 2 2这样子。
那么我们只要把相同数量的数字互相抵消,最后留下的就一定是最多的数字。
用ans记录当前哪个数字最多,count用来投票,遇到相同的+1,遇到不同的-1,当count=0的时候,更换ans,并重置count=1。
代码:
class Solution {
public:int majorityElement(vector<int>& nums) {int ans=nums[0];int count=1;for(int i=0;i<nums.size();i++){if(ans==nums[i])count++;else if(--count==0){ans=nums[i];count=1;}}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 <= 20
1 <= p.length <= 30
s
只包含从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 i=1;i<=s.length();i++){for(int j=1;j<=p.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]);*///cout<<dp[i][j]<<" ";}//cout<<endl;}//cout<<dp[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 - 1
pop
、top
和getMin
操作总是在 非空栈 上调用push
,pop
,top
, andgetMin
最多被调用3 * 104
次
思路:
用栈每次存取一个pair结构,pair的first是当前存入值,pair的second每次更新当前最小值。因为是栈的原因,每次存进来都在栈顶,所以很好去更新最小值。就是在一个元素出栈的时候,把总最小值变更为当前栈顶的second就好了。
代码:
class MinStack {
public:stack<pair<int,int> > s;int mmin=INT_MAX;MinStack() {}void push(int val) {if(val<mmin)mmin=val;s.push(pair<int,int>(val,mmin));}void pop() {s.pop();if(s.size()==0)mmin=INT_MAX;else mmin=s.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();*/