数据结构-数组

use after free:访问堆上被释放的内存
heap buffer overflow：堆上缓冲区访问溢出
stack buffer overflow：栈上缓冲区访问溢出
global buffer overflow：全局缓冲区访问溢出
use after return：访问栈上已被释放的内存

53最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

方法1：暴力求解。超出时间限制。

int maxSubArray(int* nums, int numsSize){
    int i=0,j=0;
    int sum=nums[0];
    int largestSum=nums[0];
    for(;isum?largestSum:sum;
        for(j=i+1;jsum?largestSum:sum;
        }
    }
    return largestSum;
}

方法2：贪心算法

出错的地方：while(nums[i]!=NULL),此时的nums[i]是个整型的数，不能用NULL表示。可以写Nums！=NULL，因为nums是个指针

//贪心算法：若当前的元素之和小于0，则丢弃当前元素之前的数列

/*Greedy algorithm:If the sum of the current element is less than 0, the sequence of the current element is discarded.*/
int maxSubArray(int* nums, int numsSize){
    if(nums==NULL)
        return 0;
    int sum=0;
    int i=0;
    int max=-10000;
    while(imax?sum:max;
        i++;
    }
    return max;
}

方法3：动态规划

//动态规划：如果前一个元素大于0，则把他加到当前元素
/*Dynamic programming:If the previous element is greater than 0,
it is added to the current element.*/
int maxSubArray(int* nums, int numsSize){
    int max=nums[0];
    int i;
    for(i=0;i0)
        {
            nums[i+1]=nums[i]+nums[i+1];
        }
    }
    for(i=0;inums[i]?max:nums[i];
    }
    return max;
}

方法4：分治法
对于一个区间 [l,r][l,r]，我们取 m = (r-l)/2+l;对区间 [l,m][l,m] 和 [m+1,r][m+1,r] 分治求解。当递归逐层深入直到区间长度缩小为 1 的时候，递归「开始回升」。这个时候我们考虑如何通过 [l,m][l,m] 区间的信息和 [m+1,r][m+1,r] 区间的信息合并成区间 [l,r][l,r] 的信息。

/***********partition*******************/
struct status
{
    int isum,lsum,rsum,msum;
    //isum:the sum of the current sequence within [l,r]
    //lsum:the largest sum of the sequence containing the left end point within [l,r]
    //rsum:the largest sum of the sequence containg the right end point within [l,r]
    //msum:the largest sum of the sequence within [l,r]
};

struct status recursion(struct status left,struct status right)
{
    int isum=left.isum+right.isum;
    int lsum=fmax(left.lsum,left.isum+right.lsum);
    int rsum=fmax(right.rsum,right.isum+left.rsum);
    int msum=fmax(fmax(left.msum,right.msum),left.rsum+right.lsum);

    struct status ret={isum,lsum,rsum,msum};
    return ret;
}

struct status get(int *a,int start,int end)
{
    if(start==end)
        return (struct status) {a[start],a[start],a[start],a[start]};
        
    int middle=(end-start)/2+start;

    struct status left=get(a,start,middle);
    struct status right=get(a,middle+1,end);
    return recursion(left,right);
}
int maxSubArray(int* nums, int numsSize){
    return get(nums,0,numsSize-1).msum;
}

1两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 /************哈希表*****************/
# define NULLKEY 100000001

struct Lnode
{
    int val;
    int keyAddr;
};
typedef struct
{
    struct Lnode *elem;
    int count;

}hashTable;//build a hash table of directly determining address 

void initHashTable(hashTable *H,int HASHSIZE)
{
    int i;
    H->count = HASHSIZE;
    
    H->elem = (struct Lnode *) malloc (sizeof(struct Lnode) * HASHSIZE);
    for(i=0; i < HASHSIZE; i++)
    {
        H->elem[i].val = NULLKEY;
        H->elem[i].keyAddr=-1;
    }
   
}

int hashFunc(int key,int HASHSIZE)
{
    if(key<0)   return -key % HASHSIZE;
    else        return key % HASHSIZE;
}

int insertAndSearchValue(hashTable *H, int key,int keyaddr,int target,int HASHSIZE)
{
    int addr = hashFunc(key,HASHSIZE);

    //when we insert "key",see if "target-key" exists.
    for(int i=0; i < HASHSIZE; i++)
    {
        if(H->elem[i].val == target-key)
        {
            return H->elem[i].keyAddr;
        }
    }

    while(H->elem[addr].val != NULLKEY)
    {
        addr = (addr+1) % HASHSIZE;
    }

    H->elem[addr].val = key;
    H->elem[addr].keyAddr = keyaddr;
    return -1;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    hashTable *H=(hashTable*)malloc(sizeof(hashTable));
    initHashTable(H,numsSize);
    int *ret = (int *) malloc (sizeof(int) * 2);

    for(int j=0; j

void sortArray(int *nums, int numsSize)
{
    int i,j;
    for(i=0; i i ; j--)
        {
            if(nums[j]

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    while(n>0)
    {
        if(m>0 && nums1[m-1] > nums2[n-1])
        {
            nums1[--nums1Size] = nums1[--m];
        }
        else
        {
            nums1[--nums1Size] = nums2[--n];
        }
    }
}