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)为n中1的个数。若n≠0n \ne 0，则在n-1中，n中最右边的1被置为0，而该1的左侧的1保持不变，故

f(n)=f((n−1)&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×(n−1)2\times (n-1)的大矩形和一个小矩形，以及2×(n−2)2\times (n-2)的大矩形和2个小矩形覆盖，共2种情况，故

dp[n]=dp[n−1]+dp[n−2]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[n−1]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]×An−1=[2100]×A⌊n−12⌋×A(n−1)%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=1n−1dp[i]=∑i=1n−2dp[i]+dp[n−1]dp[n]=\sum_{i=1}^{n-1}dp[i]=\sum_{i=1}^{n-2}dp[i]+dp[n-1]

而

dp[n−1]=∑i=1n−2dp[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]=2n−1dp[n]=2^{n-1}

考虑位运算，代码如下：

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