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;
}
