1.包含min函数的栈

一个比较简单的模拟栈的操作

cpp">class Solution {
public:void push(int value) {st[op++] = value;}void pop() {if(op)op--;}int top() {return st[op-1];}int min() {int mi = 10001;for(int i = 0;i<op;++i)mi = std::min(mi,st[i]);return mi;}
private:int st[310]{};int op = 0;
};

2.栈的压入、弹出序列

思考一下这道题的做法，无非就是用栈来模拟一下这个过程，比较简单

1. 借助一个辅助栈，来完成
   1. 按照pushV的顺序先插入到辅助栈中，和popV的元素去匹配

cpp">class Solution {
public:bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int>st;int n = pushV.size(),idx = 0;for(int i = 0;i<n;++i){st.push(pushV[i]);if(st.top() == popV[idx]){while(!st.empty()&&st.top() == popV[idx]){st.pop(),idx++;}}}return st.empty();}
};

3.翻转单词序列

采用两步反转法，先把整体的字符串反转，再把每个单词反转

cpp">class Solution {void reverse(string& s, int l, int r){while (l < r){swap(s[l++], s[r--]);}}
public:string ReverseSentence(string str) {int n = str.size();//时间复杂度O(n)，空间复杂度O(1)//两步反转法reverse(str, 0, n - 1);int l = 0, r = 0;while (l < n){while (l<n&&str[l] == ' ')l++;if (l >= n)break;r = l;while (r<n&&str[r] != ' ')r++;reverse(str, l, r - 1);l = r;}return str;}
};

4.滑动窗口的最大值

采用的是 set + 仿函数 的方式来解决这个问题，先把前size个数字加入到set中去，然后继续向后遍历，取出最大的，插入一个元素再删除一个元素

cpp">struct compare {bool operator()(const std::pair<int, int>& a,const std::pair<int, int>& b) const {if (a.first != b.first)return a.first > b.first;elsereturn a.second < b.second;}
};
class Solution {public:vector<int> maxInWindows(vector<int>& num, int size) {// write code hereset<pair<int, int>, compare>q; //从大到小进行排序vector<int> result;int n = num.size();if (size == 0 || size>n)return result;int i = 0;for (; i < size; ++i) {q.insert({num[i], i});}for (; i < n; ++i) {result.push_back(q.begin()->first);q.erase({num[i - size], i - size});q.insert({num[i], i});}result.push_back(q.begin()->first);return result;}
};

5.数组中出现次数超过一半的数字

方法一：双指针

cpp">class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param numbers int整型vector * @return int整型*/int MoreThanHalfNum_Solution(vector<int>& numbers) {// write code heresort(numbers.begin(),numbers.end());int n = numbers.size();int half = n/2;//双指针int left = 0;while(left<n){int val = numbers[left];int right = left;while(right<n&&numbers[right]==val)right++;if(right-left>half)return val;left = right;}return -1;}
};

方法二：分析

cpp">class Solution {
public:int MoreThanHalfNum_Solution(vector<int>& numbers) {// write code heresort(numbers.begin(),numbers.end());return numbers[numbers.size()/2];}
};

6.旋转数组的最小数字

python">class Solution:def minNumberInRotateArray(self , nums: List[int]) -> int:# write code herereturn min(nums)

7.字符串的排列

cpp">class Solution {vector<string>result;int vis[15]{};string path;int n;void dfs(string&s,int u){if(u == n){result.push_back(path);return;}for(int i = 0;i<n;++i){if(i>0&&s[i]==s[i-1]&&!vis[i-1])continue;if(!vis[i]){vis[i] = true;path.push_back(s[i]);dfs(s,u+1);path.pop_back();vis[i] = false;}}}
public:vector<string> Permutation(string str) {// write code heren = str.size();sort(str.begin(),str.end());dfs(str,0);return result;}
};

8.数字序列的某一位的数字

python">def find_nth_digit(n):length = 1count = 9start = 1while n > length * count:n -= length * countlength += 1count *= 10start *= 10num = start + (n - 1) // lengthdigit_index = (n - 1) % lengthreturn int(str(num)[digit_index])
class Solution:def findNthDigit(self , n: int) -> int:# write code herereturn find_nth_digit(n)