力扣(LeetCode)定期刷题，每期 10 道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
试题要求如下：
解题思路：
明显使用哈希表的思维，但是处理负数的时候需要注意，所以索引不能从 0 开始。
回答（C 语言）：
#define N 2001bool uniqueOccurrences(int* arr, int arrSize){ char hash[N] = {0}, set[N] = {0}; for (short i = 0; i < arrSize; i++) hash[arr[i]+1000]++; for (short i = 0; i < N; i++) { if (hash[i] > 0 && set[hash[i]] > 0) return false; else set[hash[i]] = 1; } return true;}
复制代码
运行效率如下所示：
试题要求如下：
回答（C 语言）：
int calculate(char* s){ int x = 1, y = 0; for(int i = 0; i < strlen(s);i++){ if(s[i] == 'A'){ x = 2*x +y; } else if(s[i] == 'B'){ y = 2*y +x; } } return x+y;}
复制代码
运行效率如下所示：
试题要求如下：
解题思路：
暴力破解大法好，对于一个陆地格子的每条边，它被算作岛屿的周长当且仅当这条边为网格的边界或者相邻的另一个格子为水域。 因此，可以遍历每个陆地格子，看其四个方向是否为边界或者水域，如果是则加 1。
回答（C 语言）：
const int dx[4] = {0, 1, 0, -1};const int dy[4] = {1, 0, -1, 0}; int islandPerimeter(int** grid, int gridSize, int* gridColSize) { int n = gridSize, m = gridColSize[0]; int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (grid[i][j]) { int cnt = 0; for (int k = 0; k < 4; ++k) { int tx = i + dx[k]; int ty = j + dy[k]; if (tx < 0 || tx >= n || ty < 0 || ty >= m || !grid[tx][ty]) { cnt += 1; } } ans += cnt; } } } return ans;}
复制代码
运行效率如下所示：
试题要求如下：
解题思路：
1、申请长度为 201 的哈希表；
2、遍历 nums 数组，将 nums[ i ]元素值出现的次数，映射至哈希表中；
3、遍历 nums 数组，重构 nums 元素，nums 元素低 3 位存储当前元素的值，其余元素存储元素出现的个数；
4、利用快速排序，对 nums 数组进行排序；
* 如果元素次数不相等，则利用 nums 元素高位进行比较，次数低的元素在前面，次数高的元素在后面；
* 如果元素次数相等，根据低位( 0 - 3 )的值，进行判断，即：return d % 1000 - c % 1000。
5、遍历 nums 数组，对元素的值进行还原；
6、释放缓冲区，返回数组 nums。
回答（C 语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */ #define Abs( a ) ( ( a > 0 ) * a + ( a <= 0 ) * a * -1 ) int cmp( const void * a , const void * b ) { int c = *( int * )a; int d = *( int * )b; int a_c = Abs( c ) / 1000 , b_c = Abs( d ) / 1000; if( a_c > b_c ) { return 1; } else if( a_c < b_c ) { return -1; } return d % 1000 - c % 1000; } int * frequencySort(int * nums , int numsSize , int * returnSize ){ int * hash = ( int * )malloc( sizeof( int ) * 201 ); //intializing hash table memset( hash , 0 , sizeof( int ) * 201 ); //updating hash table for( int i = 0 ; i < numsSize ; i++ ) { hash[ nums[ i ] + 100 ] += 1; } //updating nums for( int i = 0 ; i < numsSize ; i++ ) { int flag = 1; ( nums[ i ] < 0 ) && ( flag = -1 ); nums[ i ] = hash[ nums[ i ] + 100 ] * 1000 * flag + nums[ i ]; } //qsort nums qsort( nums , numsSize , sizeof( int ) , cmp ); //updating nums for( int i = 0 ; i < numsSize ; i++ ) { nums[ i ] %= 1000; } *returnSize = numsSize; free( hash ); return nums;}
复制代码
运行效率如下所示：
试题要求如下：
回答（C 语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* bit; int get(int x) { int res = 0; while (x) { res += (x % 2); x /= 2; } return res;} int cmp(void* _x, void* _y) { int x = *(int*)_x, y = *(int*)_y; return bit[x] == bit[y] ? x - y : bit[x] - bit[y];} int* sortByBits(int* arr, int arrSize, int* returnSize) { bit = malloc(sizeof(int) * 10001); memset(bit, 0, sizeof(int) * 10001); for (int i = 0; i < arrSize; ++i) { bit[arr[i]] = get(arr[i]); } qsort(arr, arrSize, sizeof(int), cmp); free(bit); *returnSize = arrSize; return arr;}
复制代码
运行效率如下所示：
试题要求如下：
解题思路：
证明数组 arr 中的数值，数组 pieces 中均存在，则说明可以连接形成数组。
1、输入的数字范围是[0，100]，所以可以建立一个 map[101]的数组，并存储它在 arr 的下标+1；
2、遍历 pieces 里面的数字，如果在 map 中没有记录，返回 false，如果 pieces 中当前的行不只一个数，则判断相邻两个数是否在 arr 中从左往右连续，不符合则返回 false 排除所有 false 的情况后，则返回 true。
回答（C 语言）：
bool canFormArray(int* arr, int arrSize, int** pieces, int piecesSize, int* piecesColSize){ int map[101] = {0}; for (int i = 0; i < arrSize; i++){ map[arr[i]] = i+1; } for (int i = 0; i < piecesSize; i++){ for (int j = 0; j < piecesColSize[i]; j++){ if (map[pieces[i][j]] == 0) return false; if (j > 0){ int x = map[pieces[i][j]] - map[pieces[i][j-1]]; if (x != 1) return false; } } } return true;}
复制代码
运行效率如下所示：
试题要求如下：
回答（C 语言）：
/** * Note: The returned array must be malloced, assume caller calls free(). */int judge(int *re,int size,int tmp){ int i=0; //判断这个数是否已经存在于答案数组里 for(i=0;i<size;i++) { if(tmp==re[i]) { return 0; } } return 1;} int* powerfulIntegers(int x, int y, int bound, int* returnSize){ int i=0,j=0,tmp=0; int max_i = log(bound)/log(x); int max_j = log(bound)/log(y); if (x == 1) max_i = 0;//处理底数为1的特殊情况，下同 if (y == 1) max_j = 0; int *re=(int *)malloc(sizeof(int)*(bound+1)); *returnSize=0; for(i=0;i<=max_i;i++) { for(j=0;j<=max_j;j++) { tmp=pow(x,i)+pow(y,j); if(tmp<=bound)//只有这个数小于等于bound，才有机会放进答案数组 { if(*returnSize>=1) { if(judge(re,(*returnSize),tmp)==1)//检查这个数字是否已经放进答案数组 { re[*returnSize]=tmp; (*returnSize)++; } } else//第一个放进答案数组里的数不需要查重 { re[*returnSize]=tmp; (*returnSize)++; } } } } return re;}
复制代码
运行效率如下所示：
试题要求如下：
回答（C 语言）：
int* sumEvenAfterQueries(int* A, int ASize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){ int* answer = (int*)calloc(queriesSize,sizeof(int)); int SumEven = 0; for (int k=0; k<ASize; k++) //先求出A中的偶数和 { if (A[k] % 2 == 0) { SumEven += A[k]; } } for (int i=0; i<queriesSize; i++) { if (A[queries[i][1]] % 2 == 0) //根据当前遍历的数奇偶情况进行处理 { SumEven-= A[queries[i][1]]; } A[queries[i][1]] += queries[i][0]; if (A[queries[i][1]] % 2 == 0) //根据当前遍历的数奇偶情况进行处理 { SumEven+= A[queries[i][1]]; } answer[i] = SumEven; } *returnSize = queriesSize; return answer;}
复制代码
运行效率如下所示：
试题要求如下：
回答（C 语言）：
int getMaximumGenerated(int n) { if (n == 0) return 0; if (n == 1) return 1; int* arr = (int*)malloc((n + 1) * sizeof(int)); arr[0] = 0; arr[1] = 1; int max = 1; for (int i = 2; i < n + 1; i++) { if (i % 2 == 0) arr[i] = arr[i / 2]; else arr[i] = arr[i / 2] + arr[i / 2 + 1]; if (max < arr[i]) max = arr[i]; } return max;}
复制代码
运行效率如下所示：
试题要求如下：
回答（C 语言）：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int maxDepth(struct TreeNode* root){ int height = 0; if(root != NULL) { int leftHeight = maxDepth(root->left); int rightHeight = maxDepth(root->right); height = leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1; } return height;}
复制代码
运行效率如下所示：
评论