diff options
Diffstat (limited to 'Computer_Science')
27 files changed, 518 insertions, 0 deletions
diff --git a/Computer_Science/leetcode/#54-spiral_matrix.c# b/Computer_Science/leetcode/#54-spiral_matrix.c# new file mode 100644 index 0000000..244cfd1 --- /dev/null +++ b/Computer_Science/leetcode/#54-spiral_matrix.c# @@ -0,0 +1,36 @@ +/** + * Note: The returned array must be malloced, assume caller calls free(). + */ + +#define MIN(a, b) ((a) > (b) ? (b) : (a)) +int* spiralOrder(int** matrix, int matrixRowSize, int matrixColSize) { + int* result = malloc(matrixRowSize * matrixColSize); + int index = 0; + int offset; + int maxOffset = MIN(matrixRowSize, matrixColSize) / 2 + 1; + + for(offset = 0; offset < maxOffset; offset++, matrixColSize--, matrixRowSize--) { + if(matrixRowSize == 0 || matrixColSize == 0) + break; + else if(matrixRowSize == 1) { + for(int i = 0; i < matrixColSize; i++) + result[index++] = matrix[offset][offset + i]; + break; + } else if(matrixColSize == 1) { + for(int i = 0; i < matrixRowSize; i++) + result[index++] = matrix[offset + i][offset]; + break; + } else { + for(int i = 0; i < matrixColSize; i++) + result[index++] = matrix[offset][offset + i]; + for(int i = 1; i < matrixRowSize; i++) + result[index++] = matrix[offset + i][offset + matrixColSize - 1]; + for(int i = 1; i < matrixColSize; i++) + result[index++] = matrix[offset + matrixRowSize - 1][offset + matrixColSize - 1 - i]; + for(int i = 1; i < matrixRowSize - 1; i++) + result[index++] = matrix[offset + matrixRowSize - 1 - i][offset]; + } + } + + return result; +} diff --git a/Computer_Science/leetcode/39-combination_sum.c b/Computer_Science/leetcode/39-combination_sum.c new file mode 100644 index 0000000..23695c5 --- /dev/null +++ b/Computer_Science/leetcode/39-combination_sum.c @@ -0,0 +1,46 @@ +#include <stdio.h> +#include <stdlib.h> + +/** + * Return an array of arrays of size *returnSize. + * The sizes of the arrays are returned as *columnSizes array. + * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). + */ +void backtracking(int** result, int* tmp, int* candidates, int candidatesSize, int left, int start, int** columnSizes, int* returnSize) +{ + if(left == 0) { + *(result + *returnSize) = malloc(*(*columnSizes + *returnSize) * sizeof(int)); + for(int i = 0; i < *(*(columnSizes + *returnSize)); i++) + *(*(result + *returnSize) + i) = tmp[i]; + ++*returnSize; + } else if(left > 0) { + tmp[*(*(columnSizes + *returnSize))] = candidates[start]; + ++*(*(columnSizes + *returnSize)); + for(int i = start; i < candidatesSize; i++) + backtracking(result, tmp, candidates, candidatesSize, left, start, columnSizes, returnSize); + --*(*(columnSizes + *returnSize)); + } +} + +int** combinationSum(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize) { + int i; + int **result; + int tmp[100]; + result = malloc(sizeof(int *) * 100); + columnSizes = malloc(sizeof(int) * 100); + *returnSize = 0; + for(i = 0; i < 100; i++) { + *(*columnSizes + i) = 0; + } + if(candidatesSize == 0) + return NULL; + + backtracking(result, tmp, candidates, candidatesSize, target, 0, columnSizes, returnSize); + + return result; +} + +int main() +{ + return 0; +} diff --git a/Computer_Science/leetcode/39-combination_sum.c.out b/Computer_Science/leetcode/39-combination_sum.c.out Binary files differnew file mode 100755 index 0000000..77e20f9 --- /dev/null +++ b/Computer_Science/leetcode/39-combination_sum.c.out diff --git a/Computer_Science/leetcode/39-combination_sum.c~ b/Computer_Science/leetcode/39-combination_sum.c~ new file mode 100644 index 0000000..6b1dd4a --- /dev/null +++ b/Computer_Science/leetcode/39-combination_sum.c~ @@ -0,0 +1,32 @@ +#include <stdio.h> +#include <stdlib.h> + +/** + * Return an array of arrays of size *returnSize. + * The sizes of the arrays are returned as *columnSizes array. + * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). + */ +void backtracking(int** result, int current, int currentSize, int left, int* returnSize, int** columnSizes) +{ + if(left < 0) + return; + else if(left > 0) + return backtracking(result, current, currentSize + 1, left, returnSize); + else { + *(result + *returnSize) = malloc(sizeof(int) * currentSize); + } +} + +int** combinationSum(int* candidates, int candidatesSize, int target, int** columnSizes, int* returnSize) { + int i; + int **result; + result = malloc(sizeof(int *) * 100); + if(candidatesSize == 0) + return NULL; + + for(i = 0; i < candidatesSize; i++) { + backtracking(result, candidates[i], i + 1, target, returnSize, columnSizes); + } + + return result; +} diff --git a/Computer_Science/leetcode/46-permutations.c b/Computer_Science/leetcode/46-permutations.c new file mode 100644 index 0000000..1249253 --- /dev/null +++ b/Computer_Science/leetcode/46-permutations.c @@ -0,0 +1,19 @@ +/** + * Return an array of arrays of size *returnSize. + * Note: The returned array must be malloced, assume caller calls free(). + */ +void backtracking(int* nums, int start, int numsSize, int* returnSize) +{ + if(start == numsSize) return; + else if(start == numsSize -1) { + //add all to result + } else + backtracking(nums, start + 1, numsSize, returnSize); +} + +int** permute(int* nums, int numsSize, int* returnSize) { + for(int i = 0; i < numsSize; i++) { + backtracking(nums, i, numsSize, returnSize); + } +} + diff --git a/Computer_Science/leetcode/46-permutations.c~ b/Computer_Science/leetcode/46-permutations.c~ new file mode 100644 index 0000000..5a7f346 --- /dev/null +++ b/Computer_Science/leetcode/46-permutations.c~ @@ -0,0 +1,18 @@ +/** + * Return an array of arrays of size *returnSize. + * Note: The returned array must be malloced, assume caller calls free(). + */ +int** permute(int* nums, int numsSize, int* returnSize) { + for(int i = 0; i < numsSize; i++) { + backtracking(nums, i + 1, numsSize, returnSize); + } +} + +void backtracking(int* nums, int start, int numsSize, int* returnSize) +{ + if(start == numsSize) return; + else if(start = numsSize -1) { + //add all to result + } else + backtracking(nums, i + 1, numsSize, returnSize); +} diff --git a/Computer_Science/leetcode/48-rotate_image.c b/Computer_Science/leetcode/48-rotate_image.c new file mode 100644 index 0000000..785965f --- /dev/null +++ b/Computer_Science/leetcode/48-rotate_image.c @@ -0,0 +1,31 @@ +void helper(int** matrix, int start, int len) +{ + if(len <= 1) return; + + int tmp1, tmp2; + + for(int i = 0; i < len - 1; i++) { + //save top + //top to righ + tmp1 = matrix[start + i][start + len - 1]; + matrix[start + i][start + len - 1] = matrix[start][start + i]; + //right to button + tmp2 = matrix[start + len - 1][start + len - 1 - i]; + matrix[start + len - 1][start + len - 1 - i] = tmp1; + tmp1 = tmp2; + //buttom to left + tmp2 = matrix[start + len - 1 - i][start]; + matrix[start + len - 1 - i][start] = tmp1; + tmp1 = tmp2; + //left to top + matrix[start][start + i] = tmp1; + } + + helper(matrix, start + 1, len - 2); + +} +void rotate(int** matrix, int matrixRowSize, int matrixColSize) { + helper(matrix, 0, matrixRowSize); +} + + diff --git a/Computer_Science/leetcode/48-rotate_image.c~ b/Computer_Science/leetcode/48-rotate_image.c~ new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/Computer_Science/leetcode/48-rotate_image.c~ diff --git a/Computer_Science/leetcode/49-group_anagrams.c b/Computer_Science/leetcode/49-group_anagrams.c new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/Computer_Science/leetcode/49-group_anagrams.c diff --git a/Computer_Science/leetcode/54-spiral_matrix.c b/Computer_Science/leetcode/54-spiral_matrix.c new file mode 100644 index 0000000..9e747f0 --- /dev/null +++ b/Computer_Science/leetcode/54-spiral_matrix.c @@ -0,0 +1,36 @@ +/** + * Note: The returned array must be malloced, assume caller calls free(). + */ + +#define MIN(a, b) ((a) > (b) ? (b) : (a)) +int* spiralOrder(int** matrix, int matrixRowSize, int matrixColSize) { + int* result = malloc(sizeof(int) * matrixRowSize * matrixColSize); + int index = 0; + int offset; + int maxOffset = MIN(matrixRowSize, matrixColSize) / 2 + 1; + + for(offset = 0; offset < maxOffset; offset++, matrixColSize-= 2, matrixRowSize-= 2) { + if(matrixRowSize == 0 || matrixColSize == 0) + break; + else if(matrixRowSize == 1) { + for(int i = 0; i < matrixColSize; i++) + result[index++] = matrix[offset][offset + i]; + break; + } else if(matrixColSize == 1) { + for(int i = 0; i < matrixRowSize; i++) + result[index++] = matrix[offset + i][offset]; + break; + } else { + for(int i = 0; i < matrixColSize; i++) + result[index++] = matrix[offset][offset + i]; + for(int i = 1; i < matrixRowSize; i++) + result[index++] = matrix[offset + i][offset + matrixColSize - 1]; + for(int i = 1; i < matrixColSize; i++) + result[index++] = matrix[offset + matrixRowSize - 1][offset + matrixColSize - 1 - i]; + for(int i = 1; i < matrixRowSize - 1; i++) + result[index++] = matrix[offset + matrixRowSize - 1 - i][offset]; + } + } + + return result; +} diff --git a/Computer_Science/leetcode/54-spiral_matrix.c~ b/Computer_Science/leetcode/54-spiral_matrix.c~ new file mode 100644 index 0000000..d1b8665 --- /dev/null +++ b/Computer_Science/leetcode/54-spiral_matrix.c~ @@ -0,0 +1,7 @@ +/** + * Note: The returned array must be malloced, assume caller calls free(). + */ +int* spiralOrder(int** matrix, int matrixRowSize, int matrixColSize) { + int* result = malloc(sizeof(int) * matrixRowSize * matrixColSize); + +} diff --git a/Computer_Science/leetcode/55-jump_game.c b/Computer_Science/leetcode/55-jump_game.c new file mode 100644 index 0000000..cdf3ca7 --- /dev/null +++ b/Computer_Science/leetcode/55-jump_game.c @@ -0,0 +1,12 @@ +#define MAX(a, b) ((a) > (b) ? (a) : (b)) +bool canJump(int* nums, int numsSize) { + int reach; + int i; + for(i = 0, reach = 0; i < numsSize && i <= reach; i++) { + reach = MAX(i + nums[i], reach); + if(reach >= numsSize - 1) + return true; + } + + return false; +} diff --git a/Computer_Science/leetcode/55-jump_game.c~ b/Computer_Science/leetcode/55-jump_game.c~ new file mode 100644 index 0000000..ede1827 --- /dev/null +++ b/Computer_Science/leetcode/55-jump_game.c~ @@ -0,0 +1,9 @@ +bool canJump(int* nums, int numsSize) { + int position[numsSize] = {0}; + int i = 0; + while(true) { + if(i == numsSize - 1) + return true; + else if(nums[i] == 1) + } +} diff --git a/Computer_Science/leetcode/58-length_of_last_word.c b/Computer_Science/leetcode/58-length_of_last_word.c new file mode 100644 index 0000000..e1a9b97 --- /dev/null +++ b/Computer_Science/leetcode/58-length_of_last_word.c @@ -0,0 +1,17 @@ +int lengthOfLastWord(char* s) { + char* space; + while(*s == ' ') + s++; + + if(*s == '\0') return 0; + space = s; + while(*s != '\0') { + if(*s == ' ' && *(s + 1) != ' ' && *(s + 1) != '\0') + space = s; + s++; + } + + while(*(--s) == ' '); + + return *space == ' ' ? s - space : s - space + 1; +} diff --git a/Computer_Science/leetcode/58-length_of_last_word.c~ b/Computer_Science/leetcode/58-length_of_last_word.c~ new file mode 100644 index 0000000..4b9e63b --- /dev/null +++ b/Computer_Science/leetcode/58-length_of_last_word.c~ @@ -0,0 +1,13 @@ +int lengthOfLastWord(char* s) { + char* space; + while(*s == ' ') + s++; + + space = s; + while(*s != '\0') { + if(*s == ' ') + space = s; + } + + return s - space; +} diff --git a/Computer_Science/leetcode/59-spiral_matrix_II.c b/Computer_Science/leetcode/59-spiral_matrix_II.c new file mode 100644 index 0000000..27b96bb --- /dev/null +++ b/Computer_Science/leetcode/59-spiral_matrix_II.c @@ -0,0 +1,34 @@ +/** + * Return an array of arrays. + * Note: The returned array must be malloced, assume caller calls free(). + */ +int** generateMatrix(int n) { + int **matrix = malloc(sizeof(int *) * n); + int offset = 0; + int maxOffset = n / 2 + 1; + int index = 1; + int i; + + for(i = 0; i < n; i++) + *(matrix + i) = malloc(sizeof(int) * n); + + for(offset = 0; offset < maxOffset; offset++, n -= 2) { + if(n == 0) + break; + else if(n == 1) { + matrix[offset][offset] = index++; + break; + } else { + for(i = 0; i < n; i++) + matrix[offset][offset + i] = index++; + for(i = 1; i < n; i++) + matrix[offset + i][offset + n - 1] = index++; + for(i = 1; i < n; i++) + matrix[offset + n - 1][offset + n - 1 - i] = index++; + for(i = 1; i < n - 1; i++) + matrix[offset + n - 1 - i][offset] = index++; + } + } + + return matrix; +} diff --git a/Computer_Science/leetcode/59-spiral_matrix_II.c~ b/Computer_Science/leetcode/59-spiral_matrix_II.c~ new file mode 100644 index 0000000..7276575 --- /dev/null +++ b/Computer_Science/leetcode/59-spiral_matrix_II.c~ @@ -0,0 +1,17 @@ +/** + * Return an array of arrays. + * Note: The returned array must be malloced, assume caller calls free(). + */ +int** generateMatrix(int n) { + int **matrix = malloc(sizeof(int *) * n); + int offset = 0; + int maxOffset = n / 2 + 1; + + for(int i = 0; i < n; i++) + *(matrix + i) = malloc(sizeof(int) * n); + for(offset = 0; offset < maxOffset; offset++, n -= 2) { + if(n == 0) + return; + else if(n == 1) + matrix +} diff --git a/Computer_Science/leetcode/60-permutation_sequence.c b/Computer_Science/leetcode/60-permutation_sequence.c new file mode 100644 index 0000000..4eadf4c --- /dev/null +++ b/Computer_Science/leetcode/60-permutation_sequence.c @@ -0,0 +1,22 @@ +char* getPermutation(int n, int k) { + char* result = malloc(sizeof(char) * n + 1); + int use; + int used[n]; + int fac[n]; + fac[0] = 1; + fac[1] = 1; + + for(int i = 2; i < n; ++i) { + fac[i] = fac[i - 1] * n; + } + + for(int i = 0; i < n; ++i) { + use = 1 + ((k - 1) / fac[n-i]); + k -= fac[n-i]; + result[i] = use + '0'; + } + + result[n] = '\0'; + + return result; +} diff --git a/Computer_Science/leetcode/60-permutation_sequence.c~ b/Computer_Science/leetcode/60-permutation_sequence.c~ new file mode 100644 index 0000000..c7cb235 --- /dev/null +++ b/Computer_Science/leetcode/60-permutation_sequence.c~ @@ -0,0 +1,3 @@ +char* getPermutation(int n, int k) { + return NULL; +} diff --git a/Computer_Science/leetcode/63-unique_paths_II.c b/Computer_Science/leetcode/63-unique_paths_II.c index e69de29..b736541 100644 --- a/Computer_Science/leetcode/63-unique_paths_II.c +++ b/Computer_Science/leetcode/63-unique_paths_II.c @@ -0,0 +1,38 @@ +#include <stdio.h> + +int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridRowSize, int obstacleGridColSize) { + int i, j; + int matrix[obstacleGridRowSize][obstacleGridColSize]; + + for(i = 0; i < obstacleGridColSize; i++) { + if(obstacleGrid[0][i] == 0) + matrix[0][i] = 1; + else + for(; i < obstacleGridColSize; i++) + matrix[0][i] = 0; + } + + for(i = 0; i < obstacleGridRowSize; i++) { + if(obstacleGrid[i][0] == 0) + matrix[i][0] = 1; + else + for(; i < obstacleGridRowSize; i++) + matrix[i][0] = 0; + } + + for(i = 1; i < obstacleGridRowSize; i++) { + for(j = 1; j < obstacleGridColSize; j++) { + if(obstacleGrid[i][j] == 1) + matrix[i][j] = 0; + else + matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1]; + } + } + + return matrix[obstacleGridRowSize - 1][obstacleGridColSize - 1]; +} + +int main() +{ + return 0; +} diff --git a/Computer_Science/leetcode/63-unique_paths_II.c.out b/Computer_Science/leetcode/63-unique_paths_II.c.out Binary files differnew file mode 100755 index 0000000..94c0724 --- /dev/null +++ b/Computer_Science/leetcode/63-unique_paths_II.c.out diff --git a/Computer_Science/leetcode/64-minimum_path_sum.c b/Computer_Science/leetcode/64-minimum_path_sum.c new file mode 100644 index 0000000..f9d7a50 --- /dev/null +++ b/Computer_Science/leetcode/64-minimum_path_sum.c @@ -0,0 +1,20 @@ +#define MIN(a, b) ((a) > (b) ? (b) : (a)) + +int minPathSum(int** grid, int gridRowSize, int gridColSize) { + int dp[gridRowSize][gridColSize]; + + int i, j; + + dp[0][0] = grid[0][0]; + + for(i = 1; i < gridColSize; i++) + dp[0][i] = dp[0][i - 1] + grid[0][i]; + for(i = 1; i < gridRowSize; i++) + dp[i][0] = dp[i - 1][0] + grid[i][0]; + + for(i = 1; i < gridRowSize; i++) + for(j = 1; j < gridColSize; j++) + dp[i][j] = MIN(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; + + return dp[gridRowSize - 1][gridColSize - 1]; +} diff --git a/Computer_Science/leetcode/64-minimum_path_sum.c~ b/Computer_Science/leetcode/64-minimum_path_sum.c~ new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/Computer_Science/leetcode/64-minimum_path_sum.c~ diff --git a/Computer_Science/leetcode/65-valid_number.c b/Computer_Science/leetcode/65-valid_number.c new file mode 100644 index 0000000..b8ee227 --- /dev/null +++ b/Computer_Science/leetcode/65-valid_number.c @@ -0,0 +1,47 @@ +#include <string.h> + +bool isNumber(char* s) { + char *p; + int dot_flag = 0; + int e_flag = 0; + + for(; *s == ' '; s++) + ; + if(*s == '+' || *s == '-') + s++; + + p = s; + + /* trim tail */ + for(; *p != '\0'; p++) + ; + for(p--; p != s && *p == ' '; p--) + ; + *(p + 1) = '\0'; + + p = s; + if(*p == '\0') return false; + + for(; *p != '\0'; p++) { + if(*p <= '9' && *p >= '0') + continue; + else if(*p == '.') { + if(dot_flag == 1) + return false; + if((s == p && *(p + 1) == '\0') + || *(p - 1) == 'e') + return false; + dot_flag = 1; + continue; + } else if(*p == 'e') { + if(e_flag == 1) + return false; + if(s == p || *(p + 1) == '\0' || (*(p - 1) == '.' && p - 1 == s)) + return false; + e_flag = 1; + } else + return false; + } + + return true; +} diff --git a/Computer_Science/leetcode/65-valid_number.c~ b/Computer_Science/leetcode/65-valid_number.c~ new file mode 100644 index 0000000..927009f --- /dev/null +++ b/Computer_Science/leetcode/65-valid_number.c~ @@ -0,0 +1,17 @@ +#include <string.h> + +bool isNumber(char* s) { + char *p = s; + int dot_flag = 0; + int e_flag = 0; + + for(; *p == ' '; p++) + ; + + for(; *p != '\0'; p++) { + if(*p <= '9' || *p >= '0') + continue; + else if(*p == '.') { + if(dot_flag == 1) + return false; +} diff --git a/Computer_Science/leetcode/66-plus_one.c b/Computer_Science/leetcode/66-plus_one.c new file mode 100644 index 0000000..63d151c --- /dev/null +++ b/Computer_Science/leetcode/66-plus_one.c @@ -0,0 +1,33 @@ +/** + * Return an array of size *returnSize. + * Note: The returned array must be malloced, assume caller calls free(). + */ +int* plusOne(int* digits, int digitsSize, int* returnSize) { + int i; + int in = 1; + int *result; + + for(i = digitsSize - 1; i >=0; i--) { + if(digits[i] == 9 && in == 1) { + digits[i] = 0; + in = 1; + } else { + digits[i] += in; + in = 0; + } + } + + if(in == 1) { + result = malloc(sizeof(int) * (digitsSize + 1)); + result[0] = 1; + for(i = 1; i < digitsSize + 1; i++) { + result[i] = digits[i-1]; + } + *returnSize = digitsSize + 1; + } else { + result = digits; + *returnSize = digitsSize; + } + + return result; +} diff --git a/Computer_Science/leetcode/66-plus_one.c~ b/Computer_Science/leetcode/66-plus_one.c~ new file mode 100644 index 0000000..1936abf --- /dev/null +++ b/Computer_Science/leetcode/66-plus_one.c~ @@ -0,0 +1,11 @@ +/** + * Return an array of size *returnSize. + * Note: The returned array must be malloced, assume caller calls free(). + */ +int* plusOne(int* digits, int digitsSize, int* returnSize) { + int i; + int in; + + for(i = digitsSize - 1; i >=1; i--) { + +} |