update

15 files changed, 401 insertions, 8 deletions

diff --git a/Computer_Science/leetcode/15-3_sum.c b/Computer_Science/leetcode/15-3_sum.c
new file mode 100644
index 0000000..cb60873
--- /dev/null
+++ b/Computer_Science/leetcode/15-3_sum.c
@@ -0,0 +1,37 @@
+/**
+ * Return an array of arrays of size *returnSize.
+ * Note: The returned array must be malloced, assume caller calls free().
+ */
+void helper(int **result, int *nums, int start, int numsSize, int *tmp, int count, int *returnSize)
+{
+	if(start >= numsSize) return;
+	if(count < 3) {
+		tmp[count] = nums[start];
+		helper(result, nums, start + 1, numsSize, tmp, count + 1, returnSize);
+	}
+	else if(count == 3) {
+		if(tmp[0] + tmp[1] + tmp[2] == 0) {
+			*(result + *returnSize) = malloc(sizeof(int) * 3);
+			**(result + *returnSize) = tmp[0];
+			*(*(result + *returnSize) + 1) = tmp[1];
+			*(*(result + *returnSize) + 2) = tmp[2];
+			++*returnSize;
+		}
+		helper(result, nums, start, numsSize, tmp, count - 1, returnSize);
+		helper(result, nums, start, numsSize, tmp, count - 2, returnSize);
+	}
+
+}
+
+int** threeSum(int* nums, int numsSize, int* returnSize) {
+	*returnSize = 0;
+	int **result = malloc(sizeof(int *) * 100);
+	int tmp[3];
+	int count = 0;
+	
+	for(int i = 0; i < numsSize; i++) {
+		helper(result, nums, i, numsSize, tmp, 0, returnSize);
+	}
+
+	return result;
+}
diff --git a/Computer_Science/leetcode/15-3_sum.c~ b/Computer_Science/leetcode/15-3_sum.c~
new file mode 100644
index 0000000..54dbbd2
--- /dev/null
+++ b/Computer_Science/leetcode/15-3_sum.c~
@@ -0,0 +1,7 @@
+/**
+ * Return an array of arrays of size *returnSize.
+ * Note: The returned array must be malloced, assume caller calls free().
+ */
+int** threeSum(int* nums, int numsSize, int* returnSize) {
+    
+}
diff --git a/Computer_Science/leetcode/17-letter_combinations_of_a_phone_number.c b/Computer_Science/leetcode/17-letter_combinations_of_a_phone_number.c
new file mode 100644
index 0000000..eeabd21
--- /dev/null
+++ b/Computer_Science/leetcode/17-letter_combinations_of_a_phone_number.c
@@ -0,0 +1,46 @@
+/**
+ * Return an array of size *returnSize.
+ * Note: The returned array must be malloced, assume caller calls free().
+ */
+void helper(char **result, char *map[10], char *digits, char *tmp, int index, int *returnSize)
+{
+	char *p = map[*digits - '0'];
+	for(; *p; ++p) {
+		tmp[index] = *p;
+		helper(result, map, digits + 1, tmp, index + 1, returnSize);
+	}
+	if(*digits == '\0') {
+		*(result + *returnSize) = malloc(sizeof(char) * index + 1);
+		for(int i = 0; i < index; i++) {
+			*(*(result + *returnSize) + i) = tmp[i];
+		}
+		*(*(result + *returnSize) + index) = '\0';
+		++*returnSize;
+	}
+}
+char** letterCombinations(char* digits, int* returnSize) {
+	int len = strlen(digits);
+	int index = 0;
+	char tmp[len + 1];
+	char **result = malloc(sizeof(int *) * 100);
+	char *map[10] = {
+		" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
+	};
+
+	*returnSize = 0;
+
+	if(len < 1)
+		return result;
+
+	while(*digits) {
+		if(*digits >= '2' && *digits <= '9') {
+			helper(result, map, digits, tmp, index, returnSize);
+		} else {
+			*returnSize = 0;
+			break;
+		}
+		++digits;
+	}
+
+	return result;
+}
diff --git a/Computer_Science/leetcode/17-letter_combinations_of_a_phone_number.c~ b/Computer_Science/leetcode/17-letter_combinations_of_a_phone_number.c~
new file mode 100644
index 0000000..d31867b
--- /dev/null
+++ b/Computer_Science/leetcode/17-letter_combinations_of_a_phone_number.c~
@@ -0,0 +1,11 @@
+/**
+ * Return an array of size *returnSize.
+ * Note: The returned array must be malloced, assume caller calls free().
+ */
+char** letterCombinations(char* digits, int* returnSize) {
+	while(*digits) {
+		if(*digits >= '2' && *digits <= '9') {
+		} else
+			return "";
+	}
+}
diff --git a/Computer_Science/leetcode/5-longest_palindromic_substring.c b/Computer_Science/leetcode/5-longest_palindromic_substring.c
new file mode 100644
index 0000000..ee65b8e
--- /dev/null
+++ b/Computer_Science/leetcode/5-longest_palindromic_substring.c
@@ -0,0 +1,34 @@
+void extend(char *s, int len, int i, int j, int *lo, int *hi)
+{
+	while(i >= 0 && i < len && s[i] == s[j]) {
+		i--;
+		j++;
+	}
+
+	if(j - i > *hi - *lo) {
+		*lo = i;
+		*hi = j;
+	}
+}
+
+char* longestPalindrome(char* s) {
+	int *lo, *hi;
+	int len = strlen(s);
+
+	lo = malloc(sizeof(int));
+	hi = malloc(sizeof(int));
+
+	*lo = *hi = 0;
+	if(len < 2)
+		return s;
+
+	for(int i = 0; i < len - 1; i++) {
+		extend(s, len, i, i, lo, hi);
+		extend(s, len, i, i + 1, lo, hi);
+	}
+
+	*(s + (*hi)) = '\0';
+	return s + *lo + 1;
+}
+
+
diff --git a/Computer_Science/leetcode/5-longest_palindromic_substring.c~ b/Computer_Science/leetcode/5-longest_palindromic_substring.c~
new file mode 100644
index 0000000..99c44fc
--- /dev/null
+++ b/Computer_Science/leetcode/5-longest_palindromic_substring.c~
@@ -0,0 +1,7 @@
+char* longestPalindrome(char* s) {
+	int *lo, *hi;
+
+	*(p + (*hi) + 1) = '0';
+	return p + *lo;
+}
+
diff --git a/Computer_Science/leetcode/60-permutation_sequence.c b/Computer_Science/leetcode/60-permutation_sequence.c
index 4eadf4c..259d00b 100644
--- a/Computer_Science/leetcode/60-permutation_sequence.c
+++ b/Computer_Science/leetcode/60-permutation_sequence.c
@@ -1,18 +1,35 @@
-char* getPermutation(int n, int k) {
-	char* result = malloc(sizeof(char) * n + 1);
+int getKth(int k, int* nums, int len)
+{
+	int result = nums[k];
+
+	for(int i = k; i < len - 1; i++)
+		nums[i] = nums[i + 1];
+
+	return result;
+}
+char* getPermutation(int n, int k)
+{
+	if(n == 0) return NULL;
+
+	char* result = malloc(sizeof(char) * (n + 1));
 	int use;
-	int used[n];
+	int nums[n];
 	int fac[n];
+	int len = n;
+
 	fac[0] = 1;
-	fac[1] = 1;
 
-	for(int i = 2; i < n; ++i) {
-		fac[i] = fac[i - 1] * n;
+	for(int i = 1; i < n; ++i) {
+		nums[i - 1] = i;
+		fac[i] = fac[i - 1] * i;
 	}
+	nums[n - 1] = n;
 
 	for(int i = 0; i < n; ++i) {
-		use = 1 + ((k - 1) / fac[n-i]);
-		k -= fac[n-i];
+		/* here k = n - 1, i.e. get 2th, index = 1 */
+		use = getKth(((k - 1) / fac[n - 1 - i]), nums, len);
+		len--;
+		k -= ((k - 1) / fac[n - 1 - i]) * fac[n - 1 - i];
 		result[i] = use + '0';
 	}
 
diff --git a/Computer_Science/leetcode/67-add_binary.c b/Computer_Science/leetcode/67-add_binary.c
new file mode 100644
index 0000000..48e4744
--- /dev/null
+++ b/Computer_Science/leetcode/67-add_binary.c
@@ -0,0 +1,75 @@
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+char* addBinary(char* a, char* b) {
+	int lenA = strlen(a);
+	int lenB = strlen(b);
+
+	int len = MAX(lenA, lenB) + 1;
+	char* result = malloc(sizeof(char) * (len + 1));
+	result[len--] = '\0';
+	char in = '0';
+	int sum = 0;
+
+	lenA--;
+	lenB--;
+
+	if(len == 0) return "0";
+	
+	while(lenA >= 0 && lenB >=0) {
+		sum = a[lenA] + b[lenB] + in - 3 * '0';
+		switch(sum) {
+		case 0:
+			in = '0';
+			result[len] = '0';
+			break;
+		case 1:
+			in = '0';
+			result[len] = '1';
+			break;
+		case 2:
+			in = '1';
+			result[len] = '0';
+			break;
+		case 3:
+			in = '1';
+			result[len] = '1';
+			break;
+		}
+		lenA--;
+		lenB--;
+		len--;
+	}
+
+	while(lenA >= 0) {
+		if(in == '0') {
+			result[len] = a[lenA];
+		} else if(a[lenA] == '1') {
+			result[len] = '0';
+			in = '1';
+		} else {
+			result[len] = '1';
+			in = '0';
+		}
+		lenA--;
+		len--;
+	}
+
+	while(lenB >= 0) {
+		if(in == '0') {
+			result[len] = b[lenB];
+		} else if(b[lenB] == '1') {
+			result[len] = '0';
+			in = '1';
+		} else {
+			result[len] = '1';
+			in = '0';
+		}
+		lenB--;
+		len--;
+	}
+
+	if(in == '0')
+		return result + 1;
+
+	*result = '1';
+	return result;
+}
diff --git a/Computer_Science/leetcode/67-add_binary.c~ b/Computer_Science/leetcode/67-add_binary.c~
new file mode 100644
index 0000000..1fdffec
--- /dev/null
+++ b/Computer_Science/leetcode/67-add_binary.c~
@@ -0,0 +1,30 @@
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+char* addBinary(char* a, char* b) {
+	char* result = malloc(sizeof(char) * (MAX(strlen(a), strlen(b)) + 2));
+	char in = '0';
+	int sum = 0;
+	while(*a && *b) {
+		sum = *a + *b + in - 3 * '0';
+		switch(sum) {
+		case 0:
+			in = '0';
+			*result = '0';
+			break;
+		case 1:
+			in = '0';
+			*result = '1';
+			break;
+		case 2:
+			in = '1';
+			*result = '0';
+			break;
+		case 3:
+			in = '1';
+			*result = '1';
+			break;
+		}
+
+		result++;
+	}
+			
+}
diff --git a/Computer_Science/leetcode/73-set_matrix_zeros.c b/Computer_Science/leetcode/73-set_matrix_zeros.c
new file mode 100644
index 0000000..31d530f
--- /dev/null
+++ b/Computer_Science/leetcode/73-set_matrix_zeros.c
@@ -0,0 +1,46 @@
+void helper(int** matrix, int rowOffset, int colOffset, int rowSize, int colSize, int maxRowSize, int maxColSize)
+{
+	if(rowOffset >= maxRowSize || colOffset >= maxColSize
+	   || rowOffset < 0 || colOffset < 0
+	   || rowSize <= 0 || colSize <= 0)
+		return;
+	for(int i = 0; i < rowSize; i++)
+		for(int j = 0; j < colSize; j++)
+			if(matrix[rowOffset + i][colOffset + j] == 0) {
+				for(int m = 0; m < colSize; m++)
+					matrix[rowOffset + i][colOffset + m] = 0;
+				for(int m = 0; m < rowSize; m++)
+					matrix[rowOffset + m][colOffset + j] = 0;
+				//left
+				helper(matrix, rowOffset + 1, colOffset, rowSize - 1 - i, j, maxRowSize, maxColSize);
+				//right
+				helper(matrix, rowOffset + 1, colOffset + j + 1, rowSize - 1 - i, colSize - 1 - j, maxRowSize, maxColSize);
+				return;
+			}
+}
+void setZeroes(int** matrix, int matrixRowSize, int matrixColSize) {
+	helper(matrix, 0, 0, matrixRowSize, matrixColSize, matrixRowSize, matrixColSize);
+}
+
+
+//Flag version need to be improved
+
+
+void setZeroes(int** matrix, int matrixRowSize, int matrixColSize) {
+	int flag = INT_MIN;
+
+	for(int i = 0; i < matrixRowSize; i++)
+		for(int j = 0; j < matrixColSize; j++) {
+			if(matrix[i][j] == 0) {
+				for(int m = 0; m < matrixRowSize; m++)
+					matrix[m][j] = matrix[m][j] == 0 ? 0 : flag;
+				for(int m = 0; m < matrixColSize; m++)
+					matrix[i][m] = matrix[i][m] == 0 ? 0 : flag;
+			}
+		}
+	
+	for(int i = 0; i < matrixRowSize; i++)
+		for(int j = 0; j < matrixColSize; j++) {
+			if(matrix[i][j] == flag) matrix[i][j] = 0;
+		}
+}
diff --git a/Computer_Science/leetcode/73-set_matrix_zeros.c~ b/Computer_Science/leetcode/73-set_matrix_zeros.c~
new file mode 100644
index 0000000..e9f222b
--- /dev/null
+++ b/Computer_Science/leetcode/73-set_matrix_zeros.c~
@@ -0,0 +1,7 @@
+void helper(int** matrix, int offset, int rowSize, int colSize)
+{
+	if(offset > rowSize || offset > colSize)
+		return;
+}
+void setZeroes(int** matrix, int matrixRowSize, int matrixColSize) {    
+}
diff --git a/Computer_Science/leetcode/746-min_cost_climbing_stairs.c b/Computer_Science/leetcode/746-min_cost_climbing_stairs.c
new file mode 100644
index 0000000..74cc72b
--- /dev/null
+++ b/Computer_Science/leetcode/746-min_cost_climbing_stairs.c
@@ -0,0 +1,14 @@
+#define MIN(a, b) ((a) > (b) ? (b) : (a))
+int minCostClimbingStairs(int* cost, int costSize) {
+	int dp[costSize + 1];
+	if(costSize == 1)
+		return cost[0];
+	dp[0] = 0;
+	dp[1] = 0;
+
+	for(int i = 2; i < costSize + 1; i++) {
+		dp[i] = MIN(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
+	}
+
+	return dp[costSize];
+}
diff --git a/Computer_Science/leetcode/746-min_cost_climbing_stairs.c~ b/Computer_Science/leetcode/746-min_cost_climbing_stairs.c~
new file mode 100644
index 0000000..44ffb6b
--- /dev/null
+++ b/Computer_Science/leetcode/746-min_cost_climbing_stairs.c~
@@ -0,0 +1,14 @@
+#define MIN(a, b) ((a) > (b) ? (a) : (b))
+int minCostClimbingStairs(int* cost, int costSize) {
+	int dp[costSize];
+	if(costSize == 1)
+		return cost[0];
+	dp[0] = 0;
+	dp[1] = 0;
+
+	for(i = 2; i < costSize; i++) {
+		dp[i] = MIN(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
+	}
+
+	return dp[costSize - 1];
+}
diff --git a/Computer_Science/leetcode/75-sort_colors.c b/Computer_Science/leetcode/75-sort_colors.c
new file mode 100644
index 0000000..cc8fe51
--- /dev/null
+++ b/Computer_Science/leetcode/75-sort_colors.c
@@ -0,0 +1,41 @@
+void swap(int* a, int*b)
+{
+	int tmp;
+	tmp = *a;
+	*a = *b;
+	*b = tmp;
+}
+
+void sortColors(int* nums, int numsSize) {
+	int wIndex, bIndex;
+	wIndex = 0;
+	bIndex = numsSize - 1;
+
+	while(nums[bIndex] == 2)
+		bIndex--;
+	
+	// here <= or < ?
+	for(int i = 0; i <= bIndex; i++) {
+		if(nums[i] == 0) {
+			swap(nums + i, nums + wIndex);
+			wIndex++;
+		} else if(nums[i] == 2) {
+			if(nums[bIndex] == 0) {
+				swap(nums + i, nums + bIndex);
+				swap(nums + i, nums + wIndex);
+				wIndex++;
+				bIndex--;
+			} else if(nums[bIndex] == 1) {
+				swap(nums + i, nums + bIndex);
+				bIndex--;
+			} else if(i != bIndex) {
+				swap(nums + i, nums + bIndex - 1);
+				if(nums[i] == 0) {
+					swap(nums + i, nums + wIndex);
+					wIndex++;
+				}
+				bIndex -= 2;
+			}
+		}
+	}
+}
diff --git a/Computer_Science/leetcode/75-sort_colors.c~ b/Computer_Science/leetcode/75-sort_colors.c~
new file mode 100644
index 0000000..1729e67
--- /dev/null
+++ b/Computer_Science/leetcode/75-sort_colors.c~
@@ -0,0 +1,7 @@
+void sortColors(int* nums, int numsSize) {
+	int wIndex, bIndex;
+	wIndex = 0;
+	bIndex = numsSize - 1;
+
+	for(int i = 0; i < numsSize && ; i++)
+}