记录一些和字符数组有关的题目

之前代码随想录day08里面有一些涉及翻转字符串的操作可以一起回顾。

8.字符串转换整数（atoi）

        除了单纯的转换之外还涉及到去空格，判断正负，以及判断是否溢出的操作。

 int myAtoi(char* s) {int i=0;bool flag=0;int n=strlen(s);//对空格进行操作while(i<n&&s[i]==' ') i++;if(i<n&&s[i]=='-'){//负数flag=1;i++;}else if(i<n&&s[i]=='+'){//正数flag=0;i++;}int sum=0;for(;i<strlen(s);++i){if(s[i]>='0'&&s[i]<='9'){//判断是否溢出，溢出就返回最大或者最小值if (sum>(INT_MAX-(s[i]-'0'))/10) {return flag==0? INT_MAX : INT_MIN;}sum=sum*10+(s[i]-'0');}else{//一旦碰到不是数字的值直接跳出循环break;} }if(flag) return -sum;return sum;
}

670.最大交换

        这题最开始想错了，还以为是找到最大的字符和第一个字符交换就完事了，但是如果第一个字符已经最大则需要把次大的字符交换到第二位，以此类推。这道题主要是要注意字符数组的各种操作一定要非常熟练。

        错误代码：

        用到了整数转字符数组，字符数组转整数的很原始的操作，可以用sprintf与atoi进行代替。

int maximumSwap(int num) {char str[10];int len=0;int temp=num;while(temp){int cur=temp%10;char s=cur+'0';str[len++]=s;temp/=10;}str[len]='\0';//找最大的那个数char mm=str[0];int index=0;for(int i=0;i<len;++i){if(str[i]>mm){index=i;}}//跟头一个数交交换char t=str[len-1];str[len-1]=str[index];str[index]=t;//字符数组化为数字int ans=0;for(int i=len-1;i>=0;--i){ans=ans*10+str[i]-'0';}return ans;
}

        正确解法：暴力解

void swap(char* s1,char* s2){char temp=*s1;*s1=*s2;*s2=temp;
}
int maximumSwap(int num) {char str[100];sprintf(str,"%d",num);int n=strlen(str);int mmax=num;for(int i=0;i<n;++i){for(int j=i+1;j<n;++j){swap(&str[i],&str[j]);mmax=fmax(mmax,atoi(str));//更新最大值swap(&str[i],&str[j]);//恢复}}return mmax;
}

        贪心算法：

        每一位数字应该不小于所有排它后面的数字，否则找最大的且排最后面的数字与之交换

void swap(char* s1,char* s2){char temp=*s1;*s1=*s2;*s2=temp;
}
int maximumSwap(int num) {char str[100];sprintf(str,"%d",num);int n=strlen(str);int maxIdx=n-1;int idx1=-1,idx2=-1;for(int i=n-1;i>=0;--i){if(str[i]>str[maxIdx]){maxIdx=i;}else if(str[i]<str[maxIdx]){idx1=i;idx2=maxIdx;}}if(idx1>=0){swap(&str[idx1],&str[idx2]);return atoi(str);}else{return num;}
}

 179.最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出："210"

         此题重要的一点是如何写比较函数，要将两个数字拼接到一起进行比较，因此要确定放在后面的数字的位数，让方前面的数字去乘相应的位数的值，大的那个数要放在前面，就是y x大就把y放在x的前面，相当于y<x

unsigned long long cmp(int* x,int* y){unsigned long long sx=10,sy=10;while(sx<=*x){sx*=10;}while(sy<=*y){sy*=10;}return sx*(*y)+(*x)-sy*(*x)-(*y);//会溢出
}
char* largestNumber(int* nums, int numsSize) {qsort(nums,numsSize,sizeof(int),cmp);if(nums[0]==0){char *ret=malloc(sizeof(char)*2);ret[0]='0',ret[1]='\0';return ret;}char *ret=malloc(sizeof(char)*1000);char *p=ret;for(int i=0;i<numsSize;++i){sprintf(p,"%d",nums[i]);p+=strlen(p);}return ret;
}

402.移除k位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 ：

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

        从0到n-1进行遍历，如果下一个数字小就替换，大就保留当前值。

        同一个单调栈存能够留下的元素，每次判断栈顶的元素能否留下。 

class Solution {
public:string removeKdigits(string num, int k) {vector<char> stk;for (auto& digit: num) {while (stk.size() > 0 && stk.back() > digit && k) {//栈不为空，栈顶元素比当前值大时，需要替换stk.pop_back();k -= 1;}stk.push_back(digit);}//如果k不为0时，将栈顶元素都弹出for (; k > 0; --k) {stk.pop_back();}string ans = "";bool isLeadingZero = true;for (auto& digit: stk) {//去掉前面的0if (isLeadingZero && digit == '0') {continue;}isLeadingZero = false;ans += digit;}return ans == "" ? "0" : ans;}
};

318.最大单词长度的乘积

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"

        此题关键在于怎样判断两个字符串没有公共字符，而这里使用的是位运算。 

int maxProduct(char ** words, int wordsSize){int makes[wordsSize];for(int i=0;i<wordsSize;++i){makes[i]=0;for(int j=0;j<strlen(words[i]);++j){makes[i]|=1<<(words[i][j]-'a');//记录第i-1个字符串的字符}}int ans=0;for(int i=0;i<wordsSize;++i){for(int j=i+1;j<wordsSize;++j){if((makes[i]&makes[j])==0){//如果没有重复的字符int cur=strlen(words[i])*strlen(words[j]);if(cur>ans){ans=cur;}}}}return ans;
}

1143.最长公共子序列

        给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

        一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

        二维数组动态规划，其中 dp[i][j] 表示 text1[0:i]、text2[0:j]的最长公共子序列的长度。注意初始化数组用函数memset（dp，0，sizeof(dp)）

int longestCommonSubsequence(char* text1, char* text2) {int m=strlen(text1),n=strlen(text2);int dp[m+1][n+1];memset(dp,0,sizeof(dp));for(int i=1;i<=m;++i){char c1=text1[i-1];for(int j=1;j<=n;++j){char c2=text2[j-1];if(c1==c2){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=fmax(dp[i-1][j],dp[i][j-1]);}}}return dp[m][n];
}

647.回文子串

        计算回文子串的个数。

         枚举回文串的中心，中心可能是一个，也可能是两个，然后从中心向两边拓展，如果不相等就退出循环。

int countSubstrings(char* s) {int n=strlen(s),ans=0;//枚举回文串的中心for(int i=0;i<n;++i){for(int j=0;j<=1;++j){//j=0,中心是一个点，j=1,中心是两个点int l=i;int r=i+j;while(l>=0&&r<n&&s[l--]==s[r++]){ans++;}}}return ans;
}

5.最长回文子串

 给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

            第一次不通过是因为误认为只要i从前往后遍历，j从后往前遍历，就可以发现最长的子串，但是一个break只能跳出一层循环，因此还会继续遍历，因此还需要记录最大长度，只有大于这个最大长度时才会更新左右下标。

bool isvaild(char *s,int l,int r){while(l<r){if(s[l]!=s[r]){return false;}l++;r--;}return true;
}
char* longestPalindrome(char* s) {int n=strlen(s);if(n<2) return s;int left=0,right=0;int mmax=0;for(int i=0;i<n;++i){for(int j=n-1;j>i;--j){if(isvaild(s,i,j)&&(j-i+1)>mmax){left=i;right=j;mmax=j-i+1;break;}}}char* ans=malloc(sizeof(char)*(n+1));int t=0;for(int i=left;i<=right;++i){ans[t++]=s[i];}ans[t]='\0';return ans;
}

97.交错字符串 

 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

        动态规划：dp(i,j) 表示s1的前i个元素和 s2的前j个元素是否能交错组成 s3的前i+j个元素,

bool isInterleave(char* s1, char* s2, char* s3) {int n=strlen(s1),m=strlen(s2),t=strlen(s3);int dp[n+1][m+1];//dp(i,j) 表示s1的前i个元素和 s2的前j个元素是否能交错组成 s3的前i+j个元素memset(dp,0,sizeof(dp));if(n+m!=t) return false;dp[0][0]=true;for(int i=0;i<=n;++i){for(int j=0;j<=m;++j){int p=i+j-1;if(i>0){dp[i][j]|=(dp[i-1][j]&&s1[i-1]==s3[p]);}if(j>0){dp[i][j]|=(dp[i][j-1]&&s2[j-1]==s3[p]);}}}return dp[n][m];
}

151.反转字符串中的单词 

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the

        翻转字符串，还有去除多余空格的操作。 

//翻转字符串
void reverse(char *s,int left,int right){int i=left,j=right-1;while(i<j){char temp=s[i];s[i]=s[j];s[j]=temp;i++;j--;}
}
//除去单词两端的空格
void removeExtraSpace(char* s) {int start = 0; int end = strlen(s) - 1; while (s[start] == ' ') start++; //找到第一个非空格字符while (s[end] == ' ') end--; // 找到第一个非空格字符int slow = 0; // 指向新字符串的下一个写入位置的指针for (int i = start; i <= end; i++) { if (s[i] == ' ' && s[i+1] == ' ')  { // 如果当前字符是空格，并且下一个字符也是空格，则跳过continue;}s[slow] = s[i]; // 否则，将当前字符复制到新字符串的 slow 位置slow++;}s[slow] = '\0'; // 在新字符串的末尾添加一个空字符
}
char* reverseWords(char* s) {removeExtraSpace(s);int n=strlen(s);reverse(s,0,n);//翻转整个字符串int slow=0;for(int i=0;i<=n;++i){if(s[i]==' '||s[i]=='\0'){//一个单词结束reverse(s,slow,i);slow=i+1;//指向下一个单词}}return s;
}

557.反转字符串中的单词 III

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1：

输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc" 

void swap(char *a,char *b){char temp=*a;*a=*b;*b=temp;return;
}
char* reverseWords(char* s) {int n=strlen(s);int i=0;while(i<n){int l=i;//确定单词首尾while(i<n&&s[i]!=' '){i++;}int r=i-1;//翻转while(l<r){swap(s+l,s+r);l++;r--;}//去空格while(i<n&&s[i]==' '){i++;}}return s;
}

402.移除K位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 ：

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

        单调栈的思想，用一个数组模拟栈，且栈中元素始终保持单调。遍历数组，如果下一个元素大于前一个元素，直接存入数组，如果下一个元素小于栈顶元素，将刚刚存入的数依次弹出，k--，然后继续进行判断，如果最后k不为0，则将栈顶的元素弹出。

 

char * removeKdigits(char * num, int k){int n=strlen(num);int top=0;//top指向当前的栈顶char* stk=malloc(sizeof(char)*(n+1));stk[0]=num[0];for(int i=1;i<n;++i){while(top>=0&&stk[top]>num[i]&&k>0){top--;k--;}stk[++top]=num[i];}//k不为0时弹出栈顶top-=k;char* ans=malloc(sizeof(char)*(n+1));int anssize=0;bool isZore=true;//将开头的0去除for(int i=0;i<=top;++i){if(isZore&&stk[i]=='0'){continue;}isZore=false;ans[anssize++]=stk[i];}//判断是否为0if(anssize==0){ans[0]='0';ans[1] ='\0';}else{ans[anssize]='\0';}return ans;
}

415.字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：

输入：num1 = "11", num2 = "123"
输出："134"

char * addStrings(char * num1, char * num2){int i=strlen(num1)-1,j=strlen(num2)-1;char* ans=malloc(sizeof(char)*(i+j+3));int ll=0;int carry=0;while(i>=0||j>=0){int x=i>=0?num1[i]-'0':0;int y=j>=0?num2[j]-'0':0;int sum=x+y+carry;carry=sum/10;sum=sum%10;ans[ll++]='0'+sum;i--;j--;}if(carry) ans[ll++]='1';ans[ll]='\0';int l=0,r=strlen(ans)-1;while(l<r){char t=ans[l];ans[l]=ans[r];ans[r]=t;l++;r--;}return ans;
}

459.重复的子字符串

 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

bool repeatedSubstringPattern(char* s) {int n=strlen(s);int j=0;//枚举子串长度for(int i=1;i<n;++i){//判断是否总长度为子串的整数倍if(n%i==0){bool match=true;//依次向后遍历判断for(int j=i;j<n;++j){if(s[j]!=s[j-i]){match=false;break;}} if(match) return true;}}return false;
}