leetcode题目解析

前言

本文为leetcode上的题目简单分析，仅作记录，欢迎提出建议，共同学习交流。题目的源代码和测试用例可以在leetcodeWithC下载

001 Two Sum

题目：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example: Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

释义：

给定整型数组，返回两个数的下标，使得这两个数相加得到特定的值。 假设每个给定的数组只能找到一组满足条件的结果，同时，不能使用同一个数两次。

分析：

题大意为，在一组数组中，找到两个数，使得这两个数的和等于特定值，并返回下标。可以从第一个数开始，循环与后面的每一个相加，与结果比较，比较成功则返回。 例如，输入[1,7,11,15],目标值26，那么循环计算1+7,1+11,1+15，7+11,7+15……，直到得到目标值。

代码如下：

001 two sum

int* twoSum(int* nums, int numsSize, int target) { int loop = 0; int inloop = 0; int* result = NULL; result =(int*) malloc(2*sizeof(int)); memset(result,0,2*sizeof(int)); printf("numsSize=%d\n",numsSize); if(NULL == nums || numsSize==0) { return result; } for(loop = 0;loop < numsSize;loop++) { for(inloop = loop+1;inloop <numsSize;inloop++) { if(*(nums+loop)+*(nums+inloop) == target) { if(NULL != result) { *result = loop; *(result+1) = inloop; } return result; } } } return result; }

002 Add Two Numbers

题目：

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

释义：

给定两个非空链表代表两个非负整数，整数的各位数以逆序存储在链表的每个节点中。将这两个数相加，并返回结果链表。

分析

题意较清晰，是将用链表形式的两个整数进行相加，并返回链表结果。 需要注意的主要有以下几点 1.加完之后需要给下一位子进位。 2.如果链表只有一位，直接计算结果，提高效率。 3.考虑两个链表长度不一样的场景

代码如下：

002 Add Two Numbers

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { unsigned int len = sizeof(struct ListNode); struct ListNode* head = NULL; struct ListNode* temp = NULL; int tempValue = 0; int flag = 0; /×个位数相加的情况×/ if(NULL == l1->next||NULL == l2->next) { head = (struct ListNode*)malloc(len); memset(head,0,len); head->val = (l1->val + l2->val)%10; /×获取进位×/ flag = (l1->val + l2->val)/10; temp = head; l1 = l1->next; l2 = l2->next; } else { /×非个位数计算×/ while(NULL != l1&& NULL != l2) { tempValue = l2->val+l1->val; struct ListNode* node = (struct ListNode*)malloc(len); memset(node,0,len); node->next = NULL; node->val = (tempValue+flag)%10; if(NULL == head) { head = node; temp = head; } { temp->next = node; temp = temp->next; } flag = (tempValue+flag)/10; l1 = l1->next; l2 = l2->next; } } /×l1的位数大于l2×/ if(NULL != l1) { while(NULL != l1) { struct ListNode* node = (struct ListNode*)malloc(len); memset(node,0,len); node->next = NULL; node->val = (l1->val+flag)%10; temp->next = node; temp = temp->next; flag = (l1->val+flag)/10; l1=l1->next; } } /×l2的位数大于l1×/ else if(NULL != l2) { while(NULL != l2) { struct ListNode* node = (struct ListNode*)malloc(len); memset(node,0,len); node->next = NULL; node->val = (l2->val+flag)%10; temp->next = node; temp = temp->next; flag =(l2->val+flag)/10; l2=l2->next; } } else{} /×如果前面有进位，记得加上×/ if(flag != 0) { temp->next = (struct ListNode*)malloc(len); memset(temp->next,0,len); temp->next->val = flag; } return head; }

258 Add Digits

题目：

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

释义：

计算各位数之和，直到最后只有一位。

分析：

计算各位数之和，采用递归，计算一次后，再次调用，直到结果位各位数。

代码如下：

258 Add Digits

int addDigits(int num) { int temp = num; if(0 == num/10) { return num; } else { num =0; while(0 != temp/10) { num +=temp; temp = temp/10; } num = num+temp; return addDigits(num); } }

344 Reverse String

题目：

Write a function that takes a string as input and returns the string reversed.

Example: Given s = “hello”, return “olleh”.

释义：

字符串翻转

分析

头尾对应位置的字符位置调换

代码如下：

344 Reverse String

char* reverseString(char* s) { unsigned int len = strlen((const char*)s); char result[len+1]; memset(result,0,len); int loop = 0; for(loop = len-1; loop >= 0;loop--) { *(result+(len-loop-1)) = *(s+loop); } result[len] = '\0'; memcpy(s,result,len); return s; }

463 Hamming Distance

题目：

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note: 0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ? ?

The above arrows point to positions where the corresponding bits are different.

释义：

分析：

两个数的汉明距离，可以理解为，二进制的情况下，两个数异或之后的数的1的个数。 比如例子中，1和4,0001与0100异或得：0101，而0101中1的个数，即为汉明距离，可以理解位，从0001，变成0100，需要改变的位数。

代码如下：

463 Hamming Distance

““ int hammingDistance(int x, int y) { int result = 0; /get the temp result/ int temp = x^y; /calc the 1 of temp result/ while (temp != 0) { if (temp % 2 == 1) { result++; } temp = temp >>1; } return result;

}

### 476 Number Complement ##### 题目： Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation. Note: The given integer is guaranteed to fit within the range of a 32-bit signed integer. You could assume no leading zero bit in the integer’s binary representation. Input: 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2. ##### 释义： 给定一个正整数，输出它的补全整数。补全策略是翻转它的每个比特位，得到补全整数。 ##### 分析： 对于补全，以5为例，101，每一位翻转得到，010，即结果为2，那么，010+101 = 111，2的3次方。再以35为例，10 0011，翻转得到011100，即有100011+011100=111111,2的6次方，那么不难得到，其实补全数，就是用2的n次方，减去该数，其中，n为该数二进制表示的位数。 ##### 代码如下： [476 Number Complement](https://github.com/yanbinghu/LeetCodeWithC/blob/master/leetcode/src/476_Number_Complement.c)

int findComplement(int num) { int temp = num; int i = 0; for(i=0;temp!=0;temp/=2,i++) {} /×pow，库函数×/ return pow(2,i)-num-1; } “`