leetcode面试100题
原创Posted Updated 数据结构41 minutes read (About 6105 words)0 visits

leetcode面试100题

版权申明：本文为原创文章，转载请注明原文出处

原文链接：http://example.com/post/4d65bd11.html

leetcode面试100题

111

合并两个有序数组（简单）

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

1
2
3
4
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

思路

从后往前存数组的值，因为从前往后存会改变nums[1]前面没有用的值，所以尝试将较大值存在Nums[1]后面

代码

1
2
3
4
5
6
7
8
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int end=(m--)+(n--)-1;
        while(end>=0&&end!=m)
            nums1[end--]=(m<0||(n>=0&&nums2[n]>=nums1[m]))?nums2[n--]:nums1[m--];
    }
};

填充每个节点的下一个右侧节点指针Ⅱ（中等）

题目描述

给定一个二叉树：

1
2
3
4
5
6
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

示例 1：

img 
1
2
3
输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

思路

BFS，但是不用额外的空间，比如遍历了第二层所有节点并连接了，只需要直到第二层的首节点，便可通过next找到下一个节点

代码

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
class Solution {
public:
    Node* connect(Node* root) {
        if(root==NULL)return root;
        Node*ans=root;
        Node* line;
        Node* line2;
        root->next=NULL;
        while(root){
            line=NULL;
            line2=NULL;
            while(root){
                if(root->left!=NULL){
                    if(line==NULL){
                        line=root->left;
                        line2=line;
                    }else{
                        line->next=root->left;
                        line=line->next;
                    }
                }
                if(root->right!=NULL){
                    if(line==NULL){
                        line=root->right;
                        line2=line;
                    }else{
                        line->next=root->right;
                        line=line->next;
                    }
                }
                root=root->next;
            }
            if(line)line->next=NULL;
            root=line2;
        }
        return ans;
    }
};

移除元素（简单）

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

思路

双指针，因为要忽略值为val的元素，所以用两个指针，i指向忽略后的下标，j指向正常下标，当遇到值为val时j继续往前，i就不动

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i=0;
        int j=0;
        while(j<nums.size()){
            if(nums[j]!=val)swap(nums[j],nums[i++]);
            j++;
        }
        return i;
    }
};

简化路径（中等）

题目描述

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/' 。
  • 最后一个目录名（如果存在）不能 以 '/' 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

1
2
3
输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

思路

用堆栈，遇到..就pop，遇到.就跳过

代码

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
class Solution {
public:
    string simplifyPath(string path) {
        stack<string>stk;
        string pushing;
        while(path[0]=='/'){
            path=path.substr(1);
        }
        while(!path.empty()){
            while(!path.empty()&&path[0]!='/'){
                pushing.push_back(path[0]);
                path=path.substr(1);
            }
            if(stk.empty()&&pushing!="."&&pushing!=".."){
                stk.push(pushing);
            }else if(!stk.empty()){
                if(pushing==".."){
                    stk.pop();
                }else if(pushing!="."){
                    stk.push(pushing);
                }
            }
            pushing="";
            while(!path.empty()&&path[0]=='/'){
                path=path.substr(1);
            }
        }
        while(!stk.empty()){
            pushing="/"+stk.top()+pushing;
            stk.pop();
        }
        return pushing==""?"/":pushing;
    }
};

路径总和（简单）

题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

示例 1：

img 
1
2
3
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

思路

很简单的回溯

代码

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root==NULL)return false;
        targetSum-=root->val;
        if(root->left==NULL&&root->right==NULL)return targetSum==0?true:false;
        return hasPathSum(root->left,targetSum)||hasPathSum(root->right,targetSum);
    }
};

删除有序数组中的重复项Ⅱ（中等）

题目描述

给你一个有序数组 nums ，请你原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

思路

i从位置0开始，j从位置1开始

分为三个阶段做：

  1. 如果i位置的值和j位置的值第一次相等，i和j直接加一（如果i和j不相连的话需要将j位置的值给i+1位置的值），因为需要保留出现超过两次的元素出现两次
  2. 接着进行比较，如果i和j位置还是相等只加j，就代表该值不要，因为之需要保留两次
  3. 遇到不相等的时候，先将j的值赋给i+1，再对i和j进行加1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int length=nums.size();
        int i=0;
        int j=1;
        while(j<length){
            if(nums[j]==nums[i])
                if(++i!=j++)swap(nums[j-1],nums[i]);
            while(j<length&&nums[j]==nums[i])j++;
            if(j<length)swap(nums[j++],nums[++i]);
        }
        return i+1;
    }
};

买卖股票的最佳时机Ⅱ（中等）

题目描述

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

思路：动态规划

其实相当于买股票就是减钱，卖股票就是加钱，只能先买股票再卖股票，对于每一个时间点，如果前一个时间点有股票，那么该时间点就可以选择留股票或者卖股票，这里没办法通过直接判断该时间点留股票赚钱多还是卖股票赚钱多，所以需要为每个时间点维护两个状态，一个状态用于存储该时间点不留股票，也就是如果该时间点的前一个时间点有股票就卖掉，没有就保持，取二者最大值为该股票能得到的最大现金数，另一个状态用于存储该时间点留股票，也就是如果前一个时间点有股票就保持，没有就买当前时间点的股票，取二者较大值作为该时间点留股票可达到的最大数目金额

买股票就相当于现金减去当前买的股票金额，卖股票就相当于现金加上当前股票金额

用dp[i][0]代表该时间点不留股票能达到的最大金额，用dp[i][1]来表示该时间点留股票能达到的最大金额，状态更新方程就为

1
2
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+price[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-price[i]);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int length=prices.size();
        vector<vector<int>>dp(length,vector<int>(2));
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<length;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
        }
        return dp[length-1][0];
    }
};

用最少数量的箭引爆气球（中等）

题目描述

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xstart ≤ x ≤ x``end，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

思路

先对points进行排序，然后从头开始确定能一次性引爆的气球数，用start，end表示能通过在该范围进行射箭引爆以遍历的气球，如果遇到有气球超过了end，那该气球就没办法一次性引爆，如果有气球没超过end，但是提前结束了，end需要往前移以便能引爆该气球

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end());
        int start;
        int end;
        int count=0;
        int i=0;
        while(i<points.size()){
            start=INT_MIN;
            end=INT_MAX;
            while(i<points.size()&&points[i][0]<=end){
                start=points[i][0];
                end=min(points[i][1],end);
                i++;
            }
            count++;
        }
        return count;
    }
};

汇总区间（简单）

题目描述

给定一个 无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

  • "a->b" ，如果 a != b
  • "a" ，如果 a == b

知识点

  1. 数字转换成字符串：

    1
    strNum=to_string(num);

思路

也就是获取连续数字的头和尾，以此遍历即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        int start=0;
        int end=0;
        vector<string>ans;
        for(int i=0;i<nums.size();i++){
            start=nums[i];
            while(i<nums.size()-1&&nums[i+1]==nums[i]+1){
                i++;
            }
            end=nums[i];
            if(start==end)ans.push_back(to_string(start));
            else ans.push_back(to_string(start)+"->"+to_string(end));
        }
        return ans;
    }
};

N皇后Ⅱ（困难）

题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

知识点

std::unordered_set 是 C++ 标准库提供的一个无序集合容器，它基于哈希表实现，允许快速的插入、删除和查找操作。这个容器不会按特定顺序来存储元素，而是按照哈希函数计算的位置进行存储，因此元素的顺序是不确定的。

以下是 std::unordered_set 的一些常用方法和使用方法：

  1. 插入元素：
    • insert(val): 向集合中插入一个元素 val。
  2. 删除元素：
    • erase(val): 从集合中移除值为 val 的元素。
    • clear(): 清空集合，移除所有元素。
  3. 查找元素：
    • find(val): 查找值为 val 的元素，返回指向该元素的迭代器；如果不存在，则返回集合尾后迭代器（end()）。
  4. 大小和容量：
    • size(): 返回集合中元素的数量。
    • empty(): 检查集合是否为空。
  5. 迭代器：
    • begin(), end(): 返回指向集合第一个元素和尾后的迭代器，用于遍历集合的元素。

思路

和之前的N皇后思路几乎一样，不做过多解释了

代码

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
class Solution {
private:
    int count;
public:
    void putQueens(int& remainN,unordered_set<int>duijiaoLeft,unordered_set<int>duijiaoRight,unordered_set<int>visited,int& n){
        if(remainN==0){
            count++;
            return;
        }
        unordered_set<int> modifiedSet;
        for (const auto& item : duijiaoLeft) {
            modifiedSet.insert(item - 1);
        }
        duijiaoLeft.clear();
        for (const auto& item : modifiedSet) {
            duijiaoLeft.insert(item);
        }
        modifiedSet.clear();
        for (const auto& item : duijiaoRight) {
            modifiedSet.insert(item + 1);
        }
        duijiaoRight.clear();
        for (const auto& item : modifiedSet) {
            duijiaoRight.insert(item);
        }
        for(int i=0;i<n;i++){
            if(duijiaoLeft.find(i)==duijiaoLeft.end()&&duijiaoRight.find(i)==duijiaoRight.end()&&visited.find(i)==visited.end()){
                duijiaoLeft.insert(i);
                duijiaoRight.insert(i);
                visited.insert(i);
                putQueens(--remainN,duijiaoLeft,duijiaoRight,visited,n);
                visited.erase(i);
                duijiaoLeft.erase(i);
                duijiaoRight.erase(i);
                remainN++;
            }
        }
    }
    int totalNQueens(int n) {
        unordered_set<int>duijiaoLeft;
        unordered_set<int>duijiaoRight;
        unordered_set<int>visited;
        int remainN=n;
        putQueens(remainN,duijiaoLeft,duijiaoRight,visited,n);
        return count;
    }
};

H指数（中等）

题目描述

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。

思路

先对原数组进行排序，我们要找最大值的h就是要满足大于等于h的数大于等于h，所以排序之后我们可以知道大于每个数的数有多少，进行查找最大值即可

代码

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(),citations.end());
        for(int i=0;i<citations.size();i++)
            if(citations[i]>=(citations.size()-i))return citations.size()-i;
        return 0;
    }
};

加一（简单）

题目描述

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

思路

从后往前加，如果遇到加了小于10的直接返回，如果所有都大于等于10，则第一位肯定是1，后面肯定是0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n=digits.size();
        for(int i=digits.size()-1;i>=0;i--){
            if(++digits[i]<10)return digits;
            digits[i]-=10;
        }
        vector<int>result(n+1,0);
        result[0]=1;
        return result;
    }
};

最后一个单词的长度（简单）

题目描述

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

思路

直接从后往前遍历即可

代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int lengthOfLastWord(string s) {
        int ans=s.size()-1;
        while(s[ans]==' ')ans--;
        for(int i=ans;i>=0;i--)
            if(s[i]==' ')return ans-i;
        return ans+1;
    }
};

Pow(x,n)(中等)

题目描述

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

思路

这里有一个比较坑的点，如果直接一个一个x相乘会超时，所以我采取的是幂不断×2，也就是现在算的幂为2，而要求n是4，直接结果乘结果，这样幂就直接是4了，直到最后不能×2时就用递归

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    double myPow(double x, long long n) {
        int fu=0;
        if(n<0)
            fu=1;
        else if(n==0)
            return 1;
        n=abs(n);
        double ans=x;
        double nowPow=1;
        while(n>=nowPow*2){
            ans*=ans;
            nowPow*=2;
        }
        if(n>=nowPow){
            ans*=myPow(x,n-nowPow);
        }
        if(fu)ans=double(1)/ans;
        return ans;
    }
};

建立四叉树（中等）

题目描述

给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

你需要返回能表示矩阵 grid 的 四叉树 的根结点。

四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：

  • val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False。注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
  • isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。
1
2
3
4
5
6
7
8
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

我们可以按以下步骤为二维区域构建四叉树：

  1. 如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
  2. 如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
  3. 使用适当的子网格递归每个子节点。
img

如果你想了解更多关于四叉树的内容，可以参考 wiki 。

四叉树格式：

你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。

它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。

如果 isLeaf 或者 val 的值为 True ，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。

示例 1：

img 
1
2
3
4
输入：grid = [[0,1],[1,0]]
输出：[[0,1],[1,0],[1,1],[1,1],[1,0]]
解释：此示例的解释如下：
请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。

思路

  1. 如果该矩阵所有元素都相等，则不需要拆分，直接就是叶子节点
  2. 如果不完全相等，则需要拆分，拆分成四份，再进行判断，用递归方式实现

代码

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
// Definition for a QuadTree node.
class Node {
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};
*/

class Solution {
public:
    int ifAll(vector<vector<int>>&grid){
        for(vector<int>its:grid){
            for(int it:its){
                if(it!=grid[0][0])return -1;
            }
        }
        return grid[0][0];
    }
    vector<vector<int>> newGridGen(vector<vector<int>>&grid,int length,int i,int j){
        vector<vector<int>>newGrid(length,vector<int>(length));
        for(int m=0;m<length;m++){
            for(int n=0;n<length;n++){
                newGrid[m][n]=grid[i+m][j+n];
            }
        }
        return newGrid;
    }
    Node* construct(vector<vector<int>> grid) {
        Node* newNode=new Node();
        int item=ifAll(grid);
        if(item!=-1){
            newNode->isLeaf=true;
            newNode->val=item;
        }else{
            int length=grid.size()/2;
            newNode->topLeft=construct(newGridGen(grid,length,0,0));
            newNode->topRight=construct(newGridGen(grid,length,0,length));
            newNode->bottomLeft=construct(newGridGen(grid,length,length,0));
            newNode->bottomRight=construct(newGridGen(grid,length,length,length));
        }
        return newNode;
    }
};

删除排序链表中的重复元素Ⅱ（中等）

题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

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

示例 2：

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

思路

在head前再设置一个节点，pre从该节点开始记录，now从head的原始头节点开始记录，如果now和now->next的值相同now就向后走，直到不等，这时now还需要往后走一格，因为now此时还是和前一个节点值相等，接着再和next进行比较，直到now既不和前节点值相同也不和后节点值相同，pre的next就指向now，now就往后走

代码

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* pre=new ListNode();
        pre->next=head;
        ListNode*now=head;
        head=pre;
        while(now){
            while(now&&now->next&&now->val==now->next->val){
                while(now&&now->next&&now->val==now->next->val){
                    now=now->next;
                }
                if(now){
                    now=now->next;
                }
            }
            pre->next=now;
            pre=pre->next;
            if(now){
                now=now->next;
            }
        }
        return head->next;
    }
};

单词搜索（困难）（待做）

O(1) 时间插入、删除和获取随机元素（中等）

题目描述

实现RandomizedSet 类：

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  • bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
  • int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

知识点

  1. 生成随机索引

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    #include <iostream>
    #include <random>
    #include <unordered_set>

    int main() {
        std::unordered_set<char> charSet = {'a', 'b', 'c', 'd', 'e'};
        if (!charSet.empty()) {
            // 设置随机数生成器
            std::random_device rd;
            std::mt19937 gen(rd());
            std::uniform_int_distribution<int> dist(0, charSet.size() - 1);

            int randomIndex = dist(gen); // 生成随机索引
            std::cout << "随机索引: " << randomIndex << std::endl;
        } else {
            std::cout << "集合为空，无法生成随机索引" << std::endl;
        }

        return 0;
    }

  2. 移动迭代器到哈希列表指定位置：

    1
    2
    auto it = sets.begin();
     advance(it, randomIndex); // 移动迭代器到随机位置

思路

利用哈希列表查询元素的1复杂度和用随机数生成随机索引

代码

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
class RandomizedSet {
private:
    unordered_set<int> sets;
public:
    RandomizedSet() {
        srand((unsigned)time(NULL));
     }
    bool insert(int val) {
        if (sets.find(val) == sets.end()) {
            sets.insert(val);
            return true;
        }
        return false;
    }

    bool remove(int val) {
        if (sets.find(val) != sets.end()) {
            sets.erase(val);
            return true;
        }
        return false;
    }
    int getRandom() {
        int randomIndex = rand()%sets.size();; // 生成随机索引
        auto it = sets.begin();
        advance(it, randomIndex); // 移动迭代器到随机位置
        return *it;
    }
};

加油站（中等）

题目描述

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

思路

这里我进行了循环，整个循环需要走三步

  1. 首先找到第一个gas[i]大于cost[i]的点，这样的点才能作为起点，start定在该点，end为start+1，余额就是gas[start]-cost[start]
  2. 从该点开始，余额加上gas[end]-cost[end]，如果大于等于0，end就往后移，余额继续加
  3. 如果end已经返回到了start，此时分两种情况
    1. 余额大于0，说明该轮成功，直接返回start的值
    2. 余额小于0，说明该轮失败，整体就不可能成功，因为最终的余额肯定就是这个值，只是中间的值会不一样
  4. 如果end没有返回到start，此时的余额已经比0小了，start就需要往前移，余额就减去该点加的，直到余额大于0，end才继续后移
  5. 如果start移到了end，此时就需要再往后找符合gas[i]>=cost[i]的点

直到start遍历过所有点都没有找到的话，就说明失败了，就直接返回-1

代码

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
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int length=gas.size();
        int start=0;
        for(;start<length;start++){
            if(gas[start]>=cost[start])break;
        }
        if(start<length){
            int remain=gas[start]-cost[start];
            int end=(start+1)%length;
            while(start<length){
                while(remain>=0&&end!=start){
                    remain+=gas[end]-cost[end];
                    end=(end+1)%length;
                }
                if(start==end){
                    return (remain>=0)?start:-1;
                }
                while(remain<0&&start!=end&&start<length){
                    remain+=cost[start]-gas[start];
                    start++;
                }
                if(start==end){
                    for(;start<length;start++){
                        if(gas[start]>=cost[start]){
                            remain=gas[start]-cost[start];
                            end=(start+1)%length;
                            break;
                        }
                    }
                }
            }
        }
        
        return -1;
    }
};

到达首都的最少油耗(中等)

题目描述

给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。

每个城市里有一个代表，他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

示例 1：

img 
1
2
3
4
5
6
7
输入：roads = [[0,1],[0,2],[0,3]], seats = 5
输出：3
解释：
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 2 直接到达首都，消耗 1 升汽油。
- 代表 3 直接到达首都，消耗 1 升汽油。
最少消耗 3 升汽油。

思路

可以将题目理解为以下过程，首先从0位置开始，到0位置消耗的总的汽油数等于0相邻的所有点消耗的汽油数加上相邻点到0所消耗的总的汽油数，以此类推就是递归，终止条件是递归到最后的点，该点往前消耗的汽油数就是1，因为该点不能再往后并且该点只有一个代表

每次递归我设置了两个返回值，因为我们既要知道到该点的代表数，又要知道已经消耗了的汽油数

（ps:看到题解将消耗了的汽油数设置成了全局变量，因为每个点实际上只会遍历一次，所以不需要传递这个值，对全局变量进行更新即可）

代码

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
class Solution {
private:
    unordered_map<int,vector<int>>map;
    int seatss;
public:
    vector<long long> numberOfRoad(int& pre,int& start){
        int length=map[start].size();
        vector<long long>sum(2);//sum[0]是车辆数量，sum[1]是消耗的汽油数量
        vector<long long>temp(2);
        for(int &node : map[start]){
            if(node!=pre){
                temp=numberOfRoad(start,node);
                sum[0]+=temp[0];
                sum[1]+=temp[1];
            }
        }
        if(start==0){
            return sum;
        }
        sum[0]++;
        sum[1]+=sum[0]/seatss;
        if(sum[0]%seatss!=0){
            sum[1]++;
        }
        return sum;
    }
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        seatss=seats;
        for(auto &road : roads){
            map[road[0]].push_back(road[1]);
            map[road[1]].push_back(road[0]);
        } 
        int pre=-1;
        int start=0;
        return numberOfRoad(pre,start)[1];
    }
};

找出字符串的可整除数组（中等）

题目描述

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

  • 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
  • 否则，div[i] = 0

返回 word 的可整除数组。

示例 1：

1
2
3
输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。

示例 2：

1
2
3
输入：word = "1010", m = 10
输出：[0,1,0,1]
解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。

思路

由于此处的word太长，所以只能使用模运算，假设num是将字符转换为数字，则word=( (num(word[0])*10) + num(word[1]) )*10...+num(word[word.size()-1])，由a mod m + b mod m = a+b mod m，则num(word) mod m=(num(word[0])*10+num(word[1]))*10... mod m

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> divisibilityArray(string word, int m) {
        int length=word.size();
        vector<int> ans(length);
        long mod=0;
        for(int i=0;i<length;i++){
            mod=(mod*10+(word[i]-'0'))%m;
            ans[i]=mod==0?1:0;
        }
        return ans;
    }
};

leetcode面试100题

http://example.com/post/4d65bd11.html

Author

yyyyyyxnp

Posted on

2023-09-21

Updated on

2024-10-08

Licensed under

#
You need to set install_url to use ShareThis. Please set it in _config.yml.

Like this article? Support the author with

You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.
Follow

Catalogue

Recents

×