【蓝桥杯速成】| 3.数据结构

题目一：两数之和

问题描述

1. 两数之和 - 力扣（LeetCode）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

解题步骤

从数组中找出和为目标值的两个数字，返回其数组下标

用最简单的思维就是嵌套循环来一套，

遍历到一个以后，再去遍历下一个符合要求的，即可暴力求解

int size=nums.size();
for(int i=0;i<size;i++){for(int j=i+1;j<size;j++){if(nums[i]+nums[j] == target){return {i,j}}}
}

暴力解法固然方便，但如果有时间限制呢？O(n^2)可经不起考验

那么如何使用更小的时间复杂度解决问题呢？

我们得换一种数据结构来解决

考虑值的同时还需要记录下标，这种既要又要的条件只有哈希表能满足

选择unordered_map，以nums数组的值作为键，数组的索引作为值

这样可以调用map的find函数，实现直接定一求一，不需要再去遍历，就减小了时间复杂度

unordered_map<int,int> record;
for(int i=0;i<nums.size();i++){record[nums[i]]=i;
}

已经转存完毕！那么可以开始找可以配对的值了

for(int i =0;i<size;i++){if(record.find(target-nums[i]) ！= record.end() ){if(record.find(target-nums[i]) ！= i){return{record[target-nums[i]],i};}}
}

观察上面两个循环，发现是一样的，为了进一步简化代码，可以边存边找

for(i=0;i<nums.size();i++){auto iter = record.find(target-nums[i]);//iter为迭代器，遍历键值对if(iter != record.end()){return{iter->second,i};//每个键值对包含两个部分：键（first）和值（second）}else{record.insert(pair<int, int>(nums[i], i));//把该索引和元素转化为一对存入记录中}
}

题目二：有效的括号

问题描述

20. 有效的括号 - 力扣（LeetCode）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

解题步骤

这个题目就是典型的栈的应用，利用后进先出原则，可以很方便的完成括号配对

具体操作为：

先初始化一个空栈，按顺序读入括号

是右括号就存入，是左括号就弹出栈顶元素进行匹配，

匹配正确则弹出，不正确就return false

stack<char> r;
//先修理一下
if(s.size()%2){//不能被2整除肯定有多的return false;
}for(char c:s){if(c=='{' || c=='(' || c=='[')r.push(c);if(c=='}'){if (r.empty()) return false;  // 栈为空，无法匹配char temp=r.top();//获取栈顶元素r.pop();if(temp != '{')return false;}if(c==')'){if (r.empty()) return false;  // 栈为空，无法匹配char temp=r.top();//获取栈顶元素r.pop();if(temp != '(')return false;}if(c==']'){if (r.empty()) return false;  // 栈为空，无法匹配char temp=r.top();//获取栈顶元素r.pop();if(temp != '[')return false;}
}
return r.empty();//如果最后栈不为空就会返回false，为空就有效

在这个代码实现过程中，有几个需要注意的点，

一开始可以做个初步判断，如果匹配那么字符串长度一定为偶数

后续匹配过程要避免空栈错误，假如输入是"}["这一类，不加if (r.empty()) return false;这行代码一定报错

再就是这个代码目前看来重复思路很多，还可以进一步优化

目前的代码为了体现相应代码的匹配逻辑，才有了三个if

为了统一这个匹配逻辑，在一个if中解决三类括号

我们可以在遍历到右括号时存入相应左括号，这样遇到左括号直接进行匹配即可，不需要管它是什么类型(堪比秦始皇统一六国的壮举啊！！！)

stack<char> r;
//剪枝操作
if(s.size()%2){//不能被2整除肯定有多的return false;
}
for(char c:s){//存入所有左括号的对应右括号，这样后续只需要匹配就可以if(c=='{')   r.push('}');else if(c=='[')  r.push(']');else if(c=='(')  r.push(')');//开始匹配else if(r.empty() || r.top()!=c){return false;}else r.pop();//匹配了就弹出该元素
} 
return r.empty();//如果最后栈不为空就会返回false，为空就有效