力扣20 ，有效的括号 ，栈
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
stack<char> z;
int i=0;
while(s[i]!='\0'){
if(s[i] == '('||s[i]=='['||s[i]=='{'){
z.push(s[i]);
}else{
if(z.size()==0){
printf("false");
return 0;
}
if(s[i]==')'&&z.top()=='(')z.pop();
else if(s[i]==']'&&z.top()=='[')z.pop();
else if(s[i]=='}'&&z.top()=='{')z.pop();
else {
printf("false");
return 0;
}
}
i++;
}
if(z.size()==0){
printf("true");
}else{
printf("false");
}
return 0;
}
力扣206，链表反转（面试考）
定义一个永远指向第一个元素的dummy指针，让head指针固定不变，将head.next接在前面实现反转。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *dummy = head;
while(head!=NULL&&head->next!=NULL){
ListNode *cdummy = dummy;
ListNode *hnext = head->next;
dummy = hnext;
head->next = hnext->next;
hnext->next = cdummy;
}
return dummy;
}
};
力扣389，找不同，s串中出现就减，t串中出现就加。哈希表
理解一下s[i]-‘a’， char z=i+‘a’;
class Solution {
public:
char findTheDifference(string s, string t) {
int ls=s.length(),lt=t.length();
int n[26]={0},i;
for(i=0;i<ls;i++){
n[s[i]-'a']--;
}
for(i=0;i<lt;i++){
n[t[i]-'a']++;
}
for(i=0;i<26;i++){
if(n[i]!=0){
char z=i+'a';
return z;
}
}
return ' ';
}
};
力扣496，找下一个最大值，数据结构，栈加哈希表(值得背一背)
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> a;
map<int,int> b;
int l1=nums1.size(),l2=nums2.size(),i;
for(i=0;i<l2;i++){
while(a.size()!=0&&nums2[i]>a.top()){
int t=a.top();
b[t]=nums2[i];
a.pop();
}
a.push(nums2[i]);
}
while(a.size()!=0){
int t=a.top();
b[t]=-1;
a.pop();
}
vector<int> ans(l1,-1);
if(l1==0) return ans;
for(i=0;i<l1;i++){
ans[i]=b[nums1[i]];
}
return ans;
}
};
力扣141，快慢指针判断循环链表。如果慢指针追上了快指针，就说明是循环链表。
/**
*Definition for singly-linked list.
*struct ListNode{
* int val;
* ListNode *next;
* ListNode(int x):val(x),next(NULL){}
*};*/
class Solution{
public:
bool hasCycle(ListNode *head){
ListNode *s=head,*q=head;
if(haed==NULL) return false;
//只需要判断快指针，因为快指针存在，慢指针也会存在
while(q!=NULL&&q->next!=>NULL&&q->next->next!=NULL){//这三个指针必须同时都存在，否则会越界
s=s->next;
q=q->next->next;
if(s==q) return true;
}
return false;
}
}
力扣704，二分法。。。啥也不说了，背哇
关键：high=nums.size()-1; (low<=high) high=mid-1； low=mid+1；
class Solution {
public:
int search(vector<int>& nums, int target) {
int mid,low=0,high=nums.size()-1;
if(nums.size()==1) {
if(nums[0]==target) return 0;
else return -1;
}
while(low<=high){
mid=(high+low)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid] > target){
high = mid-1;
}else if(nums[mid] < target){
low = mid+1;
}
}
return -1;
}
};
力扣1456，定长子串中元音的最大数目，滑动窗口
class Solution {
public:
int maxVowels(string s, int k) {
set<char> yy;
yy.insert('a');
yy.insert('e');
yy.insert('i');
yy.insert('o');
yy.insert('u');
int i,l=s.length();
int coust=0,ans=0;
for(i=0; i<k; i++){
if(yy.find(s[i])!=yy.end()){
coust++;
}
ans=max(ans,coust);
}
for(i=k; i<=l; i++){
if(yy.find(s[i]) != yy.end() ){
coust++;
}
if(yy.find(s[i-k]) != yy.end() ){
coust--;
}
if(coust<=k){
ans=max(ans,coust);
}
}
return ans;
}
};
力扣22，括号生成，回溯法
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
hishu(result,0,0,n,"");
return result;
}
void hishu(vector<string>& result,int left,int rigth,int n, string str){
if(left==rigth&&rigth==n){
result.push_back(str);
return;
}
if(left<rigth){
return;
}
if(left<n) {
hishu(result,left+1,rigth,n,str+"(");
}
if(left>rigth){
hishu(result,left,rigth+1,n,str+")");
}
}
};
力扣78
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
vector<vector<int>> subsets(vector<int>& nums){
dfs(nums,0);
return ans;
}
void dfs(vector<int>& nums,int num){
if(num==nums.size()){
ans.push_back(tmp);
return;
}
tmp.push_back(nums[num]);
dfs(nums,num+1);
tmp.pop_back();
dfs(nums,num+1);
}
};
力扣200 岛屿数量（dfs）
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int hang=grid.size(),lie=grid[0].size();
int i,j,ans=0;
for(i=0;i<hang;i++){
for(j=0;j<lie;j++){
if(grid[i][j]=='1'){
ans++;
dfs(grid,i,j,hang,lie);
}
}
}
return ans;
}
void dfs(vector<vector<char>>& grid,int nhang,int nlie,int hang,int lie){
if(nhang<0||nhang >= hang||nlie<0||nlie >= lie) return;
if(grid[nhang][nlie]=='0') return;
grid[nhang][nlie]='0';
dfs(grid,nhang+1,nlie,hang,lie);
dfs(grid,nhang,nlie+1,hang,lie);
dfs(grid,nhang-1,nlie,hang,lie);
dfs(grid,nhang,nlie-1,hang,lie);
}
};