目录
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
中等题，可太吃力了，我觉得刷题C语言费劲。
第1题：字典序排数
试题要求如下：
解题思路：
字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。
回答（C语言）：
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
#define MY_MAX 20
-
char g_sa[MY_MAX];
-
char g_sb[MY_MAX];
-
-
int cmp(const void *a, const void *b)
-
{
-
int *pa = (
int*)a;
-
int *pb = (
int*)b;
-
sprintf(g_sa,
"%d", *pa);
-
sprintf(g_sb,
"%d", *pb);
-
return
strcmp(g_sa, g_sb);
-
}
-
int* proc(int n, int* returnSize){
-
int i;
-
int *rlt = (
int*)
calloc(n,
sizeof(
int));
-
if (rlt ==
NULL) {
-
return
NULL;
-
}
-
for (i =
0; i < n; i++) {
-
rlt[i] = i +
1;
-
}
-
qsort(rlt, n,
sizeof(
int), cmp);
-
*returnSize = n;
-
return rlt;
-
}
-
-
int* lexicalOrder(int n, int* returnSize){
-
if (n <=
0) {
-
returnSize =
0;
-
return
NULL;
-
}
-
return proc(n, returnSize);
-
}
运行效率如下所示：
第2题：字符串解码
试题要求如下：
解题思路：
从右向左扫描，发现符合条件的，就替换，然后继续从右向左扫描，直到没有[]需要替换为止。
回答（C语言）：
-
char *decodeString(char *s)
-
{
-
if (s ==
NULL) {
-
return
NULL;
-
}
-
-
char *a = strdup(s);
-
while (
true) {
-
int len =
strlen(a);
-
int left =
0, right = len;
-
int i = len -
1, num =
0, w =
1;
-
for (; i >=
0; i--) {
-
if (a[i] ==
']') {
-
right = i;
-
}
else
if(a[i] ==
'[') {
-
left = i;
-
}
else
if (a[i] >=
'0' && a[i] <=
'9') {
-
do {
// 组合数字
-
num += w * (a[i] -
'0');
-
w *=
10;
-
i--;
-
}
while (i >=
0 && (a[i] >=
'0' && a[i] <=
'9'));
-
break;
-
}
-
}
-
-
if (num ==
0) {
//没有[]了
-
return a;
-
}
else {
-
int slen = (right - left -
1);
-
int count = (i +
1) + (len - right -
1) + num * slen +
1;
-
char *t = (
char*)
calloc(count,
sizeof(
char));
-
if (i +
1 >
0) {
// 左
-
memcpy(t, a, i +
1);
-
}
-
for (
int k =
0; k < num; k++) {
// 中
-
memcpy(t + (i +
1) + k * slen, a + left +
1, slen);
-
}
-
if (len - right -
1 >
0) {
-
memcpy(t + (i +
1) + num * slen, a + right +
1, len - right -
1);
-
}
-
free(a);
-
a = t;
-
}
-
}
-
}
运行效率如下所示：
第3题：查找常用字符
试题要求如下：
解题思路：
遍历所有的字符串，记录（26个小写字母）每个字符在所有字符串中都出现过的“最小”次数，则为结果。
回答（C语言）：
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
char ** commonChars(char ** A, int ASize, int* returnSize){
-
if (
NULL == A ||
0 == ASize)
-
{
-
*returnSize =
0;
-
return
NULL;
-
}
-
int minfreq[
26];
// 记录每个‘字符’出现的最小频率
-
int freq[
26];
// 缓存每个字符串中每个’字符‘出现的频率
-
for (
int i =
0; i <
26; i++)
-
{
-
minfreq[i] = INT_MAX;
-
}
-
// 遍历所有字符串
-
for (
int i =
0; i < ASize; i++)
-
{
-
// 遍历每个字符串前，重置’字符‘出现的频率
-
memset(freq,
0,
sizeof(freq));
-
int n =
strlen(A[i]);
// 当前字符串长度
-
// 遍历当前字符串
-
for (
int j =
0; j < n; j++)
-
{
-
int idx = A[i][j] -
'a';
// 字符的下标
-
++freq[idx];
// 统计’字符‘出现的次数
-
}
-
// 每遍历一个字符串，都需更新所有字符出现的最小频率
-
for (
int k =
0; k <
26; k++)
-
{
-
minfreq[k] = fmin(minfreq[k], freq[k]);
-
}
-
}
-
// 计算结果字符
-
int sum =
0;
-
for (
int i =
0; i <
26; i++)
-
{
-
sum += minfreq[i];
-
}
-
// 构造结果字符列表
-
char** result = (
char**)
malloc(
sizeof(
char*) * sum);
-
*returnSize =
0;
-
-
for (
int i =
0; i <
26; i++)
// 遍历 26 个小写字符
-
{
-
for (
int j =
0; j < minfreq[i]; j++)
// 遍历每个‘字符’在所有字符串中都出现的最小次数
-
{
-
result[*returnSize] = (
char*)
malloc(
sizeof(
char) *
2);
// 每个字符串都有结束符，所以需 +1
-
result[*returnSize][
0] = i +
'a';
// 第 i 个字符
-
result[*returnSize][
1] =
'\0';
// '\0' 作为字符串结束标识
-
(*returnSize)++;
-
}
-
}
-
return result;
-
}
运行效率如下所示：
第4题：所有奇数长度子数组的和
试题要求如下：
回答（C语言）：
-
int sumOddLengthSubarrays(int* arr, int arrSize){
-
int res =
0;
-
-
for (
int i =
0; i < arrSize; i++) {
-
for (
int j =
1; j < arrSize - i +
1; j +=
2) {
-
for (
int m = i; m < i + j; m++) {
-
res = res + arr[m];
-
}
-
}
-
}
-
-
return res;
-
}
运行效率如下所示：
第5题：长按键入
试题要求如下：
回答（C语言）：
-
bool isLongPressedName(char* name, char* typed) {
-
int n =
strlen(name), m =
strlen(typed);
-
int i =
0, j =
0;
-
-
while (j < m) {
-
if (i < n && name[i] == typed[j]) {
-
i++;
-
j++;
-
}
else
if (j >
0 && typed[j] == typed[j -
1]) {
-
j++;
-
}
else {
-
return
false;
-
}
-
}
-
-
return i == n;
-
}
运行效率如下所示：
第6题：分割字符串的最大得分
试题要求如下：
回答（C语言）：
-
int max(int x,int y){
-
return x>y?x:y;
-
}
-
-
int maxScore(char * s){
-
int l=
strlen(s);
-
int lsum=
0;
-
int rsum=
0;
-
int maxN=
0;
-
-
for(
int i=
0;i<l
-1;i++){
-
if(s[i]==
'0')
-
lsum++;
-
for(
int j=i+
1;j<l;j++){
-
if(s[j]==
'1'){
-
rsum++;
-
}
-
}
-
maxN=max(maxN,lsum+rsum);
-
rsum=
0;
-
}
-
-
return maxN;
-
}
运行效率如下所示：
第7题：回文链表
试题要求如下：
解答思路：
1、复制链表值到数组列表中；
2、使用双指针法判断是否为回文。
回答（C语言）：
-
/**
-
* Definition for singly-linked list.
-
* struct ListNode {
-
* int val;
-
* struct ListNode *next;
-
* };
-
*/
-
-
bool isPalindrome(struct ListNode* head) {
-
int vals[
50001], vals_num =
0;
-
-
while (head !=
NULL) {
-
vals[vals_num++] = head->val;
-
head = head->next;
-
}
-
for (
int i =
0, j = vals_num -
1; i < j; ++i, --j) {
-
if (vals[i] != vals[j]) {
-
return
false;
-
}
-
}
-
return
true;
-
}
运行效率如下所示：
第8题：有多少小于当前数字的数字
试题要求如下：
回答（C语言）：
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize) {
-
int* ret =
malloc(
sizeof(
int) * numsSize);
-
*returnSize = numsSize;
-
-
for (
int i =
0; i < numsSize; i++) {
-
int cnt =
0;
-
for (
int j =
0; j < numsSize; j++) {
-
if (nums[j] < nums[i]) {
-
cnt++;
-
}
-
}
-
ret[i] = cnt;
-
}
-
-
return ret;
-
}
运行效率如下所示：
第9题：两个相同字符之间的最长子字符串
试题要求如下：
解题思路：
1、初始化哈希表，定义max = -1；
2、如果当前字符第一次出现，记下当前下标i；
3、如果字符已经出现过，利用当前下标i减去表中的记录值tmp，判断如果max小于tmp，则更新max，否则不更新；
4、释放缓冲区hash。
回答（C语言）：
-
#define Max( a , b ) ( ( a > b ) * a + ( a <= b ) * b )
-
-
int maxLengthBetweenEqualCharacters( char * s ){
-
//creating hash table
-
int * hash = (
int * )
malloc(
sizeof(
int ) *
26 );
-
int max =
-1;
-
-
//intializing hash table
-
for(
int i =
0 ; i <
26 ; i++ ) {
-
hash[ i ] =
-1;
-
}
-
-
for(
int i =
0 ; s[ i ] !=
'\0' ; i++ ) {
-
-
if( hash[ s[ i ] -
97 ] !=
-1 ) {
-
max = Max( max , ( i - hash[ s[ i ] -
97 ] -
1 ) );
-
}
else {
-
hash[ s[ i ] -
97 ] = i;
-
}
-
}
-
-
free( hash );
-
return max;
-
}
运行效率如下所示：
第10题：分式化简
试题要求如下：
解题思路：
回答（C语言）：
-
/**
-
* arr[0]: 分子
-
* arr[1]: 分母
-
*
-
* 1、简单的通分，因为每次都是 1/a，所以需要分数翻转，即分子分母交换一下
-
* 2、这题不需要约分，本来就是最简
-
*/
-
int* fraction(int* cont, int contSize, int* returnSize) {
-
int* arr = (
int*)
malloc(
sizeof(
int) *
2);
-
arr[
0] =
1;
-
arr[
1] =
0;
-
for (
int i = contSize -
1; i >=
0; i--) {
-
int temp = arr[
1];
-
arr[
1] = arr[
0];
-
arr[
0] = cont[i] * arr[
1] + temp;
-
}
-
*returnSize =
2;
-
return arr;
-
}
运行效率如下所示：
转载：https://blog.csdn.net/m0_38106923/article/details/109325598
查看评论