No.1 两数之和

题目描述

难度
简单

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例

1
2
3
4
5
6

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
[c]
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target)
{
static int a[2]={0};


for (int i = 0; i < numsSize - 1; i++)
{
for (int j = i+1; j < numsSize; j++)
{
if (nums[i] + nums[j] == target)
{
a[0] = i;
a[1] = j;
return a;
}
}
}
return 0;
}

No.2 两数相加

题目描述

难度
中等

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例

1
2
3
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

思路

题解

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
94
95
96
97
[cpp]
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
#include<math.h>
class Solution {
public:
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
ListNode * ans = new ListNode(0);
ListNode * s = ans;
int flag = 0;
int i = 0;
int nt = 0;
while(l1&&l2){
nt = l1->val + l2->val;
if(flag==1){
nt+=1;
}
if(nt >= 10){
flag = 1;
nt = nt % 10;
}else{
flag = 0;
}
l1 = l1->next;
l2 = l2->next;
ans->val = nt;
if(!l1&&!l2&&flag==1){
ans -> next = new ListNode(0);
ans = ans -> next;
ans -> val = 1;
ans ->next = NULL;


}else if(l1&&l2){
ans->next = new ListNode(0);
ans = ans->next;
}else{
while(l1){
if(flag == 1){
nt = 1 + l1->val;
}else{
nt = l1->val;
}
if(nt >= 10){
flag = 1;
nt = nt % 10;
}else{
flag = 0;
}
ans -> next = new ListNode(0);
ans = ans -> next;
ans->val = nt;
l1 = l1->next;
if(!l1){
ans->next = NULL;
}

}
while(l2){
if(flag == 1){
nt = 1 + l2->val;
}else{
nt = l2->val;
}
if(nt >= 10){
flag = 1;
nt = nt % 10;
}else{
flag = 0;
}
ans -> next = new ListNode(0);
ans = ans -> next;
ans->val = nt;
l2 = l2->next;
if(!l2){
ans->next = NULL;
}
}
if(flag == 1){
ans -> next = new ListNode(0);
ans = ans -> next;
ans->val = 1;
ans -> next = NULL;
}
}

}

return s;
}
};

No.7 整数反转

题目描述

难度
简单
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

示例 1:

输入: 123
输出: 321
示例 2:

输入: -123
输出: -321
示例 3:

输入: 120
输出: 21
注意:

假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。

思路

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[java]

class Solution {
public int reverse(int x) {
boolean flag = true;
if (x < 0) {
x = Math.abs(x);
flag = false;
}
StringBuffer reverse = new StringBuffer();
reverse.append(x);
try {
int a = Integer.parseInt(reverse.reverse().toString());
if (flag) {
return a;
}else {
return -a;
}
} catch (Exception e) {
return 0;
}
}
}

No.60 第k个排列

题目描述

难度
中等
给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k,返回第 k 个排列。

说明:

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。

示例

1
2
3
4
5
6
7
8
9
10

示例 1:

输入: n = 3, k = 3
输出: "213"
示例 2:

输入: n = 4, k = 9
输出: "2314"

思路

这道题是让求出n个数字的第k个排列组合,由于其特殊性,我们不用将所有的排列组合的情况都求出来,然后返回其第k个,我们可以只求出第k个排列组合即可,那么难点就在于如何知道数字的排列顺序,可参见Here
首先我们要知道当n = 3时,其排列组合共有3! = 6种,当n = 4时,其排列组合共有4! = 24种,我们就以n = 4, k = 17的情况来分析,所有排列组合情况如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412 <--- k = 17
3421
4123
4132
4213
4231
4312
4321

我们可以发现,每一位上1,2,3,4分别都出现了6次,当第一位上的数字确定了,后面三位上每个数字都出现了2次,当第二位也确定了,后面的数字都只出现了1次,当第三位确定了,那么第四位上的数字也只能出现一次,那么下面我们来看k = 17这种情况的每位数字如何确定,由于k = 17是转化为数组下标为16:

最高位可取1,2,3,4中的一个,每个数字出现3!= 6次,所以k = 16的第一位数字的下标为16 / 6 = 2,即3被取出
第二位此时从1,2,4中取一个,k = 16时,k’ = 16 % (3!) = 4,而剩下的每个数字出现2!= 2次,所以第二数字的下标为4 / 2 = 2,即4被取出
第三位此时从1,2中去一个,k’ = 4时,k’’ = 4 % (2!) = 0,而剩下的每个数字出现1!= 1次,所以第三个数字的下标为 0 / 1 = 0,即1被取出
第四位是从2中取一个,k’’ = 0时,k’’’ = 0 % (1!) = 0,而剩下的每个数字出现0!= 1次,所以第四个数字的下标为0 / 1= 0,即2被取出

那么我们就可以找出规律了

1
2
3
4
5
6
7
8
9
10
11
12
a1 = k / (n - 1)!
k1 = k

a2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!
...

an-1 = kn-2 / 1!
kn-1 = kn-2 / 1!

an = kn-1 / 0!
kn = kn-1 % 0!

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
[cpp]
class Solution {
public:
string getPermutation(int n, int k) {
string res;
string num = "123456789";
vector<int> f(n, 1);
for (int i = 1; i < n; ++i) f[i] = f[i - 1] * i;
--k;
for (int i = n; i >= 1; --i) {
int j = k / f[i - 1];
k %= f[i - 1];
res.push_back(num[j]);
num.erase(j, 1);
}
return res;
}
};


声明:
文章标题:【LeetCode】刷题笔记(ing~)
文章作者:RookieHacker
文章链接:http://blog.rookiehacker.org/2019/01/05/LeetCode/
文章版权属本博主所有,有问题或者建议欢迎在下方评论。欢迎转载、引用,但请标明作者和原文地址,谢谢。


喜欢,就支持我一下吧~