aboutsummaryrefslogtreecommitdiff
path: root/Computer_Science/leetcode
diff options
context:
space:
mode:
Diffstat (limited to 'Computer_Science/leetcode')
-rw-r--r--Computer_Science/leetcode/15-3_sum.c37
-rw-r--r--Computer_Science/leetcode/15-3_sum.c~7
-rw-r--r--Computer_Science/leetcode/17-letter_combinations_of_a_phone_number.c46
-rw-r--r--Computer_Science/leetcode/17-letter_combinations_of_a_phone_number.c~11
-rw-r--r--Computer_Science/leetcode/5-longest_palindromic_substring.c34
-rw-r--r--Computer_Science/leetcode/5-longest_palindromic_substring.c~7
-rw-r--r--Computer_Science/leetcode/60-permutation_sequence.c33
-rw-r--r--Computer_Science/leetcode/67-add_binary.c75
-rw-r--r--Computer_Science/leetcode/67-add_binary.c~30
-rw-r--r--Computer_Science/leetcode/73-set_matrix_zeros.c46
-rw-r--r--Computer_Science/leetcode/73-set_matrix_zeros.c~7
-rw-r--r--Computer_Science/leetcode/746-min_cost_climbing_stairs.c14
-rw-r--r--Computer_Science/leetcode/746-min_cost_climbing_stairs.c~14
-rw-r--r--Computer_Science/leetcode/75-sort_colors.c41
-rw-r--r--Computer_Science/leetcode/75-sort_colors.c~7
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++)
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-20 21:58:42 +0000