【编码狂想】LeetCode 字符串和数组篇:挑战算法精髓,深化程序设计基础

2023-12-21 00:33:34

?

?📋?前言

🌈 个人主页:Sarapines Programmer

?🔥 系列专栏:本期文章收录在《C语言闯关笔记》,大家有兴趣可以浏览和关注,后面将会有更多精彩内容!

??翰墨致赠:翩翩风华激彩虹,豪情壮志醉长空。 剑指星河舞红尘,梦驰烈马向未来。

?

?🎉欢迎大家关注🔍点赞👍收藏??留言📝
?🔔作者留言:

欢迎来到我的??编程学习笔记!这里是一个探索编程世界的秘境,我的学习笔记为你揭开C/C++语言的神秘面纱。在这个学习笔记中,我不仅分享C/C++的基础知识和高级技巧,还包含实用技术和项目经验的宝贵经验。无论你是初学者还是经验丰富的程序员,这个学习笔记将为你呈现出奇妙的编程魔法,帮助你在C/C++的编程森林中展开一场精彩的学习之旅。你准备好了吗?跟着我,一起编织属于我们自己的编程魔法吧!

题库地址:学习计划 - 力扣(LeetCode)

目录

?📋?前言

🌐第一部分 数组/字符串篇

😎1?合并两个有序数组

😎2?移除元素

😎3?删除有序数组中的重复项

😎4?删除有序数组中的重复项Ⅱ

😎5 多数元素


🌐数组/字符串篇

😎1?合并两个有序数组

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

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

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

示例1:
输入: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 中的元素。

示例2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。

代码模板:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

    }
};

💡解决如下:

/*思路1*/
//先将nums2加到nums末尾,再排序(升序)即可
/*思路2*/
//遍历nums1和nums2,
//若nums1[i]>num2[j],num2[j]插入nums1[i]前
//若nums1[i]==num2[j],num2[j]插入nums1[i]后
//若nums1[i]<num2[j],则继续遍历num1,直到找到最小的nums[k]>=num2[j],num2[j]插入nums1[k]前,找不到则直接插入nums1末尾

/*思路一求解*/
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        //去除nums1多余的元素0
        //for(int i=m;i<nums1.size();i++){  //循环删除导致迭代器失效
        //    nums1.erase(nums1.begin()+i);
        //}
        nums1.erase(nums1.begin()+m,nums1.end());

        //合并nums2==>nums1
        for(int i=0;i<n;i++){
            nums1.push_back(nums2[i]);
        }
        //整体排序
        sort(nums1);
    }
    void sort(vector<int> &v){
        for(int i=0;i<v.size()-1;i++){
            int k=i;
            for(int j=i+1;j<v.size();j++){
                if(v[k]>v[j]){
                    int t=v[k];
                    v[k]=v[j];
                    v[j]=t;
                }
            }
        }
    }
};

😎2?移除元素

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

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

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

说明:

为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
? ? print(nums[i]);
}

示例1:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2]
解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。

示例2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,3,0,4]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

代码模板:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {

    }
};

💡解决如下:

//思路:遍历找到val值相等元素,删除即可
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        for(int i=0;i<nums.size();){
            if(nums[i]==val) nums.erase(nums.begin()+i);
            else i++;
        }
        return int(nums.size());
    }
};

😎3?删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:
更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
? ? assert nums[i] == expectedNums[i];
}
如果所有断言都通过,那么您的题解将被 通过。

示例 1:
输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2:
输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

代码模板:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {

    }
};

💡解决如下:

//思路:新建一个集合set存储出现过的元素【边初始化边查找】,对于每个元素都进行find,未找到则插入,找到则删除该向量元素

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        set<int> s;
        for(int i=0;i<nums.size();){
            if(i!=0){//对于向量非首项
                if(s.find(nums[i]) !=s.end()){//如果集合s中已经有出现nums[i]
                    nums.erase(nums.begin()+i);
                }
                else{
                    s.insert(nums[i]);
                    i++;
                }
            }
            else {//对于向量首项
                s.insert(nums[i]);
                i++;
            }
        }
        return nums.size();
    }
};

😎4?删除有序数组中的重复项Ⅱ

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

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

说明:

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

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

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

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);

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

示例 1:
输入:nums = [1,1,1,2,2,3]
输出:5, nums = [1,1,2,2,3]
解释:函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2:
输入:nums = [0,0,1,1,1,1,2,3,3]
输出:7, nums = [0,0,1,1,2,3,3]
解释:函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

代码模板:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {

    }
};

💡解决如下:

//思路:遍历,flag标志出现次数,[flag=0初始值]
//当前元素和前一元素不相等 | 首项,继续循环下一个
//else 当前元素和前一元素相等则flag++
//当flag=1表示出现两次,后续和前一字符相等的删去
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int flag=0;
        for(int i=0;i<nums.size();){
            if(i==0 || nums[i]!=nums[i-1]){
                i++;
                flag=0;
            }
            else{
                if(flag ==1){
                    nums.erase(nums.begin()+i);
                }
                else {
                    flag++;
                    i++;
                }
            }
        }
        return nums.size();
    }
};

😎5 多数元素

给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ? n/2 ? 的元素。

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

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

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

代码模板:

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        
    }
};

💡解决如下:

//思路:摩尔投票法
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n=nums[0],count=0;
        for(int i=0;i<nums.size();i++){
            if(i==0 || nums[i]==n){
                count++;
            }
            else{
                if(count==0){
                    n=nums[i];
                    count=1;
                }
                 count--;
            }
        }
        return n;
    }
};

😎6?轮转数组

给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
    向右轮转 1 步: [7,1,2,3,4,5,6]
    向右轮转 2 步: [6,7,1,2,3,4,5]
    向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入:nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释: 
    向右轮转 1 步: [99,-1,-100,3]
    向右轮转 2 步: [3,99,-1,-100]

代码模板:

class Solution {
public:
    void rotate(vector<int>& nums, int k) {

    }
};

💡解决如下:

//思路1:按照逻辑顺序:存储向量尾元素,然后尾部向前 逐一向前赋值。
//超出时间复杂度
/*
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        for(int i=0;i<k;i++){
            int m=nums[nums.size()-1];
            for(int j=nums.size()-1;j>0;j--){
                nums[j]=nums[j-1];
            }
            nums[0]=m;
        }
    }
};*/
//优化思路2:存储向量尾元素,去除向量尾元素,向首元素插入尾元素.
//超出时间复杂度
/*class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        for(int i=0;i<k;i++){
            int m=nums[nums.size()-1];
            nums.erase(nums.begin()+nums.size()-1);
            nums.insert(nums.begin(),m);
        }
    }
};*/
//优化思路3:直接新建一个向量,然后直接计算最终顺序解答!
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();

        //k超过向量长度
        k=k%n;

        vector<int> v(n);
        for(int i=0;i<n;i++){
            v[(i+k)%n]=nums[i];
        }
        nums=v;
    }
};

😎7?买卖股票的最佳时机

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 =             5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

代码模板:

class Solution {
public:
    int maxProfit(vector<int>& prices) {

    }
};

💡解决如下:


😎8?买卖股票的最佳时机 II

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

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

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

示例 1:
输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得        
      利润 = 5 - 1 = 4 。
      随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所 
      能获得利润 = 6 - 3 = 3 。
      总利润为 4 + 3 = 7 。

示例 2:
输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获 
      得利润 = 5 - 1 = 4 。
      总利润为 4 。

示例 3:
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0 。

代码模板:

class Solution {
public:
    int maxProfit(vector<int>& prices) {

    }
};

💡解决如下:

😎9

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

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

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

示例 1:

输入: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 中的元素。

示例2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
      合并结果是 [1] 。

代码模板:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

    }
};

💡解决如下:

😎10

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

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

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

示例 1:

输入: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 中的元素。

示例2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
      合并结果是 [1] 。

代码模板:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

    }
};

💡解决如下:

😎11

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

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

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

示例 1:

输入: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 中的元素。

示例2:

输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
      合并结果是 [1] 。

代码模板:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

    }
};

💡解决如下:

😎12?文本左右对齐

给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词;也就是说,尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充,使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配,则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐,且单词之间不插入额外的空格。

注意:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0,小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。

示例 1:
输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

示例 2:
输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐,而不是左右两端对齐。       
     第二行同样为左对齐,这是因为这行只包含一个单词。

示例 3:
输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"],maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

代码模板:

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {

    }
};

💡解决如下:

?

文章来源:https://blog.csdn.net/m0_57532432/article/details/135081676
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。