0%

输入一个链表,输出该链表中倒数第k个结点。

快慢指针,快指针先走k步。

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
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if (pListHead == nullptr || k == 0)
{
return nullptr;
}
else
{
ListNode *left = pListHead, *right = pListHead;
while (k > 1)
{
if (right->next == nullptr)
{
left = nullptr;
break;
}
else
{
right = right->next;
}
k--;
}
while (right->next != nullptr)
{
right = right->next;
left = left->next;
}
return left;
}
}
};

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

  1. 空间换时间。开新数组,第一次遍历放入奇数,第二次遍历放入偶数。
  2. 自左向右找到偶数a,再以从偶数开始,继续找到奇数b,将区间[a, b)内的偶数右移1位,将奇数b移至a原来的位置上。循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
void reOrderArray(vector<int> &array) {
bool changed = true;
const int size = array.size();
for (int i = 0; i < size - 1 && changed; i++)
{
changed = false;
for (int j = 0; j < size - 1 - i; j++)
{
if (((array[j] & 1) == 0) && ((array[j + 1] & 1) == 1))
{
changed = true;
array[j] ^= array[j + 1] ^= array[j] ^= array[j + 1];
}
}
}
}
};

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为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
39
40
41
42
43
44
45
46
47
class Solution {
public:
double Power(double base, int exponent) {
bool need_reverse = false;
if (exponent < 0)
{
exponent = - exponent;
need_reverse = true;
}
if (exponent == 0)
{
return 1;
}
else if (exponent == 1)
{
if (need_reverse)
{
return 1 / base;
}
else
{
return base;
}
}
else
{
double res = 1;
while (exponent)
{
if (exponent & 1)
{
res *= base;
}
base *= base;
exponent >>= 1;
}
if (need_reverse)
{
return 1 / res;
}
else
{
return res;
}
}
}
};

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

f(n)f(n)n1的个数。若n0n \ne 0,则在n-1中,n中最右边的1被置为0,而该1的左侧的1保持不变,故

f(n)=f((n1)&n)+1f(n) = f((n-1)\& n) + 1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int NumberOf1(int n) {
int c = 0;
while (n)
{
c++;
n &= (n - 1);
}
return c;
}
};

我们可以用2×12\times 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2×12\times 1的小矩形无重叠地覆盖一个2×n2\times n的大矩形,总共有多少种方法?

2×n2\times n的大矩形可以用dp[n]个小矩形覆盖,而2×n2\times n的大矩形有2×(n1)2\times (n-1)的大矩形和一个小矩形,以及2×(n2)2\times (n-2)的大矩形和2个小矩形覆盖,共2种情况,故

dp[n]=dp[n1]+dp[n2]dp[n]=dp[n-1]+dp[n-2]

类比斐波那契数列和跳台阶,有令

A=[1110]A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}

[dp[n+1]dp[n]00]=[dp[n]dp[n1]00]×A\begin{bmatrix} dp[n+1] & dp[n] \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} dp[n] & dp[n-1] \\ 0 & 0 \\ \end{bmatrix} \times A

[dp[2]dp[1]00]=[2100]\begin{bmatrix} dp[2] & dp[1] \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 0 & 0 \\ \end{bmatrix}

[dp[n+1]dp[n]00]=[2100]×An1=[2100]×An12×A(n1)%2\begin{bmatrix} dp[n+1] & dp[n] \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 0 & 0 \\ \end{bmatrix} \times A^{n-1} = \begin{bmatrix} 2 & 1 \\ 0 & 0 \\ \end{bmatrix} \times A^{\lfloor \frac{n-1}{2} \rfloor} \times A^{(n-1) \% 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
class Solution {
public:
int base[4] = {1, 1, 1, 0}, a_n[4] = {1, 1, 1, 0};
void times(int a[4], int b[4])
{
int r[4] = {
a[0] * b[0] + a[1] * b[2],
a[0] * b[1] + a[1] * b[3],
a[2] * b[0] + a[3] * b[2],
a[2] * b[1] + a[3] * b[3]};
a[0] = r[0];
a[1] = r[1];
a[2] = r[2];
a[3] = r[3];
}
void cal_a(int n)
{
if (n > 1)
{
n -= 2;
while (n)
{
if (n & 1)
{
times(a_n, base);
}
times(base, base);
n >>= 1;
}
}
}
int rectCover(int n)
{
if (n <= 2)
{
return n;
}
else
{
int m[4] = {2, 1, 0, 0};
cal_a(n - 1);
times(m, a_n);
return m[0];
}
}
};

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

令跳若干步跳上第n级台阶有dp[n]种跳法,则

dp[n]=i=1n1dp[i]=i=1n2dp[i]+dp[n1]dp[n]=\sum_{i=1}^{n-1}dp[i]=\sum_{i=1}^{n-2}dp[i]+dp[n-1]

dp[n1]=i=1n2dp[i]dp[n-1]=\sum_{i=1}^{n-2}dp[i]

dp[n]=2×dp[n]dp[n]=2\times dp[n]

dp[1]=1,故

dp[n]=2n1dp[n]=2^{n-1}

考虑位运算,代码如下:

1
2
3
4
5
6
class Solution {
public:
int jumpFloorII(int number) {
return 1 << number - 1;
}
};