LeetCode 每日三题( 第1天) 【 1. 两数之和 + 206. 反转链表 + 20. 有效的括号】题解

左手的ㄟ右手 2021-07-24 21:53 230阅读 0赞

##### [LeetCode 1. 两数之和 ][LeetCode 1. _] #####

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

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

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

因为`nums[0] + nums[1] = 2 + 7 = 9`  
所以返回 `[0, 1]`  
**运行截图:**  
![在这里插入图片描述][20201112204420120.png_pic_center]

**代码思路：**  
暴力写法 双重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;
        }
    };

##### [LeetCode 206. 反转链表][LeetCode 206.] #####

**题目描述：**  
反转一个单链表。

示例:

输入: `1->2->3->4->5->NULL`  
输出:`5->4->3->2->1->NULL`  
进阶:  
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？  
**运行截图：**  
![在这里插入图片描述][20201112204836123.png_pic_center]

**代码思路：**

/*======= 非递归版 ====== */
    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;
        }
    };

##### [LeetCode 20. 有效的括号][LeetCode 20.] #####

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
注意空字符串可被认为是有效字符串。

示例 1:

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

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

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

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

输入: `"{[]}"`  
输出: `true`  
**运行截图**  
![在这里插入图片描述][20201112205247883.png_pic_center]

**代码思路：**  
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();
        }
    };

[LeetCode 1. _]: https://leetcode-cn.com/problems/two-sum/
[20201112204420120.png_pic_center]: /images/20210724/849e8f36650f44f28f8dc9e19ce7a4db.png
[LeetCode 206.]: https://leetcode-cn.com/problems/reverse-linked-list/
[20201112204836123.png_pic_center]: /images/20210724/9bb33ce483594ca387d2c73446b9e386.png
[LeetCode 20.]: https://leetcode-cn.com/problems/valid-parentheses/
[20201112205247883.png_pic_center]: /images/20210724/05aa9bc9626a419c8db2686f41494f0a.png