0%

发表于

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

若数组中存在数k，则其所在行左侧的数小于等于k，右侧的数大于等于k，其所在列上方的数小于等于k，下方的数大于等于k。故若存在k，自数组的左下角开始查找，若当前数小于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
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        const int w = array.begin()->size();
        const int h = array.size();
        int x = w - 1, y = 0;
        while (x >= 0 && y <= h - 1)
        {
            if (array[y][x] > target)
            {
                x--;
            }
            else if (array[y][x] == target)
            {
                return true;
            }
            else
            {
                y++;
            }
        }
        return false;
    }
};

发表于

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

对斐波那契数列，我们有

an=an−1+an−2a_n = a_{n-1} + a_{n-2}

考虑矩阵乘法，我们有

[ab00]×[1110]=[a+ba00]\begin{bmatrix} a & b \\ 0 & 0 \\ \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} a + b & a \\ 0 & 0 \\ \end{bmatrix}

故

[an+1an00]=[anan−100]×[1110]=[1110]n\begin{bmatrix} a_{n+1} & a_n \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} a_n & a_{n-1} \\ 0 & 0 \\ \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} ^n

最后引入快速幂，即

[an+1an00]=[1110]n=([1110]⌊n2⌋)2×[1110]n%2\begin{bmatrix} a_{n+1} & a_n \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} ^n = ( \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} ^{\lfloor \frac{n}{2} \rfloor}) ^2 \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix} ^{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
class Solution {
public:
    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];
    }
    int Fibonacci(int n) {
        if (n == 0)
        {
            return 0;
        }
        if (n == 1)
        {
            return 1;
        }
        else
        {
            int base[] = {1, 1, 1, 0}, r[4] = {1, 1, 1, 0};
            n -= 2;
            while (n)
            {
                if (n & 1)
                {
                    times(r, base);
                }
                times(base, base);
                n >>= 1;
            }
            return r[0];
        }
    }
};

发表于

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

可知该数组由分别不减的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
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <limits>

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if (*rotateArray.begin() < *rotateArray.rbegin())
        {
            return rotateArray[0];
        }
        else
        {
            const int size = rotateArray.size();
            if (size == 0)
            {
                return 0;
            }
            else
            {
                int left = 0, right = size - 1;
                int i = size / 2;
                while (left < right - 1)
                {
                    if (rotateArray[i] > rotateArray[left])
                    {
                        left = i;
                        i += (right - left) / 2;
                    }
                    else if (rotateArray[i] == rotateArray[left])
                    {
                        if (rotateArray[i] > rotateArray[right])
                        {
                            left = i;
                            i += (right - left) / 2;
                        }
                        else
                        {
                            return fallback(rotateArray);
                        }
                    }
                    else
                    {
                        right = i;
                        i -= (right - left) / 2;
                    }
                }
                return rotateArray[right];
            }
        }
    }
    int fallback(vector<int> &rotateArray) {
        int last = numeric_limits<int>::max();
        for (const int v : rotateArray)
        {
            if (v < last)
            {
                last = v;
            }
        }
        return last;
    }
};

发表于

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

考虑到每将一个空格替换后，即需要将后续字符后移，并整体扩充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
class Solution {
public:
	void replaceSpace(char *str,int length) {
        char *src = str, *dst = str;
        for (; *src != '\0'; src++)
        {
            if (*src == ' ')
            {
                dst += 3;
            }
            else
            {
                dst++;
            }
        }
        for (; src >= str; src--)
        {
            const char temp = *src;
            if (temp == ' ')
            {
                *dst = '0';
                dst --;
                *dst = '2';
                dst --;
                *dst = '%';
                dst--;
            }
            else
            {
                *dst = temp;
                dst--;
            }
        }
	}
};

发表于

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

栈为先入后出，队列为先出后入，我们将全部入栈再全部出栈视为函数X，将全部入队再全部出队视为函数Y，则Y(seq)=X(X(seq))。故可使用2个栈，入队时将元素压入栈a，出队时将栈a中的元素全部弹出并压入栈b，再从栈b出栈。

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 push(int node) {
        stack1.push(node);
    }

    int pop() {
        int result;
        if (stack2.size() > 0)
        {
            result = stack2.top();
            stack2.pop();
        }
        else
        {
            if (stack1.size() == 0)
            {
                result = -1;
            }
            else
            {
                while (stack1.size() > 0)
                {
                    stack2.push(stack1.top());
                    stack1.pop();
                }
                result = stack2.top();
                stack2.pop();
            }
        }
        return result;
    }

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

发表于

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

可知设a[n]为n级台阶的跳法，则a[n+1] = a[n] + a[n-1]。

令

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

有

[a[n+1]a[n]00]=[a[n]a[n−1]00]×A=[2100]×An−1\begin{bmatrix} a[n+1] & a[n] \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} a[n] & a[n-1] \\ 0 & 0 \\ \end{bmatrix} \times A = \begin{bmatrix} 2 & 1 \\ 0 & 0 \\ \end{bmatrix} \times A ^{n-1}

考虑快速幂，有

An=(A⌊n2⌋)2×An%2A^n = (A^{\lfloor \frac{n}{2} \rfloor})^2 \times A^{n\%2}

故

[a[n+1]a[n]00]=[2100]×(A⌊n−12⌋)2×A(n−1)%2\begin{bmatrix} a[n+1] & a[n] \\ 0 & 0 \\ \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 0 & 0 \\ \end{bmatrix} \times (A^{\lfloor \frac{n-1}{2} \rfloor})^2 \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
47
48
49
50
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 jumpFloor(int n)
    {
        if (n == 1)
        {
            return 1;
        }
        if (n == 2)
        {
            return 2;
        }
        else
        {
            int m[4] = {2, 1, 0, 0};
            cal_a(n - 1);
            times(m, a_n);
            return m[0];
        }
    }
};

发表于

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

可知中序遍历序列的首位为根节点，而中序遍历的序列中，根节点分隔左、右子树，故可在中序遍历的序列中查找根节点，即得到表示左、右子树的序列，递归至序列长度不大于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
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        TreeNode *root = nullptr;
        if (pre.size() == 0)
        {
            root = nullptr;
        }
        else
        {
            const int root_val = pre[0];
            auto it = vin.begin();
            int left_size = 0;
            root = new TreeNode(root_val);
            while (*it != root_val)
            {
                it++;
                left_size++;
            }
            root->left = reConstructBinaryTree(
                vector<int>(pre.begin() + 1, pre.begin() + left_size + 1),
                vector<int>(vin.begin(), it));
            root->right = reConstructBinaryTree(
                vector<int>(pre.begin() + 1 + left_size, pre.end()),
                vector<int>(it + 1, vin.end()));
        }
        return root;
    }
};

发表于 更新于

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

找规律，2、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
class Solution {
public:
    int cutRope(int number) {
        if (number < 1)
        {
            return 0;
        }
        else if (number == 2)
        {
            return 1;
        }
        else if (number == 3)
        {
            return 2;
        }
        else
        {
            int quotient = number / 3;
            int remainder = number % 3;
            switch (remainder)
            {
            case 0:
                return pow(3, quotient);
            case 1:
                return pow(3, quotient - 1) * 4;
            case 2:
                return pow(3, quotient) * 2;
            }
        }
    }
};

发表于 更新于

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

回溯，DFS/BFS

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
const int xMove[] = {0, 1, 0, -1};
const int yMove[] = {-1, 0, 1, 0};

class Solution {
public:
    int getSum(int n)
    {
        int sum = 0;
        while (n > 0)
        {
            int left = n / 10;
            sum += n - 10 * left;
            n = left;
        }
        return sum;
    }
    int movingCount(int threshold, int rows, int cols)
    {
        if (threshold <= 0 || rows < 1 || cols < 1)
        {
            return 0;
        }
        else
        {
            bool isAdded[127][127] = {false};
            int area = 1;
            int xRoute[65535], yRoute[65535];
            int peak = 0;
            xRoute[0] = 0;
            yRoute[0] = 0;
            isAdded[0][0] = true;
            while (peak >= 0)
            {
                int x = xRoute[peak];
                int y = yRoute[peak];
                peak--;
                for (int i = 0; i < 4; i++)
                {
                    x += xMove[i];
                    y += yMove[i];
                    if (x >= 0 && x < cols && y >= 0 && y < rows && getSum(x) + getSum(y) <= threshold && !isAdded[x][y])
                    {
                        isAdded[x][y] = true;
                        peak++;
                        xRoute[peak] = x;
                        yRoute[peak] = y;
                        area++;
                    }
                    x -= xMove[i];
                    y -= yMove[i];
                }
            }
            return area;
        }
    }
};

发表于 更新于

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

回溯，格子的状态（未访问、已向上等），防撞（非未访问则回退）

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
98
99
100
101
102
103
class Solution {
public:
    int _width;
    char _state[65535]{0};
    int xRoute[65535], yRoute[65535];
    int x, y;
    inline char *state()
    {
        return &_state[y * _width + x];
    }
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        const int size = rows * cols;
        _width = cols;
        for (int startY = 0; startY < rows; startY++)
        {
            for (int startX = 0; startX < cols; startX++)
            {
                x = startX;
                y = startY;
                bool isFailed = false;
                char *nextChar = str;
                while (!isFailed && *nextChar != '\0')
                {
                    if (y >= 0 && y < rows && x >=0 && x < cols)
                    {
                        switch (*state())
                        {
                        case 0:
                            if (matrix[y * _width + x] == *nextChar)
                            {
                                nextChar++;
                                xRoute[nextChar - str] = x;
                                yRoute[nextChar - str] = y;
                                *state() = 1;
                                y--;
                            }
                            else
                            {
                                if (nextChar == str)
                                {
                                    isFailed = true;
                                }
                                else
                                {
                                    x = xRoute[nextChar - str];
                                    y = yRoute[nextChar - str];
                                }
                            }
                            break;
                        case 1:
                            *state() = 2;
                            x++;
                            break;
                        case 2:
                            *state() = 3;
                            y++;
                            break;
                        case 3:
                            *state() = 4;
                            x--;
                            break;
                        case 4:
                            if (nextChar == str + 1)
                            {
                                isFailed = true;
                                *state() = 0;
                            }
                            else
                            {
                                nextChar--;
                                *state() = 0;
                                x = xRoute[nextChar - str];
                                y = yRoute[nextChar - str];
                                continue;
                            }
                            break;
                        }
                        if (*state() != 0)
                        {
                            x = xRoute[nextChar - str];
                            y = yRoute[nextChar - str];
                        }
                    }
                    else
                    {
                        x = xRoute[nextChar - str];
                        y = yRoute[nextChar - str];
                    }
                }
                if (isFailed)
                {
                    continue;
                }
                else
                {
                    return true;
                }
            }
        }
        return false;
    }
};