leetcode标题(2)

目次
1.删除有序数组中的重复项
2.移除元素
3.找出字符中第一个匹配项的下标
4.搜索插入位置
5.最大子数组和
6.末了一个单词的长度

---

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

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

1. int removeDuplicates(int* nums, int numsSize) {
2.     if(numsSize == 0)
3.         return 0;
4.     int fast = 1,slow = 1;
5.     while(fast < numsSize)
6.     {
7.         if(nums[fast] != nums[fast - 1])
8.         {
9.             nums[slow] = nums[fast];
10.             ++slow;
11.         }
12.         ++fast;
13.     }
14.     return slow;
15. }

复制代码

2.移除元素

https://leetcode.cn/problems/remove-element/

1. int removeElement(int* nums, int numsSize, int val) {
2.     int fast = 0,slow = 0;
3.     for(int i = 0;i < numsSize;i++)
4.     {
5.         if(nums[fast] != val)
6.         {
7.             nums[slow] = nums[fast];
8.             fast++;
9.             slow++;
10.         }
11.         else
12.         {
13.             ++fast;
14.         }
15.     }
16.     return slow;
17. }

复制代码

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

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

1. class Solution {
2. public:
3.     int strStr(string haystack, string needle) {
4.         int n = haystack.size(), m = needle.size();
5.         if (m == 0)
6.             return 0;
8.         vector<int> pi(m); // 创建一个数组pi，用于存储needle的前缀函数值
9.         for (int i = 1, j = 0; i < m; i++) { // 从needle的第二个字符开始遍历
10.             while (j > 0 && needle[i] != needle[j]) { // 如果当前字符不匹配，且j不为0
11.                 j = pi[j - 1]; // 更新j为pi[j-1]，即最长的相同前缀后缀的长度
12.             }
13.             if (needle[i] == needle[j]) { // 如果当前字符匹配
14.                 j++; // 更新j为下一个字符
15.             }
16.             pi[i] = j; // 更新pi数组
17.         }
18.         for (int i = 0, j = 0; i < n; i++) { // 遍历haystack
19.             while (j > 0 && haystack[i] != needle[j]) { // 如果当前字符不匹配，且j不为0
20.                 j = pi[j - 1]; // 更新j为pi[j-1]
21.             }
22.             if (haystack[i] == needle[j]) { // 如果当前字符匹配
23.                 j++; // 更新j为下一个字符
24.             }
25.             if (j == m) { // 如果j等于needle的长度，说明找到了匹配的子字符串
26.                 return i - m + 1; // 返回needle在haystack中的起始索引
27.             }
28.         }
29.         return -1; // 如果遍历完haystack都没有找到needle，返回-1
30.     }
31. };

复制代码

4.搜索插入位置

https://leetcode.cn/problems/search-insert-position/

1. int searchInsert(int* nums, int numsSize, int target) {
2.     for(int i = 0;i<numsSize;++i)
3.     {
4.         //如果值相等,返回索引
5.         if(nums[i] == target)
6.             return i;
7.         //小于返回当前索引
8.         if(target < nums[i])
9.             return i;
10.     }
11.     //大于所有,返回数组长度
12.     return numsSize;
13. }

复制代码

5.最大子数组和

https://leetcode.cn/problems/maximum-subarray/

1. class Solution {
2. public:
3.     int maxSubArray(vector<int>& nums) {
4.         int pre = 0,maxsum = nums[0];
5.         for(const auto& x: nums)
6.         {
7.             //将x加入到子数组中与x+pre比较大小,更新最大值
8.             pre = max(pre + x, x);
9.             maxsum = max(maxsum,pre);
10.         }
11.         return maxsum;
12.     }
13. };

复制代码

6.末了一个单词的长度

https://leetcode.cn/problems/length-of-last-word/description/

1. class Solution {
2. public:
3.     int lengthOfLastWord(string s) {
4.         int index = s.size() - 1;
6.         while(s[index] == ' ')
7.             index--;
9.         int wordlength = 0;
10.         while(index >= 0 && s[index] != ' ')
11.         {
12.             wordlength++;
13.             index--;
14.         }
15.         return wordlength;
16.     }
17. };

复制代码