当前位置:网站首页>Leecode-c language implementation -15 Sum of three ----- ideas to be improved
Leecode-c language implementation -15 Sum of three ----- ideas to be improved
2022-07-06 07:25:00 【Sunshine clover lxgzxj】
One 、 subject
Two 、 Their thinking
(1) Ideas need to be improved
For example, the array is :{
-1,0,1,0,3}
(1) Construct a -10^5 To 10^5 Array of , Put the data one by one , Here for the convenience of writing -5 To 5.
(2) Define multiple variables to record the maximum and minimum subscripts and indexes when placing .
The number :-5 -4 -3 -2 -1 0 1 2 3 4 5
frequency : 0 0 0 0 1 1 1 0 1 0 0
Indexes : 0 1 2 3 4 5 6 7 8 9 10
min max
temp
The length of the array :11
MinIndex = 4
MaxIndex = 6
TempIndex = 4
MaxValue = 3
MinValue = -1
(3) If the minimum value is greater than zero , It means that no addition in the array can be 0, Returns a null value .
(4) If the maximum value is less than zero , It means that no addition in the array can be 0, Returns a null value .
(5) If twice the minimum plus the maximum is still greater than 0, It shows that this maximum value is definitely not in the final answer .
-1 * 2 + 3 > 0
MaxIndex Minus one
MaxIndex = 6
(5) If twice the maximum plus the minimum is still less than 0, It shows that this minimum value is definitely not in the final answer .
(6) Judgment logic :MaxValue + MinValue + TempValue = 0, recorded TempIndex by 5 .
-1 + 1 + 0 = 0
(7) To determine TempIndex=5 The corresponding value is 1, Explain that there is only one in the array 0, And it does not coincide with the maximum and minimum values , Meet the requirements .
MaxIndex Minus one
MaxIndex = 6
Finally, add an array to the two-dimensional array :{
{
-1 0 1 } }
(8) To determine :
MinValue : -1 , MaxValue : 0 , TempValue : 1
Find out TempValue : 1 exceed MaxValue : 0, For repeating elements , Kicked out .
(9) To determine :
MinValue : 0 , MaxValue : 1 , TempValue : -1
Find out TempValue : 1 exceed MinValue : 0, For repeating elements , Kicked out .
(10) To determine :
MinValue : 0 , MaxValue : 0 , TempValue : 0
Find out 0 There are only two values , Here I took it three times , Kicked out .
3、 ... and 、VS Test code
(1) Ideas need to be improved
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ELEMENTSIZE 3
#define INITARRAYSIZE 10000
#define RECORDARRAYSIZE 10
void PrintfArr(void *arr, int size, int elementsize);
void PrintfHeadVal();
void Printf2DimensionArray(int** Array, int num1, int num2);
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes);
int main()
{
int nums[] = {
-1,0,1,0,3 };
int numsSize = sizeof(nums) / sizeof(int);
int returnSize = 0;
int** returnColumnSizes = (int**)malloc(sizeof(int*));
PrintfArr(nums, numsSize, sizeof(int));
threeSum(nums, numsSize, &returnSize, returnColumnSizes);
return 0;
}
/* For example, the array is : The number :-5 -4 -3 -2 -1 0 1 2 3 4 5 frequency : 0 1 2 1 3 1 0 2 4 5 1 Indexes : 0 1 2 3 4 5 6 7 0 9 10 min max temp The length of the array :11 (1) Construct a -10^5 To 10^5 Array of , Put the data one by one . (2) Define two variables to record the maximum and minimum subscripts when inserting . (3) If the minimum value is greater than zero , It means that no addition in the array can be 0, Returns a null value . (4) If the maximum value is less than zero , It means that no addition in the array can be 0, Returns a null value . (5) That is, there are three variables ,MaxIndex,MinIndex,TempIndex. (6) Judgment logic :max Value + min Value + temp Value = 0, recorded . max Value + min Value + temp Value != 0, Don't record . (7)min <= 0, max >= 0, temp Value = 0 - min Value - max Value , To judge temp The index of the bit . (8)temp Whether the corresponding index bit is 0, If by 0, Don't record . by 1 You need to judge whether it is with max、min coincidence , Coincident exit , Non coincident records . Greater than, etc 2, Record . */
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
if (numsSize < ELEMENTSIZE)
{
return NULL;
}
int** ResArray = (int**)malloc(sizeof(int*) * INITARRAYSIZE);
int* RecordArray = (int*)malloc(sizeof(int) * (RECORDARRAYSIZE * 2 + 1));
*returnColumnSizes = (int*)malloc(sizeof(int) * INITARRAYSIZE);
int MaxIndex = RECORDARRAYSIZE + nums[0];
int MinIndex = RECORDARRAYSIZE + nums[0];
int TempValue = 0;
int MaxValue = MaxIndex - RECORDARRAYSIZE;
int MinValue = MinIndex - RECORDARRAYSIZE;
int TempIndex = 0;
int i = 0;
int j = 0;
int Flag = 0;
// Initialize array RecordArray
for ( i = 0; i < RECORDARRAYSIZE * 2 + 1; i++)
{
RecordArray[i] = 0;
}
// take nums The values in the array are recorded in the array RecordArray in
// Record the maximum and minimum values and index
for ( i = 0; i < numsSize; i++)
{
MaxValue = MaxIndex - RECORDARRAYSIZE;
if (nums[i] > MaxValue)
{
MaxIndex = RECORDARRAYSIZE + nums[i];
}
MinValue = MinIndex - RECORDARRAYSIZE;
if(nums[i] < MinValue)
{
MinIndex = RECORDARRAYSIZE + nums[i];
}
RecordArray[RECORDARRAYSIZE + nums[i]]++;
}
MaxValue = MaxIndex - RECORDARRAYSIZE;
MinValue = MinIndex - RECORDARRAYSIZE;
PrintfHeadVal();
printf(" The number :");
PrintfArr(RecordArray, RECORDARRAYSIZE * 2 + 1, sizeof(int));
printf("MaxIndex : %d , MaxValue : %d , MinIndex : %d , MinValue : %d\n", MaxIndex, MaxValue, MinIndex, MinValue);
// If the minimum value is greater than zero , It means that no addition in the array can be 0, Returns a null value .
// If the maximum value is less than zero , It means that no addition in the array can be 0, Returns a null value .
if (MaxValue < 0)
{
return NULL;
}
if (MinValue > 0)
{
return NULL;
}
// The following two cycles can reduce the following for Number of cycles , Speed up program efficiency .
// It's OK to , The efficiency is not improved .
while ((MinValue * 2 + MaxValue > 0) && (RecordArray[MaxIndex] != 0))
{
MaxIndex--;
MaxValue = MaxIndex - RECORDARRAYSIZE;
}
while ((MinValue + MaxValue * 2 < 0) && (RecordArray[MinIndex] != 0))
{
MinIndex++;
MinValue = MinIndex - RECORDARRAYSIZE;
}
for (i = MinIndex; i <= RECORDARRAYSIZE; i++)
{
if (RecordArray[i] == 0)
{
continue;
}
MinValue = i - RECORDARRAYSIZE;
while ((MinValue * 2 + MaxValue > 0) && (RecordArray[MaxIndex] != 0))
{
MaxIndex--;
MaxValue = MaxIndex - RECORDARRAYSIZE;
}
for ( j = MaxIndex; j >= RECORDARRAYSIZE; j--)
{
if (RecordArray[j] == 0)
{
continue;
}
MaxValue = j - RECORDARRAYSIZE;
TempValue = 0 - MinValue - MaxValue;
TempIndex = TempValue + RECORDARRAYSIZE;
printf(" i : %2d , MinValue : %2d ,j : %2d , MaxValue : %2d , TempIndex : %2d , TempValue : %2d , RecordArray[TempIndex] : %2d\n",
i, MinValue, j, MaxValue, TempIndex, TempValue, RecordArray[TempIndex]);
if (RecordArray[TempIndex] > 0)
{
if ((RecordArray[TempIndex] == 1) && (j > TempIndex) && (i < TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] == 2) && (j > TempIndex) && (i <= TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] == 2) && (j >= TempIndex) && (i < TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] > 2) && (j >= TempIndex) && (i <= TempIndex))
{
Flag = 1;
}
if (Flag)
{
printf("*returnSize : %d\n", *returnSize);
(*returnColumnSizes)[*returnSize] = ELEMENTSIZE;//*returnColumnSizes Put it in parentheses
ResArray[*returnSize] = (int*)malloc(sizeof(int) * ELEMENTSIZE);
ResArray[*returnSize][0] = MinValue;
ResArray[*returnSize][2] = MaxValue;
ResArray[*returnSize][1] = TempValue;
//printf("data : (%d , %d , %d)\n", ResArray[*returnSize][0], ResArray[*returnSize][2], ResArray[*returnSize][1]);
(*returnSize)++;
Printf2DimensionArray(ResArray, *returnSize, ELEMENTSIZE);
printf("+++++++++++++++++++++++++++++\n");
Flag = 0;
}
}
}
}
Printf2DimensionArray(ResArray, *returnSize, ELEMENTSIZE);
Printf2DimensionArray(returnColumnSizes, 1, *returnSize);
return ResArray;
}
void Printf2DimensionArray(int** Array, int num1, int num2)
{
int i, j;
printf("{");
for ( i = 0; i < num1; i++)
{
printf("{");
for ( j = 0; j < num2; j++)
{
printf("%2d ", Array[i][j]);
}
printf("} ");
}
printf("} \n");
}
void PrintfHeadVal()
{
int i;
printf(" Header :");
for (i = -RECORDARRAYSIZE; i <= RECORDARRAYSIZE; i++)
{
printf("%3d ", i);
}
printf("\n");
printf(" Indexes :");
for (i = 0; i <= RECORDARRAYSIZE * 2 ; i++)
{
printf("%3d ", i);
}
printf("\n");
}
void PrintfArr(void *arr, int size, int elementsize)
{
if (elementsize == sizeof(int))
{
int *tmparr = (int*)arr;
int i;
for (i = 0; i < size; i++)
{
printf("%3d ", tmparr[i]);
}
}
else if (elementsize == sizeof(char))
{
char *tmparr = (char*)arr;
int i;
for (i = 0; i < size; i++)
{
printf("%c ", tmparr[i]);
}
}
printf("\n========================\n");
}
Four 、VS Running results
5、 ... and 、leecode Submission code
#define ELEMENTSIZE 3
#define INITARRAYSIZE 20000
#define RECORDARRAYSIZE 100000
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
*returnSize = 0;
if (numsSize < ELEMENTSIZE)
{
return NULL;
}
int** ResArray = (int**)malloc(sizeof(int*) * INITARRAYSIZE);
int* RecordArray = (int*)malloc(sizeof(int) * (RECORDARRAYSIZE * 2 + 1));
*returnColumnSizes = (int*)malloc(sizeof(int) * INITARRAYSIZE);
int MaxIndex = RECORDARRAYSIZE + nums[0];
int MinIndex = RECORDARRAYSIZE + nums[0];
int TempValue = 0;
int MaxValue = MaxIndex - RECORDARRAYSIZE;
int MinValue = MinIndex - RECORDARRAYSIZE;
int TempIndex = 0;
int i = 0;
int j = 0;
int Flag = 0;
for ( i = 0; i < RECORDARRAYSIZE * 2 + 1; i++)
{
RecordArray[i] = 0;
}
for ( i = 0; i < numsSize; i++)
{
MaxValue = MaxIndex - RECORDARRAYSIZE;
if (nums[i] > MaxValue)
{
MaxIndex = RECORDARRAYSIZE + nums[i];
}
MinValue = MinIndex - RECORDARRAYSIZE;
if(nums[i] < MinValue)
{
MinIndex = RECORDARRAYSIZE + nums[i];
}
RecordArray[RECORDARRAYSIZE + nums[i]]++;
}
MaxValue = MaxIndex - RECORDARRAYSIZE;
MinValue = MinIndex - RECORDARRAYSIZE;
if (MaxValue < 0)
{
return NULL;
}
if (MinValue > 0)
{
return NULL;
}
while ((MinValue * 2 + MaxValue > 0) && (RecordArray[MaxIndex] != 0))
{
MaxIndex--;
MaxValue = MaxIndex - RECORDARRAYSIZE;
}
while ((MinValue + MaxValue * 2 < 0) && (RecordArray[MinIndex] != 0))
{
MinIndex++;
MinValue = MinIndex - RECORDARRAYSIZE;
}
for (i = MinIndex; i <= RECORDARRAYSIZE; i++)
{
if (RecordArray[i] == 0)
{
continue;
}
MinValue = i - RECORDARRAYSIZE;
while ((MinValue * 2 + MaxValue > 0) && (RecordArray[MaxIndex] != 0))
{
MaxIndex--;
MaxValue = MaxIndex - RECORDARRAYSIZE;
}
for ( j = MaxIndex; j >= RECORDARRAYSIZE; j--)
{
if (RecordArray[j] == 0)
{
continue;
}
MaxValue = j - RECORDARRAYSIZE;
TempValue = 0 - MinValue - MaxValue;
TempIndex = TempValue + RECORDARRAYSIZE;
if (RecordArray[TempIndex] > 0)
{
if ((RecordArray[TempIndex] == 1) && (j > TempIndex) && (i < TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] == 2) && (j > TempIndex) && (i <= TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] == 2) && (j >= TempIndex) && (i < TempIndex))
{
Flag = 1;
}
else if ((RecordArray[TempIndex] > 2) && (j >= TempIndex) && (i <= TempIndex))
{
Flag = 1;
}
if (Flag)
{
(*returnColumnSizes)[*returnSize] = ELEMENTSIZE;
ResArray[*returnSize] = (int*)malloc(sizeof(int) * ELEMENTSIZE);
ResArray[*returnSize][0] = MinValue;
ResArray[*returnSize][2] = MaxValue;
ResArray[*returnSize][1] = TempValue;
(*returnSize)++;
Flag = 0;
}
}
}
}
return ResArray;
}
6、 ... and 、 Running results
边栏推荐
- TS Basics
- Configure raspberry pie access network
- 杰理之BLE【篇】
- 杰理之开发板上电开机,就可以手机打开 NRF 的 APP【篇】
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- Jerry's general penetration test - do data transmission with app Communication [article]
- navicat如何导入MySQL脚本
- TypeScript 可索引类型
- Uncaught typeerror: cannot red properties of undefined (reading 'beforeeach') solution
- Markdown 中设置图片图注
猜你喜欢
Raspberry pie serial port login and SSH login methods
qt颜色与字符串、uint相互转换
Go learning -- implementing generics based on reflection and empty interfaces
MVVM of WPF
学go之路(一)go的基本介绍到第一个helloworld
jmeter性能测试步骤实战教程
leetcode1020. Number of enclaves (medium)
Seriously recommend several machine learning official account
杰理之AD 系列 MIDI 功能说明【篇】
Solution to the problem of breakthrough in OWASP juice shop shooting range
随机推荐
#systemverilog# 可綜合模型的結構總結
Project GFS data download
Ble of Jerry [chapter]
Thought map of data warehouse construction
[online problem processing] how to kill the corresponding process when the MySQL table deadlock is caused by the code
Jerry's general penetration test - do data transmission with app Communication [article]
【线上问题处理】因代码造成mysql表死锁的问题,如何杀掉对应的进程
Typescript indexable type
Emo diary 1
Internal and external troubles of "boring ape" bayc
Multithreading and concurrent programming (2)
OpenJudge NOI 2.1 1661:Bomb Game
jmeter性能测试步骤实战教程
杰理之BLE【篇】
Sélectionnez toutes les lignes avec un symbole dans Word et changez - les en titre
Configure raspberry pie access network
Oracle database 11gr2 uses TDE transparent data encryption to report an error ora28353. If you run to close the wallet, you will report an error ora28365. If you run to open the wallet, you will repor
网络安全基础介绍
学go之路(二)基本类型及变量、常量
TypeScript接口与泛型的使用