leetcode刷题第十天——栈与队列Ⅱ

本次刷题顺序是按照卡尔的代码随想录中给出的顺序

1047. 删除字符串中的所有相邻重复项

char* removeDuplicates(char* s) {int len = strlen(s);char* tmp = malloc(sizeof(char) * (len + 1));int top = -1, idx = 0;while(idx < len) {if(top == -1) tmp[++top] = s[idx];else {if(tmp[top] == s[idx]) top--;else tmp[++top] = s[idx];}idx++;}tmp[++top] = '\0';return tmp;
}

150. 逆波兰表达式求值

bool isNumber(char* ch) {if(strlen(ch) > 1 || '0' <= ch[0] && ch[0] <= '9') return true;else return false;
}int evalRPN(char** tokens, int tokensSize) {int* st = malloc(sizeof(int)* tokensSize);int idx = 0, top = -1;while(idx < tokensSize) {char* ch = tokens[idx];if(!isNumber(ch)){switch(ch[0]) {case '+': st[top - 1] += st[top]; top--; break;case '-': st[top - 1] -= st[top]; top--; break;case '*': st[top - 1] *= st[top]; top--; break;case '/': st[top - 1] /= st[top]; top--; break;}}else {st[++top] = atoi(ch);}idx++;}return st[top];
}

347. 前 K 个高频元素

/*** Note: The returned array must be malloced, assume caller calls free().*/typedef struct {int key;int value;UT_hash_handle hh;
}hash;typedef struct {int H_key;int H_value;
}Heap;Heap* obj;
int Heap_size;bool cmp(Heap obj1, Heap obj2) {return obj1.H_value < obj2.H_value;
}void swap(Heap* obj1, Heap* obj2) {Heap tmp = *obj1;*obj1 = *obj2;*obj2 = tmp;
}Heap H_Top() {return obj[1];
}void H_Pop() {obj[1] = obj[Heap_size--];int idx = 1, t_idx;while((idx << 1) <= Heap_size) {//当前结点有子结点时，继续循环t_idx = idx << 1;if(t_idx < Heap_size && cmp(obj[t_idx + 1], obj[t_idx])) t_idx++;if(cmp(obj[idx], obj[t_idx])) return;swap(&obj[t_idx], &obj[idx]);idx = t_idx;}
}void H_Push(hash x) {obj[++Heap_size].H_key = x.key;obj[Heap_size].H_value = x.value;int idx = Heap_size, t_idx;while(idx > 1) {t_idx = idx >> 1;if(cmp(obj[t_idx], obj[idx])) return;swap(&obj[t_idx], &obj[idx]);idx = t_idx;}
}int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {hash* ha = NULL, * tmp1, * tmp2;int idx = 0;while(idx < numsSize) {//将数据信息存入哈希表HASH_FIND_INT(ha, &nums[idx], tmp1);if(tmp1 == NULL) {tmp1 = malloc(sizeof(hash));tmp1->key = nums[idx];tmp1->value = 1;HASH_ADD_INT(ha, key, tmp1);}else {tmp1->value++;}idx++;}obj = malloc(sizeof(Heap) * (k + 1));Heap_size = 0;Heap mid;HASH_ITER(hh, ha, tmp1, tmp2) {if (Heap_size == k) {mid = H_Top();if (mid.H_value < tmp1->value) {H_Pop();H_Push(*tmp1);}} else {H_Push(*tmp1);}}// 返回结果*returnSize = k;int* ret = malloc(sizeof(int) * k);for (int i = 0; i < k; i++) {mid = H_Top();H_Pop();ret[i] = mid.H_key;}return ret;
}

栈比较适合求解括号匹配、字符去重、逆波兰表达式

今天刷题，顺带复习了哈希表和小根堆的内容。小根堆和大根堆的思维框架是完全二叉树，所以使用数组实现小根堆时，有骚操作，在调整过程中，很妙，多看几遍H_Pop和H_Push的代码，好好体会

写这个系列的博客主要是给自己一个坚持刷题的理由，今天是第十天，感觉敲代码的流畅度有所提高，虽然思维上没有质变，但是相信坚持下去一定会有更大的收获，奥里给！