LeetCode精华75题（持续更新）

LeetCode刷题笔记

数组/字符串

交替合并字符串

• 题目：

  给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

  返回 合并后的字符串 。

• 题解：

  • C:

    可以利用双指针交替移动获取字符然后存入到结果字符串中，注意结束条件，当其中一个指针到达字符串尾端时，直接将另一字符串的剩余部分加入到结果串中。

    char * mergeAlternately(char * word1, char * word2){// 直接调用strlen函数获取字符串长度int len=strlen(word1)+strlen(word2);// 申请空间，预留结束符的空间char *ans=malloc(len+1);char *p1 = word1;char *p2 = word2;int i=0;while(i<len){ ans[i]=*(p1++);i++;// 注意：字符串的结束符是'\0' 而不是"\0"if(*p1=='\0') // p1到达串1尾端，直接将串2剩余部分加到结果串，结束循环{strcpy(ans+i,p2);break;}ans[i]=*(p2++);i++;  if(*p2=='\0'){strcpy(ans+i,p1);break;}     }ans[len]='\0';	// 添加结束符，防止越界return ans;
    }
    

  • C++:

    可以利用C++的库函数尾插push_back()。

    class Solution {
    public:string mergeAlternately(string word1, string word2) {int m = word1.size();int n = word2.size();string res;res.reserve(m+n);int i=0,j=0;while(i<m||j<n) // 只要有一个字符串没有到达尾端就继续循环{if(i<m)res.push_back(word1[i++]); // 尾插if(j<n)res.push_back(word2[j++]);}return res; // string类型字符串不需要添加结束符}
    };
    

字符串中的最大公因子

• 题目：

  对于字符串 s 和 t，只有在 s = t + t + t + ... + t + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。

  给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 x 能除尽 str2 。

• 题解：

  • C:

    首先要明白最大公因子，意味着这个子串既是str1的子串又是str2的子串，更相减损法求最大公因子，递归。

    char* gcdOfStrings(char* str1, char* str2) {// 求出长串和短串char* lgr = strlen(str1) > strlen(str2) ? str1 : str2;char* shr = strlen(str1) > strlen(str2) ? str2 : str1;if(strcmp(lgr,shr) == 0){return str1; // 两串相等公因子就是本身}if(strncmp(lgr,shr,strlen(shr)) != 0){return "";  // 没有公因子}return gcdOfStrings(lgr + strlen(shr), shr); // 有公因子但是两串不相等，指针向后移动递归
    }
    

  • C++:

    如果 str1 和 str2 拼接后等于 str2和 str1 拼接起来的字符串，那么一定存在符合条件的字符串 X。并且X的长度是str1和str2长度的最大公约数。

    class Solution {
    public:string gcdOfStrings(string str1, string str2) {return(str1+str2==str2+str1 ? str1.substr(0,(gcd(str1.size(), str2.size()))) : "");// gcd() 是c++库函数，求最大公约数// 在C++的std::string类中，length()和size()两个函数在功能上是完全相同的。}
    };
    

拥有最多糖果的孩子

• 题目：

  给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

  对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。

• 题解：

  • C：

    先获取最大值，然后再将每一项加上额外的数然后和最大值比对。bool类型是C99的新特性，赋值的时候注意不是字符串。

    bool* kidsWithCandies(int* candies, int candiesSize, int extraCandies,int* returnSize) {bool* ret = (bool*)malloc(sizeof(bool) * candiesSize); // 申请堆区空间，栈区空间在函数调用后会释放*returnSize = candiesSize;int max = -1;// 找出当前最大值for (int i = 0; i < candiesSize; i++) {max = candies[i] >= max ? candies[i] : max;}// 判断加上extra是否大于最大值for (int i = 0; i < candiesSize; i++) {ret[i] = candies[i] + extraCandies >= max ? true : false;// 由于新bool类型，也可以如下写法// ret[i] = candies[i] + extraCandies >= max;}return ret;
    }
    

  • C++：

    利用vector容器来操作数据会更加方便，std::max_element 是 C++ 标准库 <algorithm> 头文件中定义的一个算法，用于在一个序列中查找最大元素。这个函数返回指向序列中最大元素的迭代器，而不是返回实际的最大值。如果序列为空，它将返回指向序列末尾的迭代器。

    class Solution {
    public:vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {vector<bool> res;int max=*max_element(candies.begin(), candies.end());vector<int>::iterator it_int = candies.begin();for (; it_int != candies.end(); it_int++) {res.push_back((*it_int) + extraCandies >= max );}return res;}
    };
    

种花问题

• 题目：

  假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

  给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

• 题解：

  • C:

    贪心算法：在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法。能种花先种花种完之后再看是否还有剩余，可以通过新建数组再首尾添0来简化判断。

    bool canPlaceFlowers(int* flowerbed, int flowerbedSize, int n) {// 新建数组的容量比原本数组容量加2int new[flowerbedSize + 2];// 拷贝,然后首位置零for (int i = 1, j = 0; j < flowerbedSize; i++, j++) {new[i] = flowerbed[j];}new[0] = 0;new[flowerbedSize + 1] = 0;// 如果前一位和后一位都为0的情况即可种花for (int i = 1; i < flowerbedSize + 1; i++) {if (new[i - 1] == 0 && new[i + 1] == 0 && new[i] != 1) {new[i] = 1;n--;}}// 直接返回bool值return n <= 0;
    }
    

  • C++:

    使用跳格子法，因为题目给的数组不存在相邻为1的情况，所以若当前为1直接跳两格，为0且到达末尾或者下一格为0可以栽花，为0但下一格为1需要跳三格。

    class Solution {
    public:bool canPlaceFlowers(vector<int>& flowerbed, int n) {int i = 0;// 不适用迭代器，会访问越界while (i < flowerbed.size()) {if (flowerbed[i] == 1) {i += 2;} else {if (i == flowerbed.size() - 1 || flowerbed[i + 1] == 0) {// if ( flowerbed[i + 1] == 0 ||i == flowerbed.size() - 1) 是错误的，会发生下表越界，利用逻辑短路的特性避免n--;i += 2;} else {i += 3;}}}return n <= 0;}
    };