20200726
直接在leetcode做题吧，此文不再更新。
源起
弱点，会被看穿，会被评价，会流下血与泪
参考
leetcode
剑指offer
001 合并两个有序链表
| 题目 |
来源 |
完成时间 |
| 将两个升序链表合并为一个新的升序链表并返回 |
剑指offer |
20200401 |
合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
my unswer
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
|
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1)
return l2;
if (!l2)
return l1;
ListNode *p1 = l1;
ListNode *p2 = l1;
ListNode *p3 = NULL;
while (l2)
{
p1 = l1;
while (p1 && l2->val >= p1->val)
{
p3 = p1;
p1 = p1->next;
}
if (!p1)
{
p3->next = l2;
break;
}
else
{
if (p1 != l1)
{
p3->next = l2;
}
p2 = l2->next;
l2->next = p1;
if (p1 == l1)
{
l1 = l2;
p1 = l1;
}
}
l2 = p2;
}
return l1;
}
};
|
002 数组中重复的数字
| 题目 |
来源 |
完成时间 |
| 找出数组中重复的数字 |
剑指offer |
20200417 |
在一个长度为n的数组里的所有数字都在0 ~ n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是数字2或者3
方法1：排序，排完序遍历数组
方法2：哈希表，插入判断是否重复
方法3：让数组索引值和数组的元素值相等，data[0] = 0, data[1] = 1,对应不上的不管
| 方法 |
时间复杂度 |
空间复杂度 |
| 排序 |
O(nlogn) |
O(n) |
| 哈希 |
O(1) |
O(n) |
| 数组索引 |
O(1) |
O(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
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
| #include <iostream>
using namespace std;
void FuncFind(int data[], int n)
{
if (data == nullptr || n <= 0)
{
cout << "Invalid param!" << endl;
return ;
}
for (int i = 0; i < n; i++)
{
if (data[i] < 0 || data[i] > n - 1)
{
cout << "Invalid param!" << endl;
return ;
}
}
for (int i = 0; i < n; )
{
if (data[i] != i)
{
if (data[i] == data[data[i]])
{
cout << data[i] << endl;
i++;
}
else
{
swap(data[i], data[data[i]]);
}
}
else
i++;
}
}
void FuncFind2(int data[], int n)
{
if (data == nullptr || n <= 0)
{
cout << "Invalid param!" << endl;
return ;
}
for (int i = 0; i < n; i++)
{
if (data[i] < 0 || data[i] > n - 1)
{
cout << "Invalid param!" << endl;
return ;
}
}
for (int i = 0; i < n; i++)
{
while (data[i] != i)
{
if (data[i] == data[data[i]])
{
cout << data[i] << endl;
break;
}
else
{
swap(data[i], data[data[i]]);
}
}
}
}
int main()
{
int data[] = {2,3,1,0,2,5,3,1,8,10,6,6};
int n = sizeof(data)/sizeof(int);
FuncFind(data, n);
return 0;
}
|
2
3
1
3
6
Process returned 0 (0x0) execution time : 0.011 s
Press any key to continue.
003 不修改数组找出数组中重复的数字
| 题目 |
来源 |
完成时间 |
| 不修改数组找出数组中重复的数字 |
剑指offer |
20200418 |
读题：
在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。
思路：
- 新建一个数组，复制过来，把数组值和数组索引对应上，则可以找出重复的元素
- 二分查找的方法，找出每个半区的元素个数是否刚好是半区总数，然后不断递归
思路2的实现：
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
| #include <iostream>
using namespace std;
int FuncFind(int data[], int left, int right, int len)
{
if(data == nullptr || len <= 0)
{
cout << "Invalid param!" << endl;
return -1;
}
int mid = (right + left) / 2;
int lnum = 0;
int rnum = 0;
if (left >= right)
{
return mid;
}
for (int i = 0; i < len; i++)
{
if (data[i] > mid && data[i] <= right)
rnum++;
else if(data[i] <= mid && data[i] >= left)
lnum++;
}
if (right - mid < rnum)
{
return FuncFind(data, mid + 1, right, len);
}
else if (mid - left + 1 < lnum)
{
return FuncFind(data, left, mid, len);
}
return -1;
}
int main()
{
int data[] = {4,5,6,7,1,2,3,2};
int n = sizeof(data)/sizeof(int);
cout << FuncFind(data, 1, n-1, n) << endl;
return 0;
}
|
004 不修改数组找出数组中重复的数字
| 题目 |
来源 |
完成时间 |
| 二维数组中的查找 |
剑指offer |
20200418 |
读题
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
思路
从右上角开始找
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
| #include <iostream>
using namespace std;
void FuncFind(int data[][4], int row, int col, int n)
{
col--;
int line = 0;
while(line < row && col >=0)
{
if (n == data[line][col])
{
cout << "exist!" << endl;
return;
}
else if (n > data[line][col])
line++;
else
col--;
}
cout << "not exist!" << endl;
return;
}
int main()
{
int data[][4] = {
1, 2, 8, 9,
2, 4, 9, 12,
4, 7, 10, 13,
6, 8, 11, 15
};
int n = 0;
while(cin >> n)
{
FuncFind(data, 4, 4, n);
}
return 0;
}
|
005 从尾到头打印链表
| 题目 |
来源 |
完成时间 |
| 从尾到头打印链表 |
剑指offer |
20200418 |
读题
输入一个链表的头节点，从头到尾反过来打印出每个节点的值。链表节点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_npNext;
};
思路：
- 栈是后进先出，可以放到栈数据结构中再取出来
- 采用函数递归，但要考虑到递归不易太深，否则会溢出
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
| #include <iostream>
#include <stack>
using namespace std;
struct ListNode
{
int m_nKey;
ListNode* m_npNext;
};
void ReversePrint(ListNode* pHead)
{
if (pHead != NULL)
{
if (pHead->m_npNext != NULL)
ReversePrint(pHead->m_npNext);
cout << pHead->m_nKey << " ";
}
}
int main()
{
int n = 0;
ListNode *pHead = new ListNode;
ListNode *pNode = pHead;
while(cin >> n)
{
pNode->m_nKey = n;
pNode->m_npNext = NULL;
if (cin.get() == '\n')
break;
pNode->m_npNext = new ListNode;
pNode = pNode->m_npNext;
}
stack<ListNode*> oStack;
pNode = pHead;
while(pNode)
{
oStack.push(pNode);
pNode = pNode->m_npNext;
}
pNode = pHead;
while(!oStack.empty())
{
pNode = oStack.top();
cout << pNode->m_nKey << " ";
oStack.pop();
}
cout << endl;
return 0;
}
|
006 替换空格
| 题目 |
来源 |
完成时间 |
| 替换空格 |
剑指offer |
20200521 |
读题
请实现一个函数，把字符串中的每个空格替换成”%20”.例如，输入 “we are happy”, 则输出 “we%20are%20happy”
思路：
ending
