题目描述:

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9​​

因为​​nums[0] + nums[1] = 2 + 7 = 9​​​ 所以返回 ​​[0, 1]​​运行截图:

代码思路：

暴力写法 双重for循环 时间复杂度 O(n^2)

class Solution {public:vector<int> twoSum(vector<int>& nums, int target){vector<int>res;for(int i=0;i<nums.size();i++){for(int j=0;j<i;j++){if(nums[i]+nums[j]==target){res={j,i}; //记录答案break;}}if(res.size()>0) break;}return res;}};

使用 unordered<int,int>hash; 使用hash表进行优化，

建立key(元素)到value(下标)的映射，时间复杂度为O(n)。

class Solution {public:    vector<int> twoSum(vector<int>& nums, int target)    {        vector<int>res;        unordered_map<int,int>hash;        for(int i=0;i<nums.size();i++)        {            int another=target-nums[i];            if(hash.count(another))            {               res=vector<int>{hash[another],i};               break;            }            hash[nums[i]]=i;        }        return res;    }};

题目描述：

反转一个单链表。

示例:

输入: ​​1->2->3->4->5->NULL​​​ 输出:​​5->4->3->2->1->NULL​​ 进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

运行截图：

代码思路：

/*======= 非递归版 ====== */class Solution {public: ListNode* reverseList(ListNode* head) { if(!head) return NULL; //链表为空，返回 NULL auto a=head,b=head->next; //a指向头结点，b指向头结点的下一个结点 while(b) { auto c=b->next; b->next=a; //反转 a=b; b=c; } head->next=NULL; return a; }};/*========== 递归版本 =========== */class Solution {public: ListNode* reverseList(ListNode* head) { if(!head||head->next==NULL) return head; auto tail=reverseList(head->next); head->next->next=head; head->next=NULL; return tail; }};

题目描述

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

输入: ​​"()"​​​ 输出: ​​true​​ 示例 ​​2:​​

输入:​​"()[]{}"​​​ 输出:​​true​​ 示例 ​​3:​​

输入: ​​"(]"​​​ 输出: ​​false​​ 示例 ​​4:​​

输入: ​​"([)]"​​​ 输出: ​​false​​ 示例 ​​5:​​

输入: ​​"{[]}"​​​ 输出: ​​true​​运行截图

代码思路：

1.遇到 ‘(’,’{’,’[’ 入栈

2.遇到’)’,’]’,’}’,判断栈顶元素和当前元素是否匹配

若不匹配，直接返回 false

否匹配，让当前栈顶元素出栈

3.重复上述过程

class Solution {public:    bool isValid(string s) {        stack<char> st;        for(int i = 0; i < s.size(); i++)        {            if(s[i] == '(' || s[i] == '[' || s[i] =='{')   st.push(s[i]);            if(s[i] == ')')            {                if(!st.empty() && st.top() == '(')  st.pop();                else return false;            }            if(s[i] == ']')            {                if(!st.empty() && st.top() == '[')  st.pop();                else return false;            }            if(s[i] == '}')            {                if(!st.empty() && st.top() == '{')  st.pop();                else return false;            }        }        return st.empty();    }};