数组 / 字符串算法笔记(题解)

[以下代码为c++编写]

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int x=m+n;
       
         for(int i=0;i<n;i++)
         nums1[i+m]=nums1[i+m]+nums2[i];

    sort(nums1.begin(), nums1.end());

    }
};

c++偷懒,正常应该加入后使用排序算法

1.计算长度

2.在数组nums1后添加新的元素

3.对添加完毕的元素排序(sort)


27. 移除元素

给你一个数组 nums和一个值 val,你需要 原地 移除所有数值等于 val的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
        int i = 0, j = 0;//双指针i、j
        for (; i < nums.size(); ++i) {//i先动,向前查找最新的元素
            if (nums[i] != val) {//判断是否相等val
                nums[j++] = nums[i];//找到不等于val的存入,并且j指向下一个要存放的位置
            }
        }
        nums.resize(j);//调整数组大小
        return j;
    }
};

双指针关键:一快一慢

以下是模板:

//模板
int i = 0, j = 0;//双指针i、j
        for (; i < 快指针i的边界; ++i) {//快指针i先动
            if (判断触发慢指针j的条件) {
                j++;//触发后,使慢指针j指向下一个位置
            }

1.两个指针,一个先走,另一个被触发后才动

2.遍历完后调整大小


26. 删除有序数组中的重复项

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:
更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

参考上题27,类似解法

依旧是双指针,一块一慢

相同点在快指针的边界依旧是数组的最大长度。不同的是,这里的慢指针的触发条件(注意是递增排列 的数组)

如果是初学者可以先参考上一题先思考一下,再看下面的完整代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();//得到数组大小
        if (n == 0) {//排除特殊情况
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {//快指针边界
            if (nums[fast] != nums[fast - 1]) {
//慢指针的触发条件,递增排列 数组中指向的数字不等于它上一个数字,可以判断得是未存入的新数字
                nums[slow] = nums[fast];//将新的唯一数字存入
                slow++;//慢指针+1 指向下一个要存放的位置
            }
            fast++;
        }
        return slow;
    }
};


169. 多数元素

给定一个大小为 n的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。

对于这题,暴力遍历O(n)时间复杂度

对数组循环一遍,统计一遍所有数字次数,有超过一半长度的就跳出

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> countMap;
        int candidate = 0;

        // 遍历数组,统计每个元素的出现次数
        for (const auto& num : nums) {
            countMap[num]++;
            
            // 如果当前元素的计数超过了一半数组长度跳出
            if (countMap[num] > nums.size() / 2 ) {
                candidate = num;
                break;
            }
        }

        // 因为题目保证了存在一个出现次数超过一半的元素,所以我们可以直接返回候选元素
        return candidate;
    }
};

121. 买卖股票的最佳时机

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

这是一个考察动态规划的题目,如果想不出来,可以使用暴力搜索来求解。

这里使用动态规划,关于动态规划这里不做详细讲解,动态规划将会在下一篇笔记中详细分析,感兴趣的朋友请移步下一篇笔记观看

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

           int x=prices.size();
           if(x==0)
           return 0;
            int maxprofix=0,minprices=1e9;
           for(int t:prices)遍历
           {
                maxprofix=max(maxprofix,t-minprices);//找出最大利润
                minprices=min(minprices,t);//找出最小值

           }
           return maxprofix;
    }
};

因为想找出最大利润,必须找出在卖得最贵那一天减去买入最便宜的价格

所以我们假设每天都是卖得最贵的,维护一个碰见比自己小就更新的数minprices。

而如果碰见比自己还大的,那么则不更新。

这个最小数只在碰见比自己小的就更新,说明他肯定是卖出前能买到最小的。

然后假设每天都是卖得最贵的,每天都减去这个最小数,就会得到每天卖出的最大利润maxprofix

最后比较每天的最大利润与之前存储的就可以得到综合最大利润


13. 罗马数字转整数

罗马数字包含以下七种字符: I, V, X, LCD 和 M
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1 。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。

这里使用暴力打表解决,通过一个存储有字符对应的数字,遍历字符,检测到就加上它的值。如果存在前一个数比后一个数字小的时侯就减去,可以得到目标数字。

class Solution {
public:
    int romanToInt(string s) {

int len=s.length();

int sum=0;

        for(int i=0;i<len;i++)
        {
                int v1=0,v2=0,flag=1;

            if(s[i]=='I')v1=1;
            if(s[i]=='V')v1=5;
            if(s[i]=='X')v1=10;
            if(s[i]=='L')v1=50;
            if(s[i]=='C')v1=100;
            if(s[i]=='D')v1=500;
            if(s[i]=='M')v1=1000;

if(i+1<len){
            if(s[i+1]=='I')v2=1;
            if(s[i+1]=='V')v2=5;
            if(s[i+1]=='X')v2=10;
            if(s[i+1]=='L')v2=50;
            if(s[i+1]=='C')v2=100;
            if(s[i+1]=='D')v2=500;
            if(s[i+1]=='M')v2=1000;

            }

if(v1<v2)sum-=v1;//前一个数比后一个数字小减去
else//正常直接加
{
sum+=v1;

}

        }

return sum;
    }
};

58. 最后一个单词的长度

给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大
子字符串。

这里下面的的代码写的时候比较混乱,更简洁的思路应该如下:

确定单词的开头和单词结尾,然后每碰到一个单词就统计长度,返回最后的单词长度。

状态判断:默认在判断开头开始,在开头被触发后进行结尾判断,在结尾被触发后重新开始开头的判断

单词开头的判定:上一个是空格或者边界即为开头

单词结尾的判定:下一个是空格或者边界即为结尾

单词长度:结尾索引减去开头索引即为单词长度

class Solution {
public:
    int lengthOfLastWord(string s) {

            int len=s.size();

          

            int flag=0,wordlen=0;//状态指示和单词长度,flag为1是处于单词中,flag为0是单词外,单词中就开始每次给wordlen加一统计长度,单词外判断开头
            if(s[0]!=' ')flag=1;//开头非空,状态改1判断单词内
            for(int i=0;i<len;i++)
            {
                
                if(s[i]==' '&&flag==0&&s[i+1]<='z'&&s[i+1]>='a')//索引内容为空,状态改1判断单词内
                {

                   flag=1;
                   wordlen=0; //此时为新进入一个单词,长度清零
                }

                if(s[i]==' '&&flag==0&&s[i+1]<='Z'&&s[i+1]>='A')//索引内容为空,状态改1判断单词内
                {

                   flag=1;
                   wordlen=0;
                }

                if(flag==1&&s[i]!=' ')//不为空,长度加一
                {

                   wordlen++; 
                   if(s[i+1]==' ')flag=0;//如果为空,状态转换为0,进行处于单词外判定
                }

            }

            return wordlen;

    }
};

更为简洁的方法,翻转字符串

class Solution {
public:
    int lengthOfLastWord(string s) {
        int ans=0;
        int vis=0;// 判断标志:是否空格出现在单词前面
        reverse(s.begin(),s.end());//更具题意翻转字符串,
        for(char i:s){
            
            if(i!=' ' )
            {
                ans++;
                vis=1;
            }
            if(i==' '&&vis==1) break;//已经找到单词但又出现空格说明是与下个单词的分隔符,直接break输出答案
            
        }
        return ans;

    }
};


14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""

思路非常简单,因为是公共前缀,所有字符串必须满足,直接参考第一个字符串,对每个字符串遍历第一个字符串的字符,如果不同就缩短为上一次遍历长度的结果,然后重继续遍历,直到全部遍历结束

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {

        int len = strs.size();
        if (len == 0) return "";//特殊情况直接返回

        string prefix = strs[0];

        for (int i = 1; i < len; i++) {//遍历每个字符串
            int minLen = min(prefix.size(), strs[i].size());//调整公共前缀长度,对比原先的和新返回的哪个更短
            int j = 0;
            while (j < minLen && prefix[j] == strs[i][j]) {//对比每个字符串,到达最大相同长度就返回
                j++;//长度加一
            }
            prefix.resize(j);//调整新返回长度
        }

        return prefix;
    }
};

28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回  -1 

遍历比较即可,如果碰到首字母相同先存储下标索引,然后再逐字比较。完全相同直接返回,不同则继续遍历至边界

class Solution {
public:
    int strStr(string haystack, string needle) {

int lenhs=haystack.size();
int lennd=needle.length();

int Match=-1;

for(int i=0;i<lenhs&&i+lennd<=lenhs;i++)
{
    if(haystack[i]==needle[0]){//对比首字母
        int t=0;
       
    for(int j=0;j<lennd;j++)//逐字比较
    {
        if(haystack[i+j]==needle[j]){t++;}//长度加一
    }
    if(t==lennd){Match=i;return Match;}//满足相同条件直接跳出
    
    }
}




 return -1;//没有符号条件返回-1
    }
};
博客内容均系原创,未经允许严禁转载!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
下一篇