哈希
两数之和
-
暴力求解方法略，两个for
-
哈希表方法
#include <uthash.h>
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
struct hashTable{
int key;
int val;
UT_hash_handle hh;
}
struct hashTable* hashTable;
struct hashTable* find(int ikey){
struct hashTable* tmp;
HASH_FIND_INT(hashTable, &ikey, tmp);
retrun tmp;
}
void insert(int ikey, int ival){
struct hashTable* it = find(ikey);
if(it == NULL){
struct hashTable* tmp = malloc(sizeof(struct hashTable));
tmp->key = ikey, tmp->val = ival;
HASH_ADD_INT(hashTable,key,tmp);
}else{
it->val = ival;
}
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
hashTable = NULL;
for(int i=0;i<numsSize;i++){
struct hashTable* it = find(target-nums[i]);
if(it != NULL){
int* ret = malloc(sizeof(int)*2);
ret[0]=it->val,ret[1]=i;
*returnSize = 2;
return ret;
}
insert(nums[i],i);
}
*returnSize = 0;
return NULL;
}
字母异位词分组
太难了，不看。。
最长连续序列
依次读取数字，加入哈希表
遍历哈希表，如果有x-1，则跳过。
否则，循环找x+1，取最大长度。
struct HashEntry{
int key;
UT_hash_handle hh;
};
int longestConsecutive(int* nums, int numsSize) {
struct HashEntry* hashSet = NULL;
struct HashEntry* e;
for(int i=0;i<numsSize;i++){
HASH_FIND_INT(hashSet, &nums[i],e);
if(e == NULL){
e = malloc(sizeof(struct HashEntry));
e->key = nums[i];
HASH_ADD_INT(hashSet, key, e);
}
}
int ans = 0;
struct HashEntry* next;
HASH_ITER(hh, hashSet,e,next){
int x = e->key;
int y = x-1;
HASH_FIND_INT(hashSet, &y, e);
if(e){
continue;
}
y = x;
do {
y++;
HASH_FIND_INT(hashSet, &y, e);
}while(e);
ans = fmax(ans, y-x);
}
HASH_CLEAR(hh, hashSet);
return ans;
}
双指针
移动零
个人做法
0移到最后，其余数字往前移。
void moveZeroes(int* nums, int numsSize) {
int end = numsSize-1;
int start = 0;
for(int i=0;i<=end;i++){
if(nums[i] == 0){
for(int j=i;j<end;j++){
nums[j] = nums[j+1];
}
nums[end] = 0;
i--;
end--;
}
}
}
双指针做法
左指针指向当前已经处理好的序列的尾部。左指针左边均为非零数；
右指针指向待处理序列的头部。右指针左边直到左指针处均为零。
void swap(int *a, int *b){
int t = *a;
*a = *b, *b = t;
}
void moveZeroes(int* nums, int numsSize) {
int left = 0, right = 0;
while(right < numsSize){
if(nums[right]){
swap(nums + left, nums + right);
left++;
}
right++;
}
}
盛最多水的容器
指针指向两端，当移动长的那根时，容量不会增大。
所以移动小的那根，不会漏掉更大的容量。
最后比较，取最大。
int maxArea(int* height, int heightSize) {
int start = 0, end = heightSize-1;
int max = 0;
while(start!=end){
int v = (end-start)*fmin(height[start],height[end]);
max = fmax(v,max);
if(height[start]<height[end]){
start++;
}else{
end--;
}
}
return max;
}
二叉树
二叉树的中序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
void inorder(struct TreeNode* root, int* res, int* resSize){
if(root!=NULL){
inorder(root->left,res,resSize);
res[(*resSize)++] = root->val;
inorder(root->right,res,resSize);
}
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int* res = malloc(sizeof(int)*100);
*returnSize = 0;
inorder(root, res, returnSize);
return res;
}
二叉树的最大深度
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int maxDepth(struct TreeNode *root) {
if (root == NULL) return 0;
return fmax(maxDepth(root->left), maxDepth(root->right)) + 1;
}
翻转二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* invertTree(struct TreeNode* root) {
if(root == NULL){
return NULL;
}
struct TreeNode* left = invertTree(root->left);
struct TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
对称二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool check(struct TreeNode* p,struct TreeNode* q){
if(!p && !q) return true; //两个节点都不存在
if(!p || !q) return false;//有一个节点不存在
return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
}
bool isSymmetric(struct TreeNode* root) {
return check(root->left, root->right);
}
二叉树的直径
同求二叉树深度，在代码中增加取左右子树深度和的最大值。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int ans;
int depth(struct TreeNode* root){
if(root == NULL){
return 0;
}
int L = depth(root->left);
int R = depth(root->right);
ans = fmax(ans, L+R);
return fmax(L,R)+1;
}
int diameterOfBinaryTree(struct TreeNode* root) {
ans = 0;
depth(root);
return ans;
}
技巧
只出现一次的数字
异或运算，偶数次出现的数字都被消除。
int singleNumber(int* nums, int numsSize) {
int single = 0;
for(int i=0;i<numsSize;i++){
single ^= nums[i];
}
return single;
}
多数元素
方法一：排序后，去中值
使用快速排序
int cmp(const void* a, const void *b){
return *(int *)a - *(int*)b;
}
int majorityElement(int* nums, int numsSize) {
qsort(nums, numsSize,sizeof(int),cmp);
return nums[numsSize/2];
}
方法二：同归于尽消杀法
https://leetcode.cn/problems/majority-element/solutions/3043071/duo-shu-yuan-su-by-magical-vvingxna-qtgz
int majorityElement(int* nums, int numsSize) {
int flag=nums[0];
int flagnum=0;
int i=0;
while(i<numsSize){
if(nums[i]==flag){
flagnum++;
}else{
if(flagnum==0){
flag=nums[i];
flagnum++;
}else{
flagnum--;
}
}
i++;
}
return flag;
}