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;
    }
};

声明：
文章标题：刷题笔记(ing~)
文章作者：h3h3da
文章链接：https://www.liucunzhan.com/p/cc3771d5-dab9-4ac5-b8bf-d90fd90545bf
文章版权属本博主所有，有问题或者建议欢迎在下方评论。欢迎转载、引用，但请标明作者和原文地址，谢谢。

喜欢，就支持我一下吧~