LeetCode 刷题记录(数据结构三周)

| 默认分类 | 热度:911°C |

一、简单

1.第一天（数组）

a.只出现一次的数字

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

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解析：对于任意数a对于异或运算有以下的性质：

$$ 任何数和 0 做异或运算，结果仍然是原来的数，即 a \oplus 0=a $$

$$ 任何数和其自身做异或运算，结果是 0，即 a \oplus a=0 $$

$$ 异或运算满足交换律和结合律，即 a \oplus b \oplus a=b \oplus a \oplus a=b \oplus (a \oplus a)=b \oplus0=b $$

/*利用异或运算的原理,其中b出现一次，在异或之后结果为b*/
int singleNumber(int* nums, int numsSize){
    int re=0;
    for(int i=0;i<numsSize;i++)
        re=nums[i]^re;
    return re;
}

b.多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：[3,2,3]
输出：3
示例 2：

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

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析，我们使用map的键对关系，其中键存放数字，值存放出现的最多次数

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        map<int,int> count;
        int majority=0,cnt=0;  //分别记录最多的数以及其出现的最多次数;
        for(int num:nums)
        {
            ++count[num];
            if(count[num]>cnt)
            {
                majority=num;
                cnt=count[num];
            }
        } 
        return majority;
    }
};

c.三数之和（中等）

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

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

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我使用的解法(超时且没有考虑到特殊的情况)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> ans_set;
        vector<vector<int>> ans;
        int n= nums.size();
        sort(nums.begin(),nums.end());
        for(int first=0;first<n;first++)
        {
            for(int second=first+1;second<n;second++)
            {
                for(int third=second+1;third<n;third++)
                {
                    if(nums[first]+nums[second]+nums[third]==0)
                    {
                        ans_set.insert({nums[first],nums[second],nums[third]});  
                        break;  
                    }
                }
            }
        }
        for(vector<int> each:ans_set)
            ans.push_back(each);
        return ans;
    }
};

上述的解法利用了三个循环其时间复杂度为

$$ O(n^3) $$

以下为正解

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        /*判断是否本身元素少于三，此时直接输出空的vector*/
        if(nums.size()<3) return ans;
        /*对元素排序*/
        sort(nums.begin(), nums.end());
        if(nums[0]>0) return ans;    //当最小的元素都大于0时，那么不存在可能加起来等于0
        int i = 0;
        while(i<nums.size()){
            if(nums[i]>0) break;        // 将结果分为大于0和小于0两个部分
            int left = i+1, right = nums.size()-1;   //双指针，一个是区间最小，一个是区间最大
            while(left< right){
                // 转换为long long避免加法过程中溢出
                long long y = static_cast<long long>(nums[i]);
                long long x = static_cast<long long>(nums[left]);
                long long z = static_cast<long long>(nums[right]);
                if(x + y >0-z)   //防止数太大溢出
                    right--;
                else if(x + y <0-z)
                    left++;
                else{
                    ans.push_back({nums[i], nums[left], nums[right]});
                    // 相同的left和right不应该再次出现，因此跳过
                    while(left<right&&nums[left]==nums[left+1])
                        left++;
                    while(left<right&&nums[right] == nums[right-1])
                        right--;
                    left++;
                    right--;
                }
            }
            // 避免nums[i]作为第一个数重复出现
            while(i+1<nums.size()&&nums[i] == nums[i+1])
                i++;
            i++;
        }
        return ans;
    }
};

2.第二天（数组）

a.颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

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

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

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：

你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：本题为排序，基本思路为双指针和单指针排序代码如下

# 方法一 单指针 不适用排序，主要采用的是0,1,2特性
# 方法二 双指针， 选择排序，时间复杂度O(n^2)
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(nums[i]>nums[j])
                swap(nums[i],nums[j]);
            }
        }
        
    }
};

b.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：建立一个数组，数组大小为最大值，如果值在区间里面，将数组对应的值改为1，反之为0，最后遍历整个数组，得到对应的区间。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        int a[10001];
        int max = 0, min = 10001;
        for (vector<int>interval : intervals)
        {
            /*找到最大与最小的值*/
            for (int i : interval)
            {
                if (i > max)
                    max = i;
                if (i < min)
                    min = i;
            }
            /*设定各自的值*/
            for (int j = interval[0]; j <= interval[1]; j++)
            {
                a[j] = 1;
            }
        }
        for (int i = min; i <= max; i++)
        {
            vector<int> temp;// 用于记录每一个独立的区间
            //对于多个区间的开始阶段，排除都不存在的情况
            while (a[i] != 1)
            {
                i++;
            }
            //记录开始位置
            temp.push_back(i);
            
            //遍历连续区间
            while (a[i] == 1)
            {
                i++;
            }
            temp.push_back(i - 1);
            i--;
            result.push_back(temp);
        }
        return result;
    }
};

c.设计hash映射

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

MyHashMap() 用空映射初始化对象
void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

示例：

输入：
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出：
[null, null, null, 1, -1, null, 1, null, -1]

解释：
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2); // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1（未找到），myHashMap 现在为 [[1,1]]

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/design-hashmap
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// 对于该题目，可以使用链表的形式，也可以使用vector的形式保存在一个类里面，这里主要是C++的写法
struct KV{
    int key;
    int value;
};
class MyHashMap {
private:
    vector<KV> Key_Value;
public:
    MyHashMap() {
        ;
    }

    void put(int key, int value) {
        /*如果已经存在*/
        for (int i = 0; i < Key_Value.size(); i++)
        {
            if (key == Key_Value[i].key)
            {
                Key_Value[i].value = value;
                return;
            }
        }
        /*不存在*/
        KV p;
        p.key = key;
        p.value = value;
        Key_Value.push_back(p);
    }

    int get(int key) {
        /*表为空*/
        if (Key_Value.empty())
            return -1;
        /*表不为空*/
        for (int i = 0; i < Key_Value.size(); i++)
        {
            if (key == Key_Value[i].key)
                return Key_Value[i].value;
        }
        return -1;
    }

    void remove(int key) {
        /*表为空*/
        if (Key_Value.empty())
            return;
        /*表不为空*/
        for (int i = 0; i < Key_Value.size(); i++)
        {
            if (key == Key_Value[i].key)
            {
                Key_Value.erase(Key_Value.begin() + i);
                return;
            }
        }
        return;
    }
};
/*
注意在put操作的时候，我们所使用的并不是直接添加，而是先查找是否存在该键对，然后修改存在的情况，如果不存在，就添加一个节点保存该键对。
*/

3.第三天（数组）

a.杨辉三角

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

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

示例 1:

输入: rowIndex = 3
输出: [1,3,3,1]
示例 2:

输入: rowIndex = 0
输出: [1]
示例 3:

输入: rowIndex = 1
输出: [1,1]

提示:

0 <= rowIndex <= 33

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/pascals-triangle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/*方法很多，这里采用比较复杂的递推方式
    思路就是将一个二维的数组，先初始化他的值，然后通过杨辉三角的关系逐渐推出他的每个位置的值，
    注意：不止每行的开始需要初始化，结尾也需要
*/
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> C(rowIndex+1);
        for(int i=0;i<rowIndex+1;i++)
        {
            C[i].resize(i+1);
            C[i][0]=1;
            C[i][i]=1;
            for(int j=1;j<i;j++)
            {
                C[i][j]=C[i-1][j]+C[i-1][j-1];
            }
        }
        return C[rowIndex];

    }
};

拓展方法：

  1. 递推式

$$ \mathcal{C}_n^i=\mathcal{C}_{n-1}^i+\mathcal{C}_{n-1}^{i-1} $$

 表明，当前行第 ii 项的计算只与上一行第 i-1i−1 项及第 ii 项有关。因此我们可以倒着计算当前行，这样计算到第 ii 项时，第 i-1i−1 项仍然是上一行的值。
  1. 由组合数公式

$$ \mathcal{C}_n^m=\dfrac{n!}{m!(n-m)!} $$

可以得到同一行的相邻组合数的关系

$$ \mathcal{C}_n^m= \mathcal{C}_n^{m-1} \times \dfrac{n-m+1}{m} $$

由于

$$ \mathcal{C}_n^0=1 $$

利用上述公式我们可以在线性时间计算出第 nn 行的所有组合数。

b.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/rotate-image
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/*对于本题，可以先添加对应的矩阵行，之后再删除*/
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        /*返回类型为void，所以不能另外创建矩阵*/
        /*思路就是遍历整个矩阵，让对应的交换*/
        int n = matrix.size();
        /*对每一个进行处理*/
        for(int i=0;i<n;++i)
        {
            vector<int> temp;   //用于保存每一个新的
            for(int j=n-1;j>=0;--j)
            {
                temp.push_back(matrix[j][i]);
            }
            matrix.push_back(temp);
        }
        /*删除之前的*/
       // matrix.erase(matrix.begin()+1);
         for(int i=0;i<n;i++)
         {
             matrix.erase(matrix.begin());
         }
    }
};

/*这里在删除的时候有一个需要注意的点，由于删除之后对应的下标会移动，所以不能在迭代器的位置加i，这样删除的位置其实是跳跃的*/

c.螺旋矩阵 II(模拟)

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：

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

提示：

1 <= n <= 20

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/spiral-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：该题主要是模拟，我们假设对于矩阵而言，我们从每一位开始对其进行赋值，同时建立一个方向的向量，每次到达边界对向量进行加1，从而对于矩阵改变的方向就可以定下来。

class Solution{
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n,vector<int>(n));
        int cur=1;
        int max=n*n;
        int row=0,col=0;
        int directionIndex=0;
        vector<vector<int>> directions = {{0,1},{1,0},{0,-1},{-1,0}};  //分别表示每个区域的位置
        while(cur<=max)
        {
            result[row][col]=cur;
            int Nextrow=row+directions[directionIndex][0];
            int Nextcol=col+directions[directionIndex][1];
            if(Nextcol>=n||Nextcol<0||Nextrow>=n||Nextcol<0||result[Nextrow][Nextcol]!=0)
            {
                directionIndex=(directionIndex+1)%4;
            }
            row=row+directions[directionIndex][0];
            col=col+directions[directionIndex][1];
            cur++;
        }
        return result;

    }
};

4.第四天(数组)

a.搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/search-a-2d-matrix-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：由于每一行都是顺序排列，我们可以对于每一行使用二分查找，对于不同方法的查找，暴力的时间复杂度为

O(mn), 而对于使用二分查找的空间复杂度为O(mlogn) ，

class Solution {
public:
    bool binarySearch(vector<int> &matrix, int target){
        int top=matrix.size()-1;
        int low=0;
        int mid;
        while(low<=top)
        {
            if(matrix[low]==target||matrix[top]==target)
                return true;
            mid=low+(top-low)/2;
            if(matrix[mid]==target)
                return true;
            else if(matrix[mid]<target)
                low=mid+1;
            else
                top=mid-1;
        }
        return false;
    }
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int n=matrix.size();
        for(int i=0;i<n;i++)
        {
            if(binarySearch(matrix[i],target))
                return true;
        }
        return false;
    }
};

b.无重叠区间

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

来源：力扣（LeetCode）
链接： https://leetcode-cn.com/problems/non-overlapping-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：本题存在动态规划与贪心的解法，这里使用贪心的解法，时间复杂度为O(nlogn)，主要思路为我们要删除最少的区间，那么我们可以将区间排序（按照每个区间右边界从小到大进行排序）！！！注意，如果是要使用最多的区间，那么最好使用的区间不包含任何区间，所以不能从大到小。然后遍历每个区间，如果下一个区间的左边界大于上一个区间的右边界，那么这个区间将可以被使用，同时更新右边界的值。最后返回区间总数与被使用区间数的差

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        /*先对于区间进行排序，按照区间的右边从小到大排序*/
        //此处使用Lambda表达式，设定对应的判断依据对原来的向量进行排序
        sort(intervals.begin(),intervals.end(),[](vector<int> &u,vector<int> &v){
            return u[1]<v[1];
    });
    int right=intervals[0][1];
    int n=intervals.size();
    int ans=1;   //可以使用的区间
    for(int i=1;i<n;i++)
    {
        /*判断下一个区间的最小是否大于上一个区间的最大，如果大于则可以使用*/
        if(intervals[i][0]>=right)
        {
            right=intervals[i][1];
            ++ans;
        }
        //如果不大于，那么这个区间被排除
    }
    return n-ans;
    }
};


标签:暂无标签
版权属于：Jtripper 所有，转载请注明文章来源。

本文链接： https://www.jtripperbacaf.com/index.php/archives/33/

上一篇
Pytorch（延缓更新）
下一篇
web 安全——内网渗透（延缓更新）
赞 (0)

评论区

发表评论

43+41=?

暂无评论，要不来一发？

回到顶部
微信分享二维码

微信里点“发现”，扫一下
二维码便可将本文分享至朋友圈。