【蓝桥杯速成】| 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 ，判断字符串是否有效。

有效字符串需满足：

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

解题步骤

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

具体操作为：

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

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

匹配正确则弹出，不正确就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，为空就有效

总结

一般来说哈希表都是用来快速判断一个元素是否出现集合里。

栈用于匹配问题