LeetCode-top-100

1 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

创建一个哈希表，对于每一个 x，首先查询哈希表中是否已存在 target - x，如果存在那么就已经找到了答案，不存在直接将 x 插入到哈希表中，方便下一次快速匹配。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;//创建哈希表
        vector<int> res(2, -1);
        for (int i = 0; i < nums.size(); i++) {
            if (mp.count(target - nums[i]) == 0) {
                mp.insert(pair<int, int>(nums[i], i));
            } else {
                res[0] = mp[target - nums[i]];
                res[1] = i;
                break;
            }
        }
        return res;
    }
};

2 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

将每一个字符串都进行排序得到唯一的序列，将序列用hash表保存起来，做映射，最后遍历hash表得到结果

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> hash;
        for(vector<string>::iterator it=strs.begin();it!=strs.end();it++){
            string str_tmp = *it;
            sort(str_tmp.begin(),str_tmp.end());
            hash[str_tmp].push_back(*it);
        }
        vector<vector<string>> res;
        for(unordered_map<string,vector<string>>::iterator it=hash.begin();it!=hash.end();it++){
            res.push_back(it->second);
        }
        return res;
    }
};
};

3 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int max_len = 0;
        unordered_set<int> st;
        for (auto num : nums)
            st.insert(num);
        for (auto num : st){
            if(st.find(num-1)==st.end()){
                int len=1;
                while(st.find(num+len)!=st.end())len++;
                max_len=max(max_len,len);
            }
        }
            return max_len;
    }
};

4 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int count = 0;
        for (vector<int>::iterator it = nums.begin(); it != nums.end();) {
            if (*it == 0) {
                nums.erase(it);
                count++;     
            } else {
                it++;
            }
        }
        for (int i = 0; i < count; i++){
            nums.push_back(0);
        }
    }
};

5 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

img

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

双指针法，初始化i、j为两端，取height最小的向右或者向左移，直到两端相遇

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1, MAX = -1;
        while(i < j){
            MAX = height[i] > height[j] ? 
    max(MAX, (j-i) * height[j--]):max(MAX, (j-i)* height[i++]);
        }
        return MAX;
    }
};

6 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        int N = nums.size();
        for (int i = 0; i < N; i++) {
            if(nums[i] > 0) break;//当nums[i]大于零的时候,nums[l]和nums[r]必定大于零
            if(i != 0 && nums[i] == nums[i-1])continue;//去重，跳过
            int l = i+1;
            int r = N-1;
            while(l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if( sum == 0 ){
                    res.push_back({nums[i],nums[l],nums[r]});
                    while( l+1 < r && nums[l] == nums[l+1]) l++;//去重
                    while( r-1 > l && nums[r-1] == nums[r]) r--;//去重
                    l++;
                    r--;
                } else if(sum < 0) {
                    l++;
                } else if(sum > 0){
                    r--;
                }
            }
        }

        return res;
    }
};

7 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

输入：nums = [2,2,1]
输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

输入：nums = [1]
输出：1

一开始想法为对数组进行排序，再用栈进行匹配处理

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        stack<int> stk;
        sort(nums.begin(),nums.end());
        for(auto num:nums){
            if(!stk.empty() && num==stk.top()){
                stk.pop();
            }else{
                stk.push(num);
            }
        }
        return stk.top();
    }
};

在题解中看到异或运算 ：注意题目中的“除了某个元素只出现一次以外，其余每个元素均出现两次”，采用异或运算即可求出所需数字

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(auto num:nums){
            res ^= num;
        }
        return res;
    }
};

8 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

采用滑动窗口法解决，

如何移动？我们只要把队列的左边的元素移出就行了，直到满足题目要求！

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l = 0, r = 1;
        int res = 0;
        int n = s.size();
        while (r <= s.size()) {
            res = max(res, r-l);
            for (int i = l; i < r; i++) {
                if(s[i] == s[r]){
                    l = i + 1;
                    break;
                }
            }
            r++;
        }
        return res;
    }
};

9 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

img

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        for (int i = 0; i < numRows; i++) {
            vector<int> tmp;
            for (int j = 0; j <= i; j++) {
                if (j == 0 || i == j)
                    tmp.push_back(1);
                else {
                    tmp.push_back(res[i-1][j]+res[i-1][j-1]);
                }
            }
            res.push_back(tmp);
        }
        return res;
    }
};

10 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

一眼便知是二分查找算法

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0,r = n-1;
        int mid;
        while(l <= r){
            mid = (l + r) >> 1;
            if(nums[mid] == target) break;
            if(nums[mid] > target) r = mid - 1;
            if(nums[mid] < target) l = mid + 1;
        }
        return nums[mid]==target?mid:l;
    }
};

11 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

img

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

class Solution {
public:
    void mid_read(TreeNode* a, vector<int> & res){   
       if(a->left != NULL){//左
            mid_read(a->left, res);
        }
        res.push_back(a->val);//中
        if(a->right != NULL){//右
            mid_read(a->right, res);
        }
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root != NULL) mid_read(root, res);
        return res;
    }
};

12 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        int N = nums.size();
        do{
            vector<int> tmp;
            for(int i=0;i<N;i++){
                tmp.push_back(nums[i]);
            }
            res.push_back(tmp);
        }while(next_permutation(nums.begin(),nums.end()));

        return res;
    }
};

13 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res;
        int p_size = p.length(), s_size = s.length();
        if(p_size > s_size) return res; 
        vector<int> window(26, 0);
        vector<int> target(26, 0);
        for(int i = 0; i < p_size; i++){
            target[p[i] - 'a']++;
            window[s[i] - 'a']++;
         }
        if(target == window) res.push_back(0);
        for(int i = 1; i + p_size <= s_size; i++){
            window[ s[i - 1] - 'a'] --;
            window[ s[i + p_size - 1] - 'a'] ++;
            if(window == target) res.push_back(i);
        }

        return res;
    }
};

学会一个东西，容器可以直接比较

14.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思路：

1.用哈希表记录是否访问过

/**
 * 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) {
        unordered_map<ListNode*, bool> m;
        while(head!=NULL){
            if(m[head])return true;
            m[head] = true;
            head = head->next;
        }
        return false;
    }
};

2.采用快慢指针

链表如下所示，设线上有若干个节点。红指针为 fast，蓝指针为 slow。从头节点同时前进，fast 每次前进两个节点，slow 每次前进一个节点。

141_2.png

如下所示，fast 和 slow 先后入环。此时设 fast 与 slow 沿箭头方向的距离为 x。

141_3.png

因为 x 是整数且 fast 比 slow 快一个单位的速度，所以 fast 和 slow 再前进 x 次即可相遇。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr) return false;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
};