剑指offer题解

题目链接

超越保佑,offer++

替换空格

我自己一开始写的,非常笨的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
void replaceSpace(char *str, int length)
{
for (int i = 0; i < length; i++)
{
if (str[i]==' ')
{
for (int j = length+1; j > i+2; j--)
{
str[j] = str[j - 2];
}
length += 2;
str[i++] = '%';
str[i++] = '2';
str[i] = '0';
}
}
}
};

然后点开讨论区,大佬们开始秀自己的牛逼的算法,菜鸡瑟瑟发抖。

大概思路如下:

  1. 先遍历一遍字符串,找出字符串中有多少个空格。
  2. 计算替换后,字符串的长度。
  3. 从后往前,放入字符,如果遇到了空格,则用”%20”来替代。

代码如下:

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
class Solution
{
public:
void replaceSpace(char *str, int length)
{
//遍历一边字符串找出空格的数量
if (str == NULL || length < 0)
return;
int i = 0;
int oldnumber = 0;//记录以前的长度
int replacenumber = 0;//记录空格的数量
while (str[i] != '\0')
{
oldnumber++;
if (str[i] == ' ')
{
replacenumber++;
}
i++;
}
int newlength = oldnumber + replacenumber * 2;//插入后的长度
if (newlength > length)//如果计算后的长度大于总长度就无法插入
return;
int pOldlength = oldnumber; //注意不要减一因为隐藏个‘\0’也要算里
int pNewlength = newlength;
while (pOldlength >= 0 && pNewlength > pOldlength)//放字符
{
if (str[pOldlength] == ' ') //碰到空格就替换
{
str[pNewlength--] = '0';
str[pNewlength--] = '2';
str[pNewlength--] = '%';

}
else //不是空格就把pOldlength指向的字符装入pNewlength指向的位置
{
str[pNewlength--] = str[pOldlength];

}
pOldlength--; //不管是if还是elsr都要把pOldlength前移

}
}
};

从尾到头打印链表

使用头插法,将链表逆置之后,压入vector中。

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
#include<iostream>
#include<vector>

#pragma warning(disable:4996)
using namespace std;

struct ListNode
{
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
ListNode L(0);

void init()
{
int n, temp;
ListNode *ptr = &L;
cin >> n;
L.val = n;
for (int i = 0; i < n; i++)
{

ptr->next = (ListNode*)malloc(sizeof(ListNode));
cin >> ptr->next->val;
ptr->next->next = NULL;
ptr = ptr->next;
}
}

class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head)
{
vector<int> V;
if (head==NULL)
return V;
ListNode* pre=head;
head = head->next;
pre->next = NULL;
ListNode* p = NULL;
while (head!=NULL)
{
p = head;
head = head->next;
p->next = pre;
pre = p;
}

while (pre != NULL)
{
V.push_back(pre->val);
cout << pre->val << ' ';
pre = pre->next;
}
return V;
}

};

int main()
{
freopen("3.txt", "r", stdin);
init();
Solution a;
a.printListFromTailToHead(L.next);
system("pause");
return 0;
}

测试数据

1
2
3
4
5
6
7
8
9
10
Test1:
7
1 2 6 3 4 5 6

Test2:
4
67 0 24 58

Test3:
0

二维数组中的查找

  1. 可以使用暴力搜索,但是要注意剪枝。
  2. 留意到,对于每行,都是按照从小到大递增排序,对于每列,也是按照从小到大递增。因此可以从最左下进行搜索:若当前数>target,向上。反之,若当前数\<target,向右。

暴力搜索+剪枝

这里没用到每列都是按照从小到大进行排序的条件。这是一开始写的,写的不好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
public:
bool Find(int target, vector<vector<int>> array)
{
int hang = array.size();
int lie = array[0].size();
for (int i = 0; i < hang; i++)
{
for (int j = 0; j < lie; j++)
{
if (array[i][j] == target)
return true;
else if (array[i][j] > target)
break;
}
}
return false;
}
};

更好的代码:从左下开始搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
// array是二维数组,这里没做判空操作
int rows = array.size();
int cols = array[0].size();
int i=rows-1,j=0;//左下角元素坐标
while(i>=0 && j<cols){//使其不超出数组范围
if(target<array[i][j])
i--;//查找的元素较少,往上找
else if(target>array[i][j])
j++;//查找元素较大,往右找
else
return true;//找到
}
return false;
}
};

用两个栈实现队列

基础题,可以认为两个栈的空间都不会爆。

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
class Solution
{
public:
void push(int node)
{
stack1.push(node);
}

int pop()
{
if (!stack2.empty())
{
int temp = stack2.top();
stack2.pop();
return temp;
}
else
{
while (!stack1.empty())
{
int temp = stack1.top();
stack1.pop();
stack2.push(temp);
}
if (true)
{
int temp = stack2.top();
stack2.pop();
return temp;
}
else
return -1;
}
}

private:
stack<int> stack1;
stack<int> stack2;
};

旋转数组的最小数字

找数组中,前一个【>】后一个的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray)
{
if (rotateArray.size()==0)
{
return 0;
}
for (int i = 0; i < rotateArray.size()-1; i++)
{
if (rotateArray[i] > rotateArray[i + 1])
return rotateArray[i + 1];
}
return 0;
}
};

斐波那契数列

斐波那契数列:0 1 1 2 3….

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int Fibonacci(int n)
{
int res_pre = 0, res = 1;
if (n == 0)
return 0;
for (int i = 1; i < n; i++)
{
res = res + res_pre;
res_pre = res - res_pre;
}
return res;
}
};

跳台阶

组合

利用组合去做

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
class Solution {
public:
int zuhe(int a, int b)
{
long long int res = 1;
for (int i = 0; i < b; i++)
{
res *= (a - i);
}
for (int i = 2; i <= b; i++)
{
res /= i;
}
return res;
}

int jumpFloor(int number)
{
int min = number / 2;
if (number % 2 == 1)
min++; //最少的步数
int res = 0;
for (int i = min; i < number; i++)
{
res += zuhe(i, number-i);
}
res ++;
return res;
}
};

Fib序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int JumpFloor(int n) 
{
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 1;
for (int i = 2; i < n; i++)
{
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}

变态跳台阶

组合

组合,根据1~number-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
class Solution {
public:
int zuhe(int a, int b)
{
long long int res = 1; //必须用 long long,否则会溢出
for (int i = 0; i < b; i++)
{
res *= (a - i);
}
for (int i = 2; i <= b; i++)
{
res /= i;
}
return res;
}
int jumpFloorII(int number)
{
int res=0;
for (int i = 0; i < number-1; i++)
{
res += zuhe(number-1, i);
}
res++;
return res;
}
};

动态规划

数学推导

跳上 n-1 级台阶,可以从 n-2 级跳 1 级上去,也可以从 n-3 级跳 2 级上去…,那么

1
f(n-1) = f(n-2) + f(n-3) + ... + f(0)

同样,跳上 n 级台阶,可以从 n-1 级跳 1 级上去,也可以从 n-2 级跳 2 级上去… ,那么

1
f(n) = f(n-1) + f(n-2) + ... + f(0)

综上可得

1
f(n) - f(n-1) = f(n-1)

1
f(n) = 2*f(n-1)

所以 f(n) 是一个等比数列。

1
2
3
4
public int JumpFloorII(int target)
{
return (int) Math.pow(2, target - 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
class Solution {
public:
int zuhe(int a, int b)
{
long long int res = 1;
for (int i = 0; i < b; i++)
{
res *= (a - i);
}
for (int i = 2; i <= b; i++)
{
res /= i;
}
return res;
}
int rectCover(int number)
{
if (number == 0)
return 0;
//和跳台阶类似?
int temp = number / 2; //最多有多少个横着的。
int res = 0;
for (int i = 0; i <= temp; i++)
{
res += zuhe(number-i, i);
}
return res;
}
};

Fib序列

1
2
3
4
5
6
7
8
9
10
11
12
public int RectCover(int n) {
if (n <= 2)
return n;
int pre2 = 1, pre1 = 2;
int result = 0;
for (int i = 3; i <= n; i++) {
result = pre2 + pre1;
pre2 = pre1;
pre1 = result;
}
return result;
}

二进制中1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int NumberOf1(int n)
{
int res = 0;
if (n<0)
{
n = n & 0x7FFFFFFF; //部分编译器,对于复数的右移,是补1的。
res++;
}
while (n!=0)
{
res += (n & 1);
n = n >> 1;
}
return res;
}
};

数值的整数次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
double Power(double base, int exponent)
{
double res=1;
if (exponent>=0)
{
for (int i = 0; i < exponent; i++)
{
res *= base;
}
}
if (exponent < 0)
{
exponent = -exponent;
for (int i = 0; i < exponent; i++)
{
res /= base;
}
}
return res;
}
};

调整数组顺序使奇数位于偶数前面

解法一:类似于冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    class Solution {
public:
void reOrderArray(vector<int> &array)
{
for (int i = 0; i < array.size(); i++)
{
for (int j = array.size()-1; j > i; j--)
{
if (array[j-1] % 2 == 0 && array[j] % 2 == 1)
swap(array[j-1], array[j]);
}
}
}
};

解法二:先保存奇数,再保存偶数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    class Solution {
public:
void reOrderArray(vector<int> &array)
{
vector<int> temp;
for (int i = 0; i < array.size(); i++)
{
if (array[i] % 2 == 1)
temp.push_back(array[i]);
}
for (int i = 0; i < array.size(); i++)
{
if (array[i] % 2 == 0)
temp.push_back(array[i]);
}
array = temp;
}
};

链表中倒数第k个结点

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k)
{
//两个指针
ListNode* p1 = pListHead, *p2 = NULL;
for (int i = 0; i < k; i++)
if (p1 != NULL)
p1 = p1->next;
else
return NULL;
p2 = pListHead;
while (p1!=NULL)
{
p1 = p1->next;
p2 = p2->next;
}
return p2;
}
};

反转链表

这里,pre相当于辅助用的头结点。

使用头插法反转链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
//注意,这个题是没有链表的头结点的。即是整个链表都要逆置。
//带头结点的链表,头结点往往存储链表的长度或者其他信息。带头结点的链表逆置的时候,头结点不动。
public:
ListNode* ReverseList(ListNode* pHead)
{
ListNode *pre = NULL, *next = NULL;
while (pHead!=NULL) //头插法
{
next = pHead->next;
pHead->next = pre;
pre = pHead;
pHead = next;
}
return pre;
}
};

合并两个排序的链表

非递归,循环版本

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
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode *res = NULL, *p = NULL;
if (pHead1 != NULL && pHead2 != NULL) //确定头
if (pHead1->val < pHead2->val)
{
res = pHead1;
pHead1 = pHead1->next;
}
else
{
res = pHead2;
pHead2 = pHead2->next;
}
else if (pHead1 != NULL)
{
res = pHead1;
pHead1 = pHead1->next;
}
else if (pHead2 != NULL)
{
res = pHead2;
pHead2 = pHead2->next;
}

p = res;
while (pHead1!=NULL&&pHead2!=NULL)
{
if (pHead1->val > pHead2->val)
{
p->next = pHead2;
pHead2 = pHead2->next;
p = p->next;
}
else
{
p->next = pHead1;
pHead1 = pHead1->next;
p = p->next;
}
}
if (pHead1 != NULL)
p->next = pHead1;
else if (pHead2 != NULL)
p->next = pHead2;

return res;
}
};

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* Merge2(ListNode* pHead1, ListNode* pHead2)
{
if (pHead1==NULL)
{
return pHead2;
}
if (pHead2==NULL)
{
return pHead1;
}
if (pHead1->val < pHead2->val)
{
pHead1->next = Merge2(pHead1->next, pHead2);
return pHead1;
}
else
{
pHead2->next = Merge2(pHead1, pHead2->next);
return pHead2;
}
}

添加辅助头结点的方法

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
class Solution2 {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode L(0); //添加辅助的头结点
ListNode *p = &L;
if (pHead1 == NULL)
return pHead2;
if (pHead2 == NULL)
return pHead1;
while (pHead1!=NULL&&pHead2!=NULL)
{
if (pHead1->val <= pHead2->val)
{
p->next = pHead1;
pHead1 = pHead1->next;
p = p->next;
}
else
{
p->next = pHead2;
pHead2 = pHead2->next;
p = p->next;
}
}
if (pHead1 == NULL)
p->next=pHead2;
if (pHead2 == NULL)
p->next = pHead1;
return L.next;
}
};

树的子结构

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
    class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
bool res = false;
if (pRoot1 == NULL || pRoot2 == NULL)
return false;
if (pRoot1->val == pRoot2->val)
res = judge(pRoot1, pRoot2);
if (!res)
res = HasSubtree(pRoot1->left, pRoot2); //找不到,搜左子树
if (!res)
res = HasSubtree(pRoot1->right, pRoot2); //找不到,搜右子树
return res;

}
bool judge(TreeNode* p1, TreeNode* p2)
{
if (p2 == NULL)
return true; //T2已经遍历完并且都能对的上,返回true
if (p1 == NULL)
return false; //T2还没有遍历完,但是T1已经没了,返回false
if (p1->val != p2->val)
return false; //值对不上,返回false。
return judge(p1->left, p2->left) && judge(p1->right, p2->right);
}
};

为了方便测试,我的构建树的代码为:

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
    struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};

TreeNode* T;


queue<TreeNode **>q;
void init(TreeNode*& T)
{
int n;
string temp;
cin >> n;
if (n == 0)
T = NULL;
TreeNode **ptr;
q.push(&T);
for (int i = 0; i < n; i++)
{
ptr = q.front();
q.pop();
cin >> temp;
if (temp != "null")
{
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = stoi(temp);
node->left = NULL;
node->right = NULL;
*ptr = node;
}
q.push(&(*ptr)->left);
q.push(&(*ptr)->right);
}
while (!q.empty())
{
q.pop();
}
return;
}

输入的时候按层输入,注意,这个代码是有bug的,不能生成任意一棵二叉树!想要完全序列化一棵二叉树,请看后面的序列二叉树。

二叉树的镜像

树的遍历,递归即可

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
void Mirror(TreeNode *pRoot)
{
if (pRoot == NULL)
return;
Mirror(pRoot->left);
Mirror(pRoot->right);
swap(pRoot->left, pRoot->right);
return;
}
};

包含min函数的栈

解法一(很挫的解法)

思路:利用Map的自动排序特性,很挫

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
class Solution {
public:
stack<int> s;
map<int, int>m;
//int minn=0x7FFFFFFF;
void push(int value)
{
s.push(value);
if (!m.count(value))
m[value] = 1;
else
m[value]++;
}
void pop()
{
int k = s.top();
s.pop();
if (--m[k] == 0)
m.erase(k);
}
int top()
{
return s.top();
}
int min()
{
return m.begin()->first;
}
};

利用最小元素栈

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
class Solution2 
{
//第二种方法。利用辅助栈
/*
压栈的时候,如果A栈的压入比B栈的大, 则B栈不压,如果小于等于,则AB栈同时压入/
在出栈的时候,如果AB栈顶元素不一样,则A出B不出。
*/
public:
stack<int> s1, s2;
void push(int value)
{
int t;
s1.push(value);
if (s2.empty())
s2.push(value);
else
{
t = s2.top();
if (value <= t)
s2.push(value);
}
}
void pop()
{
int t1 = s1.top(), t2 = s2.top();
if (t1 == t2)
{
s1.pop(); s2.pop();
}
else
s1.pop();
}
int top()
{
return s1.top();
}
int min()
{
return s2.top();
}
};

顺时针打印矩阵

解法一

不是特别好,利用模拟来做。

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
class Solution 
{
public:
vector<int> printMatrix(vector<vector<int> > matrix)
{
int i = 0, j = 0, a = 0, cnt = 0, total = 1;
vector<int>res;
total *= matrix.size();
if (total != 0)
total *= matrix[0].size();
while (cnt<total)
{
for (; j< matrix[i].size()-a; j++)
{
res.push_back(matrix[i][j]);
cnt++;
if (cnt >= total)
return res;
}
j--, i++;
for (; i < matrix.size()-a; i++)
{
res.push_back(matrix[i][j]);
cnt++;
if (cnt >= total)
return res;
}
i--; j--;
for (; j >=a; j--)
{
res.push_back(matrix[i][j]);
cnt++;
if (cnt >= total)
return res;
}
j++; i--; a++;
for ( ; i >a ; i--)
{
res.push_back(matrix[i][j]);
cnt++;
if (cnt >= total)
return res;
}
}
return res;
}
};

解法二

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
class Solution2 
{
/*解题思路:顺时针打印就是按圈数循环打印,一圈包含两行或者两列,
在打印的时候会出现某一圈中只包含一行,
要判断从左向右打印和从右向左打印的时候是否会出现重复打印,
同样只包含一列时,要判断从上向下打印和从下向上打印的时候是否会出现重复打印的情况*/

public:
vector<int> printMatrix(vector<vector<int> > matrix)
{
vector<int>res;
int row = matrix.size();
if (row == 0)
return res;
int collor = matrix[0].size();
int circle = ((row < collor ? row : collor) - 1) / 2 + 1;//圈数
for (int i = 0; i < circle; i++)
{
//从左向右打印
for (int j = i; j < collor-i; j++)
{
res.push_back(matrix[i][j]);
}
//从上往下的数据
for (int k = i+1; k < row- i; k++)
{
res.push_back(matrix[k][collor - 1 - i]);
}
//判断是否会重复打印(从右向左打印)
//row-i-1!=i是防止某一行曾经从左
//到右被输出,又在从右到左时被输出
for (int m = collor-i-2; (m>=i)&&(row-i-1!=i); m--)
{
res.push_back(matrix[row - i - 1][m]);
}
for (int n = row-i-2; (n>i)&&(collor-i-1!=i); n--)
{
res.push_back(matrix[n][i]);
}
}
return res;
}
};

栈的压入、弹出序列

添加辅助栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool IsPopOrder(vector<int> pushV, vector<int> popV)
{
if (pushV.size() == 0)
return false;
stack<int>s;
int j = 0;
for (int i = 0; i < pushV.size(); i++)
{
s.push(pushV[i]);
while (!s.empty()&&s.top() == popV[j])
{
s.pop();
j++;
}
}
return s.empty();
}
};

从上往下打印二叉树

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root)
{
queue<TreeNode*> q;
TreeNode* p;
vector<int> v;
if (root == NULL)
return v;
q.push(root);
while (!q.empty())
{
p = q.front(); q.pop();
if (p->left != NULL)
q.push(p->left);
if (p->right != NULL)
q.push(p->right);
v.push_back(p->val);
}
return v;
}
};

二叉树中和为某一值的路径

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
class Solution 
{
public:
vector<int> temp;
vector<vector<int>> res;
void dfs(TreeNode *root,int expectNumber)
{
temp.push_back(root->val);
if ((expectNumber == root->val)&&root->left == NULL && root->right == NULL)
res.push_back(temp);
if (root->left != NULL)
dfs(root->left, (expectNumber - root->val));
if (root->right != NULL)
dfs(root->right, expectNumber - root->val);
temp.pop_back();
return;
}
vector<vector<int>> FindPath(TreeNode* root, int expectNumber)
{
if (root == NULL)
return res; //边界条件
dfs(root, expectNumber);
return res;
}
};

复杂链表的复制

做法:

  1. 复制每个节点,如:复制节点A得到A1,将A1插入节点A后面
  2. 遍历链表,A1->random = A->random->next;注意这里是给复制节点的random赋值,整个复制链表里,不能出现原来链表的节点。
  3. 将链表拆分成原链表和复制后的链表。
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
class Solution 
{
public:
RandomListNode* Clone(RandomListNode* pHead)
{
if (!pHead) //若为空,返回NULL
return NULL;
RandomListNode* currNode=pHead,* newNode; //表示当前的节点
while (currNode!=NULL)
{
newNode= (RandomListNode *)malloc(sizeof(RandomListNode));
//复制节点信息
newNode->label = currNode->label;
newNode->next = currNode->next;
newNode->random = currNode->random;
//插到后面
currNode->next = newNode;
currNode = newNode->next;
}

currNode = pHead;

//第二次遍历
while (currNode!=NULL)
{
newNode = currNode->next;
if(currNode->random!=NULL)
newNode->random = currNode->random->next;
currNode = currNode->next->next;
}

//拆分
RandomListNode* pCloneHead = pHead->next,* temp;
currNode = pHead;
while (currNode->next!=NULL)
{
temp = currNode->next;
currNode->next = temp->next;
currNode = temp;
}
return pCloneHead;
}
};

二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

感觉像是二叉搜索树的线索化。

二叉搜索树与二叉排序树意思相同,定义如下:

二叉排序树/二叉查找树(Binary Search Tree),或者是一棵空树,或者是具有下列性质的二叉树:

若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

它的左、右子树也分别为二叉排序树。

解法一

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
class Solution			//循环写法
{
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if (pRootOfTree == NULL)
return NULL; //若为空,返回空
stack<TreeNode*> s;
TreeNode* p = pRootOfTree, *pre = NULL;
bool isFirst = true;
while (p!=NULL||!s.empty())
{
while (p!=NULL)
{
s.push(p);
p = p->left;
}
p = s.top(); s.pop();
if (isFirst)
{
pRootOfTree = p; //将中序遍历序列中的第一个节点记为root
pre = pRootOfTree;
isFirst = false;
}
else
{ //连接前后关系
pre->right = p;
p->left = pre;
pre = p;
}
p = p->right; //中序遍历,左中右,这个地方是处理右边的部分
}
return pRootOfTree;
}
};

解法二

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
class Solution2 
{
public:
TreeNode* Convert(TreeNode* pRootOfTree)
{
if (pRootOfTree == NULL)
return NULL;
TreeNode * pre = NULL;
trans(pRootOfTree, pre);
TreeNode* res = pRootOfTree;
while (res->left!=NULL)
{
res = res->left;
}
return res;
}


void trans(TreeNode * cur, TreeNode *&pre) //类似于树的左中右遍历
{
if (cur == NULL)
return;
trans(cur->left, pre);
cur->left = pre;
if (pre != NULL)
pre->right = cur;
pre = cur;
trans(cur->right, pre);
}
};

字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

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
class Solution {
public:
vector<string> res;
vector<string> Permutation(string str)
{
if (str != "")
dfs(str, 0); //从0开始DFS
return res;
}
void dfs(string str, int start)
{
int size = str.size();
if (start == size) //达到了压入vector的条件
{
res.push_back(str);
return;
}
for (int i = start; i < size; i++)
{
if (i != start && str[i] == str[start])
continue; //防止abb这种两个一样的
swap(str[i], str[start]);
dfs(str, start + 1);
}
}
};

数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

不能简单的用排序,因为如果出现次数不超过一半,要输出0.

时间复杂度为O(n)

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
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
int n = numbers.size();
if (n == 0)
return 0;
int num = numbers[0], cnt = 1;
for (int i = 1; i < n; i++)
{
if (numbers[i] == num)
cnt++;
else
cnt--;
if (cnt == 0) //如果cnt为0了,重新选择为当前数字,重新进行计数
{
num = numbers[i];
cnt = 1;
}
}

cnt = 0;
for (int i = 0; i < n; i++)
{
if (numbers[i] == num)
cnt++;
}
if (cnt * 2 > n)
return num;
else
return 0;

}
};

最小的K个数

解法一

偷懒的写法(这样也能过)时间复杂度O(n*lg n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
vector<int>res;
if (k > input.size())
return res;
res.resize(k);
sort(input.begin(), input.end());
for (int i = 0; i < k; i++)
{
res[i] = input[i];
}
return res;
}
};

解法二

第二种方法,参考快速排序的思想

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
class Solution {
public:
//第二种方法,参考快速排序的思想
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
vector<int>res;
if (k > input.size() || k <= 0)
return res;
res.resize(k);

int low = 0, high = input.size() - 1;
while (low < high)
{
int temp = partition(input, low, high);
if (temp == k)
break;
else if (high > k) //当前区间大于k
high = temp - 1;
else
low = temp + 1;
}

for (int i = 0; i < k; i++)
{
res[i] = input[i];
}
return res;
}

int partition(vector<int>&input, int low, int high)
{
int cur = input[low], i = low, j = high;
while (i<j)
{
while (j >i && input[j] >= cur)
j--;
while (i < j&&input[i] <= cur)
i++;
swap(input[i], input[j]);
}
swap(input[low], input[i]);
return i;
}

};

连续子数组的最大和

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)

时间复杂度O(n)

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
class Solution 
{
public:
int FindGreatestSumOfSubArray(vector<int> array)
{
int start, end, maxsum = 0xFFFFFFFF, tempsum = 0xFFFFFFFF, n = array.size(), tempstart;
if (n==0)
return 0;

for (int i = 0; i < n; i++)
{
if (tempsum < 0)
{
tempsum = array[i];
tempstart = i;
}
else
tempsum += array[i];
if (tempsum > maxsum)
{
maxsum = tempsum;
start = tempstart;
end = i;
}
}
return maxsum;

}
};

整数中1出现的次数(从1到n整数中1出现的次数)

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

思路分析:

设N = abcde ,其中abcde分别为十进制中各位上的数字。 如果要计算百位上1出现的次数,它要受到3方面的影响:百位上的数字,百位以下(低位)的数字,百位以上(高位)的数字。

① 如果百位上数字为0,百位上可能出现1的次数由更高位决定。比如:12013,则可以知道百位出现1的情况可能是:100~199,1100~1199,2100~2199,,…,11100~11199,一共1200个。可以看出是由更高位数字(12)决定,并且等于更高位数字(12)乘以 当前位数(100)。

② 如果百位上数字为1,百位上可能出现1的次数不仅受更高位影响还受低位影响。比如:12113,则可以知道百位受高位影响出现的情况是:100~199,1100~1199,2100~2199,,….,11100~11199,一共1200个。和上面情况一样,并且等于更高位数字(12)乘以 当前位数(100)。但同时它还受低位影响,百位出现1的情况是:12100~12113,一共114个,等于低位数字(113)+1。

③ 如果百位上数字大于1(2~9),则百位上出现1的情况仅由更高位决定,比如12213,则百位出现1的情况是:100~199,1100~1199,2100~2199,…,11100~11199,12100~12199,一共有1300个,并且等于更高位数字+1(12+1)乘以当前位数(100)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution 
{
public:
int NumberOf1Between1AndN_Solution(int n)
{
int cnt = 0;
for (int i = 1; i <= n; i*=10)
{
int a = n / i;
int b = n % i;
cnt += (a + 8) / 10 * i;
if (a % 10 == 1)
cnt += (b + 1);
}
return cnt;
}
};

把数组排成最小的数

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

可以看成是一个排序问题,在比较两个字符串 S1 和 S2 的大小时,应该比较的是 S1+S2 和 S2+S1 的大小,如果 S1+S2 < S2+S1,那么应该把 S1 排在前面,否则应该把 S2 排在前面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
static bool cmp(int a, int b)
{
string s1 = to_string(a), s2 = to_string(b);
string s3 = s1 + s2, s4 = s2 + s1;
if (s3 < s4)
return true;
else
return false;
}
string PrintMinNumber(vector<int> numbers)
{
if (numbers.size() == 0)
return "";
sort(numbers.begin(), numbers.end(),cmp);
string res;
for (auto i = numbers.begin(); i != numbers.end(); i++)
{
res += to_string(*i);
}
return res;
}
};

丑数

把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution 
{
public:
int GetUglyNumber_Solution(int index)
{
if (index < 7)
return index;
int p2 = 0, p3 = 0, p5 = 0, num = 1;
vector<int> res;
res.push_back(num);
while (res.size()<index)
{
num = min(res[p2] * 2, min(res[p3] * 3, res[p5] * 5));
if (res[p2] * 2 == num)
p2++;
if (res[p3] * 3 == num)
p3++;
if (res[p5] * 5 == num) //为了防止重复,这里必须是三个if
p5++;
res.push_back(num);
}
return num;
}
};

第一个只出现一次的字符

题目描述

在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).

两次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int FirstNotRepeatingChar(string str)
{
char s[256] = { 0 };
int n = str.length();
for (int i = 0; i < n; i++)
{
s[str[i]]++;
}
for (int i = 0; i < n; i++)
{
if (s[str[i]] == 1)
return i;
}
return -1;
}
};

两个链表的第一个公共结点

题目描述

输入两个链表,找出它们的第一个公共结点。

两次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution 
{
public:
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
{
ListNode* p1 = pHead1;
ListNode* p2 = pHead2;
if (p1 == NULL || p2 == NULL)
return NULL;
while (p1!=p2)
{
if (p1 == NULL)
p1 = pHead2;
else
p1 = p1->next;
if (p2 == NULL)
p2 = pHead1;
else
p2 = p2->next;
}
return p2;
}
};

数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。

二分法查找,因为数组中都是整数,所以可以考虑搜索num-0.5和num+0.5。

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
class Solution {
public:
int GetNumberOfK(vector<int> data, int k)
{
double temp1 = k - 0.5, temp2 = k + 0.5;
int res = binSearch(data, temp2) - binSearch(data, temp1);
return res;
}

int binSearch(vector<int> data, double num)
{
int start = 0, end = data.size() - 1;
int mid;
while (start<=end)
{
mid = (end - start) / 2 + start;
if (data[mid] < num)
start = mid + 1;
else if (data[mid] > num)
end = mid - 1;
}
return start;
}

};

二叉树的深度

题目描述

输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

经典的递归。

1
2
3
4
5
6
7
8
9
10
11
class Solution
{
public:
int TreeDepth(TreeNode* pRoot)
{
if (pRoot == NULL)
return 0;
else
return max(TreeDepth(pRoot->left) + 1, TreeDepth(pRoot->right) + 1);
}
};

平衡二叉树

题目描述

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

第一版代码(能AC,没有剪枝,借用上一题二叉树的深度的代码。

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
class Solution 
{
public:
bool IsBalanced_Solution(TreeNode* pRoot)
{
if (pRoot == NULL)
return true;

if (IsBalanced_Solution(pRoot->left) == false)
return false;
if (IsBalanced_Solution(pRoot->right) == false)
return false;
int leftDepth = TreeDepth(pRoot->left);
int rightDepth = TreeDepth(pRoot->right);
if (abs(leftDepth - rightDepth) > 1)
return false;
return true;
}
static int TreeDepth(TreeNode* pRoot)
{
if (pRoot == NULL)
return 0;
else
return max(TreeDepth(pRoot->left) + 1, TreeDepth(pRoot->right) + 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
class Solution 
{
public:
bool IsBalanced_Solution(TreeNode* pRoot)
{
if (pRoot == NULL)
return true;
if (TreeDepth(pRoot) == -1)
return false;
return true;
}
static int TreeDepth(TreeNode* pRoot)
{
if (pRoot == NULL) return 0;
int leftDepth = TreeDepth(pRoot->left);
if (leftDepth == -1)return -1;
int rightDepth = TreeDepth(pRoot->right);
if (rightDepth == -1) return -1;

if (abs(rightDepth - leftDepth) > 1)
return -1;
else
return max(rightDepth, leftDepth) + 1;
}
};

数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

如果这个题改成,一个整形只有一个数字出现了一次,可以使用异或来做,把这个数组里的所有数字进行异或。

原因是,相同的数异或结果为0。

首先我们考虑这个问题的一个简单版本:一个数组里除了一个数字之外,其他的数字都出现了两次。请写程序找出这个只出现一次的数字。

这个题目的突破口在哪里?题目为什么要强调有一个数字出现一次,其他的出现两次?我们想到了异或运算的性质:任何一个数字异或它自己都等于0 。也就是说,如果我们从头到尾依次异或数组中的每一个数字,那么最终的结果刚好是那个只出现一次的数字,因为那些出现两次的数字全部在异或中抵消掉了。

有了上面简单问题的解决方案之后,我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中,包含一个只出现一次的数字,而其它数字都出现两次。如果能够这样拆分原数组,按照前面的办法就是分别求出这两个只出现一次的数字了。

我们还是从头到尾依次异或数组中的每一个数字,那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其它数字都出现了两次,在异或中全部抵消掉了。由于这两个数字肯定不一样,那么这个异或结果肯定不为0 ,也就是说在这个结果数字的二进制表示中至少就有一位为1 。我们在结果数字中找到第一个为1 的位的位置,记为第N 位。现在我们以第N 位是不是1 为标准把原数组中的数字分成两个子数组,第一个子数组中每个数字的第N 位都为1 ,而第二个子数组的每个数字的第N 位都为0 。

现在我们已经把原数组分成了两个子数组,每个子数组都包含一个只出现一次的数字,而其它数字都出现了两次。因此到此为止,所有的问题我们都已经解决。

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
class Solution 
{
public:
void FindNumsAppearOnce(vector<int> data, int* num1, int *num2)
{
if (data.size() < 2) //异常情况
return;
int temp = 0,n=data.size();
for (int i = 0; i < n; i++) //所有的数,全部相互异或
{
temp = temp ^ data[i];
}
if (temp == 0)
return; //异常情况。
int first = 0;
while ((temp&1)==0) //找出第一位,数值不为0的
{
temp = temp >> 1; //右移一位
first++;
}
*num1 = 0; *num2 = 0;
for (int i = 0; i < n; i++)
{
if (isBit(data[i], first))
*num1 = *num1^data[i];
else
*num2 = *num2^data[i];
}
}

//判断某一位是不是1的函数
bool isBit(int num, int index)
{
num = num >> index;
return (num & 1);
}

};

和为S的连续正数序列

题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序。

这个题与 和为S的两个数字 类似,可以参考

方法是用滑动窗口去做。

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
class Solution 
{
public:
vector<vector<int> > FindContinuousSequence(int sum)
{
int start = 1, end = 2;
int cur;
vector<int>temp;
vector<vector<int>>res;
while (start < end)
{
cur = (start + end)*(end - start + 1) / 2;
if (cur > sum)
start++;
if (cur < sum)
end++;
if (cur == sum)
{
temp.clear();
for (int i = start; i <= end; i++)
{
temp.push_back(i);
}
start++;
res.push_back(temp);
}
}
return res;
}
};

和为S的两个数字

题目描述

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

输出描述:

对应每个测试案例,输出两个数,小的先输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution 
{
public:
vector<int> FindNumbersWithSum(vector<int> array, int sum)
{
int n = array.size();
vector<int>res;
int num1, num2 = n - 1;
for (num1=0; num1 < n; )
{
if (array[num1] + array[num2] > sum)
num2--;
if (array[num1] + array[num2] < sum)
num1++;
if(array[num1] + array[num2] == sum)
{
res.push_back(array[num1]);
res.push_back(array[num2]);
return res;
}
}
return res;
}
};

左旋转字符串

题目描述

汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution 
{
public:
string LeftRotateString(string str, int n)
{
int size = str.size();
if (size == 0)
return str;
n = n % size;
string res;
res += str.substr(n, size);
res += str.substr(0, n);
return res;
}
};

翻转单词顺序列

题目描述

牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

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
class Solution 
{
public:
string ReverseSentence(string str)
{
if (str.size() == 0)
return str;
string temp, res;
vector<string> v;
int end = str.size();
int i;
for (i = str.size()-1; i >= 0; i--)
{
if (str[i] == ' ')
{
temp.clear();
temp = str.substr(i + 1, end - i - 1);
temp += " ";
v.push_back(temp);
end = i;
}
}
temp = str.substr(0, end);
v.push_back(temp);

for (int j = 0; j < v.size(); j++)
{
res += v[j];
//cout << v[j];
}
return res;
}
};

扑克牌顺子

题目描述

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何, 如果牌能组成顺子就输出true,否则就输出false。为了方便起见,你可以认为大小王是0。

三个条件

  1. 最大-最小(不计0)<5;

  2. 没有重复

  3. 数组长度为5

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
class Solution
{

public:
/*三个条件:
1. 最大-最小(不计0)<5;
2. 没有重复
3. 数组长度为5
*/
bool IsContinuous(vector<int> numbers)
{
if (numbers.size() != 5)
return false;
int maxn, minn;
sort(numbers.begin(), numbers.end());
maxn = numbers[4];
for (int i = 0; i < 5; i++)
{
if (numbers[i] != 0)
{
minn = numbers[i];
break;
}
}
for (int i = 0; i < 4; i++)
{
if (numbers[i] == 0)
continue;
if (numbers[i] == numbers[i + 1])
return false;
}
if ((maxn - minn) >= 5)
return false;
return true;
}
};

求1+2+3+…+n

求1+2+3+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

解法一

1
2
3
4
5
6
7
8
9
10
class Solution 
{
public:
int Sum_Solution(int n)
{
int ans = n;
ans && (ans += Sum_Solution(n - 1)); //当ans=0时发生短路
return ans;
}
};

解法二

利用pow

1
2
3
4
5
6
7
8
9
10
11
class Solution2 
{
public:
int Sum_Solution(int n)
{
int a = pow(n,2);
a += n;
a=a >> 1;
return a;
}
};

把二叉树打印成多行

题目描述

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

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
class Solution 
{
public:
vector<vector<int> > Print(TreeNode* pRoot)
{
vector<vector<int>>res;
vector<int>temp;
TreeNode* p;
if (pRoot == NULL)
return res;
queue<TreeNode*>q1, q2;
q1.push(pRoot);
bool flag = false;
while ((!q1.empty()) || (!q2.empty()))
{
temp.clear();
flag = false;
while (!q1.empty())
{
p = q1.front(); q1.pop();
temp.push_back(p->val);
flag = true;
if (p->left != NULL)
q2.push(p->left);
if (p->right != NULL)
q2.push(p->right);
}
if(flag)
res.push_back(temp);
temp.clear();
flag = false;
while (!q2.empty())
{
p = q2.front(); q2.pop();
temp.push_back(p->val);
flag = true;
if (p->left != NULL)
q1.push(p->left);
if (p->right != NULL)
q1.push(p->right);
}
if (flag)
res.push_back(temp);
}
return res;
}
};

删除链表中重复的结点

题目描述

在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

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
class Solution 
{
public:
ListNode* deleteDuplication(ListNode* pHead)
{
if (pHead == NULL)
return NULL;
ListNode* T = new ListNode(-1);
T->next = pHead;
ListNode* pre = T, *cur=pHead, *next;
while (cur!=NULL&&cur->next!=NULL)
{
next = cur->next;
if (cur->val==next->val)
{
while (next != NULL && cur->val == next->val) //一直往下找
next = next->next;
pre->next = next;
cur = next;
}
else
{
pre = cur;
cur = next;
}
}
return T->next;
}
};

二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

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
class Solution 
{
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if (pNode == NULL)
return NULL;
TreeLinkNode *res = pNode;
if (pNode->right!=NULL)
{
res = pNode->right;
while (res->left != NULL)
res = res->left;
return res;
}
while (res->next!=NULL)
{
if (res == res->next->left) //如果当前节点是其父节点的左孩子
return res->next;
if (res == res->next->right)
res = res->next;
}
return NULL;
}
};

二叉搜索树的第k个结点

题目描述

给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution
{
public:
TreeNode* KthNode(TreeNode* pRoot, int k)
{
TreeNode*res = NULL;
if (pRoot == NULL)
return NULL;
res = KthNode(pRoot->left, k);
if (res != NULL)
return res;
cnt++;
if (this->cnt == k)
return pRoot;
res = KthNode(pRoot->right, k);
if (res != NULL)
return res;
return NULL;
}
int cnt = 0;
};

数据流中的中位数

题目描述

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

类似题目:PAT-A-1057

使用multiset维护两个multiset upper和lower。

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
class Solution 
{
public:
void Insert(int num)
{
if (num > mid)
upper.insert(num);
else
lower.insert(num);
adjust();
}

double GetMedian()
{
if (upper.size() == lower.size())
return(((*upper.begin()) + (*lower.begin())) / 2.0);
else
return *lower.begin();
}
void adjust()
{
if (upper.size() > lower.size())
{
lower.insert(*upper.begin());
upper.erase(upper.begin());
}
else if (lower.size()>upper.size()+1)
{
upper.insert(*lower.begin());
lower.erase(*lower.begin());
}
mid = *lower.begin();
}
private:
multiset<int> upper;
multiset<int, greater<int>>lower;
int mid = 0;
};

滑动窗口的最大值

题目描述

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,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
class Solution 
{
public:
//第一种方法:维护一个max
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
int maxID = 0;
vector<int>res;
if (size == 0 || size > num.size())
return res;
for (int i = 0; i < size; i++)
if (num[maxID] < num[i])
maxID = i;
res.push_back(num[maxID]); //第一个
for (int i = 1; i < num.size()-size+1; i++)
{
if (num[i + size - 1] > num[maxID])
maxID = i + size - 1;
if (i > maxID) //超过滑动窗口的范围了
{
maxID = i;
for (int j = 0; j < size; j++)
{
if (num[j + i] > num[maxID])
maxID = j + i;
}
}
res.push_back(num[maxID]);
}
return res;
}
};

解法二

使用双边队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution 
{
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int>res;
deque<int>q; //双边队列
for (int i = 0; i < num.size(); i++)
{
while (q.size() != 0 && num[q.back()] <= num[i])
q.pop_back();
if (q.size() != 0 && i - q.front() + 1 > size)
q.pop_front();
q.push_back(i);
if (size != 0 && i + 1 >= size)
res.push_back(num[q.front()]);
}
return res;
}
};

数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

开一个长度为n的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution 
{
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication)
{
vector<int>v(length);
for (int i = 0; i < length; i++)
{
if (v[numbers[i]]++ != 0)
{
*duplication = numbers[i];
return true;
}
}
return false;
}
};

构建乘积数组

题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]A[i-1]A[i+1]A[n-1]。不能使用除法。

思路分析:

<分析>:

解释下代码,设有数组大小为5。

对于第一个for循环

第一步:b[0] = 1;

第二步:b[1] = b[0] * a[0] = a[0]

第三步:b[2] = b[1] a[1] = a[0] a[1];

第四步:b[3] = b[2] a[2] = a[0] a[1] * a[2];

第五步:b[4] = b[3] a[3] = a[0] a[1] a[2] a[3];

然后对于第二个for循环

第一步

temp *= a[4] = a[4];

b[3] = b[3] temp = a[0] a[1] a[2] a[4];

第二步

temp = a[3] = a[4] a[3];

b[2] = b[2] temp = a[0] a[1] a[4] a[3];

第三步

temp = a[2] = a[4] a[3] * a[2];

b[1] = b[1] temp = a[0] a[4] a[3] a[2];

第四步

temp = a[1] = a[4] a[3] a[2] a[1];

b[0] = b[0] temp = a[4] a[3] a[2] a[1];

由此可以看出从b[4]到b[0]均已经得到正确计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution 
{
public:
vector<int> multiply(const vector<int>& A)
{
vector<int>b(A.size());
if (A.size() == 0)
return b;
b[0] = 1;
for (int i = 0; i < A.size()-1; i++)
b[i + 1] = b[i]*A[i];
int temp = 1;
for (int i = A.size()-1; i >= 0; i--)
{
b[i] = b[i] * temp;
temp *= A[i];
}
return b;
}
};

字符流中第一个不重复的字符

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符”go”时,第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时,第一个只出现一次的字符是”l”。

输出描述:

如果当前字符流没有存在出现一次的字符,返回#字符。

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//时间复杂度为O(n)的解法
class Solution
{
public:
//Insert one char from stringstream
void Insert(char ch)
{
s += ch;
cnt[ch]++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
for (int i = 0; i < s.size(); i++)
{
if (cnt[s[i]] == 1)
return s[i];
}
return '#';
}
private:
char cnt[260] = { 0 };
string s;
};

解法二

现说明为什么是O(1),其实判断部分在Insert部分已经完成。

由于最多是有128个ascii码,所以队列的长度最大为128.故限定在了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
//时间复杂度为O(1)的解法
class Solution2
{
public:
//Insert one char from stringstream
void Insert(char ch)
{
cnt[ch]++;
if (cnt[ch] == 1)
q.push(ch);
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
while (!q.empty() && cnt[q.front()] != 1)
q.pop();
if (!q.empty())
return q.front();
return '#';
}
private:
char cnt[260] = { 0 };
queue<char> q;
};

链表中环的入口结点

题目描述

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

这个题不仅仅是要判断是否有环,而且还说,如果有环,找出环的入口点。

判断有没有环可以用快慢指针。

分析:

1557257019018

假设x为环前面的路程(黑色路程),a为环入口到相遇点的路程(蓝色路程,假设顺时针走), c为环的长度(蓝色+橙色路程)

当快慢指针相遇的时候:

此时慢指针走的路程为Sslow = x + m * c + a

快指针走的路程为Sfast = x + n * c + a

2 *slow = fast

2 * ( x + m*c + a ) = (x + n *c + a)

从而可以推导出:

x = (n - 2 * m )*c - a

= (n - 2 *m -1 )*c + c - a

即环前面的路程 = 数个环的长度(为可能为0) + c - a

什么是c - a?这是相遇点后,环后面部分的路程。(橙色路程)

所以,我们可以让一个指针从起点A开始走,让一个指针从相遇点B开始继续往后走,

2个指针速度一样,那么,当从原点的指针走到环入口点的时候(此时刚好走了x)

从相遇点开始走的那个指针也一定刚好到达环入口点。

所以2者会相遇,且恰好相遇在环的入口点。

最后,判断是否有环,且找环的算法复杂度为:

时间复杂度:O(n)

空间复杂度:O(1)

一共三种方法,第一个是前文所述。

第二个是断链法,只有在有环的时候才成立,没有环则有错误。

第三个方法是存储地址法,使用set存储地址。如果出现了一个曾经出现过的地址,表示有环,且是环的起始点。

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
class Solution 
{
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if (pHead == NULL || pHead->next == NULL || pHead->next->next == NULL)
return NULL;
//先判断有没有环
ListNode* fast = pHead->next->next, *slow = pHead->next;
while (fast!=slow)
{
if (fast->next != NULL && fast->next->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
}
else
return NULL; //表示没有环,返回
}
//循环跳出,就表示有环,且此时,fast=slow
fast = pHead;
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
//循环跳出表示在环的起始点了,且此时fast=slow
return fast;
}


//断链法。适用于一定有环的情况。如果没有环,则会有错误。牛客的测试数据不严谨,这个是能AC的
ListNode* EntryNodeOfLoop2(ListNode* pHead)
{
if (pHead == NULL || pHead->next == NULL)
return NULL;
ListNode* fast = pHead->next, *slow = pHead;
while (fast!=NULL)
{
slow->next = NULL; //断开
slow = fast;
fast = fast->next;
}
return slow;
}

//存地址法,把曾经出现过的地址用set存储,如果出现了一个曾经出现过的地址,表示有环,且是环的起始点
ListNode* EntryNodeOfLoop3(ListNode* pHead)
{
set<ListNode*> s;
while (pHead != NULL && (!s.count(pHead))) //判断当前节点是否曾出现过
{
s.insert(pHead);
pHead = pHead->next;
}
if (pHead == NULL)
return NULL;
else
return pHead;
}
};

按之字形顺序打印二叉树

题目描述

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

解法一

用两个队列,本质上是层次遍历,只不过在偶数层部分,reverse之后再存入。这个还是比较好理解的

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
class Solution
{
public:
vector<vector<int> > Print(TreeNode* pRoot)
{
vector<vector<int>>res;
vector<int> v;
if (pRoot == NULL)
return res;
TreeNode* cur=pRoot;
q1.push(cur);
while (!q1.empty()||!q2.empty())
{
while (!q1.empty())
{
cur = q1.front(); q1.pop();
v.push_back(cur->val);
if (cur->left != NULL)
q2.push(cur->left);
if (cur->right != NULL)
q2.push(cur->right);
}
res.push_back(v);
v.clear();
while (!q2.empty())
{
cur = q2.front(); q2.pop();
v.push_back(cur->val);
if (cur->left != NULL)
q1.push(cur->left);
if (cur->right != NULL)
q1.push(cur->right);
}
if (v.size() != 0)
{
reverse(v.begin(), v.end());
res.push_back(v);
v.clear();
}

}
return res;
}
private:
//q1从左往右,q2从右向左
queue<TreeNode*> q1, q2;
};

解法二

(我感觉比较难理解,这个是我面阿里的时候做出来的,很难理解,用一个stack和一个queue,stack用于翻转)

好处是省去了reverse环节,不过一个reverse也没多少时间,写的是真TM难懂,我自己回过头来看自己都看不明白了。

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
class Solution2 
{
public:
vector<vector<int> > Print(TreeNode* pRoot)
{
vector<vector<int>>res;
vector<int> v;
if (pRoot == NULL)
return res;
que.push(pRoot);
L1:
while (!que.empty())
{
p = que.front(); que.pop();
sta.push(p);
v.push_back(p->val);
//cout << p->val; //访问了
}
res.push_back(v);
v.clear();
flag = !flag;
while (!sta.empty())
{
p = sta.top(); sta.pop();
if (flag == 0)
{
if (p->right != NULL)
que.push(p->right);
if (p->left != NULL)
que.push(p->left);
}
else
{
if (p->left != NULL)
que.push(p->left);
if (p->right != NULL)
que.push(p->right);
}
}
if (sta.empty() && que.empty())
return res;
else
goto L1;
}
private:
bool flag = 1; //1表示从左往右
queue<TreeNode*>que;
stack<TreeNode*>sta;
TreeNode* p;
};

解法三

使用栈,可以不用reverse

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
class Solution3 
{
public:
vector<vector<int> > Print(TreeNode* pRoot)
{
vector<vector<int>>res;
vector<int> v;
if (pRoot == NULL)
return res;
TreeNode* cur = pRoot;
s1.push(cur);
while (!s1.empty()||!s2.empty())
{
while (!s1.empty())
{
cur = s1.top(); s1.pop();
v.push_back(cur->val);
if (cur->left != NULL)
s2.push(cur->left);
if (cur->right != NULL)
s2.push(cur->right);
}
res.push_back(v);
v.clear();
while (!s2.empty())
{
cur = s2.top(); s2.pop();
v.push_back(cur->val);
if (cur->right != NULL)
s1.push(cur->right);
if (cur->left != NULL)
s1.push(cur->left);
}
if (v.size() != 0)
{
res.push_back(v);
v.clear();
}
}

return res;
}
private:
stack<TreeNode*>s1, s2;
};

解法四

使用一个队列,使用reverse

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
//使用一个队列,然后再使用reverse
class Solution4
{
public:
vector<vector<int> > Print(TreeNode* pRoot)
{
vector<vector<int>>res;
vector<int> v;
if (pRoot == NULL)
return res;
TreeNode* cur = pRoot;
q.push(cur);
int size;
while (!q.empty())
{
v.clear();
size = q.size();
for (int i = 0; i < size; i++)
{
cur = q.front(); q.pop();
v.push_back(cur->val);
if (cur->left != NULL)
q.push(cur->left);
if (cur->right != NULL)
q.push(cur->right);
}
if (flag)
reverse(v.begin(), v.end());
res.push_back(v);
flag = !flag;
}
return res;
}
private:
queue<TreeNode*> q;
bool flag = false;
};

对称的二叉树

题目描述

请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

递归算法:

左右孩子的值相等。且左右子树必须同时为空。

由于只是这棵树的对称,所以左孩子的右子树同右孩子的左子树成镜像。

左孩子的左子树同右孩子的右子树成镜像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution 
{
public:
bool isSymmetrical(TreeNode* pRoot)
{
if (pRoot == NULL)
return true;
return check(pRoot->left, pRoot->right);
}

bool check(TreeNode* left, TreeNode* right)
{
if (left == NULL) //左孩子为空,则右孩子也要为空
return right == NULL;
if (right == NULL)
return false;
if (left->val != right->val)
return false;
return check(left->right, right->left) && check(left->left, right->right);
}
};

序列化二叉树

题目描述

请实现两个函数,分别用来序列化和反序列化二叉树

序列化二叉树就是把二叉树以某种顺序存起来,可以是前序,可以是中序,后续,也可以是层次遍历。

题目中给的返回类型是char*类型,不满足我们的需求,所以需要强制类型转换一下。

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
class Solution 
{
public:
vector<int>buf;
void encode(TreeNode* cur)
{
if (cur == NULL)
buf.push_back(0xFFFFF);
else
{
buf.push_back(cur->val);
encode(cur->left);
encode(cur->right);
}
}
TreeNode* decode(int* &p)
{
if (*p==0xFFFFF)
{
++p;
return NULL;
}
TreeNode* res = new TreeNode(*p);
p++;
res->left = decode(p);
res->right = decode(p);
return res;
}
char* Serialize(TreeNode *root)
{
buf.clear();
encode(root);
int *res = new int[buf.size()];
for (int i = 0; i < buf.size(); i++)
res[i] = buf[i];
return (char*)res;
}
TreeNode* Deserialize(char *str)
{
int *p = (int*)str;
return decode(p);
}
};

唯一确定一棵二叉树的时候,必须要知道前序/后续+中序,只知道前序+后序是不可以的。

但是在序列化二叉树的时候,给出了空节点的信息,所以可以根据前序来唯一确定一棵二叉树。

彩蛋

1
2
3
4
5
6
7
8
9
10
11
12
typedef TreeNode* pnode;
class Solution {
pnode hehe;
public:
char* Serialize(TreeNode *root) {
hehe = root;
return "(*^_^*)";
}
TreeNode* Deserialize(char *str) {
return hehe;
}
};

不用加减乘除做加法

  1. 两个数异或:相当于每一位相加,而不考虑进位;
  2. 两个数相与,并左移一位:相当于求得进位;
  3. 将上述两步的结果相加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
int Add(int num1, int num2)
{
while (num2 != 0)
{
int sum = num1 ^ num2;
int carray = (num1 & num2) << 1;
num1 = sum;
num2 = carray;
}
return num1;
}
};

彩蛋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
int add(int a, int b)
{
_asm
{
MOV EAX, a
MOV ECX, b
ADD EAX, ECX
MOV a, EAX
}
return a;
}
};