# Leetcode
## binary search
### Search a 2D Matrix
https://leetcode.com/problems/search-a-2d-matrix/submissions/
Regarding whether technique should I use.
A: while(right > left) + right = mid
B: while(right >= left) + right = mid - 1;
Well, A and B can be used to catch the value we want after
it jumps out of the loop.
However, If we want to find a value inside the loop,
it will be better to use A.
Solution 1:
```
bool searchMatrix(int** nums, int matrixSize, int* matrixColSize, int target){
int i = 0, left = 0, right = 0;
if(matrixSize == 1 && *matrixColSize == 1){
if(nums[0][0] == target) return true;
else return false;
}
for(; i < matrixSize; ++i){
right = *matrixColSize - 1;
left = 0;
while(left <= right){
int mid = left + (right - left) / 2;
//printf("left: %d right %d nums[%d] : %d\n", left, right, i, nums[i][mid]);
if(nums[i][mid] == target){
return true;
}
else if(nums[i][mid] < target){
left = mid + 1;
}
else right = mid - 1;
}
}
return false;
}
```
Solution 2
```
bool searchMatrix(int** nums, int matrixSize, int* matrixColSize, int target){
int i = 0, left = 0, right = 0;
if(matrixSize == 1 && *matrixColSize == 1){
if(nums[0][0] == target) return true;
else return false;
}
for(; i < matrixSize; ++i){
right = *matrixColSize - 1;
left = 0;
while(left < right){
int mid = left + (right - left) / 2;
//printf("left: %d right %d nums[%d] : %d\n", left, right, i, nums[i][mid]);
if(nums[i][mid] < target){
left = mid + 1;
}
else right = mid;
}
if(nums[i][left] == target) return true;
}
return false;
}
```
Solution 3.
```
bool searchMatrix(int** nums, int matrixSize, int* matrixColSize, int target){
// if(matrixSize == 1 && *matrixColSize == 1){
// if(nums[0][0] == target) return true;
// else return false;
//}
int left = 0, right = matrixSize * (*matrixColSize) - 1;
int mid = 0, mid_element = 0;
while(right >= left){
mid = left + (right - left) / 2;
mid_element = nums[mid / (*matrixColSize)][mid % (*matrixColSize)];
printf("mid: %d\n", mid_element);
if(mid_element == target) return true;
else if(mid_element < target)
left = mid + 1;
else
right = mid - 1;
}
return false;
}
```
### Find the Peak Element
https://leetcode.com/problems/find-peak-element/description/
```
int findPeakElement(int* nums, int numsSize){
if(numsSize == 1) return 0;
int left = 0;
int right = numsSize - 1;
while(left < right){
int mid = (left + right) / 2;
if(nums[mid] < nums[mid + 1]){
left = mid + 1;
}
else right = mid;
}
return left;// or right
}
```
### Find Minimum in Rotated Sorted Array II
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/
```
int recur(int* nums, int l, int r){
if(l == r) return nums[l];
int mid = (l + r) / 2;
if(nums[mid] > nums[r]) return recur(nums, mid + 1, r);
if(nums[mid] < nums[r]) return recur(nums, l, mid);
return recur(nums, l, r - 1);
//By taking look at the element closer to the left, we can tailor the condition we want.
}
int findMin(int* nums, int numsSize){
return recur(nums, 0, numsSize - 1);
}
```
### Search in Rotated Sorted Array
https://leetcode.com/problems/search-in-rotated-sorted-array/description/
Solution 1:
```
int search(int* nums, int numsSize, int target){
if(nums == NULL || numsSize == 0) return -1;
int left = 0, right = numsSize - 1, mid = 0;
while(right > left){//We do not have to let right = left
//Because we just want to find the one doesn't suit our need
//instead of the one needed to be screened out when fitting the condition.
mid = (right + left) >> 1;
if(nums[mid] > nums[right]){
left = mid + 1;
}
else right = mid;
//printf("%d %d %d\n", left, right, nums[mid]);
}
/* However, this does work:
while(right > left){//We do not have to let right = left
//Because we just want to find the one doesn't suit our need
//instead of the one needed to be screened out when fitting the condition.
mid = (right + left) / 2;
if(nums[mid] > nums[right]){
left = mid + 1;
}
else right = mid;
//printf("%d %d %d\n", left, right, nums[mid]);
}
*/
int start = left;
left = 0;
right = numsSize - 1;
if(target >= nums[start] && target <= nums[right]){
left = start;
}
else{
right = start;
}
while(right >= left){
mid = (right + left) >> 1;
if(nums[mid] == target) return mid;
else if(nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
```
Solution 2:
```
int search(int* nums, int numsSize, int target) {
int low = 0, high = numsSize - 1;
while (low < high) {
int m = (low + high) >> 1;
if (target > nums[high])
//This indicates that we have to search the first part
//of the array.
if (nums[m] < target && nums[m] > nums[high]) low = m + 1;
//The second part of expression tells me that
//Midpoint should not exceed the pivot.
//If midpoint is lower than the high element,
//we have to increase the left point.
else high = m;
else
if (nums[m] >= target && nums[m] <= nums[high]) high = m;
else low = m + 1;
}
return nums[low] == target ? low : -1;
}
```
### Search Insert Position
https://leetcode.com/problems/search-insert-position/description/
```
int searchInsert(int* nums, int numsSize, int target){
int left = 0, right = numsSize;
int mid = 0;
while(left < right){
mid = (right + left) / 2;
if(nums[mid] == target){
return mid;
}else if(nums[mid] < target){
left = mid + 1;
}else{
right = mid;
}
}
return left;
}
```
## Matrix
### Shortest Path in Binary Matrix
https://leetcode.com/problems/shortest-path-in-binary-matrix/description/
```
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int rsize = grid.size();
if(rsize == 0) return -1;
int csize = grid[0].size();
if(csize == 0) return -1;
if(grid[0][0] != 0 || grid[rsize - 1][csize - 1] != 0) return -1;
queue<pair<int, int>> q;
q.push({0, 0});
grid[0][0] = 1;
vector<int> v{1, 1, 0, 1, -1, -1, 0, -1, 1};
//(1, 1) (1, 0) (0, 1) (1, -1) (-1, -1) (-1, 0) (0, -1) (-1, 1)
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
if(x == rsize - 1 && y == csize - 1) return grid[x][y];
for(int i = 0; i < 8; ++i){
int nx = x + v[i], ny = y + v[i + 1];
if(nx >= 0 && nx < rsize && ny >= 0 && ny < csize && grid[nx][ny] == 0){
q.push({nx, ny});
grid[nx][ny] = grid[x][y] + 1;
}
}
q.pop();
}
return -1;
}
};
```
### Where Will the Ball Fall
https://leetcode.com/problems/where-will-the-ball-fall/description/
```
class Solution {
public:
int len = 0;
int len2 = 0;
int recur(vector<vector<int>> &grid, int col, int row){
if(row == len2) return col;
if(col < 0 || col >= len) return -1;
if(grid[row][col] == 1 && col + 1 < len){
if(grid[row][col] == grid[row][col + 1])
return recur(grid, col + 1, row + 1);
}
else if(grid[row][col] == -1 && col - 1 >= 0){
if(grid[row][col] == grid[row][col - 1])
return recur(grid, col - 1, row + 1);
}
return -1;
}
vector<int> findBall(vector<vector<int>>& grid) {
len = grid[0].size();
len2 = grid.size();
cout << len << endl;
vector<int> v;
int i = 0;
for(i = 0; i < len; ++i){
v.push_back(recur(grid, i, 0));
}
return v;
}
};
```
### Spiral Matrix
https://leetcode.com/problems/spiral-matrix/
```
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* spiralOrder(int **matrix, int matrixSize, int* matrixColSize, int* returnSize){
//Use an array to calculate how many steps it should take
//Use another to specify the direction
/*
*dir : {0, 1, 0, -1, 0};
*num : length, width - 1
*until length < 0 && width < 0 break;
*/
if(!matrixSize)
return NULL;
int r = 0, c = -1;
int nr = matrixSize, nc = *matrixColSize;
*returnSize = matrixSize * *matrixColSize;
int *array = (int*)malloc(sizeof(int) *(*returnSize));
int j = 0;
int dir[5] = {0, 1, 0, -1, 0};
int d = 0;
int num[2] = {nc, nr - 1};
while(num[d % 2]){
for(int i = 0; i < num[d % 2]; ++i){
r += dir[d], c += dir[d + 1];
array[j++] = matrix[r][c];
}
--num[d % 2];
d = (d + 1) % 4;
}
return array;
}
```
## backtracking
### Maximum Compatibility Score Sum
https://leetcode.com/problems/maximum-compatibility-score-sum/discuss/1360805/Backtracking-with-STL-or-10-lines-of-code-or-C%2B%2B
```
int max;
void backtracking(int **students, int sidx, int studentsSize, int studentsColSize,
int **mentors, int *mentor_visited, int mentorsSize, int *res);
int maxCompatibilitySum(int** students, int studentsSize, int* studentsColSize, int** mentors, int mentorsSize, int* mentorsColSize){
int i;
int res = 0;max = 0;
int sidx=0;
int p;
int mentor_state[10];
for (i=0; i < mentorsSize; i++)
{
res = 0;
memset(mentor_state,0,sizeof(mentor_state));
mentor_state[i] = 1;
for (p=0; p < *studentsColSize; p++)
{
if (students[sidx][p] == mentors[i][p])
{
res++;
}
}
backtracking(students,sidx+1,studentsSize,*studentsColSize,
mentors,mentor_state,mentorsSize,&res);
}
return max;
}
void backtracking(int **students, int sidx, int studentsSize, int studentsColSize,
int **mentors, int *mentor_visited, int mentorsSize, int *res)
{
int i,p;
int mentor_v[10];
int res_local;
if (sidx >= studentsSize)
{
if (*res > max)
max = *res;
return;
}
for (i=0; i < mentorsSize; i++)
{
memcpy(mentor_v ,mentor_visited ,sizeof(int)*10);
res_local = *res;
if (mentor_v[i] == 1)
continue;
mentor_v[i] = 1;
for (p=0; p < studentsColSize; p++)
{
if (students[sidx][p] == mentors[i][p])
{
res_local++;
}
}
backtracking(students,sidx+1,studentsSize,studentsColSize,
mentors, mentor_v ,mentorsSize,&res_local);
}
return;
}
```
## number operations
### String to Integer (atoi)
https://leetcode.com/problems/string-to-integer-atoi/submissions/
```
int myAtoi(char * str){
long int i = 0, neg;
while (isspace(*str) || isalpha(*str)) // ignore leading spaces
if (isalpha(*str++)) // no leading alphabet
return 0;
str += (neg = *str == '-') || *str == '+'; // isneg() or ispos()?
while (isdigit(*str) && i < INT_MAX)
i = (i * 10) + *str++ - '0'; // build the int
i = neg ? -i : i; // fix the sign
return i < (int)i ? INT_MIN : i > (int)i ? INT_MAX : i; // fix if out-of-int-range
}
```
### reverse integer
https://leetcode.com/problems/reverse-integer/
```
int reverse(int x) {
int reversed = 0;
int flag = 0;
int mode = 0;
if (x > pow(2, 31) - 1 && x < -(pow(2, 31))) {
return 0;
}
while (x != 0) {
mode = x % 10;
if (reversed > (pow(2, 31) - 1) / 10 || reversed < -(pow(2, 31) / 10)) {
return 0;
}
reversed = reversed * 10 + mode;
x /= 10;
}
return reversed;
}
```
### happy number
https://leetcode.com/problems/happy-number/submissions/
```
bool isHappy(int n){
unsigned int add = 0;
//Use array to split it up
//If the array contain one number and that doesn't equal to one, return false;
while(1){
add = 0;
while(n > 0){
add += (n % 10) * (n % 10);
n /= 10;
}
n = add;
if(add == 1 || add == 7) return true;
if(n < 7 && n > 1) return false;
}
}
```
## Sum
### Combination Sum
https://leetcode.com/problems/combination-sum/description/
```
class Solution {
public:
void recur(vector<int>&can, vector<vector<int>>& v,int target, int ind, vector<int>&v2){
if(target == 0){
v.emplace_back(v2);
return;
}
while(ind < can.size() && target - can[ind] >= 0){
v2.emplace_back(can[ind]);
recur(can, v, target - can[ind], ind, v2);
++ind;
v2.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& can, int target) {
sort(can.begin(), can.end());
can.erase(unique(can.begin(), can.end()), can.end());
vector<vector<int>> v;
vector<int> v2;
recur(can, v, target, 0, v2);
return v;
}
};
```
### Combination Sum II
https://leetcode.com/problems/combination-sum-ii/description/
```
class Solution {
public:
void recur(vector<int>&can, int target, int ind, vector<vector<int>> &v, vector<int>&v2){
if(target == 0){
v.emplace_back(v2);
return;
}
for(int i = ind; i < can.size(); ++i){
if(i > ind && can[i] == can[i - 1]) continue;
if(can[i] > target) break;
v2.emplace_back(can[i]);
recur(can, target - can[i], i + 1, v, v2);
v2.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& can, int target) {
sort(can.begin(), can.end());
cout << endl;
vector<vector<int>> v;
vector<int> v2;
recur(can, target, 0, v, v2);
return v;
}
};
```
### Best Time To Sell
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/submissions/
If the profits haven't turn into negative
, I would keep the stock and also find the maximun during this process.
If it becomes negative, it will be better time to abandon this stock and choose this one.
```
#define max(i, j) ((i) > (j) ? (i): (j))
int maxProfit(int* prices, int size){
//If I lose money in the process, then discard the selection.
int max_cur = 0;
int max_global = 0;
for(int i = 1; i < size; ++i){
max_cur += prices[i] - prices[i - 1];
max_cur = max(0, max_cur);
max_global = max(max_global, max_cur);
}
return max_global;
}
```
### Two sum
https://leetcode.com/problems/two-sum/solutions/?envType=study-plan&id=data-structure-i&q=c&orderBy=most_relevant
```
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int sum = 0;
int *ptr = (int*) malloc (sizeof(int) * 2);
for(int i = 0; i < numsSize; ++i){
sum = target - nums[i];
ptr[0] = i;
for(int j = i + 1; j < numsSize; ++j){
if(nums[j] == sum){
ptr[1] = j;
return ptr;
}
}
}
return NULL;
}
```
### 3Sum Closest
https://leetcode.com/problems/3sum-closest/submissions/
```
void quicksort(int *nums, int l, int r, int numsSize){
if(l < 0 || r > numsSize || r - l < 1) return;
int pi = nums[l];
int i = l, j = r;
while(i < j){
while(i < j && nums[j] >= pi){ --j;};
while(i < j && nums[i] <= pi){ ++i;};
if(i < j){
nums[j] ^= nums[i] ^= nums[j] ^= nums[i];
}
}
nums[l] = nums[i];
nums[i] = pi;
quicksort(nums, l, i - 1, numsSize);
quicksort(nums, i + 1, r, numsSize);
}
int threeSumClosest(int* nums, int numsSize, int target){
if(numsSize < 3) return 0;
//We need three variables:
//first: keeps iterating
//second: if it is smaller than what we want, increase
//third: if it is larger, do the opposite thing.
int result = nums[0] + nums[1] + nums[2];
int sum = 0;
int dis = abs(result -target), dis2 = 0;
//dis: Distance to calculate the minimal
//sum: to calculate the summation
//result: to record the final result
int first = 0, second = 0, third = 0;
quicksort(nums, 0, numsSize - 1, numsSize);
for(int first = 0; first < numsSize - 1; ++first){
second = first + 1;
third = numsSize - 1;
while(second < third){
sum = nums[first] + nums[second] + nums[third];
dis2 = abs(sum - target);
if(dis2 < dis){
dis = dis2;
result = sum;
}
if(result == target) return result;
else if(sum > target) --third;
else if(sum < target) ++second;
}
}
return result;
}
```
### 3sum
https://leetcode.com/problems/3sum/submissions/
```
void quicksort(int left, int right, int n, int *nums){
if(left < 0 || right > n || right - left < 1) return;
int pi = nums[left];
int i = left, j = right;
while(i < j){
while(i < j && (nums[j] >= pi)){ --j;}
while(i < j && (nums[i] <= pi)){ ++i;}
if(i < j){
nums[i] ^= nums[j] ^= nums[i] ^= nums[j];
}
}
nums[left] = nums[i];
nums[i] = pi;
quicksort(left, i - 1, n, nums);
quicksort(i + 1, right, n, nums);
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
int i,j,k,sum,t,total=64;
quicksort(0, numsSize - 1, numsSize, nums);
*returnSize=0;
int **q=(int**)malloc(sizeof(int*)*total);
*returnColumnSizes=(int*)malloc(sizeof(int)*total);
for(int j = 0; j < numsSize; ++j) printf("%d ", nums[j]);
printf("\n");
for(i=0;i<numsSize-2;i++)
{
if(nums[i]>0||nums[i]+nums[i+1]+nums[i+2]>0)
break;
if(i>0&&nums[i]==nums[i-1])
continue;
j=i+1;
k=numsSize-1;
sum=-nums[i];//Since the first several items in that array must be negative
//, we change its sign. If that element is not negative, the following elements will not either.
printf("%d\n", sum);
while(j<k)
{
t=nums[j]+nums[k];
if(t<sum)
j++;
else if(t>sum)
k--;
else//t must equal sum or it will not form the result of zero.
{
(*returnColumnSizes)[*returnSize]=3;
q[*returnSize]=(int*) malloc(sizeof(int)*3);
q[*returnSize][0]=nums[i];
q[*returnSize][1]=nums[j++];
q[*returnSize][2]=nums[k--];
(*returnSize)++;
while(j<k&&nums[j]==nums[j-1])
j++;
while(j<k&&nums[k]==nums[k+1])
k--;
if((*returnSize)==total)
{
total*=2;
*returnColumnSizes=(int*)realloc(*returnColumnSizes,sizeof(int)*total);
q=(int**)realloc(q,sizeof(int*)*total);
}
}
}
}
return q;
}
```
### 4sum
```
int cmp(const void *a,const void *b){
return *(int *)a-*(int *)b;
}
int** fourSum(int* nums, int len, int target, int* returnSize, int** returnColumnSizes){
if(len<4){
*returnColumnSizes=NULL;
*returnSize=0;
return NULL;
}
qsort(nums,len,sizeof(int),cmp);
int cnt=0;
int base=8;
int **ans=malloc(sizeof(int *)*8);
int sum;
int l,r;
for(int i=0;i<len-3;i++){
if(i>0&&nums[i]==nums[i-1]){
continue;
}
if(nums[i]*4>target){
break;
}
for(int j=i+1;j<len-2;j++){
if(j>i+1&&nums[j]==nums[j-1]){
continue;
}
if(nums[j]*3+nums[i]>target||nums[len-1]*3+nums[i]<target){
break;
}
l=j+1;
r=len-1;
while(l<r){
sum=nums[i]+nums[j]+nums[l]+nums[r];
if(sum==target){
ans[cnt]=malloc(sizeof(int)*4);
ans[cnt][0]=nums[i];
ans[cnt][1]=nums[j];
ans[cnt][2]=nums[l];
ans[cnt][3]=nums[r];
cnt++;
if(cnt==base){
base*=2;
ans=realloc(ans,sizeof(int *)*base);
}
while(l<r&&nums[l]==nums[l+1]){
l++;
}
while(l<r&&nums[r]==nums[r-1]){
r--;
}
l++;
r--;
}
else if(sum>target){
r--;
}
else{
l++;
}
}
}
}
*returnColumnSizes=malloc(sizeof(int)*cnt);
for(int i=0;i<cnt;i++){
(*returnColumnSizes)[i]=4;
}
*returnSize=cnt;
return ans;
}
```
## string
### Multiply Strings
https://leetcode.com/problems/multiply-strings/description/
```
class Solution {
public:
string multiply(string num1, string num2) {
string sum(num1.size() + num2.size(), '0');
for(int i = num1.size() - 1; i >= 0; --i){
int carry = 0;
for(int j = num2.size() - 1; j >= 0; --j){
int tmp = (sum[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0') + carry;
sum[i + j + 1] = tmp % 10 + '0';
carry = tmp / 10;
}
sum[i] += carry;
}
size_t startpos = sum.find_first_not_of("0");
if (string::npos != startpos) {
return sum.substr(startpos);
}
return "0";
//900 3 9 1 = 8100 4
}
};
```
### Add Binary
https://leetcode.com/problems/add-binary/description/
```
class Solution {
public:
string addBinary(string a, string b) {
string s = "";
int i = a.size() - 1, j = b.size() - 1;
int sum = 0;
while(i >= 0 || j >= 0 || sum == 1){
sum += i >= 0 ? a[i--] - '0' : 0;
sum += j >= 0 ? b[j--] - '0' : 0;
s = char(sum % 2 + '0') + s;
//If we don't want to put string before the character,
//we can use s = ... + s.
sum /= 2;
}
return s;
}
};
```
### Backspace String
https://leetcode.com/problems/backspace-string-compare/solutions/?envType=study-plan&id=algorithm-ii&q=c&orderBy=most_relevant
```
void processString(char *S)
{
int start = 0;
for(int i = 0; S[i] != '\0'; i++)
{
if(S[i] != '#')
{
S[start++] = S[i];
}
else if(S[i] == '#' && start > 0)
start--;//printf("%s\n", S);
}
S[start] = '\0';
}
bool backspaceCompare(char* S, char* T) {
processString(S);
processString(T);
//printf("%s\n", S);
//printf("%s", T);
if(strcmp(S, T) == 0)
return true;
else
return false;
}
```
### Subarray Product Less Than K
https://leetcode.com/problems/subarray-product-less-than-k/description/?envType=study-plan&id=algorithm-ii
```
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k == 0) return 0;
int cnt = 0;
int pro = 1;
for (int i = 0, j = 0; j < nums.size(); j++) {
pro *= nums[j];
cout << pro << " ";
while (i <= j && pro >= k) {
pro /= nums[i++];
cout << pro << " ";
}
cnt += j - i + 1;
cout<< "cnt: "<< cnt << endl;
}
return cnt;
}
};
```
### Isomorphic Strings
https://leetcode.com/problems/isomorphic-strings/description/
```
bool isIsomorphic(char * s, char * t){
int arr[225] = {0};
int arr2[225] = {0};
for(int i = 0; i < strlen(s); ++i){
if(arr[s[i]] == 0 && arr2[t[i]] == 0){
arr[s[i]] = t[i];
arr2[t[i]] = s[i];
}
else if(arr[s[i]] != t[i] || arr2[t[i]] != s[i]){
return false;
}
}
return true;
}
```
### Contains Duplicate
https://leetcode.com/problems/contains-duplicate/description/
```
int compare(const void *a,const void *b) {
int *x = (int *) a;
int *y = (int *) b;
return *x - *y;
}
bool containsDuplicate(int* nums, int numsSize){
qsort (nums, numsSize, sizeof(int), compare);
for (int i=1; i<numsSize; i++) {
if (nums[i]==nums[i-1])
return true;
}
return false;
}
```
### Find the index of the First occurrence in a string
https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
```
int strStr(char * string1, char * string2)
{
int len1, len2 = 0;
len1 = strlen(string1);
len2 = strlen(string2);
int i =0,counter =0;
for(i=0;i<len1;i++)
{
if(counter==len2)
break;
if(string2[counter]==string1[i])
{
printf("%s\n", string1 + i);
counter++;
}
else
{
if(counter > 0)
{
i -= counter;
}
counter = 0;
}
//When bouncing back, we will alternatively determine if the next will
//have the same element.
//Since the loop will add i by one automatically, we can just subtract i by counter.
}
return counter < len2 ?-1:i-counter;
}
```
### Generate Parentheses
https://leetcode.com/problems/generate-parentheses/
```
void process(char** ans, int* idx, char* s, int size, int pos, int left, int right){
if(left == 0 && right == 0){
char* t = malloc((size + 1) * sizeof(char));
t[size] = '\0';
strcpy(t, s);
ans[*idx] = t;
*idx = *idx + 1;
return;
}
if(left == 0){
s[pos] = ')';
process(ans, idx, s, size, pos+1, left, right-1);
}
else if(left == right){
s[pos] = '(';
process(ans, idx, s, size, pos+1, left-1, right);
}
else{
s[pos] = ')';
process(ans, idx, s, size, pos+1, left, right-1);
s[pos] = '(';
process(ans, idx, s, size, pos+1, left-1, right);
}
}
char ** generateParenthesis(int n, int* returnSize){
char** ans = malloc(10000 * sizeof(char*));
int* idx = calloc(1, sizeof(int));
int size = 2 * n;
char* s = malloc((size + 1) * sizeof(char));
s[size] = '\0';
process(ans , idx, s, size, 0, n, n);
ans = realloc(ans, (*idx)* sizeof(char*));
* returnSize = *idx;
free(idx);
return ans;
}
```
### Zigzag conversion
https://leetcode.com/problems/zigzag-conversion/
```
/*We need to find the maxoffset or the period in which it repeat itself in "paypalishiring" question with row number 4 it is 6 how ?
explantion 1 : it takes (row-1) jump to get down that is from p to p then it takes same number of jumps to get to I so the equation to get max offset (period) = (row-1)*2
so when in each row when you jump max offset it reaches to another row element but in rows
except first and last we miss one element to accommodate this element we need to jump back and this jump back depend on the row
jump back = (j + maxoffset ) - (2 * rownumber)
*/
char * convert(char * s, int numRows){
int len=strlen(s);
if(numRows == 1 || numRows > len)
return s;
char * result = malloc(len+1);
result[len] = 0;
int idx = 0;
int maxOffset = (numRows -1)*2;
for(int i = 0 ; i < numRows; i++) {
for(int j = i ; j < len ;){
result[idx++]=s[j];
j +=maxOffset;
if( i != 0 && i != (numRows - 1) && (j -(2*i)) < len) {
//Because sometimes j + maxOffset will exceed the length,
// this condition can't be counted.
result[idx++] =s[j-(2*i)];
}
}
}
return result;
}
```
### Letter Combinations
https://leetcode.com/problems/letter-combinations-of-a-phone-number/submissions/
```
char** letterCombinations(char* digits, int* returnSize) {
int len = strlen(digits);
if ( !digits || !len ) {
*returnSize = 0;
return NULL;
}
char* array[9] = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
int size = 1, cnt = 0, cur_size = 0, rest_size = 0;
for (int i = 0; i < len; i++) {
size *= strlen(array[digits[i] - '1']);
printf("%d\n", size);
}
*returnSize = rest_size = size;
char** ret = (char**) malloc(sizeof(char*) * (*returnSize));
for (int i = 0; i < size; i++) {
ret[i] = (char*) malloc (sizeof(char) * (len+1));
}
for (int i = 0; i < len+1; i++) {
if (i < len) {
cur_size = strlen(array[digits[i] - '1']);
rest_size /= cur_size;
printf("rest_size %d cur_size %d\n", rest_size, cur_size);
}
for (int j = 0; j < size; j++) {
if (i == len) {
ret[j][cnt] = '\0';
} else {
// every character need rest_size times -> j/rest_size%cur_size
// Current size indicates how many numbers there are in this string
// Since rest_size will be the sum of all strings length, divde it by the rest size.
printf("%d : %d \\", j, j/rest_size % cur_size);
ret[j][cnt] = array[digits[i] - '1'][j/rest_size%cur_size];
}
}
printf("\n");
cnt++;
}
return ret;
}
```
### Longest palindromic substring
https://leetcode.com/problems/longest-palindromic-substring/submissions/
```
char * longestPalindrome(char * s){
//Start、end
//Use p to iterate the string
//If finding that
int maxLen = 1;
char *sub = s;
char* p = s;
while(*p){
char* end = p;
char* start = p;
while(*(end + 1) && *(end + 1) == *end){
end++;
}
p = end + 1;
while(*(end + 1) && (start > s) && *(end + 1) == *(start - 1)){
++end;
--start;
}
if(end - start + 1 > maxLen){
maxLen = end - start + 1;
sub = start;
}
}
char *rst = (char*)calloc(maxLen + 1, sizeof(char));
strncpy(rst, sub, maxLen);
return rst;
}
```
### isSubsequence
https://leetcode.com/problems/is-subsequence/discuss/2473010/Very-Easy-oror-100-oror-Fully-Explained-oror-Java-C%2B%2B-Python-JS-C-Python3-(Two-Pointers-Approach)
```
bool isSubsequence(char * s, char * t){
int count = 0;
char *p = s;
while(*t != '\0'){
if(*p == *t){
++count;
++p;
}
++t;
}
if(count == strlen(s)) return true;
return false;
}
```
### minWindow
https://leetcode.com/problems/minimum-window-substring/submissions/
```
char* minWindow(char* s, char* t) {
int tChars['z' + 1] = {0}, count = 0, minLen = INT_MAX;
char* p = s, *q = s;
while (t[count]) tChars[t[count++]]++; //ABCB -> tChars = {1 2 1}: the amounts of chars we need; count = 4 here: the total amount
while (*q) {
if (-- tChars[*q++] >= 0) count--;
while (tChars[*p] < 0) tChars[*p++]++;
if (!count && q - p < minLen) minLen = q - (s = p);
}
return !(*(s + (minLen == INT_MAX ? 0 : minLen)) = 0) ? s : s;
}
```
## Linked list
### Remove Duplicates from Sorted List
https://leetcode.com/problems/remove-duplicates-from-sorted-list/submissions/
```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head){
struct ListNode *cur = head;
while(cur && cur->next){
if(cur->val == cur->next->val){
cur->next = cur->next->next;
}
else{
cur = cur->next;
}
}
return head;
}
```
### Remove Duplicates from Sorted List II
https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/
Video: https://www.youtube.com/watch?v=R6-PnHODewY
```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head){
if(head == NULL || head->next == NULL) return head;
struct ListNode *dummy = (struct ListNode*) malloc (sizeof(struct ListNode));
dummy->next = head;
struct ListNode* prev = dummy;
while(head){
if(head->next && head->val == head->next->val){
while(head->next && head->val == head->next->val){
head = head->next;
}
prev->next = head->next;
// printf("%d\n", dummy->next->val);
}
else{
prev = head;
}
head = head->next;
}
return dummy->next;
}
```
### Reverse Nodes in k-Group
https://leetcode.com/problems/reverse-nodes-in-k-group/submissions/
video source : https://www.youtube.com/watch?v=BfQeP6XEXEc
```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseKGroup(struct ListNode* head, int k){
if(!head || !head->next || k == 1) return head;
int n = 0;
struct ListNode* cur = head;
while(cur){
cur = cur->next;
++n;
}
/*
* We first count the total number;
* For each interation, we reverse
* every element
* After reversing, we will find that the cur will be the next section
* We will utilize t2 to be the end of the section, which is required to connection two sections
*/
cur = head;
struct ListNode* pre = NULL, *next = NULL, *newHead = NULL;
struct ListNode *t1 = NULL, *t2 = head;
while(n >= k){
for(int i = 0; i < k; ++i){
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
if(t1) t1->next = pre;
if(!newHead) newHead = pre;
t2->next = cur;
t1 = t2;
t2 = cur;
pre = NULL;
n -= k;
}
return newHead;
}
```
### merge k sorted lists
https://leetcode.com/problems/merge-k-sorted-lists/description/
```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* travel(struct ListNode* l1, struct ListNode* l2){
if(l1 == NULL && l2 == NULL) return NULL;
if(l1 == NULL) return l2;
if(l2 == NULL) return l1;
struct ListNode* main = (struct ListNode*) malloc (sizeof(struct ListNode));
main->val = -1;
main->next = NULL;
struct ListNode* result = main;
struct ListNode* tr1 = l1;
struct ListNode* tr2 = l2;
while(1){
if(tr1->val <= tr2->val){
result->next = tr1;
result = result->next;
tr1 = tr1->next;
if(tr1 == NULL){
while(tr2 != NULL){
result->next = tr2;
tr2 = tr2->next;
result = result->next;
}
break;
}
}
else{
result->next = tr2;
result = result->next;
tr2 = tr2->next;
if(tr2 == NULL){
while(tr1 != NULL){
result->next = tr1;
tr1 = tr1->next;
result = result->next;
}
break;
}
}
}
return main->next;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
if(listsSize == 0) return NULL;
if(listsSize == 1) return lists[0];
struct ListNode* result = travel(lists[0], lists[1]);
for(int i = 2; i < listsSize; ++i){
result = travel(result, lists[i]);
}
return result;
}
```
### swap Nodes in Pairs
https://leetcode.com/problems/swap-nodes-in-pairs/description/
```
struct ListNode* swapPairs(struct ListNode* head) {
struct ListNode* first = head;
struct ListNode* prev = NULL;
int firstTime = 1;
while (first != NULL && first->next != NULL)
{
struct ListNode* second = first->next;
struct ListNode* third = second->next;
if (prev != NULL) prev->next = second;
second->next = first;
first->next = third;
if (firstTime == 1)
head = second;
firstTime = 0;
prev = first;
first = first->next;
}
return head;
}
```
### Odd and even linked list
https://leetcode.com/problems/odd-even-linked-list/submissions/
If [1, 2] happens, ptr2->next will be NULL.
```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* oddEvenList(struct ListNode* head){
if(head){
struct ListNode* ptr1 = head;
struct ListNode* ptr2 = head->next, *ptr2_head = head->next;
while(ptr2 && ptr2->next){//Make sure that ptr2 exists
ptr1->next = ptr1->next->next;
ptr1 = ptr1->next;
ptr2->next = ptr2->next->next;
ptr2 = ptr2->next;
}
ptr1->next = ptr2_head;
}
return head;
}
```
### Construct Binary Tree from Preorder and Inorder Traversal
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/
```
struct TreeNode* buildTree_r(int* preorder, int* inorder, int preStart, int preEnd,
int inStart, int inEnd) {
if(preStart > preEnd || inStart > inEnd)
return NULL;
struct TreeNode* root = malloc(sizeof(struct TreeNode));
root->val = preorder[preStart];
int in_rootidx; // Find root in inorder
for(int i = inStart; i <= inEnd; i++) {
if(inorder[i] == root->val) {
in_rootidx = i;
break;
}
}
root->left = buildTree_r(preorder, inorder, preStart + 1, preEnd, inStart,
in_rootidx - 1);
root->right = buildTree_r(preorder, inorder, preStart+in_rootidx-inStart + 1,
preEnd, in_rootidx + 1, inEnd);
// Since we have to skip the left node, we make use of inorder to know how many nodes are in the left.
//in_rootidx - instart = how many nodes in the left subtree.
return root;
}
struct TreeNode* buildTree(int* preorder, int preorderSize,
int* inorder, int inorderSize) {
if(inorder == NULL || preorder == NULL)
return NULL;
return buildTree_r(preorder, inorder, 0, preorderSize - 1, 0, inorderSize - 1);
}
```
### Split linked list in parts
https://leetcode.com/problems/split-linked-list-in-parts/
```
struct ListNode** splitListToParts(struct ListNode* head, int k, int* returnSize){
struct ListNode ** result = (struct ListNode **)malloc(k*sizeof(struct ListNode *));
struct ListNode * temp = head;
int count = 0;
while(temp)
{
count++;
temp = temp->next;
}
int n = count / k;
int c = count % k;
temp = head;
for(int i=0; i<k; i++)
{
int num = n + (c>0?1:0);
result[i] = (struct ListNode *)calloc(1, sizeof(struct ListNode));
if(num == 0) result[i] = NULL;
struct ListNode * p = result[i];
for(int j=0; j<num; j++)
{
p->val = temp->val;
temp = temp->next;
if(j < num-1) p = p->next = (struct ListNode *)calloc(1, sizeof(struct ListNode));
}
c--;//The modulus. If c > 0, then we have to add extra number in the first linked list
}
*returnSize = k;
return result;
}
```
### Rotate the linked list
https://leetcode.com/problems/rotate-list/submissions/
```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* rotateRight(struct ListNode* head, int k){
if(head == NULL || head->next == NULL) return head;
struct ListNode* node = head;
int c = 0;
while(node){
node = node->next;
++c;
}
node = head;
k %= c;
struct ListNode* prev = NULL;
while(k--){
while(node && node->next){
prev = node;
node = node->next;
}
node->next = head;//Because the next pointer node have to be connected with the head
prev->next = NULL;
head = node;//This allow me to let the next head be connected with the current node.
node = head;//The beginning in the next loop
}
return head;
}
```
## array
### note
Even though I assume that the subtraction of two pointer can't really be a decimal number, it eventually is.
E.g.
```
int arr[3] = {1, 2, 3};
int *ptr = arr + 1;
printf("%d", ptr - arr);//The result is 1
```
E.g.2
### Longest Increasing Subsequence
https://leetcode.com/problems/longest-increasing-subsequence/description/?envType=study-plan&id=algorithm-ii
```
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(int i=0; i<nums.size(); i++) {
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
// if(it != res.end()) cout << "it: " << *it << endl;
if(it==res.end()) res.push_back(nums[i]);
else *it = nums[i];
// for(auto j : res) cout << j << " ";
//cout << endl;
}
return res.size();
}
};
```
### Remove Duplicates From Sorted Array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
```
int removeDuplicates(int* nums, int numsSize){
if (numsSize == 0) { return 0;}
int count = 1; // counts the number of unique elements
int j = 0; // counts the number of duplicates between unique elements
for (int i=0; i< numsSize-1; i++) {
if (nums[i] != nums[i+1]) {
count++;
nums[i+1-j] = nums[i+1];
//We directly replace the elements before i + 1 by j
//Since we don't have to care about these elements behind k
//,fWe move these element forward.
}
else j++;
}
return count;
}
```
### Permutations
https://leetcode.com/problems/permutations/description/
```
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
if(nums.size() <= 0){
return {nums};
}
vector<vector<int>> result;
for(int i = 0; i < nums.size(); ++i){
vector<int> v(nums.begin(), nums.end());
v.erase(v.begin() + i);
auto res = permute(v);
for(int j = 0; j < res.size(); ++j){
vector<int> _v = res[j];
_v.insert(_v.begin(), nums[i]);
result.emplace_back(_v);
}
}
return result;
}
};
```
### Rotate Array
https://leetcode.com/problems/rotate-array/submissions/
Solution 1.
```
void rotate(int* nums, int numsSize, int k)
{
size_t tmp;
size_t i;
for(i = 0; i < numsSize / 2; i++)
{
// reverse array
tmp = nums[i];
nums[i] = nums[numsSize - i - 1];
nums[numsSize - i - 1] = tmp;
}
//We reverse the whole array.
//If we reverse the rest of the array second time
//it would be back to normal.
k %= numsSize;
//The first part of array can be
//reverse so that it will be in ascending order.
for(i = 0; i < k / 2; i++)
{
// reverse first k elements
tmp = nums[i];
nums[i] = nums[k - i - 1];
nums[k - i - 1] = tmp;
}
for(i = k; i < (numsSize - k) / 2 + k ; i++)
{
// reverse last (numsSize - k) elements
tmp = nums[i];
nums[i] = nums[numsSize - i + k - 1];
nums[numsSize - i + k - 1] = tmp;
}
}
```
Solution 2.
```
void rotate(int* nums, int numsSize, int k){
//We extract the final element.
//Put every items backwards
int* arr = (int*) malloc (sizeof(int) * numsSize);
k %= numsSize;
int i = numsSize - k;
int j = 0;
for(; i < numsSize; ++i){
arr[j++] = nums[i];
}
for(i = 0; i < numsSize - k; ++i){
arr[j++] = nums[i];
}
for(int i = 0; i < numsSize; ++i) nums[i] = arr[i];
}
```
### Squares of a sorted array
https://leetcode.com/problems/squares-of-a-sorted-array/description/
Solution 1 (optimal)
```
int* sortedSquares(int* A, int ASize, int* returnSize){
int* arr = malloc(sizeof(int)*ASize);
*returnSize = ASize;
int end = ASize-1, start = 0, ptr = ASize-1;
while ((start <= end) && (ptr>=0))
{
if (pow(A[end],2) >= pow(A[start],2))
{
arr[ptr] = pow(A[end--],2);
}
else
{
arr[ptr] = pow(A[start++],2);
}
ptr--;
//The both sides will contain the maximum,
//we gradually compare these elements one
//by one and put it into another array.
}
return arr;
}
```
Solution 2
```
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int compare(const void* x_void, const void* y_void){
int x = *(int*) x_void;
int y = *(int*) y_void;
return x - y;
}
int* sortedSquares(int* nums, int numsSize, int* returnSize){
*returnSize = numsSize;
for(int i = 0; i < numsSize; ++i){
nums[i] = nums[i] * nums[i];
}
qsort(nums, numsSize, sizeof(int), compare);
return nums;
}
```
### Merge two sorted array
https://leetcode.com/problems/merge-sorted-array/description/
Solution 1 (optimal)
```
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int i, i1, i2;
i1 = m - 1;
i2 = n - 1;
i = nums1Size - 1;
while (i1 >= 0 && i2 >= 0) {
if (nums1[i1] > nums2[i2]) {
nums1[i--] = nums1[i1--];
} else {
nums1[i--] = nums2[i2--];
}
}
while (i2 >= 0) {
nums1[i--] = nums2[i2--];
}
}
```
Solution 2
```
int compare(const void* x_void, const void* y_void){
int x = *(int*) x_void;
int y = *(int*) y_void;
return x - y;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int i = m;
int j = 0;
if(nums2 == NULL || nums1 == NULL) return;
if((nums1Size == 1 && nums1[0] != 0)) return;
for(; j < n; ++i, ++j){
nums1[i] = nums2[j];
}
qsort(nums1, nums1Size, sizeof(int), compare);
}
```
### First Bad Version
https://leetcode.com/problems/first-bad-version/description/
```
int firstBadVersion(int n) {
int mid,left = 1,right = n,ans = 0;
while(left <= right){
//the reason why the left
//could equal to the right is that if the array only contain one element
//,it will not be kicked out from the loop
mid=left+(right-left)/2;
printf("%d\n", mid);
if(isBadVersion(mid)){
//After finding the bad version
//We choose to keep searching
//And target the aim to the left
//By doing this, we can spot
//The element which is the closest to the left.
ans=mid;
right=mid-1;
}
else// if(!isBadVersion(mid))
left=mid+1;
}
return ans;
}
```
### Find the first and last position of element in sorted array.
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Solution 1.(more optimal)
```
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
int l=0, r=numsSize-1, mid = r/2;
*returnSize = 2;
int* res = malloc(sizeof(int)*2);
res[0] = -1; res[1] = -1;
while (l <= r)
{
mid = l+(r-l)/2;
if (target == nums[mid]) // might be in both sides
{
printf("target==mid %d\n", mid);
int mid2 = mid;
while (l < mid)
{
int l_mid = (mid+l)/2;
if (nums[l_mid] < target)
l = l_mid+1;
//if we have to find the elements in the right-side,
//we move left towards the middle.
else
mid = l_mid;
//if finding that nums[l_mid] > target or = target,
//we choose l_mid as mid so that the next step will
//allow the index to move left.
printf("mid: %d\n", mid);
}
while (mid2 < r)
{
int r_mid = (mid2+r+1)/2;
//For r_mid, the addition of one is essential
//because the program tends to remove the number behind
//the decimal point. As a result, every number needed to
//move to the right by forming the number containing
//some digits behind the decimal point that will be
//eliminated.
//But the left-hind side will benefit from this.
if (nums[r_mid] > target)
r = r_mid-1;
else
mid2 = r_mid;
//Because we want to find the number exactly located
//on the boundary instead of being the right side of
//that number, we use mid2 = r_mid instead of
//mid2 = r_mid - 1
}
res[0] = l; res[1] = r;
printf("mid2: %d\n", mid2);
return res;
}
else if (target < nums[mid]) // not in right side
r = mid-1;
else if (target > nums[mid]) // not in left side
l = mid+1;
}
return res;
}
```
Solution 2.
```
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
int left = 0, right = 0;
bool cfm = true;
*returnSize = 2;
int *arr = (int*) malloc (sizeof(int) * 2);
for(int i = 0; i < numsSize; ++i){
if(cfm && nums[i] == target){
left = i;
right = left;
cfm = false;
}
else if(nums[i] == target){
++right;
}
}
if(cfm){
arr[0] = arr[1] = -1;
}else{
arr[0] = left;
arr[1] = right;
}
return arr;
}
```
Solution 3.
Using two binary search
```
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
int* arr = (int*) malloc (sizeof(int) * 2);
*returnSize = 2;
int left = 0, right = numsSize - 1;
arr[0] = arr[1] = -1;
while(right >= left){
int mid = (left + right) / 2;
if(nums[mid] == target){
printf("mid: %d\n", mid);
int l = left, r = mid;
while(r >= l){
int mid2 = (l + r) / 2;
if(nums[mid2] == target){
r = mid2 - 1;
arr[0] = mid2;
}
else
l = mid2 + 1;
}
l = mid; r = right;
while(r >= l){
int mid2 = (l + r) / 2;
if(nums[mid2] == target){
l = mid2 + 1;
arr[1] = mid2;
}
else
r = mid2 - 1;
}
return arr;
}
else if(nums[mid] > target){
right = mid - 1;
}
else
left = mid + 1;
}
return arr;
}
```
### Find pivot index
https://leetcode.com/problems/find-pivot-index/?envType=study-plan&id=level-1
```
int pivotIndex(int* nums, int numsSize){
int * sum =(int *)malloc((numsSize+2)*sizeof(int));
sum[0] = 0;
for(int i=0; i<numsSize; i++)
sum[i+1] = sum[i] + nums[i];
sum[numsSize+1] = sum[numsSize];
//for(int i = 0; i < numsSize + 2; ++i) printf("%d ", sum[i]);
for(int i=1; i<numsSize+1; i++)
if(sum[numsSize+1] - sum[i] == sum[i-1])//the total summation
//subtracted by the current will be the remaining summation after the piviot.
//So if the remaining summation is equal to the previous summation,
//that is the piviot.
return i-1;
free(sum);
return -1;
}
```
### Valid Sudoku
https://leetcode.com/problems/valid-sudoku/submissions/
```
bool isValidSudoku(char** board, int boardSize, int* boardColSize){
//To get through a whole row and column, then estimate if there is a number exceed 1
//The first position can be : j = 0 3 6, z = 0 3 6
int hashset[10] = {0};
int r = 0, c = 0;
//col
int _r = 0;
int max_r = 0;
//row
int _c = 0;//starting point
int max_c = 0;//ending point
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
if(isdigit(board[j][i])){
if(hashset[board[j][i] - '0'] == 1){
//printf("%d, %d: ", j, i);
//printf("%c\n", board[j][i]);
return false;
}
else{
++hashset[board[j][i] - '0'];
}
}
}
memset(hashset, 0, sizeof(hashset));
for(int j = 0; j < 9; ++j){
if(isdigit(board[i][j])){
if(hashset[board[i][j] - '0'] == 1) return false;
else{
++hashset[board[i][j] - '0'];
}
}
}
memset(hashset, 0, sizeof(hashset));
}
memset(hashset, 0, sizeof(hashset));
for(int i = 0; i < 9; ++i){
if(!(i % 3)){
_c = 0;
if(i != 0)
_r += 3;
}
else _c += 3;
max_c = _c + 3;
max_r = _r + 3;
for(r = _r; r < max_r; ++r){
for(c = _c; c < max_c; ++c){
// the vertical test:
if(isdigit(board[r][c])){
if(hashset[board[r][c] - '0'] == 1){
//printf("WOW\n");
return false;}
else{
++hashset[board[r][c] - '0'];
}
}
}
}
/*
[[".",".",".",".","5",".",".","1","."],
[".","4",".","3",".",".",".",".","."],
[".",".",".",".",".","3",".",".","1"],
["8",".",".",".",".",".",".","2","."],
[".",".","2",".","7",".",".",".","."],
[".","1","5",".",".",".",".",".","."],
[".",".",".",".",".","2",".",".","."],
[".","2",".","9",".",".",".",".","."],
[".",".","4",".",".",".",".",".","."]]
*/
memset(hashset, 0, sizeof(hashset));
}
//Starting point must be set: r and c.
//Ending point : r + 3 and c + 3.
/*the outside loop
* 0 1 2 the first column will be the multiplication of 3
* 3 4 5 if it is the multiplication of 3, then the r has to be reset
* 6 7 8
*/
/*when locating the specific number, we have to use another for loop to iterate
*_r and _c will be seperated.
* first operate the row and then operate the column
*/
return true;
}
```
### Next permutation
https://leetcode.com/problems/next-permutation/submissions/857110223/
```
void swap(int* n, int i,int j){
int tmp = n[i];
n[i] = n[j];
n[j] = tmp;
}
void nextPermutation(int* nums, int numsSize){
int i = numsSize - 2;
for(; i >= 0 && nums[i] >= nums[i + 1]; --i);
if(i >= 0){
int j = i + 1;
for(; j < numsSize && nums[i] < nums[j]; ++j);
swap(nums, i, j - 1);
//Because the overall next permutation has to be greater, we have to find the first number greater than nums[i] to increase it.
}
++i;
int k = numsSize - 1;
for(; k > i; ++i, --k){
swap(nums, i, k);
}
}
```
### Remove Element
https://leetcode.com/problems/remove-element/submissions/857082538/
```
int removeElement(int* nums, int numsSize, int val){
int size = numsSize;
bool cfm = true;
for(int i = 0; i < numsSize;){
cfm = true;
if(nums[i] == val){
cfm = false;
if(i == size - 1){
--size;
break;
}
for(int j = i; j + 1 < size; ++j){
nums[j] = nums[j + 1];
}
--size;
}
if(cfm == true) ++i;
}
return size;
}
```
### Container with most water
https://leetcode.com/problems/container-with-most-water/submissions/
```
int maxArea(int* height, int n){
int *i = height, *j = i + n - 1;
int water = 0, h = 0, w = 0;
while(i < j){
h = *i < *j ? *i : *j;
w = h * (j - i);
printf("j - i: %d\n", j - i);
if(w > water) water = w;
while(i < j && *i <= h) ++i;
while(i < j && *j <= h) --j;
}
return water;
}
```
### merge sort
https://leetcode.com/problems/sort-colors/submissions/
```
void merge(int *arr, int l, int m, int r)
{
//View the array as a temperary array
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int *L = (int*)calloc(n1, sizeof(int));
int *R = (int*)calloc(n2, sizeof(int));
//We use the two parts of array to split the array.
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
//When it comes to the next step. Since the L and R are both sorted, we can just simply compare
//two element in that separate arrays.
}
//The remaining will be the larger one.
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
free(L);
free(R);
}
void mergeSort(int *arr,int l, int r)
{
if (l < r)
{
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void sortColors(int* nums, int n){
mergeSort(nums, 0, n - 1);
}
```
Sign in with Wallet
Connect another wallet