Featured image of post LeetCode 热题 100 (1)
代码 比赛

LeetCode 热题 100 (1)

前14题

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]

示例 3：

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

两数之和

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>hash_map;
        for(int i=0;i<nums.size();i++)
        {
            auto it =hash_map.find(target-nums[i]);
            if(it !=hash_map.end())
            {
                return {it->second,i};
            }
            hash_map[nums[i]]=i;
        }
        return{};
    }
};

解法

使用unordered_map对数组进行遍历，查看另一半是否在unordered_map中，不在就加入，存在就返回

49. 字母异位词分组

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

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

示例 1:

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

示例 2:

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

示例 3:

输入: strs = [“a”] 输出: [[“a”]]

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for(string& str:strs){
            string key =str;
            sort(key.begin(),key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for(auto it = mp.begin();it!=mp.end();++it){
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

解法

接着使用unordered_map 前边是排序后的字符串，后边是为排序的字符串，然后打印出来

128. 最长连续序列

给定一个未排序的整数数组 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

示例 3：

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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> set;
        for(const int& num :nums){
            set.insert(num);
        }

        int l=0;

        for(const int &num:set){
            if(!set.count(num-1)){
                int temp=num;
                int now =1;

                while(set.count(temp+1)){
                    now+=1;
                    temp+=1;
                }
                l=max(l,now);
            }
        }
        return l;
    }
};

解法

先使用unordered_set去重，然后遍历set，只有处于第一位（n-1不存在）进入队列长度的计量。时间复杂度是O（n）

283. 移动零

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

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

示例 1:

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

示例 2:

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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int a=0,b=0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[b]!=0)
            {
                nums[a]=nums[b];
                a++;
                b++;
            }
            else
            {
                b++;
            }
        }
        for(;a < nums.size();a++)
        {
            nums[a]=0;
        }
    }
};

解法

双指针，一前一后，同时记录0的数量在最后给他补上（代码里好像没b什么事）

11. 盛最多水的容器

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

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

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

说明：你不能倾斜容器。

示例 1：

输入：[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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l =0,r=height.size()-1;
        int ans=0;
        while(l<r){
            int area=min(height[l],height[r])*(r-l);
            ans=max(ans,area);
            if(height[l]<=height[r]){
                l++;
            }
            else{
                r--;
            }
        }
        return ans;
    }
};

解法

使用双指针，从两边接近中间，偏小的一边前进，同时记录之间最大的面积

证明：因为高板前进必然会导致结果的减小，使用只能前进短板，同时排除一部分结果

x
x x
x x o
x o o x
x o x x x
o o x x x x

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出：Intersected at ‘8’

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
    if(headA==nullptr||headB==nullptr)
    {
        return nullptr;
    }
    ListNode *pa=headA, *pb=headB;
    while(pa!=pb)
    {
        pa = pa == nullptr ? headB : pa->next;
        pb = pb == nullptr ? headA : pb->next;
    }
    return pa;
};
};

解法

使用两个指针，分别类似倒8字遍历两条链，直到相交或者都为空（无相交）

证明：a+c+b==b+c+a

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

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

示例 3：

输入：head = [] 输出：[]

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* nex=head;
        ListNode* now=nullptr;
        ListNode* temp;
        while(nex!=nullptr)
        {
            temp=nex->next;
            nex->next=now;
            now=nex;
            nex=temp;
        }
        return now;
    }
};

解法

使用三个指针，两个负责反向，一个负责指向下一个位置

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1] 输出：true

示例 2：

输入：head = [1,2] 输出：false

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int x[50110];
        int num=0;
        while(head!=null)
        {
            x[num]=head->val;
            head=head->next;
            num++;
        }
        for(int i=0,j=num-1;i<j;i++,j--)
        {
            if(x[i]!=x[j])
            {
                return false;
            }
        }
        return true;
    }
};

解法

用数组将链表读取，然后双指针一左一右对进判断，时间复杂度O（n）

141. 环形链表

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：head = [1], pos = -1 输出：false 解释：链表中没有环

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    bool hasCycle(ListNode *head) {
    unordered_set<ListNode*> hash;
    while(head!=nullptr)
    {
        if(hash.count(head))
        {
            return true;
        }
        hash.insert(head);
        head=head->next;
    }
    return false;
    }
};

解法

使用unordered_set,对每个加入的节点搜索，看看有没有一样的（使用数组一样的，只是时间复杂度会高

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = [] 输出：[]

示例 3：

输入：l1 = [], l2 = [0] 输出：[0]

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* head;
    struct ListNode* p;
    if(list1==NULL&&list2==NULL)
    {
        return NULL;
    }

    if(list1!=NULL&&list2==NULL)
    {
        return list1;
    }
    if(list2!=NULL&&list1==NULL)
    {
        return list2;
    }


    if(list1->val>=list2->val)
    {
        head=list2;
        p=list2;
        list2=list2->next;
    }
    else
    {
        head=list1;
        p=list1;
        list1=list1->next;
    }
    while((list1!=NULL)||(list2!=NULL))
    {
        if(list1==NULL&&list2!=NULL)
        {
            p->next=list2;
            list2=list2->next;
            p=p->next;
            break;
        }
        if(list2==NULL&&list1!=NULL)
        {
            p->next=list1;
            list1=list1->next;
            p=p->next;
            break;
        }
        if(list1->val>=list2->val)
        {
            p->next=list2;
            list2=list2->next;
            p=p->next;
        }
        else
        {
            p->next=list1;
            list1=list1->next;
            p=p->next;
        }
    }
    return head;
}

解法

极度丑陋的代码，主要部分是维护三个指针，两个分别指着a，b，一个指着目标。但是需要考虑空，就需要超级多的if，else语句

94. 二叉树的中序遍历

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

示例 1：

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

示例 2：

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

示例 3：

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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    void inorder(TreeNode* root, vector<int>& res)
    {
        if (root==nullptr) {
            return;
        }
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root,res);
        return res;
    }
};

解法

传入一个栈，用res.push_back(root->val);压入

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：3

示例 2：

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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int deep (TreeNode* root,int d)
    {
        if(root==nullptr)
        {
            return d;
        }
        int l=deep(root->left,d+1);
        int r=deep(root->right,d+1);
        if(l>=r)
        {
            return l;
        }
        else{
            return r;
        }
    }
    int maxDepth(TreeNode* root) {
        int i=deep(root,0);
        return i;
    }
};

解法

二叉树大部分用的都是递归，取左+取右，比较

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]

示例 2：

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

示例 3：

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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==nullptr) return nullptr;
        TreeNode *temp=root->left;
        invertTree(root->left);
        invertTree(root->right);   
        root->left=root->right;
        root->right=temp;
        return root;
    }
};

解法

二叉树大部分用的都是递归，左子树先换，右子树再换，最后在根节点换

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

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

示例 2：

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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    bool fx(TreeNode* left,TreeNode* right){
        if(left==nullptr&&right==nullptr){
            return true;
        }
        if(left==nullptr&&right!=nullptr){
            return false;
        }
        if(left!=nullptr&&right==nullptr){
            return false;
        }
        if(left->val==right->val){
            int a=fx(left->left,right->right);
            int b=fx(left->right,right->left);
            if(a==true&&b==true){
                return true;
            }
            else{
                return false;
            }
        }
        return false;
    }
    bool isSymmetric(TreeNode* root) {
        return fx(root->left,root->right);
    }
};

解法

二叉树大部分用的都是递归，传入左右两个节点，对称的来比较

Licensed under CC BY-NC-SA 4.0
comments powered by Disqus
© 2025 dolly
2777619715@qq.com
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
代码来自：https://yeelz.com/post/564.html