力扣(LeetCode)刷题，简单题(第27期)
【摘要】 目录
第1题：独一无二的出现次数
第2题：速算机器人
第3题：岛屿的周长
第4题：按照频率将数组升序排序
第5题：根据数字二进制下 1 的数目排序
第6题：能否连接形成数组
第7题：强整数
第8题：查询后的偶数和
第9题：获取生成数组中的最大值
第10题：二叉树的深度
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，...
目录
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：独一无二的出现次数
试题要求如下：
解题思路：
明显使用哈希表的思维，但是处理负数的时候需要注意，所以索引不能从0开始。
回答（C语言）：
-
#define N 2001
-
bool 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;
-
}
运行效率如下所示：
第2题：速算机器人
试题要求如下：
回答（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;
-
}
运行效率如下所示：
第3题：岛屿的周长
试题要求如下：
解题思路：
暴力破解大法好，对于一个陆地格子的每条边，它被算作岛屿的周长当且仅当这条边为网格的边界或者相邻的另一个格子为水域。 因此，可以遍历每个陆地格子，看其四个方向是否为边界或者水域，如果是则加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;
-
}
运行效率如下所示：
第4题：按照频率将数组升序排序
试题要求如下：
解题思路：
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;
-
}
运行效率如下所示：
第5题：根据数字二进制下 1 的数目排序
试题要求如下：
回答（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;
-
}
运行效率如下所示：
第6题：能否连接形成数组
试题要求如下：
解题思路：
证明数组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;
-
}
运行效率如下所示：
第7题：强整数
试题要求如下：
回答（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;
-
}
运行效率如下所示：
第8题：查询后的偶数和
试题要求如下：
回答（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;
-
}
运行效率如下所示：
第9题：获取生成数组中的最大值
试题要求如下：
回答（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;
-
}
运行效率如下所示：
第10题：二叉树的深度
试题要求如下：
回答（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;
-
}
运行效率如下所示：
文章来源: handsome-man.blog.csdn.net，作者：不脱发的程序猿，版权归原作者所有，如需转载，请联系作者。
原文链接：handsome-man.blog.csdn.net/article/details/109325933
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）