目錄
第1題：獨一無二的出現次數
第2題：速算機器人
第3題：島嶼的周長
第4題：按照頻率将數組升序排序
第5題：根據數字二進制下 1 的數目排序
第6題：能否連接配接形成數組
第7題：強整數
第8題：查詢後的偶數和
第9題：擷取生成數組中的最大值
第10題：二叉樹的深度
力扣(LeetCode)定期刷題，每期10道題，業務繁重的同志可以看看我分享的思路，不是最高效解決方案，隻求互相提升。
試題要求如下：
解題思路：
明顯使用哈希表的思維，但是處理負數的時候需要注意，是以索引不能從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;
} 運作效率如下所示：
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。
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。
/**
* 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;
} /**
* 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。
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;
} /**
* 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;
} 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;
} 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;
} /**
* 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;
}