发布时间：2025-12-09 11:46:07 浏览次数：1
刷题是应届生找工作不可缺少的部分,一种公认的刷题策略是按类别刷题,可是每个类别也有许多题,在有限的时间里到底该刷哪些题呢?个人根据LeetCode官方给出的每个题目的出现频率,整理并收录了每个类别里高频出现的题目,对于官方统计频率太低的题目,不予收录。
整理了下力扣中字符串的高频题目,题目名称后面括号里的数字表示的是出现频率,当时做题的时候顺便把相似的题目也做了。有些题目思路确实不好想,需要多多思考。有些题目看了几遍也没有看懂,比如外观序列这个,先放着。题目以后还会更新一些。
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
示例 1: 输入: “()” 输出: true 示例 2: 输入: “()[]{}” 输出: true 示例 3: 输入: “(]” 输出: false 示例 4: 输入: “([)]” 输出: false 示例 5: 输入: “{[]}” 输出: true
/*这是一道很简单的题目,用栈可以很轻松的实现当左括号出现的时候入栈,当右括号出现的出栈,如果匹配就继续,不匹配就错误当字符串遍历完成之后,栈内仍有字符串就错误用一个数组进行和一个记录栈顶值的int进行了栈的模拟,代码很简单,很好理解(虽说题目也很简单就是了)*/bool isValid(char * s){ int len = strlen(s); char stack[3500]; int top = -1; int i = 0; for( i=0;i<len;i++) { if((s[i] == '(')||(s[i] == '{')||(s[i] == '[')) stack[++top] = s[i]; else { if(top<0)//出现了右括号,但数组为空,即没有左括号与之匹配 return false; if((s[i] == ')')) { if(stack[top]!='(') return false; else top--; } if((s[i] == '}')) { if(stack[top]!='{') return false; else top--; } if((s[i] == ']')) { if(stack[top]!='[') return false; else top--; } } } if(top>=0) //数组内仍有左括号,没有右括号与之匹配 return false; //这里一定要有返回值 return true;}数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例: 输入:n = 3 输出:[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]
回溯算法,以后再看
/** * Note: The returned array must be malloced, assume caller calls free(). *//** * Note: The returned array must be malloced, assume caller calls free(). */ void generate(char *item,int index,int left,int right,char **result,int *count,int n) { if(left==0&&right==0)//已经全部插满了 { result[(*count)]=(char*)malloc(sizeof(char)*(2*n+1)); strcpy(result[(*count)++],item); return; } //result[(*count)++][]=item; item[index]='(';//插入左括号 item[index+1]=''; if(left>0) generate(item,index+1,left-1,right,result,count,n); if(right>left)//待插入右括号的个数多余待插入左括号的个数 { item[index]=')';//插入右括号 generate(item,index+1,left,right-1,result,count,n); } }char ** generateParenthesis(int n, int* returnSize){ //左右括号的总个数 int left=n,right=n; int length=2*2*n; int count=0;//记录已经插入的个数 int index=0;//记录当前插入元素的下标 char **result=(char **)malloc(sizeof(char *)*(5000));//创建二维数组 char *item=(char *)malloc(sizeof(char)*(2*n+1));//创建存储数组 generate(item,index,left,right,result,&count,n); *returnSize=count; return result;}给定有效字符串 “abc”。
对于任何有效的字符串 V,我们可以将 V 分成两个部分 X 和 Y,使得 X + Y(X 与 Y 连接)等于 V。(X 或 Y 可以为空。)那么,X + “abc” + Y 也同样是有效的。
例如,如果 S = “abc”,则有效字符串的示例是:“abc”,“aabcbc”,“abcabc”,“abcabcababcc”。无效字符串的示例是:“abccba”,“ab”,“cababc”,“bac”。
如果给定字符串 S 有效,则返回 true;否则,返回 false。
示例 1: 输入:“aabcbc” 输出:true 解释: 从有效字符串 “abc” 开始。 然后我们可以在 “a” 和 “bc” 之间插入另一个 “abc”,产生 “a” + “abc” + “bc”,即 “aabcbc”。 示例 2: 输入:“abcabcababcc” 输出:true 解释: “abcabcabc” 是有效的,它可以视作在原串后连续插入 “abc”。 然后我们可以在最后一个字母之前插入 “abc”,产生 “abcabcab” + “abc” + “c”,即 “abcabcababcc”。 示例 3: 输入:“abccba” 输出:false 示例 4: 输入:“cababc” 输出:false 提示: 1 <= S.length <= 20000 S[i] 为 ‘a’、‘b’、或 ‘c’
题目有点绕,其实原理类似与消消乐,abc相遇会消去,看下最后的字符串是否都可以消完,能消除完全就返回true,不能则返回false。
本题可以利用栈来解决,思路如下: 如果字母不为c,则入栈;否则,判断栈顶是否为ba,如果是则出栈,不是则返回false。当字符串整个处理结束时,判断栈是否为空,不为空则返回false。
char* stack;int top;void Push(char val){ stack[++top] = val;}void Pop(){ top--;}char Gettop() { if(top>=0) return stack[top]; else return '0';}bool isValid(char * S){ int len = strlen(S); stack = (char*)calloc(sizeof(char), len); top = -1; for (int i = 0; i < len; i++) { //入栈 if (S[i] != 'c') { Push(S[i]); } else { //不为b则false if (Gettop() != 'b') return false; Pop(); //不为b则false if (Gettop() != 'a') return false; Pop(); } } //如果栈中没有元素,则为true if (top < 0) return true; return false;}注意要从低位开始进行计算,模拟进位的操作。将字符串的ascii码-48就可以得到实际的数值。注意计算进位的时候要加上carry。三目运算符的运用可以减少代码的复杂度。
给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。
注意: num1 和num2 的长度都小于 5100. num1 和num2 都只包含数字 0-9. num1 和num2 都不包含任何前导零。 你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。
因为最大可能就是两个都是5100个9,进位最多产生2个位,因此加上末尾的’’那么够多了。 注意:不能开函数体内,因为里面res[5103]栈内存,虽然这个够小完全可以开,但是返回返回结束就小时,再次访问可能是NULL或者报错。解决办法在函数体内用关键字static char res[5103],这跟下面代码放在全局是一样的。
char res[5103] = {''};char * addStrings(char * num1, char * num2){ short s1 = strlen(num1), s2 = strlen(num2), len = 5101, carry = 0; for (s1--, s2--; s1 >= 0 || s2 >= 0 || carry;) { //长度为0时,数值取0 carry += (s1 >= 0 ? num1[s1--] - 48: 0) + (s2 >= 0 ? num2[s2--] - 48 : 0); // 最长遍历处理 res[len--] = carry % 10 + 48; carry /= 10; } return &res[len+1]; // 返回指针,取地址}给你两个二进制字符串,返回它们的和(用二进制表示)。 输入为 非空 字符串且只包含数字 1 和 0。
示例 1: 输入: a = “11”, b = “1” 输出: “100” 示例 2: 输入: a = “1010”, b = “1011” 输出: “10101” 提示: 每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。 1 <= a.length, b.length <= 10^4 字符串如果不是 “0” ,就都不含前导零。
这种不管是十进制的加减还是二进制的加减本质都是一样的,定义一个carry变量足够了,只要注意下数组的边界条件和结束条件,写对没问题。
char * addBinary(char * a, char * b){ int carry = 0;//进位int length = (strlen(a)>strlen(b)? strlen(a)+2:strlen(b)+2);char* result = (char*)malloc(sizeof(char)*length);//开辟空间result[length-1] = '';//多开辟两个空间 一个存储进位,一个存储结束符for(int i = strlen(a)-1,j = strlen(b)-1,k = length -2; (i >=0)||(j >= 0); i--,j--,k--){int sum = carry;sum += (i >= 0? a[i]-'0':0);sum += (j >= 0? b[j]-'0':0);carry = sum /2;result[k] = '0'+ sum % 2;}if(carry == 0) //最后无进位,直接返回//为什么result+1可以 result[0]+1会报错return result+1; else result[0] = '1'; //有进位,补一个最高位return result;}简洁代码
char * addBinary(char * a, char * b){ int len1 = strlen(a)-1; int len2 = strlen(b)-1; int carry = 0; //多开辟了两个空间存储进位和结束符 char*res = (char*)malloc(sizeof(char)*10002); //倒着开始存储 int cnt = 10000; res[10001] = ''; while(len1>=0||len2>=0||carry) { //注意判断数组是否为空 carry +=(len1<0?0:a[len1]-'0')+(len2<0?0:b[len2]-'0'); res[cnt--] = carry%2+48; carry = carry/2; //注意判断结束条件len1 len2 len1 = (len1>=0?len1-1:-1); len2 = (len2>=0?len2-1:-1); } return &res[cnt+1];}给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
示例 1: 输入: num1 = “2”, num2 = “3” 输出: “6” 示例 2: 输入: num1 = “123”, num2 = “456” 输出: “56088” 说明: num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头,除非是数字 0 本身。 不能使用任何标准库的大数类型(比如 BigInteger)或直接将输入转换为整数来处理。
这道题让我们求两个字符串数字的相乘,输入的两个数和返回的数都是以字符串格式储存的,这样做的原因可能是这样可以计算超大数相乘,可以不受 int 或 long 的数值范围的限制,那么该如何来计算乘法呢,小时候都学过多位数的乘法过程,都是每位相乘然后错位相加,那么这里就是用到这种方法,举个例子,比如 89 x 76,那么根据小学的算术知识,不难写出计算过程如下:
8 9 <- num2 7 6 <- num1------- 5 4 4 8 6 35 6-------6 7 6 4再写些例子出来,比如 125 x 48,计算过程如下:
1 2 5 <- num2 8 8 <- num1----------- 4 0 1 6 8 4 0 1 6 8----------- 1 1 0 0 0不难发现,以下三点:
两数相乘得到的乘积的长度不会超过两个数字的长度之和,若num1长度为length1,num2 长度为lenght2,则 num1 x num2 的长度不会超过 length1 + length2 还有就是乘的时候需要错位的原因,比如6 x 8得到的 48 为啥要跟6 x 9得到的 54 错位相加,因为 8 是十位上的数字,其本身相当于80,所以错开的一位实际上末尾需要补的0 num1 和 num2 中任意位置的两个数字相乘,得到的两位数在最终结果中的位置是确定的,比如 num1 中位置为i的数字乘以 num2 中位置为j的数字,那么得到的两位数字的位置为 i+j 和 i+j+1,这也是由错位相乘引起的 首先开辟两个空间,一个用来存储错位相乘的中间结果,int类型,另外一个作为最终返回的结果,char类型。需要注意的是后一个指针需要比totalLength多一个字符用来在C语言当中指示字符串数组的结束,对于int类型的中间结果初始化为0。
由于要从个位上开始相乘,所以从 num1 和 num2 字符串的尾部开始往前遍历,分别提取出对应位置上的字符,将其转为整型后相乘,将num1[i]与num[j]相乘的结果累加存储在value[i+j+1]当中,注意这里是累加。以上面的 89 x 76 为例,num1[1] x num2[0]的结果 48 是需要与num1[0] x num2[1]的结果 63相加以后一并存储在value[2]当中再进入下一步的处理工序的。
在进入下一道工序之前,我们先看看下面这段代码运行以后的结果:
for(int i = length1 - 1; i >= 0; i--){ for(int j = length2 - 1; j >= 0; j--) { value[i + j + 1] += (num1[i] - '0') * (num2[j] - '0'); }}依然以 89 x 76 为例,运行以后value数组的存储结构如下:
0 1 2 3 -----------------------| 0 | 56 | 111 | 54 | -----------------------后面就是要对value数组进行修改,改保留的保留,改相加的相加,改进位的进位 ,通过以下三行代码:
for(int i= totalLength - 1; i > 0; i--) //获取每个位置上面的数字并处理进位 { value[i - 1] += value[i] / 10; value[i] %= 10; }最终得到的value数组如下:
0 1 2 3 -----------------------| 6 | 7 | 6 | 4 | -----------------------这三行代码主要做了两件事,首先依然从数组的尾部开始遍历,将第i位的高位通过/累加到第i-1位,然后通过%求余获得当前位的数字。
后面在将数字转化成字符拷贝到待返回的结果之前需要将多余的 0 去掉。
具体的代码如下:
char * multiply(char * num1, char * num2){ int length1 = strlen(num1); int length2 = strlen(num2); int totalLength = length1 + length2; //获取相乘后字符串的总有效位数 int charIndex = 0; //定义负责索引字段 int valueIndex = 0; //int *value = (int *)malloc(sizeof(int) * totalLength); //memset(value, 0, sizeof(int) * totalLength); int *value = (int *)calloc(totalLength,sizeof(int)); //char *result = (char *)malloc(sizeof(char) * (totalLength + 1)); char *result =(char *)calloc(totalLength + 1,sizeof(char)); for(int i = length1 - 1; i >= 0; i--) { for(int j = length2 - 1; j >= 0; j--) { value[i + j + 1] += (num1[i] - '0') * (num2[j] - '0'); } } //获取每个位置上面的数字并处理进位 for(int i= totalLength - 1; i > 0; i--) { //后一个的进位要加到前一个 取商获得进位 value[i - 1] += value[i] / 10; //当前位置只保留余数 value[i] %= 10; } // //忽略掉前面多余的0,但是最高位也就是唯一的一位0不能忽略 //因为我们设置的最大长度为length1 + length2,并且初始化为了0,实际长度有可能没有占满,前面会有多于的0,处理掉 while(value[valueIndex] == 0 && valueIndex < totalLength -1 ) { valueIndex++; } //将数值转化为字符串 while(valueIndex < totalLength) { result[charIndex++] = value[valueIndex++] + '0'; } result[charIndex] = ''; //默认补上字符串的终止符 return result; }给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例: 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){ struct ListNode* l3 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* p1 = l1; struct ListNode* p2 = l2; struct ListNode* q = l3; int carry = 0; int sum = 0; while((p1!=NULL) ||(p2!=NULL)) { sum = 0; if(p1!=NULL) { sum += p1->val; printf("sum:%drn",sum); } if(p2!=NULL) { sum += p2->val; printf("sum:%drn",sum); } printf("sum:%d,carry:%drn",sum,carry); struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode)); temp->val = sum%10+carry; carry = (sum>=10)? 1 : 0; printf("temp->val:%drn",temp->val); printf("rn"); temp->next = NULL; q->next = temp; q = temp; p1 = p1->next; p2 = p2->next; } return l3->next;}给你两个字符串,请你从这两个字符串中找出最长的特殊序列。 「最长特殊序列」定义如下:该序列为某字符串独有的最长子序列(即不能是其他字符串的子序列)。 子序列 可以通过删去字符串中的某些字符实现,但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列,任何字符串为其自身的子序列。 输入为两个字符串,输出最长特殊序列的长度。如果不存在,则返回 -1。
示例 1: 输入: “aba”, “cdc” 输出: 3 解释: 最长特殊序列可为 “aba” (或 “cdc”),两者均为自身的子序列且不是对方的子序列。 示例 2: 输入:a = “aaa”, b = “bbb” 输出:3 示例 3: 输入:a = “aaa”, b = “aaa” 输出:-1 提示: 两个字符串长度均处于区间 [1 - 100] 。 字符串中的字符仅含有 ‘a’~‘z’ 。
标签:题意理解,本题题意难于理解 独有指的是只有自己有,另一个字符串没有 举例说明,设两个字符串变量名分别为 a 和 b a = ‘c’, b = ‘cd’,‘cd’ 是 b 独有的,所以最长子序列为 ‘cd’,长度为 2 a = ‘cd’, b = ‘cd’, ‘cd’, ‘c’, ‘d’ 在两个字符串中都有,所以不存在独有的最长子序列,返回 -1 通过举例分析,得出以下结论: 如果两个字符串长度不一样,则较长的字符串本身不可能是短字符串的子序列,直接返回其长度即可 如果两个字符串内容相等,那么他们独有的最长子序列不存在,返回 -1
int findLUSlength(char * a, char * b){ int lenA=strlen(a),lenB=strlen(b); if (strcmp(a,b)==0)return -1; return lenA>lenB?lenA:lenB;}给定字符串列表,你需要从它们中找出最长的特殊序列。最长特殊序列定义如下:该序列为某字符串独有的最长子序列(即不能是其他字符串的子序列)。 子序列可以通过删去字符串中的某些字符实现,但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列,任何字符串为其自身的子序列。 输入将是一个字符串列表,输出是最长特殊序列的长度。如果最长特殊序列不存在,返回 -1 。
示例: 输入: “aba”, “cdc”, “eae” 输出: 3 提示: 所有给定的字符串长度不会超过 10 。 给定字符串列表的长度将在 [2, 50 ] 之间。
思路分析: 请先翻阅 LeetCode 最长特殊序列I 由上一题我们知道判断两个字符串的最长特殊序列只要比较两个字符串是否相等、长度即可, 但是在此道题并不能这样判断,因为长度大的字符串可能存在重复(重复了一定不能作为 整个字符串数组的最长特殊序列),长度短的字符串可能是长度大的字符串的子序列。 (比如“ab”是“acbd”的子序列)。所以我们的重新定义两个字符串是否是子序列的问题。
算法如下: 第一步:将整个字符串数组按照长度降序排序 第二步:统计各个字符串出现的次数 第三步:寻找可以作为整个字符串数组的最长序列
// 按照字符串长度降序排序// 字符串比较:如果该字符串不是之前字符串的子序列,//而且与后面跟他长度相同的字符串不是相同的字符串,则该字符串本身为特殊序列// 如果跟后面字符串比较是重复的话,顺序到不是重复的下一个字符串再进行判断int cmp1(const void *a, const void *b){ return strlen(*(char **)b) - strlen(*(char **)a);}int cmp2(const void *a, const void *b){ return strcmp(*(char **)a, *(char **)b);}//a是不是b的子序列 a为当前序列 b为当前序列之前的序列bool isSequence(char *a, char *b){ int len1 = strlen(a); int len2 = strlen(b); printf("%d,%drn",len1,len2); int count = 0; int j = 0; for (int i = 0; i < len1; i++) { while (j < len2) { if (a[i] == b[j++]) { count++; break; } // j++; } } if (count == len1) return true; return false;}int findLUSlength(char ** strs, int strsSize){ bool flag = false; qsort(strs, strsSize, sizeof(strs[0]), cmp2); qsort(strs, strsSize, sizeof(strs[0]), cmp1); // 向前查询是否为子串 for (int i = 0; i < strsSize; i++) { bool f1 = true, f2 = true; //从第二个序列开始,往前查询 之前的序列是否为当前序列的子序列 if (i >= 1) { for (int j = 0; j < i; j++) { //第二个序列strs[i] 是不是第一个序列strs[j]的子序列 if (isSequence(strs[i], strs[j])) { f1 = false; break; } } } // 向后查询有无重复字符串 for (int k = i + 1; k < strsSize; k++) { //长度不同 内容肯定不同 跳出循环,继续往后比较 if (strlen(strs[k]) != strlen(strs[i])) break; //长度相同时,比较内容是否相同 if (strcmp(strs[k], strs[i]) == 0) { f2 = false; //内容不同时,将从此序列开始比较 i = k; } } if (f1 && f2) return strlen(strs[i]); } return -1;}编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1: 输入:[“h”,“e”,“l”,“l”,“o”] 输出:[“o”,“l”,“l”,“e”,“h”] 示例 2: 输入:[“H”,“a”,“n”,“n”,“a”,“h”] 输出:[“h”,“a”,“n”,“n”,“a”,“H”]
常规题目,定义两个变量,同时从开头和结尾遍历,交换字符即可
void swap(char *s,int start,int end){ while(start<end) { char temp; temp = s[start]; s[start] = s[end]; s[end] = temp; start++; end--; }}void reverseString(char* s, int sSize){ int start = 0; int end = sSize-1; swap(s,start,end); }给定一个字符串 s 和一个整数 k,你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。 如果剩余字符少于 k 个,则将剩余字符全部反转。 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。
示例: 输入: s = “abcdefg”, k = 2 输出: “bacdfeg” 提示: 该字符串只包含小写英文字母。 给定字符串的长度和 k 在 [1, 10000] 范围内。
void swap(char *str,int start,int end){ while(start<end) { char temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; }}char * reverseStr(char * s, int k){ int len = strlen(s); for (int i = 0; i < len; i += 2 * k) { int start = i; //如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。 //如果剩余字符少于 k 个,则将剩余字符全部反转。 int end = (len-start+1 >k ) ? i + k - 1 : len - 1; //是否超界? swap(s,start,end); } return s;}给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
示例 1: 输入: “Let’s take LeetCode contest” 输出: “s’teL ekat edoCteeL tsetnoc” 注意:在字符串中,每个单词由单个空格分隔,并且字符串中不会有任何额外的空格。
void swap(char *str,int start,int end){ while(start<end) { char temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; }}char * reverseWords(char * s){ int i = 0; int start = 0; int end = 0; int len = strlen(s); while(s[end++]!='') { //注意边界条件 if(s[end] == ' ' || s[end] == '') { swap(s,start,end-1); start = end+1; } } return s;}编写一个函数,以字符串作为输入,反转该字符串中的元音字母。
示例 1: 输入: “hello” 输出: “holle” 示例 2: 输入: “leetcode” 输出: “leotcede” 说明: 元音字母不包含字母"y"。
和之前的反转字符串差不多,只不过在反转以前要判断下是否是元音字母,注意大写字母也要判断。
void swap(char *str,int start,int end){ char temp = str[start]; str[start] = str[end]; str[end] = temp;}int vowel(char c){ if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') return 1; else return 0;}char * reverseVowels(char * s){ int i = 0 int j = strlen(s) - 1; while(i < j) { //注意不要越界 while(i < j && !vowel(s[i])) i++; while(i < j && !vowel(s[j])) j--; swap(s,i,j); i++; j--; } return s;}给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串B成为叠加后的字符串A的子串,如果不存在则返回 -1。
举个例子,A = “abcd”,B = “cdabcdab”。 答案为 3, 因为 A 重复叠加三遍后为 “abcdabcdabcd”,此时 B 是其子串;A 重复叠加两遍后为"abcdabcd",B 并不是其子串。 注意: A 与 B 字符串的长度在1和10000区间范围内。
解题思路 构造新字符串,每次增加复制一次字符串A,判断B是否为A的字串,直到多复制2次A之后如果B仍然不是A的子串,那么返回-1
关于重复次数的解释: 当lenA>lenB,如果B是A的子串的话 1.B可能在A的中间 2.可能是在A的末尾和A的开头组成的字符串,这种情况需要复制一次,类似AA. 因此,我们要最少复制1次,newStr的空间大小max * lenA + 1,为才可以有2的情况。情况1不用复制就可以出现
当lenA<lenB,如果B是A的子串的话 1.B不可能在A的中间 2.首先要保证lenA>lenB,所以最少复制的次数为lenB/lenA。 3.其次,如同上面的情况1,2
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
int repeatedStringMatch(char * A, char * B){ int lenA = strlen(A); int lenB = strlen(B); //最大复制次数 int max = lenB / lenA + 2; //空间大小的确定 char newStr[max * lenA + 1]; memset(newStr, 0, sizeof(newStr)); for (int i = 0; i < max; i++) { strcat(newStr, A); char *tmp = NULL; if (strlen(newStr) >= strlen(B)) { tmp = strstr(newStr, B); } if (tmp == NULL) { continue; } else { return i + 1; } } return -1;}给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。
示例 1: 输入: “abab” 输出: True 解释: 可由子字符串 “ab” 重复两次构成。 示例 2: 输入: “aba” 输出: False 示例 3: 输入: “abcabcabcabc” 输出: True 解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)
如果一个字符串可以由多个重复子串构成,即具有循环节。设最小循环节用a来表示,他代表通过子串a重复多次可以构成s。 即s换成a来表示就是aa···aaa,由多少个最小循环节a构成s,那么就有几个a。 找循环节一个一个对比比较麻烦,最简单方法就是s+s就可以直接增加多一倍的循环节。 假设原来s=aaaa,那ss=s+s=aaaa aaaa 因为是不断重复的循环节,可以通过简单的屏蔽的第一个字符,然后再在ss中寻找s 。因为屏蔽第一个字符,即第一个最小循环节被破坏,所以找到的s应该是从第二个循环节开始 但倘若不是由一个子串重复构成 即s=abcd,那ss=abcd abcd=s+s 屏蔽掉第一个字符,又因不匹配,所以在ss中寻找s,一定是对应着新增s的位置,即s.size()处
bool repeatedSubstringPattern(char * s){ int len =strlen(s); char *ch =(char *)malloc(sizeof(char)*(2*len -1)); //屏蔽掉第一个字符 strcpy(ch,s+1); printf("%srn",ch); //将len-1个字符连接到ch后面,即屏蔽掉最后一个 strncat(ch,s,len-1); //返回非空,说明可以由循环节构成 return strstr(ch,s);}实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2 示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1 说明: 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。 对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
对于本题可以使用kmp算法,不过kmp有点复杂。本人使用的是暴力解法,时间复杂度比较高,但是思路比较好理解。 本题整体的思路为:对于haystack字符串,要逐个遍历,首页比较haystack 和needle 中的第一个字符,如果相等,则继续往下比较,移动haystack和needle 的位置。 这里要注意的是,在继续往下比较之前,要记录下首次相同的位置。同时重新定义一个变量进行haystack 的遍历,遍历时要记录相等的元素的个数。当needle 遍历完的的时候,比较记录的元素个数和needle 长度是否相等。相等则返回之前记录的haystack的起始位置。
int strStr(char * haystack, char * needle){ int n,n1,start=0; //n,n1分别为字符串长度,start记录正确匹配开始的位置。 n=strlen(haystack); n1=strlen(needle); if(n1==0) return 0; if(n<n1) return -1; for(int i=0;i<n;++i) //首先i为haystack数组的指针,遍历该数组 { //在遍历过程中,找到haystack与needle数组第一个字符相同的位置,并且用haystack减去该位置 //(n-i)看是否大于needle数组的长度 如果不大于直接跳出,减少遍历次数 if(needle[0]==haystack[i] && (n-i)>=n1) { int count=0; //用来记录下一个for循环匹配正确的次数 start=i; int z=i; for(int j=0;j<n1;++j) { if(needle[j]==haystack[z]) { ++count; //正确则加1 ++z; //并且haystack数组z指针后移 } } if(count==n1) //看匹配正确次数是否等于needle数组的长度 return start; } } return -1;}给定一组字符,使用原地算法将其压缩。 压缩后的长度必须始终小于或等于原数组长度。 数组的每个元素应该是长度为1 的字符(不是 int 整数类型)。 在完成原地修改输入数组后,返回数组的新长度。 进阶: 你能否仅使用O(1) 空间解决问题? 示例 1: 输入: [“a”,“a”,“b”,“b”,“c”,“c”,“c”] 输出: 返回 6 ,输入数组的前 6 个字符应该是:[“a”,“2”,“b”,“2”,“c”,“3”] 说明: “aa” 被 “a2” 替代。“bb” 被 “b2” 替代。“ccc” 被 “c3” 替代。 示例 2: 输入: [“a”] 输出: 返回 1 ,输入数组的前 1 个字符应该是:[“a”] 解释: 没有任何字符串被替代。 示例 3: 输入: [“a”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”] 输出: 返回 4 ,输入数组的前4个字符应该是:[“a”,“b”,“1”,“2”]。 解释: 由于字符 “a” 不重复,所以不会被压缩。“bbbbbbbbbbbb” 被 “b12” 替代。 注意每个数字在数组中都有它自己的位置。
用start和end分别指向相同字符的终点与起点,当start的下一个与start不同,或者start指向最后一个字符时,保存start指向的字符与其出现次数,即start - end + 1,但要注意start == end时(即只出现一次时)不用保存次数。
int compress(char* chars, int charsSize){int start = 0, end = 0, k = 0, t, i, j; for(; start < charsSize; start++){ if(start + 1 == charsSize || chars[start] != chars[start+1]){ chars[k++] = chars[end]; //chars 存下字符 if(start > end){ //连续次数大于1时保存次数 t = start - end + 1; //相同字符出现的次数 i = k; //次数转为字符串时需要翻转,用i保存翻转的起点 while(t > 0){ //测试用例的次数最多两位数,但我们要考虑多位数的情况 chars[k++] = t % 10 + '0'; //chars 存下次数 t /= 10; } for(j = 0; j < (k - i) / 2; j++){ //翻转 char tmp = chars[i + j]; chars[i + j] = chars[k - 1 -j]; chars[k - 1 -j] = tmp; } } end = start + 1; } } return k;}给定一个正整数 n(1 ≤ n ≤ 30),输出外观数列的第 n 项。 注意:整数序列中的每一项将表示为一个字符串。 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下: 描述前一项,这个数是 1 即 “一个 1 ”,记作 11 描述前一项,这个数是 11 即 “两个 1 ” ,记作 21 描述前一项,这个数是 21 即 “一个 2 一个 1 ” ,记作 1211 描述前一项,这个数是 1211 即 “一个 1 一个 2 两个 1 ” ,记作 111221 示例 1: 输入: 1 输出: “1” 解释:这是一个基本样例。 示例 2: 输入: 4 输出: “1211” 解释:当 n = 3 时,序列是 “21”,其中我们有 “2” 和 “1” 两组,“2” 可以读作 “12”,也就是出现频次 = 1 而 值 = 2;类似 “1” 可以读作 “11”。所以答案是 “12” 和 “11” 组合在一起,也就是 “1211”。
没看懂。。。
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明:本题中,我们将空字符串定义为有效的回文串。
示例 1: 输入: “A man, a plan, a canal: Panama” 输出: true 示例 2: 输入: “race a car” 输出: false
1、回文串判断,首尾比较。忽略大小写,可以都转换为同一个基准,比如都是小写 2、只考虑数字和字母,可以使用isalpha,isdigit(数字,字母返回非0,不是返回0)来过滤 3、考虑空指针或空串的场景
bool isPalindrome(char * s){ int len = strlen(s); //空字符串定义为有效的回文串 if (len == 0) return true; //单个字符定义为有效的回文串 if (len == 1) return true; //两个指针,一个指向开头,一个指向结尾 char *p = s; char *q = s+len-1; //双指针同时遍历字符串 while(p<q) { //跳过非字符和非字母,注意每次判断是否两个指针相遇 while((!(isalpha(*p))&&!(isdigit(*p)))&&(p<q)) { p++; } while((!(isalpha(*q))&&!(isdigit(*q)))&&(p<q)) { q--; } //只要有一个不相等就返回false if((tolower(*p)!=tolower(*q))) return false; //下一个字符的比较 p++; q--; } return true;}给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。
示例 1: 输入: “aba” 输出: True 示例 2: 输入: “abca” 输出: True 解释: 你可以删除c字符。 注意: 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
检查到前后不一样的字符,必须要删掉一个且只能删除一次(要么开头,要么结尾)。删掉之后检查剩下的字符串是否为回文。 以"abdda"这个串为例,此时i指向’b’,j指向’d’,发现不对了。但是有一次删除的机会,我们自己写几个case其实就能发现,此时子串范围为(i+1, j)或(i, j-1)的俩子串只要有任意一个是回文串,则结果就是回文串,否则就不是。
bool isPalindrome (char* start, char* end) //检查s中一段是否为回文数{ while(start <= end) { if(*start != * end) { return false; } start++; end--; } return true;}bool validPalindrome(char * s){ int flag = 0; // 一次删除机会 int len = strlen(s); if (len <= 2) { //单独一字符或者两字符肯定能变成回文 return true; } char* start = s; char* end = s + len -1; while (start <= end) { if (*start != *end) { //删除左边 if (isPalindrome(start+1, end)) { return true; } //删除右边 if (isPalindrome(start, end - 1)) { return true; } return false; } start++; end--; } return true;}给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
示例: s = “leetcode” 返回 0 s = “loveleetcode” 返回 2 提示:你可以假定该字符串只包含小写字母。
设置一个辅助数组flag[26],两次遍历:第一遍统计各字符出现次数,第二遍找到第一个值为1的索引即为所求
//设置一个辅助数组flag[26],两次遍历:第一遍统计各字符出现次数,第二遍找到第一个值为1的索引即为所求int firstUniqChar(char * s){ int flag[26]={0}; int len=strlen(s); int i; for(i=0;i<len;i++){ flag[s[i]-'a']++; } for(i=0;i<len;i++){ if(flag[s[i]-'a']==1) return i; } return -1;}给定一个字符串,请将字符串里的字符按照出现的频率降序排列。
示例 1: 输入: “tree” 输出: “eert” 解释: 'e’出现两次,'r’和’t’都只出现一次。 因此’e’必须出现在’r’和’t’之前。此外,"eetr"也是一个有效的答案。 示例 2: 输入: “cccaaa” 输出: “cccaaa” 解释: 'c’和’a’都出现三次。此外,"aaaccc"也是有效的答案。 注意"cacaca"是不正确的,因为相同的字母必须放在一起。 示例 3: 输入: “Aabb” 输出: “bbAa” 解释: 此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。 注意’A’和’a’被认为是两种不同的字符。
字符范围为:0-128,利用数组去构建哈希表: 1.首先对字符串进行遍历,取得每个字符出现的次数保存在数组count中 2.循环遍历count数组,每次找出最大值所对应的索引,将其值赋为0(这次下次就不会重复找到它),然后将索引所对应的字符赋值到字符串s中。
char * frequencySort(char * s){ int flag[128] = {0}; int len = strlen(s); if (len <= 2) return s; for(int i = 0;i<len;i++) { printf("%d ",s[i]); flag[s[i]]++; } int i ,j = 0; while(i < len){int maxValue = 0;int maxIndex = 0; //每次都找到最大值 记录下最大值和下标for( j = 0; j < 128; j++){if (flag[j] > maxValue){maxValue = flag[j];maxIndex = j;}} //把最大值对应的内容置0 表示已经打印了if (maxValue != 0){flag[maxIndex] = 0;} //将当前的字符串中出现的最大频率的字母放在s中for(j = 0; j < maxValue; j++){s[i++] = maxIndex;}} return s;}给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1] 提示: 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。 你可以按任意顺序返回答案。
方法一: 此处撰写解题思路 1、自己构建hash数据结构,记录val和对应出现次数 2、然后根据cnt进行排序 3、将cnt中出现的非零元素靠前存放,有效减少排序的时间。 4、输出排序后后K数据 方法二:使用uthash数据结构
#define Hash_SIZE 20001#define OFFSET 10000//对下标为负数进行偏移使数组下标>=0typedef struct { int val; int cnt;}HashTable;//结构体数组HashTable hash[Hash_SIZE];//比较函数,对cnt出现次数进行排序int comp(const void *a, const void *b) { return (((HashTable *)a)->cnt - ((HashTable *)b)->cnt);}int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){ memset(hash,0,sizeof(hash));//初始化sizeof(hash)个字节 int i=0,j=0; for(i=0;i<numsSize;i++)//将nums数组的值和出现的次数放入hash表中 { hash[(nums[i]+OFFSET)%Hash_SIZE].cnt++; hash[(nums[i]+OFFSET)%Hash_SIZE].val=nums[i]; } //对原hash表进行优化 把所有非零值靠前存放 for(i=0;i<Hash_SIZE;i++) { if(hash[i].cnt!=0) { hash[j].cnt=hash[i].cnt; hash[j].val=hash[i].val; j++; } } //对hash表中的cnt进行快速排序,出现次数少的在前面,次数多的在后面 //hash[j-i-1]//注意sizeof里面是hashtable qsort(hash,j,sizeof(HashTable),comp); //输出前k个高频元素 从最后一个开始 j-0-1 j-1-1 j-2-1 for(i=0;i<k;i++) nums[i]=hash[j-i-1].val; *returnSize=k; return nums;}#include <uthash.h>struct Number { int key; int cnt; UT_hash_handle hh;};static void CountNum(struct Number **hash, int num, int cnt){ struct Number *node = NULL; HASH_FIND_INT(*hash, &num, node); if (node != NULL) { node->cnt++; return; } node = malloc(sizeof(struct Number)); node->cnt = cnt; node->key = num; HASH_ADD_INT(*hash, key, node);}static void CountArray(struct Number **hash, int *array, int n){ for (int i = 0; i < n; i++) { CountNum(hash, array[i], 1); }}static void Release(struct Number **hash){ struct Number *node, *next; HASH_ITER(hh, *hash, node, next) { HASH_DEL(*hash, node); }}static int Cmp(struct Number *a, struct Number *b){ return b->cnt - a->cnt;}int *topKFrequent(int *nums, int numsSize, int k, int *returnSize){ int *result = malloc(sizeof(int) * k); assert(result != NULL); *returnSize = k; struct Number *ha = NULL; CountArray(&ha, nums, numsSize); HASH_SORT(ha, Cmp); int index = 0; struct Number *node = NULL; struct Number *next = NULL; HASH_ITER(hh, ha, node, next) { result[index++] = node->key; if (index == k) { break; } } Release(&ha); return result;}/** * Note: The returned array must be malloced, assume caller calls free(). *///哈希表#define MAX_NUM 50000typedef struct { int num; int cnt; UT_hash_handle hh;}hash_entry;hash_entry* users = NULL;hash_entry hash_item[MAX_NUM];int g_cnt = 0;void add_users(int num) { hash_entry* t = NULL; HASH_FIND_INT(users,&num,t); if(t == NULL) { hash_item[g_cnt].num = num; hash_item[g_cnt].cnt = 1; t = &hash_item[g_cnt]; g_cnt++; HASH_ADD_INT(users,num,t); return; } t->cnt++;}int cmp(hash_entry* a,hash_entry* b) { return b->cnt - a->cnt;}int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){ users = NULL; hash_entry* t = NULL; for(int i = 0;i < numsSize;i++) { add_users(nums[i]); } //对哈希表进行排序 HASH_SORT(users,cmp); int* res = (int*)malloc(sizeof(int) * k); int cnt = 0; //遍历哈希表 for(t = users;t != NULL;t = t->hh.next) { if(cnt >= k) { break; } res[cnt++] = t->num; } *returnSize = k; return res;}给一非空的单词列表,返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率,按字母顺序排序。
示例 1: 输入: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2 输出: [“i”, “love”] 解析: “i” 和 “love” 为出现次数最多的两个单词,均为2次。 注意,按字母顺序 “i” 在 “love” 之前。 示例 2: 输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4 输出: [“the”, “is”, “sunny”, “day”] 解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词, 出现次数依次为 4, 3, 2 和 1 次。 注意: 假定 k 总为有效值, 1 ≤ k ≤ 集合元素数。 输入的单词均由小写字母组成。 扩展练习: 尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。
qsort的结构体的排序,注意字典序是如何排序的。
/** * Note: The returned array must be malloced, assume caller calls free(). */typedef struct node{ char word[20]; int num;}NODE;int cmp1(const NODE* a, const NODE* b){ return (b->num - a->num);}int cmp2(const NODE* a, const NODE* b){ return strcmp(a->word, b->word);}char ** topKFrequent(char ** words, int wordsSize, int k, int* returnSize){ NODE* node = calloc(wordsSize, sizeof(NODE)); char** ret = calloc(wordsSize, sizeof(char*)); int node_len = 0; for (int i = 0; i < wordsSize; i++) {// 建立结构体数组,存储出现次数 bool flag = false; // 若前面出现过这个单词,直接累加次数 for (int j = 0; j < node_len; j++) { // printf("check : "%s" ", node[j].word); // printf("compare with "%s"n", words[i]); if (strcmp(words[i], node[j].word) == 0) { node[j].num++; flag = true; // printf("node[%d].num++n", j); break; } } if (!flag) {// 若前面没出现过,新增一个节点 strcpy(node[node_len].word, words[i]); node[node_len].num = 1; // printf("add node : "%s" %dn", node[node_len].word, node[node_len].num); node_len++; // puts("-----"); } } qsort(node, node_len, sizeof(NODE), cmp2);// 排序字符串 qsort(node, node_len, sizeof(NODE), cmp1);// 排序出现次数 for (int i = 0; i < k; i++) { // printf("print node : "%s" %dn", node[i].word, node[i].num); ret[i] = node[i].word; } *returnSize = k; return ret;}给你一个按升序排序的整数数组 num(可能包含重复数字),请你将它们分割成一个或多个子序列,其中每个子序列都由连续整数组成且长度至少为 3 。
如果可以完成上述分割,则返回 true ;否则,返回 false 。
示例 1: 输入: [1,2,3,3,4,5] 输出: True 解释: 你可以分割出这样两个连续子序列 : 1, 2, 3 3, 4, 5 示例 2: 输入: [1,2,3,3,4,4,5,5] 输出: True 解释: 你可以分割出这样两个连续子序列 : 1, 2, 3, 4, 5 3, 4, 5 示例 3: 输入: [1,2,3,4,4,5] 输出: False 提示: 输入的数组长度范围为 [1, 10000]
题目看不懂系列
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4 说明: 你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。
思路没难度,将数组排序后输出第k-1个就可以了。题目没有限制,我们可以利用qsort直接排序,也可以手写一个快速排序。
int cmp(const void*a, const void* b) { return *(int*)b - *(int*)a;}int findKthLargest(int* nums, int numsSize, int k){ if(nums==NULL||numsSize==0) return 0; qsort(nums, numsSize, sizeof(int), cmp); return nums[k-1];}手写快排
void quickSort(int arr[], int low, int high){ int first = low; int last = high; int key = arr[first]; if(first >= last) return; while(first < last) { while(first < last && arr[last] <= key) { last--; } //从后往前,找到一个比key大的和first指向的位置交换 arr[first] = arr[last]; while(first < last && arr[first] > key) { first++; } //从前往后,找到一个比key小的和last指向的位置交换 arr[last] = arr[first]; } //最后跳出时 first == last first就是key的位置 arr[first] = key; //继续排序前半部分 和后半部分 quickSort(arr, low, first-1); quickSort(arr, first+1, high);}int findKthLargest(int* nums, int numsSize, int k){ if(nums==NULL||numsSize==0) return 0; quickSort(nums,0,numsSize-1); //for(int i = 0;i<numsSize;i++) //printf("%drn",nums[i]); return nums[k-1];}我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
(这里,平面上两点之间的距离是欧几里德距离。)
你可以按任何顺序返回答案。除了点坐标的顺序之外,答案确保是唯一的。
示例 1: 输入:points = [[1,3],[-2,2]], K = 1 输出:[[-2,2]] 解释: (1, 3) 和原点之间的距离为 sqrt(10), (-2, 2) 和原点之间的距离为 sqrt(8), 由于 sqrt(8) < sqrt(10),(-2, 2) 离原点更近。 我们只需要距离原点最近的 K = 1 个点,所以答案就是 [[-2,2]]。 示例 2: 输入:points = [[3,3],[5,-1],[-2,4]], K = 2 输出:[[3,3],[-2,4]] (答案 [[-2,4],[3,3]] 也会被接受。) 提示: 1 <= K <= points.length <= 10000 -10000 < points[i][0] < 10000 -10000 < points[i][1] < 10000
方法一:qsort排序 方法二:另一种qsort排序 额外定义一个结构体存放坐标和距离的数值,然后对结构体内的距离值进行排序
方法一
int cmp(const void*a, const void*b){//将(int**)指针解一次引用再用索引访问元素,解一次引用相当于一维数组int x1=(*(int**)a)[0], y1=(*(int**)a)[1];int x2=(*(int**)b)[0], y2=(*(int**)b)[1];return (x1*x1+y1*y1) - (x2*x2+y2*y2);}int** kClosest(int** a, int n, int* col, int k, int* returnSize, int** returnColumnSizes){qsort(a, n, sizeof(int**), cmp);*returnColumnSizes = (int*)calloc(k, sizeof(int));for (int i = 0; i < k; i++) {(*returnColumnSizes)[i] = 2;}*returnSize = k;return a;}/*************************************************************************//* qsort排序二维数组,cmp的每个元素都是一个独立的 int 数组,也就是指针 */int cmp(const void* a, const void* b) { // 解一次引用转换为对应一维数组 int* arry1 = *(int**)a; int* arry2 = *(int**)b; // 解两次引用 获取对应arry1 的两个元素 int x1 = *arry1; int y1 = *(arry1 + 1); int x2 = *arry2; int y2 = *(arry2+1); return (x1*x1 + y1*y1) - (x2*x2 + y2*y2);}int** kClosest(int** points, int pointsSize, int* pointsColSize, int K, int* returnSize, int** returnColumnSizes){ if(points==NULL || pointsSize==0 || K==0) return NULL; qsort(points, pointsSize, sizeof(int)*pointsColSize[0], cmp); /* 这里注意 qsort 的传参,使用不当会报错 Line 11: char 11: runtime error: load of misaligned address 0x602000000032 for type 'int *', which requires 8 byte alignment (solution.c) 0x602000000032: note: pointer points here */ // 指定return输出的二维数组是包含有几个一维数组 *returnSize = pointsSize > K ? K : pointsSize; *returnColumnSizes = (int*)malloc(sizeof(int*)*(*returnSize)); // 指定每个一维数组的 col for(int i = 0; i< (*returnSize); i++) { (*returnColumnSizes)[i] = 2; } return points;}方法二
typedef struct node {int x, y;int d;} node_t;int cmp(const void*a, const void*b){node_t *a1 = (node_t *)a;node_t *b1 = (node_t *)b;return a1->d - b1->d;}int** kClosest(int** a, int n, int* col, int k, int* returnSize, int** returnColumnSizes){if (a == NULL || col == NULL || n == 0 || k == 0|| returnSize == NULL || returnColumnSizes== NULL) {return NULL;}*returnSize = k;*returnColumnSizes = (int*)calloc(k, sizeof(int));int **result = (int**)calloc(k, sizeof(int*));node_t *p = (node_t *)calloc(n, sizeof(node_t)); for (int i = 0; i < n; i++) {int x = a[i][0];int y = a[i][1];int d = x*x+y*y;p[i].x=x;p[i].y=y;p[i].d=d;// printf("(%d,%d)=%dn", x, y, d);}qsort(p, n, sizeof(node_t), cmp);/* for (int i = 0; i < n; i++) {printf("(%d,%d)=%dn", p[i].x, p[i].y, p[i].d);}*/for (int i = 0; i < k; i++) {(*returnColumnSizes)[i] = 2;result[i] = (int*)malloc(sizeof(int)*2); result[i][0] = p[i].x;result[i][1] = p[i].y; }free(p);return result;}方法2:堆排序法
typedef struct node{ int row; int column; int dist;}Node_t,*pNode_t;void adjustheap(pNode_t heap,int start,int end){ Node_t temp; int dad=start; int son=dad*2+1; while(son<end) { if(son+1<end&&heap[son+1].dist>heap[son].dist) son++; if(heap[dad].dist>heap[son].dist) return; else { temp=heap[dad]; heap[dad]=heap[son]; heap[son]=temp; dad=son; son=dad*2+1; } }}给定一个仅包含大小写字母和空格 ’ ’ 的字符串 s,返回其最后一个单词的长度。如果字符串从左向右滚动显示,那么最后一个单词就是最后出现的单词。 如果不存在最后一个单词,请返回 0 。 说明:一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。 示例: 输入: “Hello World” 输出: 5
因为只包含字母和空格,所以从结尾开始遍历,直接使用库函数isalpha判断是否是字母就可以,当非字母的时候说明遇到了空格,跳出就可以。
int lengthOfLastWord(char * s){ int l; int i; int res = 0; if(NULL == s) return 0; l = strlen(s); for(i = l-1; i >=0; i--) { if(isalpha(s[i])) res++; //空格字符 else if(res) break; } return res;}. 统计字符串中的单词个数,这里的单词指的是连续的不是空格的字符。
请注意,你可以假定字符串里不包括任何不可打印的字符。
示例: 输入: “Hello, my name is John” 输出: 5 解释: 这里的单词是指连续的不是空格的字符,所以 “Hello,” 算作 1 个单词。
统计前一个为空格且自身不是空格的数量即可。(注意s[0])
int countSegments(char * s){ if(s[0] == '') return 0; int cnt=0; int i = 0; int len = strlen(s); for(i =0; i < len; i++){ //注意第一个单词的判断 i == 0 if ((i == 0 || s[i-1] == ' ') && s[i] != ' ') cnt++; } return cnt;}罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。
字符 数值I 1V 5X 10L 50C 100D 500M 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。 给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1: 输入: “III” 输出: 3 示例 2: 输入: “IV” 输出: 4 示例 3: 输入: “IX” 输出: 9 示例 4: 输入: “LVIII” 输出: 58 解释: L = 50, V= 5, III = 3. 示例 5: 输入: “MCMXCIV” 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.
对于各种情况以此判断,当出现I、X、C三个字符时,如果右边是对应的特殊情况,就相应减法。
int romanToInt(char * s){ int count = 0;while (*s){if (*s == 'V') count += 5;else if (*s == 'L') count += 50;else if (*s == 'D') count += 500;else if (*s == 'M') count += 1000;else if (*s == 'I')//加多了减去,巧妙地规律判断count = (*(s + 1) == 'V' || *(s + 1) == 'X') ? count - 1 : count + 1;else if (*s == 'X')count = (*(s + 1) == 'L' || *(s + 1) == 'C') ? count - 10 : count + 10;elsecount = (*(s + 1) == 'D' || *(s + 1) == 'M') ? count - 100 : count + 100;s++;}return count;}给定一个字符串来代表一个学生的出勤记录,这个记录仅包含以下三个字符:
‘A’ : Absent,缺勤 ‘L’ : Late,迟到 ‘P’ : Present,到场 如果一个学生的出勤记录中不超过一个’A’(缺勤)并且不超过两个连续的’L’(迟到),那么这个学生会被奖赏。
你需要根据这个学生的出勤记录判断他是否会被奖赏。
示例 1: 输入: “PPALLP” 输出: True 示例 2: 输入: “PPALLL” 输出: False
思路 遍历字符串统计字符出现的次数即可。注意,题目最多允许出现两个连续的L,但不允许三个连续的L.这里判断的时候用三个L作为边界来判断,只要满足cntL条件就会+3,说明已经超过。不满足条件((s[i] == 'L')&&(s[i+1])&&(s[i+1] == 'L')&&(s[i+2] == 'L')),说明小于三个连续L,cntL就会小于3,下面进行判断的时候会判断为true。当然也可以在for循环的时候判断是否要终结循环也可以省一点时间。
bool checkRecord(char * s){ if (s[0] == '') return false; int len = strlen(s); int cntA = 0; int cntL = 0; //计数 for(int i = 0;i<len;i++) { if(s[i] == 'A') cntA++; //允许出现两个连续的L,但不允许连续的三个L //只要满足cntL条件就会+3,说明已经超过。不满足条件说明小于三个连续L,cntL就会小于3,下面进行判断的时候会判断为true。 if((s[i] == 'L')&&(s[i+1])&&(s[i+1] == 'L')&&(s[i+2] == 'L')) cntL+=3; } if((cntA<=1)&&(cntL<=2)) return true; else return false;}}编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例 1: 输入: [“flower”,“flow”,“flight”] 输出: “fl” 示例 2: 输入: [“dog”,“racecar”,“car”] 输出: “” 解释: 输入不存在公共前缀。 说明: 所有输入只包含小写字母 a-z 。
以第一个字符串为基准进行竖向扫描,将每个字符串的前col个字符进行依次比较。
char * longestCommonPrefix(char ** strs, int strsSize){ if(0==strsSize)return ""; char *s0= strs[0]; //首个字符串作为基准 for(int col=0; s0[col]!='' ;++col){ //s0的第col个字符作为基准 for(int row=1; row<strsSize; ++row){//扫描其他字符串,仅当所有字符串的第col个字符都同基准,才会正常结束循环 if(s0[col]!=strs[row][col]){ //不会越界!因为即将越界会有 ''停止符作为哨兵,此时马上跳出。 s0[col]=''; // 用''表示结束,改短s0 return s0; } }//而且C语言即便越界,只要越的界没有超出整个进程代码段的地址空间,都不会报错。 }return s0; //其他字符串不存在或都包含s0的前缀}在二维平面上,有一个机器人从原点 (0, 0) 开始。给出它的移动顺序,判断这个机器人在完成移动后是否在 (0, 0) 处结束。
移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R(右),L(左),U(上)和 D(下)。如果机器人在完成所有动作后返回原点,则返回 true。否则,返回 false。
注意:机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次,“L” 将始终向左移动等。此外,假设每次移动机器人的移动幅度相同。
示例 1: 输入: “UD” 输出: true 解释:机器人向上移动一次,然后向下移动一次。所有动作都具有相同的幅度,因此它最终回到它开始的原点。因此,我们返回 true。 示例 2: 输入: “LL” 输出: false 解释:机器人向左移动两次。它最终位于原点的左侧,距原点有两次 “移动” 的距离。我们返回 false,因为它在移动结束时没有返回原点。
直接统计字符串中RLUD的个数就好了,只要个数RL并且UD,他总是可以回到原点。
bool judgeCircle(char * moves){ int cntR = 0; int cntL = 0; int cntU = 0; int cntD = 0; int len = strlen(moves); for(int i = 0;i<len;i++) { if(moves[i] == 'R') cntR++; else if(moves[i] == 'L') cntL++; else if(moves[i] == 'U') cntU++; else if(moves[i] == 'D') cntD++; } if(((cntR == cntL))&&((cntU == cntD))) return true; return false;}每封电子邮件都由一个本地名称和一个域名组成,以 @ 符号分隔。
例如,在 alice@leetcode.com中, alice 是本地名称,而 leetcode.com 是域名。除了小写字母,这些电子邮件还可能包含 ‘.’ 或 ‘+’。
如果在电子邮件地址的本地名称部分中的某些字符之间添加句点(’.’),则发往那里的邮件将会转发到本地名称中没有点的同一地址。例如,"alice.z@leetcode.com” 和 “alicez@leetcode.com” 会转发到同一电子邮件地址。 (请注意,此规则不适用于域名。)
如果在本地名称中添加加号(’+’),则会忽略第一个加号后面的所有内容。这允许过滤某些电子邮件,例如 m.y+name@email.com 将转发到 my@email.com。 (同样,此规则不适用于域名。)可以同时使用这两个规则。
给定电子邮件列表 emails,我们会向列表中的每个地址发送一封电子邮件。实际收到邮件的不同地址有多少?
示例: 输入:[“test.email+alex@leetcode.com”,“test.e.mail+bob.cathy@leetcode.com”,“testemail+david@lee.tcode.com”] 输出:2 解释:实际收到邮件的是 “testemail@leetcode.com” 和 “testemail@lee.tcode.com”。 提示: 1 <= emails[i].length <= 100 1 <= emails.length <= 100 每封 emails[i] 都包含有且仅有一个 ‘@’ 字符。
参考大佬的解法,自己加了注释。 主要思路:利用strtok函数字符串以@为界限分割为first和last两部分。将第一部分处理成标准的字符串,遇到.跳过,遇到+跳出,丢掉后面的。剩下的放进res数组中。最后将first和last两部分合起来放进res即可。
放进res的部分,需要判断下是否和res当前已有的内容重复,如果重复,就清零即将放进的部分,否则就直接放入。
int numUniqueEmails(char **emails, int emailsSize){ //初始化 char **res = calloc(emailsSize, sizeof(char*)); for (int i = 0; i < emailsSize; i++) { res[i] = calloc(101, sizeof(char)); } char *first, *last; int count1 = 0, count2 = 0, flag = 0; for (int i = 0; i < emailsSize; i++) { //以@为界限进行分割为first,last两部分 //首次调用时,s必须指向要分解的字符串,随后调用要把s设成NULL。 //https://blog.csdn.net/sxy19930313/article/details/78548174 first = strtok(emails[i], "@"); last = strtok(NULL, "@"); for (int j = 0; j < strlen(first); j++) { //遇到 . 跳过,进行下一次循环 if (first[j] == '.') { continue; } //遇到+直接跳出循环,+后面的都不要 else if (first[j] == '+') { break; } //其余的都放进res数组 else { res[count1][count2++] = first[j]; } } //连接@ 和last部分 strcat(res[count1], "@"); strcat(res[count1], last); flag = 1; //比较res中已有内容res[j] 和目前的res[count1]的内容是否相同 for (int j = 0; j < count1; j++) { //二者相同,flag置1 同时清空res[count1] if (!strcmp(res[count1], res[j])) { flag = 0; memset(res[count1], 0, sizeof(char) * 101); break; } } //flag为1说明二者不等,count1++,进行下一个 if (flag == 1) { count1++; } count2 = 0; } //最后count1的值就是不同的内容的个数 return count1;}国际摩尔斯密码定义一种标准编码方式,将每个字母对应于一个由一系列点和短线组成的字符串, 比如: “a” 对应 “.-”, “b” 对应 “-…”, “c” 对应 “-.-.”, 等等。
为了方便,所有26个英文字母对应摩尔斯密码表如下:
[".-","-…","-.-.","-…",".","…-.","–.","…","…",".—","-.-",".-…","–","-.","—",".–.","–.-",".-.","…","-","…-","…-",".–","-…-","-.–","–…"] 给定一个单词列表,每个单词可以写成每个字母对应摩尔斯密码的组合。例如,“cab” 可以写成 “-.-…–…”,(即 “-.-.” + “-…” + ".-"字符串的结合)。我们将这样一个连接过程称作单词翻译。
返回我们可以获得所有词不同单词翻译的数量。
例如: 输入: words = [“gin”, “zen”, “gig”, “msg”] 输出: 2 解释: 各单词翻译如下: “gin” -> “–…-.” “zen” -> “–…-.” “gig” -> “–…--.” “msg” -> “–…--.” 共有 2 种不同翻译, “–…-.” 和 “–…--.”. 注意: 单词列表words 的长度不会超过 100。 每个单词 words[i]的长度范围为 [1, 12]。 每个单词 words[i]只包含小写字母。
建立字符串数组morse,存放words中的字符串转成莫尔斯密码后的字符串,每次处理words中的字符串,如果不重复,就添加到morse里面,最终输出morse中字符串的个数
int uniqueMorseRepresentations(char ** words, int wordsSize){ char dict[26][5] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}; //5*12 = 60 char morse[100][60] = {0}; int count = 0; for (int i = 0; i < wordsSize; i++) { char tmp[60] = { 0 }; int flag = 0; //每个字符串对应的摩斯码放入tmp中 for (int j = 0; j < strlen(words[i]); j++) { strcat(tmp, dict[words[i][j] - 'a']); } //定义flag分辨相同和不同,如果tmp和morse中的不同 就放入morse中 for (int k = 0; k < count; k++) { if (strcmp(morse[k], tmp) == 0) { flag = 1; break; } } //不同的话就放入morse中 if (flag == 0) { strcpy(morse[count], tmp); count++; } } return count;}你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
示例 1: 输入: 二叉树: [1,2,3,4] 1 / 2 3 / 4 输出: “1(2(4))(3)” 解释: 原本将是“1(2(4)())(3())”, 在你省略所有不必要的空括号对之后, 它将是“1(2(4))(3)”。 示例 2: 输入: 二叉树: [1,2,3,null,4] 1 / 2 3 4 输出: “1(2()(4))(3)” 解释: 和第一个示例相似, 除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。
日常题目难懂系列:题目的意思是子节点需要用()来包裹。举例来说,二叉树[root,left,right],则转换为root(left)(right)。如果只有left为空节点,则输出root()(right);如果只有right为空节点则可以忽略右节点的(),输出为root(left)。
1.先把根节点写入字符串 2.再判断左子树是否为空,不为空则先加左括号,再写左子树的值,最后加右括号–root(left)(right) 3.如果左子树为空,再判断右子树是否为空,如果不为空,则直接添加一对括号–root()(right) 4.判断右子树是否为空,不为空则与不空的左子树同样处理–root(left) 5.右子树为空则什么都不做
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */#define MAX_SIZE 50000void transfer_bitree(struct TreeNode* t, char *s, int *len){ if (t) { *len += sprintf(s + *len, "%d", t->val); if (t->left || t->right) { *len += sprintf(s + *len, "%s", "("); transfer_bitree(t->left, s, len); *len += sprintf(s + *len, "%s", ")"); } if (t->right) { *len += sprintf(s + *len, "%s", "("); transfer_bitree(t->right, s, len); *len += sprintf(s + *len, "%s", ")"); } }}char * tree2str(struct TreeNode* t){ char *str = malloc(MAX_SIZE); int len = 0; transfer_bitree(t, str, &len); str[len] = ''; return str;}给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false。
(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
注意: 你可以假设两个字符串均只含有小写字母。 canConstruct(“a”, “b”) -> false canConstruct(“aa”, “ab”) -> false canConstruct(“aa”, “aab”) -> true
思路:题目抽象出来很简单,就是判断ransom字符串能不能由magazines 字符串的内容构成(magazines 中的字符只能使用一次)。 1.将magazines中的字符按照ascii码为下标存储在数组中,出现一次,对应的数组内容+1,这样就可以知道出每个字母的出现次数了。 2.遍历magazines一遍之后,magazines中的字母在count数组中已经有相应的位置,其中的内容不为0。ransom中同样以ascii码为下标遍历,判断对应的位置是否为0,如果为0,说明已经使用过了或者根本没有对应的字母,则返回false。如果对应的位置是不为0,说明magazines中有对应的字母,对应的数组内容就直接- -。
bool canConstruct(char * ransomNote, char * magazine){ int count[26] = {0};//初始化为全零 int i; char ch; for(i = 0; (ch=magazine[i]) != ''; i++) count[ch-'a']++; for(i = 0; (ch=ransomNote[i])!= ''; i++){ if(count[ch-'a']==0) return false; else count[ch-'a']--; } return true;}给定一个字符串 s,计算具有相同数量0和1的非空(连续)子字符串的数量,并且这些子字符串中的所有0和所有1都是组合在一起的。
重复出现的子串要计算它们出现的次数。
示例 1 : 输入: “00110011” 输出: 6 解释: 有6个子串具有相同数量的连续1和0:“0011”,“01”,“1100”,“10”,“0011” 和 “01”。 请注意,一些重复出现的子串要计算它们出现的次数。 另外,“00110011”不是有效的子串,因为所有的0(和1)没有组合在一起。 示例 2 : 输入: “10101” 输出: 4 解释: 有4个子串:“10”,“01”,“10”,“01”,它们具有相同数量的连续1和0。 注意: s.length 在1到50,000之间。 s 只包含“0”或“1”字符。
由于0和1是分别组合在一起的,也就是说满足要求的字符串(不会存在0和1混合的情况如:0101 1001) 这个思路是这样的, 假设最简单的情况 000111, 先遍历, 前面的 0 的数量为 curr = 3, 遍历到 1 时, pre = curr 赋值为 3, 然后 curr = 1 表示现在 1 的个数, 只要 curr <= pre, 比如 curr = 1, 那么可以组成 01; curr = 2, 可以组成 0011, curr = 3, 组成 000111, 直到出现下一次 0, 然后那么 prev 就是 1 的个数, curr 表示 0001110…这个 1 后面 0 的个数, 不断重复迭代下去, 不知道我说明白没有.
int countBinarySubstrings(char * s){ int n = 0, pre = 0, curr = 1, len = strlen(s)-1; for (int i = 0; i < len; ++i) { if (s[i] == s[i+1]) ++curr; else {pre = curr; curr = 1;} if (pre >= curr) ++n; } return n;}给定一个单词,你需要判断单词的大写使用是否正确。
我们定义,在以下情况时,单词的大写用法是正确的:
全部字母都是大写,比如"USA"。 单词中所有字母都不是大写,比如"leetcode"。 如果单词不只含有一个字母,只有首字母大写, 比如 “Google”。 否则,我们定义这个单词没有正确使用大写字母。
示例 1: 输入: “USA” 输出: True 示例 2: 输入: “FlaG” 输出: False 注意: 输入是由大写和小写拉丁字母组成的非空单词。
检测大写字母的个数即可, 1.当字符串全为大写字母或者没有一个大写字母,返回true。 2.当字符串第一个为大写并且后面的不为大写字母是,返回true。 3.其余情况返回false
bool detectCapitalUse(char * word){ int len = strlen(word); int cnt = 0; for(int i = 0;i<len;i++) { if((word[i] >='A' )&&(word[i] <='Z')) cnt++; } //对应情况1和情况3 if((cnt == len)||(cnt == 0)) return true; //对应情况2 要考虑到首字母 else if(((word[0]>='A')&&(word[0]<='Z')&&(cnt==1))) return true; else return false;免责声明：本站内容（文字信息+图片素材）来源于互联网公开数据整理或转载，仅用于学习参考，如有侵权问题，请及时联系本站删除，我们将在5个工作日内处理。联系邮箱：303555158#qq.com（把#换成@）
微信便捷交流