Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

NOTE:
1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canPartition(int *nums, int numsSize);

int main()
{
    int nums[] = {1,5,11,5};
    int n = 4;
    int can = 0;

    can = canPartition(nums,n);
    printf("result is: %d\n",can);

    return 0;
}

int canPartition(int *nums, int numsSize)
{
    int i = 0, j = 0;
    int total = 0;
    int half = 0;
    int max = 0;
    int *sum; // sum[i]=1表示和等于i

    for(i = 0; i < numsSize; i++)
    {
        total += nums[i];
        max = max > nums[i] ? max : nums[i];
    }

    if(total%2) return 0; // 和为奇数，不能划分为等和子集
    if(max > total/2) return 0; // 最大元素大于和的一半，不能划分为等和子集

    half = total/2;
    sum = (int *)malloc((half+1)*sizeof(int));
    memset(sum,0,(half+1)*sizeof(int));

    sum[0] = 1; // 和等于0一定成立，空集就行
    for(i = 0; i < numsSize; i++)
    {
        for(j = half; j >= nums[i]; j--)
        {
            if(sum[j-nums[i]])
            {
                sum[j] = 1;
                if(j == half)
                {
                    return 1;
                }
            }
        }
    }

    return 0;
}

相关资料

https://leetcode.com/problems/edit-distance/
https://www.cnblogs.com/easonliu/p/3661537.html
https://blog.csdn.net/baodream/article/details/80417695

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:
1. Insert a character
2. Delete a character
3. Replace a character

解法

定义：d[i][j] 为 word1 前 i 个字符与 word2 前 j 个字符的最小编辑距离，则：
  d[i][0] = i;
  d[0][j] = j;
  d[i][j] = min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+cost)
其中：word1[i] == word2[j]，则 cost = 0，否则 cost = 1；

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int minDistance(char *s1, char *s2);
int min(int a, int b);

int main()
{
    char *s1 = "horse";
    char *s2 = "ros";

    int d = minDistance(s1,s2);

    printf("min edit distance is: %d\n", d);

    return 0;
}

int minDistance(char *s1, char *s2)
{
    int i,j;
    int cost = 0;
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int **d = (int **)malloc((len1+1)*sizeof(int *)); // 分配指针数组
    d[0] = (int *)malloc((len1+1)*(len2+1)*sizeof(int)); // 二维数组空间

    for(i = 1; i < (len1+1); i++)
    {
        d[i] = d[i-1] + (len2+1);
    }
    memset(d[0],0,(len1+1)*(len2+1)*sizeof(int));

    if (len1 == 0) return len2;
    if (len2 == 0) return len1;

    for (i = 1; i <= len1; i++)
    {
        d[i][0] = i;
    }
    for (j = 1; j <= len2; j++)
    {
        d[0][j] = j;
    }
    for (i = 1; i <= len1; i++)
    {
        for (j = 1; j <= len2; j++)
        {
            if (s1[i-1] == s2[j-1]) cost = 0;
            else cost = 1;

            d[i][j] = min(d[i-1][j]+1, min(d[i][j-1]+1, d[i-1][j-1]+cost));
        }
    }

    return d[len1][len2];
}

int min(int a, int b)
{
    return a < b ? a : b;
}

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

解法

1、n = 1，只有一种方法；
2、n = 2，有两种方法；
3、对于n > 2，则有 第一步爬1级台阶方法数 + 第一步爬2级台阶方法数，即：
                 f(n) = f(n-1) + f(n-2)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int climbStairs(int n, int *steps);

int main()
{
    int n = 10;
    int *steps = malloc(sizeof(int)*(n+1));
    memset(steps,0,sizeof(int)*(n+1));

    steps[n] = climbStairs(n,steps);
    printf("steps=%d\n",steps[n]);

    return 0;
}

int climbStairs(int n, int *steps)
{
    if(n == 1)
    {
        steps[n] = 1;
    }
    else if(n == 2)
    {
        steps[n] = 2;
    }
    else
    {
        if(steps[n-1] == 0)
        {
            steps[n-1] = climbStairs(n-1,steps);
        }
        if(steps[n-2] == 0)
        {
            steps[n-2] = climbStairs(n-2,steps);
        }
        steps[n] = steps[n-1] + steps[n-2];
    }

    return steps[n];
}

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

参考资料

https://www.cnblogs.com/zywscq/p/5403051.html
https://www.cnblogs.com/skysand/p/4300711.html

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node *next;
}node; 

struct heap {
    int ele;
    struct node *head;
};

node **generateList(int (*data)[6], int row, int column);
void displayList(node **head, int row);
void heapsort(struct heap *heap);
void makeHeap(struct heap *heap);
void siftDown(struct heap *heap, int i, int len);

int main()
{
    int i,j;
    int data[][6] = {{1,2,21,47},
                     {15,60,65,84},
                     {77,88,93,100},
                     {5,8,17,36},
                     {20,24,63,72}};
    int *merged = (int *)malloc(sizeof(data));
    int row = sizeof(data)/sizeof(data[0]);
    int column = sizeof(data[0])/sizeof(data[0][0]);
    struct heap *h = (struct heap *)malloc(sizeof(struct heap)*(row+1));

    node **head;

    head = generateList(data,row,column);
    displayList(head,row);

    h[0].ele = row;
    h[0].head = NULL;
    for(i = 0; i < row; i++)
    {
        h[i+1].ele = head[i]->value;
        h[i+1].head = head[i];
    }
    heapsort(h);

    i = 0;
    while(1)
    {
        if(h[0].ele == 0) break;

        merged[i++] = h[1].ele;
        if(h[1].head->next != NULL)
        {
            h[1].head = h[1].head->next;
            h[1].ele = h[1].head->value;
        }
        else
        {
            h[1] = h[h[0].ele];
            h[0].ele--;
        }
        heapsort(h);
        
    }

    printf("合并后数组：");
    for(j = 0; j < i; j++)
    {
        printf("%d ",merged[j]);
    }
    printf("\n");

    return 0;
}

/*
 * 生成链表
 * @param data 二维数组
 * @param row 行数
 * @param column 列数
 */
node **generateList(int (*data)[6], int row, int column)
{
    int i,j;
    node **head = (node **)malloc(sizeof(node *)*row);
    node **tail = (node **)malloc(sizeof(node *)*row);
    
    for(i = 0; i < row; i++)
    {
        tail[i] = (node *)malloc(sizeof(node));
        head[i] = tail[i];
        for(j = 0; j < column; j++)
        {
            if(data[i][j] != 0)
            {
                tail[i]->value = data[i][j];
                if(data[i][j+1] != 0)
                {
                    tail[i]->next = (node *)malloc(sizeof(node));
                    tail[i] = tail[i]->next;
                }
                else
                {
                    tail[i]->next = NULL;
                }
            }
        }
    }
    
    return head;
}

void displayList(node **head, int row)
{
    int i;
    node *cur;

    for(i = 0; i < row; i++)
    {
        cur = head[i];
        while(cur != NULL)
        {
            printf("%d ",cur->value);
            cur = cur->next;
        }
        printf("\n");
    }
}

void heapsort(struct heap *heap)
{
    int len = heap[0].ele;
    int i;
    struct heap temp;
    
    makeHeap(heap);
    
    i = len;
    while(i > 1)
    {
        temp = heap[1];
        heap[1] = heap[i];
        heap[i] = temp;
        i--;

        siftDown(heap,1,i);
    }
}

void makeHeap(struct heap *heap)
{
    int len = heap[0].ele;
    int i;

    for(i = len/2; i >= 1; i--)
    {
        siftDown(heap, i, len);
    }
}

/*
 * 使父节点的值大于其子节点的值
 * @param heap 堆地址
 * @param i 节点索引
 * @param len 长度
 */
void siftDown(struct heap *heap, int i, int len)
{
    struct heap temp;

    if(i < 1 || 2*i > len) return;

    temp = heap[i];
    while(2*i <= len)
    {
        i *= 2;
        if((i < len) && (heap[i].ele < heap[i+1].ele))
        {
            i += 1;//找出子节点中的较大者
        }

        if(temp.ele >= heap[i].ele)
        {
            i /= 2;
            break;
        }

        heap[i/2] = heap[i];
    }
    heap[i] = temp;
}

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

解法

1、查找第k小的数
对于数组A，前p个元素A[0]、A[1]、...、A[p-1]，有p-1个元素不大于A[p-1]，同样，对于数组B，前k-p个元素B[0]、B[1]、...、B[k-p-1]，有k-p-1个元素不大于B[k-p-1]。比较A[p-1]和B[k-p-1]存在三种情况：
1) 若A[p-1] = B[k-p-1]，那么共有(p-1)+(k-p-1)+1=k-1个元素不大于A[p-1]，即A[p-1]是第k小的数；
2) 若A[p-1] < B[k-p-1]，那么第k小的数不可能在区间A[0,p-1]之内。反证法证明：不妨设A[p-1]是第k小的数，也就是说最多只有p-1个数不比它大，而B[k-p-1]大于A[p-1]，所以B[k-p-1]之后的所有数都大于A[p-1]，这样即使B[k-p-1]之前的所有数都不比A[p-1]大，B中也只能找到k-p-1个数不比A[p-1]大，那么A和B中最多只有(p-1)+(k-p-1)=k-2个数不大于A[p-1]，因此A[p-1]不可能是第k小的数；同样的，B[k-p-1]之后的数也不可能是第k小的数，因为它至少是B[k-p]，前面有k-p个数不比B[k-p]大，再加上A[0,p-1]有p个数不比B[k-p]大，因此至少有k-p+p=k个数不比B[k-p]大，也就是说B[k-p]至少是第k+1小的数。舍弃区间之后，问题就变成寻找第k-p小的数。
3) 若A[p-1] > B[k-p-1]，同理可舍去B[0,k-p-1]区间和A[p-1]之后的区间。

2、查找中位数
如果合并后的总元素个数为奇数，则中位数的下标是n/2+1，如果为偶数，则中位数是下标n/2和下标n/2+1两个元素的平均值。

参考资料

https://blog.csdn.net/lxhpkm01/article/details/53823595
https://www.cnblogs.com/davidluo/articles/k-smallest-element-of-two-sorted-array.html

#include <stdio.h>

int findMedian(int *a, int m, int *b, int n);
int findk(int *a, int m, int *b, int n, int k);

int main()
{
    int a[] = {1,3,5,7,9};
    int b[] = {2,4,6,8};
    int m = sizeof(a)/sizeof(int);
    int n = sizeof(b)/sizeof(int);
    int median;

    median = findMedian(a,m,b,n);
    printf("the median is: %d\n",median);

    return 0;
}

/**
 * 查找中位数
 */
int findMedian(int *a, int m, int *b, int n)
{
    int len = m + n;

    if ((len&1) == 0) { // len 为偶数
        return (findk(a,m,b,n,len/2) + findk(a,m,b,n,len/2+1))/2;
    } else { // len 为奇数
        return findk(a,m,b,n,len/2+1);
    }
}

/**
 * 查找第k小的数
 */
int findk(int *a, int m, int *b, int n, int k)
{
    if (m == 0) {
        return b[k-1];
    }
    if (n == 0) {
        return a[k-1];
    }
    if (k == 1) {
        return a[0] < b[0] ? a[0] : b[0];
    }

    if (m > n) {
        return findk(b,n,a,m,k);
    }

    int i = m < k/2 ? m : k/2;
    int j = k - i;

    if (a[i-1] == b[j-1]) {
        return a[i-1];
    } else if (a[i-1] < b[j-1]) {
        return findk(a+i,m-i,b,j,k-i);
    } else {
        return findk(a,i,b+j,n-j,k-j);
    }
}

Given a string, find the length of the longest substring without repeating characters.

解法

滑动窗口

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int longestSubstring(char *s);
int max(int a, int b);

int main()
{
    char *s = "abcabcbb";
    int length;

    length = longestSubstring(s);
    printf("The length of longest substring is: %d\n", length);

    return 0;
}

int longestSubstring(char *s)
{
    int start,end;
    int len = strlen(s); // 字符串长度
    int lenW; // 滑动窗口长度
    char window[128]; // 滑动窗口内的字符
    int pos[128]; // 滑动窗口内的字符在原字符串的位置
    int p,i,flag;
    int length = 0;

    memset(window,0,128*sizeof(char));
    memset(pos,0,128*sizeof(int));
    
    for (start = 0, end = 0; end < len; end++)
    {
        flag = 0;
        p = 0;
        lenW = strlen(window);
        for (i = 0; i < lenW; i++)
        {
            if (window[i] == s[end])
            {
                flag = 1;
                p = pos[i];
                break;
            }
        }
        if (flag)
        {
            start = p + 1;
        }

        length = max(length, end-start+1);
        
        memset(window,0,128*sizeof(char));
        memset(pos,0,128*sizeof(int));
        for (i = 0, p = start; p <= end; p++)
        {
            window[i] = s[p];
            pos[i] = p;
            i++;
        }
    }
    
    return length;
}

int max(int a, int b)
{
    return a > b ? a : b;
}