leetCode刷题

两数之和
法1：暴力枚举

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int flag = 0;
    for(int i=0; i
        for(int j=i+; j
            if(nums[i]+nums[j] == target){
                int *res = (int*)malloc(sizeof(int)*2);
                res[0] = i;
                res[1] = j;
                *returnSize = 2;
                return res;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

法2：利用hash表

typedef struct _hashTable{
    int key;
    int value;
    UT_hash_handle hh;
}HashTable;

HashTable *hashtable;

HashTable *find(int ikey){
    HashTable *temp = NULL;
    HASH_FIND_INT(hashtable, &ikey, temp);
    return temp;
}

void add(int ikey, int ivalue){
    HashTable *h = find(ikey);
    if(h == NULL){//没找到则添加到表中
        HashTable *temp = (HashTable*)malloc(sizeof(HashTable));
        temp->key = ikey;
        temp->value = ivalue;
        HASH_ADD_INT(hashtable, key, temp);
    }
    //else
    //   h->value = ivalue;//否则修改原结构
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    hashtable = NULL;
    for(int i=0; i
        HashTable *temp = find(target - nums[i]);
        if(temp != NULL){
            int* res = (int*)malloc(sizeof(int)*2);
            res[0] = temp->value;
            res[1] = i;
            *returnSize = 2;
            return res; 
        }
        add(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

关于uthash.h 参考名叫：嵌入式与Linux那些事的一位博主写的文章C语言哈希表uthash的使用方法详解

两数相加

typedef struct _ListNode{
    int val;
    struct _ListNode *next;
}ListNode;

void insert(ListNode *loc, int value){
    ListNode *node = (ListNode*)malloc(sizeof(ListNode));
    node->next = loc->next;
    node->val = value;
    loc->next = node;
}

struct ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){
    int sum = 0, carry = 0, a, b;
    ListNode *pL1 = l1, *pL2 = l2, *rear;
    ListNode *pRes = (ListNode*)malloc(sizeof(ListNode));
    rear = pRes;
    pRes->next = NULL;

    while(pL1 != NULL || pL2 != NULL){
        a = pL1 == NULL ? 0 : pL1->val;
        b = pL2 == NULL ? 0 : pL2->val;
        sum = a+b+carry >= 10 ? a+b+carry-10 : a+b+carry;
        carry = a+b+carry >= 10 ? 1 : 0;
        insert(rear,sum);
        rear = rear->next;
        pL1 = pL1 == NULL ? pL1 : pL1->next;
        pL2 = pL2 == NULL ? pL2 : pL2->next;
        
    }
    if(carry != 0)
        insert(rear, 1);
    pRes = pRes->next;
    return pRes;
}

无重复字符的最长子串

int lengthOfLongestSubstring(char *s) {
    int low, high, length;
    low = high = length = 0;

    while(s[high] != ''){
        for(int i=low; i
            if(s[i] == s[high]){
                low = i+1;
                break;
            }
        }
        length = high - low + 1 > length ? high - low + 1 : length;
        high++;
    }
	return length;
}

最长回文子串

1. 中心扩散法

int PalindromeSize(char *s, int low, int high, int len){
    while(low>=0 && high
        low--;
        high++;
    }
    return high - low -1;
}
char *longestPalindrome(char *s) {
    int s_len, maxLen, begin; 
    s_len = maxLen = begin = 0;
    while(*(s+s_len))
        s_len++;
    if(s_len < 2)
        return s;
    for(int i=0; i
        int oddLen = PalindromeSize(s, i, i, s_len);//长度为奇数的回文串形如xax
        int evenLen = PalindromeSize(s, i, i+1, s_len);//长度为偶数的回文串形如xx

        int tempLen = oddLen > evenLen ? oddLen : evenLen;
        if(tempLen > maxLen){
            maxLen = tempLen;
            begin = maxLen%2 == 0 ? i - maxLen/2+1: i - maxLen/2;
        }
    }
    *(s+begin+maxLen) = '';
    return s+begin;
}

2. 动态规划
		dp[i][j] 表示字符串s[i...j]是否为回文串，若s[i] != s[j] , 则dp[i][jj] = 0; 若s[i] == s[j], 则dp[i][j] = dp[i+1][j-1]; 
		若字符串长度小于3 形如xx类型，则dp[i][j] = 1;

char * longestPalindrome(char * s){
    int s_len, maxLen, begin;
    s_len = strlen(s);
    maxLen = begin = 0;

    if(s_len < 2)
        return s;
    int dp[1000][1000] = {0};
    for(int i=0; i
        int l;
        for(l=0; l<=r; l++){
            if(s[l] != s[r])
                dp[l][r] = 0;
            else{
                if(r-l < 3)
                    dp[l][r] = 1;
                else
                    dp[l][r] = dp[l+1][r-1];
            }
            if(dp[l][r] && r-l+1 > maxLen){
            begin = l;
            maxLen = r-l+1;
        }
        }
    }
    *(s+begin+maxLen) = '';
    return s+begin;
}