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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
* 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int addDigits(int num) {
int temp = num;
if(0 == num/10)
{
return num;
}
else
{
num =0;
while(0 != temp/10)
{
num +=temp%10;
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
2
3
4
5
6
7
8
9
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;
}

守望 wechat
关注[编程珠玑]获取更多原创技术文章
出入相友,守望相助!