75. 颜色分类

• 相关标签： 排序 数组 双指针

/*
r, w, b [0 .... n-1] arr[n]
说白了就是个排序 
但是 排序最快也是 nlogn
O(n) 级别的话 
应该就是 双指针了 

这边 r, w ,b  可以用三指针
0 《 1 《 2
p0
p1
p2

p2  p1  p0 初始状态 

p1 移动 
    遇到0 需要和 P2 进行交换 这样就保证了 p1 经过的位置前面  都 是 0 p2++, p1++ (应为p1, p2 是同一起点， P1 先走， 所有P2 只可能小于1 == 0， 所以可以p1++)
    遇到1  不变 
    遇到2 需要和 P0 交换 这样 p1 进过的 2 都变大 P1 后面qule p0--, (p1 不能++，因为p0 swap 过来的数  可能是 任何数)

po, p2 终止 
*/


void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}


void sortColors(int* nums, int numsSize){
    
    int p0, p1, p2;
    p0 = numsSize -1;
    p1 = p2 = 0;            
    
    while(p1 <= p0) {
        
        if(nums[p1] == 0) {
            swap(&nums[p1], &nums[p2]);
            p2++;
            p1++;
        } else if (nums[p1] == 2) {
            swap(&nums[p1], &nums[p0]);
            p0--;
        } else {
            p1++;
        }
    }
    
}

583. 两个字符串的删除操作

• 相关标签： 字符串 （实际上是动归）

/*
这不就是最长公共子序列嘛。，。

if word1[i] == word2[j] 
    dp[i+1][j+1] = dp[i][j] + 1
else 
    max(dp[i+1][j], dp[i][j+1])

*/

#define BUFLEN 501
#define MAX(x,y) (x > y ? x : y)
int minDistance(char * word1, char * word2){
    
    
    int dp[BUFLEN][BUFLEN] = {0};
    
    for (int i = 0; i < strlen(word1); i++) {
        for (int j = 0; j < strlen(word2); j++) {
             if(word1[i] == word2[j]) {
                 dp[i+1][j+1] = dp[i][j] + 1;
             } else {
                 dp[i+1][j+1] = MAX(dp[i+1][j], dp[i][j+1]);
             }
        }
    }
    
    int longcommsubseq = dp[strlen(word1)][strlen(word2)];
    return strlen(word1) + strlen(word2) - 2 *longcommsubseq;

}