directory
Problem 1: Sum of two numbers 2- enter an ordered array
Question 2: Wine exchange
Problem 3: The peak index of the mountain array
Problem 4: Lucky numbers in matrices
Question 5: The average wage after removing the minimum wage and the maximum wage
Problem 6: the smallest sequence in non-increasing order
Question 7: The number of unique occurrences
Problem 8: Reverse the word 3 in the string
Problem 9: Playing with chips
Question 10: all letters in case
LeetCode brushes the questions regularly, with 10 questions in each period. Comrades with heavy business can look at the ideas I share, which are not the most efficient solutions, but for mutual improvement.
Problem 1: Sum of two numbers 2- enter an ordered array
The requirements are as follows:
Answer (C language) :
/** * Note: The returned array must be malloced, assume caller calls free(). */
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
int* ret = (int*)malloc(sizeof(int) * 2);
*returnSize = 2;
for (int i = 0; i < numbersSize; ++i) {
int low = i + 1, high = numbersSize - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i]) {
ret[0] = i + 1, ret[1] = mid + 1;
return ret;
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
ret[0] = - 1, ret[1] = - 1;
return ret;
}
Copy the codeThe operating efficiency is as follows:
Question 2: Wine exchange
The requirements are as follows:
Answer (C language) :
int numWaterBottles(int numBottles, int numExchange){
int temp_numBottles = numBottles;
int temp_num = 0;
int temp_data = numBottles;
while(temp_numBottles >= numExchange){
temp_num = temp_numBottles/numExchange;
temp_data += temp_num;
temp_numBottles %= numExchange;
temp_numBottles += temp_num;
}
return temp_data;
}
Copy the codeThe operating efficiency is as follows:
Problem 3: The peak index of the mountain array
The requirements are as follows:
Answer (C language) :
int peakIndexInMountainArray(int* A, int ASize){
int i=0;
while(A[i]<A[i+1]) i++;
return i;
}
Copy the codeThe operating efficiency is as follows:
Problem 4: Lucky numbers in matrices
The requirements are as follows:
Answer:
The size of the array is either the number of rows or the number of columns.
First pass: saves the minimum value of each row to the array;
Second pass: saves the maximum value of each column into the array;
Third pass: Adds the array of results to be returned if the criteria are met.
Answer (C language) :
int* luckyNumbers (int** matrix, int matrixSize, int* matrixColSize, int* returnSize){
int i, j;
int *ret = (int*)malloc(sizeof(int) * matrixSize);
int minRow[matrixSize], maxCol[*matrixColSize];
for (i = 0; i < matrixSize; i++) {
minRow[i] = INT_MAX;
for (j = 0; j < *matrixColSize; j++) {
if(matrix[i][j] <= minRow[i]) { minRow[i] = matrix[i][j]; }}}for (i = 0; i < *matrixColSize; i++) {
maxCol[i] = INT_MIN;
for (j = 0; j < matrixSize; j++) {
if (matrix[j][i] >= maxCol[i]) {
maxCol[i] = matrix[j][i];
}
}
}
*returnSize = 0;
for (i = 0; i < matrixSize; i++) {
for (j = 0; j < *matrixColSize; j++) {
if(matrix[i][j] == minRow[i] && matrix[i][j] == maxCol[j]) { ret[*returnSize] = matrix[i][j]; (*returnSize)++; }}}return ret;
}
Copy the codeThe operating efficiency is as follows:
Question 5: The average wage after removing the minimum wage and the maximum wage
The requirements are as follows:
Answer:
To find the maximum Max, minimum min and total sum, average = (sum-max-min)/(salarysize-2), there is no difficulty, just need to pay attention to the data type.
Answer (C language) :
double average(int* salary, int salarySize){
int max = salary[0];
int min = salary[0];
int sum = 0;
double average = 0;
if(salarySize <= 2)
return 0;
for(int i = 0; i < salarySize; i++){
if(max < salary[i])
max = salary[i];
else if(min > salary[i])
min = salary[i];
sum += salary[i];
}
average = (double)(sum - max - min) / (double)(salarySize - 2);
return average;
}
Copy the codeThe operating efficiency is as follows:
Problem 6: the smallest sequence in non-increasing order
The requirements are as follows:
Answer (C language) :
/** * Note: The returned array must be malloced, assume caller calls free(). */
int cmp(int *a,int *b)
{
return *b - *a;
}
int* minSubsequence(int* nums, int numsSize, int* returnSize)
{
qsort(nums,numsSize,sizeof(int),cmp);
int left = 0,right = numsSize- 1,leftsum = nums[left],rightsum = nums[right];
while(left < right)
{
if(leftsum > rightsum)
{
right--;
rightsum += nums[right];
}
else
{
left++;
leftsum +=nums[left];
}
}
*returnSize = left+1;
return nums;
}
Copy the codeThe operating efficiency is as follows:
Question 7: The number of unique occurrences
The requirements are as follows:
Answer (C language) :
bool uniqueOccurrences(int* arr, int arrSize){
int result[2001];
int result_nums[2001];
memset(result, 0.2001 * sizeof(int));
memset(result_nums, 0.2001 * sizeof(int));
for(int i=0; i < arrSize; ++i){if(arr[i] < 0){
result[arr[i]*(- 1) +1000] + =1;
}
else{
result[arr[i]] += 1; }}for(int j=0; j <2001; ++j){if(result[j]>0){
result_nums[result[j]] += 1;
}
if(result_nums[result[j]]>1) {return false; }}return true;
}
Copy the codeThe operating efficiency is as follows:
Problem 8: Reverse the word 3 in the string
The requirements are as follows:
Answer:
1. Use I and j to start and end words.
2. Reverse s[I] to S [j] with revers;
3. Repeat 1 and 2 until the string is iterated.
Answer (C language) :
void revers(char *s,int i,int j){
char temp;
while(i<j){
temp=s[i];
s[i]=s[j];
s[j]=temp;
i++;j--;
}
}
char * reverseWords(char * s){
int i=0,j=0;int slen=strlen(s);
for(int n=0; n<slen; n++){if(s[n]! =' '){ i=n; n++;while(s[n]! ='\ 0'&&s[n]! =' '){
n++;
}
j=n- 1;
revers(s,i,j); }}return s;
}
Copy the codeThe operating efficiency is as follows:
Problem 9: Playing with chips
The requirements are as follows:
Answer:
1. First of all, it is found that the cost of transferring even positions to any even positions is 0, and the cost of transferring odd positions to any odd positions is also 0;
2. Secondly, we simplify the position of the chips by concentrating all the even numbers into 2X position and all the odd numbers into 2X+1 (or 2X-1) position;
To minimize the cost, is to move the smallest number of sets.
4, comprehensive analysis, found that in fact is to count the number of odd and even, take the smaller.
Answer (C language) :
int minCostToMoveChips(int* chips, int chipsSize){
int odd =0, even = 0;
for(int i = 0; i < chipsSize; i++){
if(chips[i]%2)
odd++;
else
even++;
}
return (odd <= even)? odd: even;
}
Copy the codeThe operating efficiency is as follows:
Question 10: all letters in case
The requirements are as follows:
Answer (C language) :
/** * Note: The returned array must be malloced, assume caller calls free(). */
char ** letterCasePermutation(char * S, int* returnSize){
int len = strlen(S), size = 1;
char **res = (char* *)malloc(sizeof(char*) *pow(2, len));
*res = (char*)calloc(len + 1.sizeof(char));
strcpy(*res, S);
for (int i = 0; i < len; i++){
if (S[i]>'9') {int k = size;
for (int j = 0; j < k; j++){
res[k + j] = (char*)calloc(len + 1.sizeof(char));
strcpy(res[k + j], res[j]);
res[k + j][i] = S[i] < 'a' ? S[i] + 32 : S[i] - 32;
size++;
}
}
}
*returnSize = size;
return res;
}
Copy the codeThe operating efficiency is as follows:
