力扣(LeetCode)刷题，简单题(第27期)

目录

第1题：独一无二的出现次数

第2题：速算机器人

第3题：岛屿的周长

第4题：按照频率将数组升序排序

第5题：根据数字二进制下 1 的数目排序

第6题：能否连接形成数组

第7题：强整数

第8题：查询后的偶数和

第9题：获取生成数组中的最大值

第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  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