今天有几道leetcode的题目。
1、两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例: 给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7> = 9
所以返回 [0, 1]
最终的输出代码：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int *result = NULL;
int i, j;
*returnSize = 2;
result = (int *)malloc(sizeof(int) * 2);
for(i = 0; i < numsSize; i++)
{
for(j = 0; j < numsSize; j++)
{
if( (nums[i] + nums[j] == target) && (i != j) )
{
result[0] = i;
result[1] = j;
return result;
}
}
}
return 0;
}
总结：这个题目很简单，用一个二重循环就可以实现，需要注意的是要判断两个输出的值不重复。同时在malloc函数之前，需将待分配内存的地址指向NULL，不然该值在释放之后没有指向，编译器会报错。
2、两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例： 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode *prev = NULL, *Output = NULL, *OutputHead = NULL;
int val1 = 0, val2 = 0;
int flag = 0;
while(1)
{
if(l1 == NULL && l2 == NULL)
{
break;
}
Output = (struct ListNode *)malloc(sizeof(struct ListNode));
Output->next = NULL;
if(OutputHead == NULL)
{
OutputHead = Output;
}
else
{
prev->next = Output;
}
val1 = (l1 == NULL) ? 0 : l1->val;
val2 = (l2 == NULL) ? 0 : l2->val;
Output->val = val1 + val2 + flag;
flag = (Output->val >= 10) ? 1 : 0;
Output->val %= 10;
l1 = (l1 != NULL) ? l1->next : NULL;
l2 = (l2 != NULL) ? l2->next : NULL;
prev = Output;
}
if( flag == 1 )
{
Output = (struct ListNode *)malloc(sizeof(struct ListNode));
Output->next = NULL;
prev->next = Output;
Output->val = flag;
}
return OutputHead;
}
总结这个题目通过链表实现，算是对链表有了一个很好复习和巩固，在这个里面设置了三个链表结构体指针，分别用于存储链表的头指针OutputHead，在循环中不断赋值的指针临时变量Output和prev。功能的实现为认为链表中的每一个节点是整数中的一位，从链表的头地址开始认为数的最低位，按照两数相加一位一位的进位相加就可以，同时需要注意当最高为为新出现的情况，例如500+500=1000，则1000中的1需要进行判断，并且分配对应的内存进行输出。同时这个题目中需要对数据的溢出进行判断，如果两个数的位数不一样的情况下也填充一个0,，但是为了避免内存的溢出，需要对链表的下一个节点进行判断是否为空。最后，还是在分配内存的时候需要判断将分配之后的内存用如下代码进行初始化，否则链表的next会为一个未知的地址，导致溢出。
Output = (struct ListNode *)malloc(sizeof(struct ListNode));
Output->next = NULL;
3、整数翻转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123 输出: 321 示例 2:
输入: -123 输出: -321 示例 3:
输入: 120 输出: 21 注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
int reverse(int x){
long output = 0;
int xbackup = x;
while(xbackup!=0)
{
output = output *10 + (xbackup %10);
xbackup /= 10;
}
if (output > INT_MAX || output < INT_MIN ) return 0;
return output;
}
总结这里最主要的代码为
while(xbackup!=0)
{
output = output *10 + (xbackup %10);
xbackup /= 10;
}
通过如上代码逻辑为将值从最低位开始，将最低位取出来，通过while循环不断地乘10，然后将其置到最高位。注意一点是可以不用区分输入的是否为负。这个代码的实现逻辑很巧妙，比我自己之前的不断循环取值要好很多。
4、回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121 输出: true
示例 2:
输入: -121 输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例3:
输入: 10 输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶: 你能不将整数转为字符串来解决这个问题吗？
bool isPalindrome(int x)
{
if(x < 0)
return false;
int xbackup = x;
long output=0;
while(x!=0)
{
output = output * 10 + (x %10);
x = x/10;
}
return (output == xbackup);
}
总结这个代码即将3、整数反转中的结果进行比较判断即可。
5、两数相除
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。
示例 1:
输入: dividend = 10, divisor = 3 输出: 3
示例 2:
输入: dividend = 7, divisor = -3 输出: -2
说明:
被除数和除数均为 32 位有符号整数。 除数不为 0。 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 −1]。本题中，如果除法结果溢出，则返回 2^31 − 1。
long funcdiv(long dividend, long divisor);
long funcdiv(long dividend, long divisor)
{
int result = 0;
int divisorinput = divisor;
while(dividend >= divisor)
{
divisor += divisorinput;
result++;
}
return result;
}
int divide(int dividend, int divisor){
int flag, movetag=0;
long dividendbackup, divisorbackup, divisorinput, result=0;
long dividendtemp, divisortemp;
dividendbackup = dividend;
divisorbackup = divisor;
if( ((dividend > 0) && (divisor > 0)) || ((dividend < 0) && (divisor < 0)) )
{
flag = 1;
}
else if( ((dividend < 0) && (divisor > 0)) || ((dividend > 0) && (divisor < 0)) )
{
flag = -1;
}
else
{
return 0;
}
dividendbackup = (dividendbackup > 0)?dividendbackup:-dividendbackup;
divisorbackup = (divisorbackup > 0)?divisorbackup:-divisorbackup;
dividendtemp = dividendbackup;
divisortemp = divisorbackup;
if(divisorbackup <= dividendbackup)
{
result = 0;
for(movetag = 31; movetag >= 0; movetag--)
{
if((dividendtemp >> movetag) >= divisorbackup)
{
result += ((long)1) << movetag;
dividendtemp -= divisorbackup<<movetag;
}
}
}
else
{
return 0;
}
result = ((flag>0) ? result : (-result));
if((int)result != result)
{
return 2147483647;
}
return result;
}
总结 这个题目昨天晚上弄了好久，在这里把他的实现原理再复盘一遍。首先判断输出值的符号正负，然后通过转换，将计算的值都按照正值计算，最开始使用了暴力的不断的减法的逻辑，结果时间超时了，最终参考了别人的计算的核心代码见下：
result = 0;
for(movetag = 31; movetag >= 0; movetag--)
{
if((dividendtemp >> movetag) >= divisorbackup)
{
result += ((long)1) << movetag;
dividendtemp -= divisorbackup<<movetag;
}
}
其计算思路为任何整数都可以表示成2的幂次方的多项式，因此在程序中从大往小，不断的试，例如当被除数为50，除数为2的时候，
判断22?最接近被除数。算出来是？=4，于是计数+24 = 16，然后继续往下减，50-216 = 18，
继续判断22? 最接近18，算出来？=3，于是计数+=23 ，为24，于是继续往下减，18-28 = 2。
继续判断22? 最接近2，算出来？=0，于是计数+=20 ，为25，于是继续往下减，2-20 = 0。这个时候，“”？“”已经为0了， 跳出循环。返回计数值25。
程序的逻辑为从2的最大次幂，即31不断的往下试，当找到了最接近被除数的时候，则将计数累加。这种方法的时间复杂度为O(1)，即不论多大数据，其时间长度均为定值。