Eric's Blogs

Better Code, Better Life

0%

发表于 分类于
本文字数： 2.7k 阅读时长 ≈ 2 分钟

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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
public ArrayList<Integer> maxInWindows(int[] num, int size) {
    LinkedList<Integer> list = new LinkedList<>();
    ArrayList<Integer> arrayList = new ArrayList<>();
    if (size <= 0 || size > num.length) {
        return arrayList;
    }
    for (int i = 0; i < size; i++) {
        list.add(num[i]);
    }
    Collections.sort(list);
    arrayList.add(list.getLast());

    for (int i = 1; i <= num.length - size; i++) {//窗口前移
        list.remove(new Integer(num[i - 1]));
        list.add(num[i + size - 1]);
        Collections.sort(list);
        arrayList.add(list.getLast());
    }
    return arrayList;
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/1624bc35a45c42c0bc17d17fa0cba788?answerType=1&f=discussion
来源：牛客网

方法一：暴力方法

根据题目描述，我们很容易想到暴力方法。并且也很轻松的就可以写出来。如果数组的大小是n，窗口的大小是size，那么窗口的数量就是 n - size + 1.
算法步骤如下：

  • 枚举每个窗口的左边界 i
  • 根据窗口的左边界i可以对应计算出右边界j
  • 遍历窗口，计算出最大值

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> ret;
        if (num.size() == 0 || size < 1 || num.size() < size) return ret;
        int n = num.size();

        for (int i = 0; i + size - 1 < n; ++i) {
            int j = i + size - 1;
            int max_val = num[j];
            for (int k = i; k < j; ++k) {
                max_val = max(max_val, num[k]);
            }
            ret.push_back(max_val);
        }
        return ret;
    }
};

时间复杂度：O(n*k), 其中n为数组大小，k为窗口大小
空间复杂度：O(1)，存结果必须要开的数组不算入额外空间

方法二：单调队列

方法一种存在很多大量重复计算，比如说，对于数组，假设我们当前遍历到下标i，对于下标i+1的元素（假设i和i+1都在同一个窗口），如果比arr[i]大，说明了什么？
如果arr[i+1] 已经大于了 arr[i], 那么还要arr[i]有什么用.就有点“既生瑜何生亮”的感觉。
如果arr[i+1] < arr[i]呢？显然arr[i]还是需要保留的。为什么呢？
因为又可以arr[i] 对于下一个arr[i+1]所在的窗口来说，arr[i]已经失效了。

假设这里有那么一个容器可以保留上述操作。

  1. 遍历数组的每一个元素，
  2. 如果容器为空，则直接将当前元素加入到容器中。
  3. 如果容器不为空，则让当前元素和容器的最后一个元素比较，如果大于，则将容器的最后一个元素删除，然后继续讲当前元素和容器的最后一个元素比较
  4. 如果当前元素小于容器的最后一个元素，则直接将当前元素加入到容器的末尾
  5. 如果容器头部的元素已经不属于当前窗口的边界，则应该将头部元素删除

总结一下，首先容器中放的元素应该是单调递减的。然后还有删除容器头部元素和最后一个元素的操作。因此，这样的数据结构就是双端队列。c++中就是deque

如何判断队列中头部的元素是否过期呢？
这里我们可以存数组的下标，根据下标的比较来判断。比如，当前遍历到下标为5的元素，窗口的大小为3， 显然显然下标为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
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> ret;
        if (num.size() == 0 || size < 1 || num.size() < size) return ret;
        int n = num.size();
           deque<int> dq;
           for (int i = 0; i < n; ++i) {
               while (!dq.empty() && num[dq.back()] < num[i]) {
                   dq.pop_back();
               }
               dq.push_back(i);
               // 判断队列的头部的下标是否过期
               if (dq.front() + size <= i) {
                   dq.pop_front();
            }
            // 判断是否形成了窗口
               if (i + 1 >= size) {
                   ret.push_back(num[dq.front()]);
               }
           }
           return ret; 
    }
};

时间复杂度：O(n), 其中n为数组大小
空间复杂度：O(k)，k为窗口的大小

发表于 分类于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如

1
2
3
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
char[] mat, str;
int X, Y;

class P {
    int x, y;
    char c;

    public P(int x, int y) {
        this.x = x;
        this.y = y;
        if (x < 0 || y < 0 || x >= X || y >= Y) {
            c = ' ';
        } else {
            this.c = mat[Y * x + y];
        }
    }

    @Override
    public boolean equals(Object obj) {
        return x == ((P) obj).x && y == ((P) obj).y;
    }

    @Override
    public int hashCode() {
        int i = Integer.valueOf(x + "" + y);
        return i;
    }
}

public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
    mat = matrix;
    this.str = str;
    X = rows;
    Y = cols;
    List<P> list = findFirst(str[0]);
    for (P p : list) {
        if (findPath(p)) {
            return true;
        }
    }
    return false;
}

Set<P> set = new HashSet<>();
boolean ok = false;

private boolean findPath(P p) {
    ok = false;
    set.clear();
    dfs(p, 0);
    if (ok) {
        return true;
    } else {
        return false;
    }
}

private void dfs(P p, int i) {

    if (ok || p.c == ' ' || set.contains(p)) {
        return;
    }
    if (p.c == str[i]) {
        if (i == str.length - 1) {/** 路径找到了 */
            ok = true;
            return;
        }
        set.add(p);
        dfs(new P(p.x + 1, p.y), i + 1);
        dfs(new P(p.x - 1, p.y), i + 1);
        dfs(new P(p.x, p.y + 1), i + 1);
        dfs(new P(p.x, p.y - 1), i + 1);
    }
}

private List<P> findFirst(char c) {
    List<P> list = new ArrayList<>();
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < Y; j++) {
            P p = new P(i, j);
            if (p.c == c) {
                list.add(p);
            }
        }
    }
    return list;
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc?answerType=1&f=discussion
来源：牛客网

方法：DFS

这道题大家都知道是DFS的题，关键是怎么可以快速并且正确的写出，是本题解讨论的重点。
首先解释一下递归函数。
递归函数：就是当前处理的问题是什么，并且下一次在规模减小的情况下处理相同的问题。
比如此题：当前处理的问题是：判断字符串str[0 … len]是否在mat中匹配，显然下一次递归处理的问题是:如果str[0]已经匹配，则判断字符串str[1 … len]是否在mat中匹配。

这里先给出一个我认为比较清晰的DFS模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dfs(){

    // 第一步，检查下标是否满足条件

    // 第二步：检查是否被访问过，或者是否满足当前匹配条件

    // 第三步：检查是否满足返回结果条件

    // 第四步：都没有返回，说明应该进行下一步递归
    // 标记
    dfs(下一次)
    // 回溯
}  


main() {
    for (对所有可能情况) {
        dfs()
    }
}

上面每步的顺序都不能颠倒。

所以，对于这道题来说，首先dfs()的参数是什么，返回值是什么。
可以像这样：

1
2
3
// i, j 表示mat中的位置， pos表示当前正在匹配的字符串str的下标
// 成功返回整个字符串str, 则返回true, 否则返回false
bool dfs(int i, int j, int pos, char *str);

主函数该怎么写？可以像如下这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 几个全局变量，便于程序的简洁，只是在刷题中建议
char *mat = 0;
int h = 0, w = 0;
int str_len = 0;
int dir[5] = {-1, 0, 1, 0, -1};
bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        mat = matrix;
        h = rows, w = cols;
         str_len = strlen(str);

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(i, j, 0, str)) {
                    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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    char *mat = 0;
    int h = 0, w = 0;
    int str_len = 0;
    int dir[5] = {-1, 0, 1, 0, -1};

    bool dfs(int i, int j, int pos, char *str) {
        // 因为dfs调用前，没有进行边界检查，
        // 所以需要第一步进行边界检查，
        // 因为后面需要访问mat中元素，不能越界访问
        if (i < 0 || i >= h || j < 0 || j >= w) {
            return false;
        }

        char ch = mat[i * w + j];
        // 判断是否访问过
        // 如果没有访问过，判断是否和字符串str[pos]匹配
        if (ch == '#' || ch != str[pos]) {
            return false;
        }

         // 如果匹配，判断是否匹配到最后一个字符
        if (pos + 1  == str_len) {
            return true;
        }

        // 说明当前字符成功匹配，标记一下，下次不能再次进入
        mat[i * w + j] = '#';
        for (int k = 0; k < 4; ++k) {
            if (dfs(i + dir[k], j + dir[k + 1], pos + 1, str)) {
                return true;
            }
        } 
        // 如果4个方向都无法匹配 str[pos + 1]
        // 则回溯， 将'#' 还原成 ch          
        mat[i * w + j] = ch;
        // 说明此次匹配是不成功的
        return false;   
    }
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        mat = matrix;
        h = rows, w = cols;
         str_len = strlen(str);

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(i, j, 0, str)) {
                    return true;
                }
            }
        }
        return false;
    }
};

时间复杂度：O(3^k)， 每个位置除当前自己的方向，还有3个方向可以展开。k为str的长度
空间复杂度：O(k), 最大递归栈的深度为k

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

题目描述

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

解答

dfs遍历即可

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
/**
 * 用来判断是否访问过
 */
Set<String> set = new HashSet<>();
int X, Y, max;
int count = 0;

public int movingCount(int threshold, int rows, int cols) {

    X = rows;
    Y = cols;
    max = threshold;

    dfs(0, 0);
    return count;
}

private void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= X || y >= Y) {
        return;
    }
    String id = x + "," + y;
    if (set.contains(id)) {
        return;
    } else {
        set.add(id);
    }
    char[] xs = String.valueOf(x).toCharArray();
    char[] ys = String.valueOf(y).toCharArray();
    int xc = 0, yc = 0;
    for (char c : xs) {
        xc += (c - '0');
    }
    for (char c : ys) {
        yc += (c - '0');
    }
    if (xc + yc > max) {
        return;
    }
    count++;
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y - 1);
    dfs(x, y + 1);
}

官方解答

链接：https://www.nowcoder.com/questionTerminal/6e5207314b5241fb83f2329e89fdecc8?answerType=1&f=discussion
来源：牛客网

方法一：DFS遍历

根据题目描述，我们可以模拟题目，我们假设一个5x5矩阵，阈值sho=3，如果我们用DFS的话，就相当于“不撞南墙不回头”，我在下面画了一个图，

最开始，我们在(0,0)的位置，我们假设按照{右，下，左，上}的方向去试探。所以我们走的顺序应该是按照图中的下标走的。
当走到4的时候，发现不能往继续往右边走，并且4个方向都走不通了，那就回溯到3,发现可以走到5，接着就站在5的视角，发现可以走6，就一直按照这个想法。

本题的递归函数就是：首先站在(0,0)的视角，先往右试探，发现可以走，就以下一个为视角，继续做相同的事情。
递归函数模板为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
dfs(){

    // 第一步，检查下标

    // 第二步：检查是否被访问过，或者是否满足当前匹配条件

    // 第三步：检查是否满足返回结果条件

    // 第四步：都没有返回，说明应该进行下一步递归
    // 标记
    dfs(下一次)
    // 回溯
}  
int main() {
    dfs(0, 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
48
49
50
class Solution {

public:
    using V = vector<int>;
    using VV = vector<V>;    
    int dir[5] = {-1, 0, 1, 0, -1};

    int check(int n) {
        int sum = 0;

        while (n) {
            sum += (n % 10);
            n /= 10;
        }

        return sum;
    }

    void dfs(int x, int y, int sho, int r, int c, int &ret, VV &mark) {
        // 检查下标 和 是否访问
        if (x < 0 || x >= r || y < 0 || y >= c || mark[x][y] == 1) {
            return;
        }
        // 检查当前坐标是否满足条件
        if (check(x) + check(y) > sho) {
            return;
        }
        // 代码走到这里，说明当前坐标符合条件
        mark[x][y] = 1;
        ret += 1;

        for (int i = 0; i < 4; ++i) {
            dfs(x + dir[i], y + dir[i + 1], sho, r, c, ret, mark);
        }



    } 
    int movingCount(int sho, int rows, int cols)
    {
        if (sho <= 0) {
            return 0;
        }

        VV mark(rows, V(cols, -1));
        int ret = 0;
        dfs(0, 0, sho, rows, cols, ret, mark);
        return ret;
    }
};

时间复杂度：O(mn)， m,n为矩阵大小，每个元素最多访问过一次
空间复杂度：O(mn)

方法二：BFS遍历

当前图的遍历算法还有bBFS，所以也可以用BFS做。方法一实例的图，用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
class Solution {
public:
    using pii = pair<int,int>;
    int dir[5] = {-1, 0, 1, 0, -1};
    int check(int n) {
        int sum = 0;

        while (n) {
            sum += (n % 10);
            n /= 10;
        }

        return sum;
    }
    int movingCount(int sho, int rows, int cols)
    {
        if (sho <= 0) {
            return 0;
        }

        int ret = 0;
        int mark[rows][cols];
        memset(mark, -1, sizeof(mark));
        queue<pii> q;
        q.push({0, 0});
        mark[0][0] = 1;


        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            // 每次保证进队列的都是满足条件的坐标
            ++ret;

            for (int i = 0; i < 4; ++i) {
                int x = node.first + dir[i];
                int y = node.second + dir[i + 1];

                if (x >= 0 && x < rows && y >= 0 && y < cols && mark[x][y] == -1) {
                    if (check(x) + check(y) <= sho) {
                        q.push({x, y});
                        mark[x][y] = 1;
                    }
                }
            }
        }

        return ret;
    }
};

时间复杂度：O(mn)， m,n为矩阵大小，每个元素最多访问过一次
空间复杂度：O(mn)

发表于 分类于
本文字数： 3.4k 阅读时长 ≈ 3 分钟

题目描述

给你一根长度为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。

输入描述:

1
输入一个数n，意义见题面。（2 <= n <= 60）

输出描述:

1
输出答案。

示例1

输入

1
8

输出

1
18

解答

得到最大值的m值是距离sqrt(target)最近的两个整数.讨论这两种情况即可.

数学证明待补充

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
public int cutRope(int target) {
    if (target <= 3) {
        return target - 1;
    }
    int m = (int) Math.floor(Math.sqrt(target));

    int k1 = target / m, mult1 = 1;
    int i = 0;
    for (; i < m - 1; i++) {
        mult1 *= k1;
    }
    int remain = target - k1 * i;
    mult1 *= remain;

    m++;
    int k2 = (target / m) + 1, mult2 = 1;
    for (i = 1; i * k2 <= target; i++) {
        mult2 *= k2;
    }
    remain = target - k2 * i;
    if (remain != 0) {
        mult2 *= remain;
    }
    return mult1 > mult2 ? mult1 : mult2;
}

官方题解

链接：https://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8?answerType=1&f=discussion
来源：牛客网

题目描述：给定一个长度为n的绳子，将其分成m段（m>1）,求m段的乘积最大。
转化成数学上的描述：给定一个数n，求n = a1 + a2 … +am, （m>1）在此条件下, s = a1 * a2 * … * am， s最大

进入此题的讲解之前，先提出一个问题：什么样的题适合用动态规划？
针对本题来说，假如我们用暴力枚举的思路去思考，会出现以下一些问题：

  1. 这段绳子到底应该分几段，才能得到最优的结果？
  2. 假设我已经知道了要分m段（假设m已知），那么每段的长度又应该是多少呢？

可能你的问题不止上面2个。但是，仅仅是上面两个问题，已经让我感觉要分好多种情况，然后选出一个最优的。

当然，普通的for循环枚举所有情况是有难度的，但是幸运的是，我们可以用递归回溯。
所以，方法一如下：

方法一：暴力递归

暴力递归就要想到递归三部曲：

  1. 递归函数的设计和功能：back_track(n); 含义是：求长度为n的数，最后分段后的最大乘积，这里我们不需要关心分成多少段
  2. 递归函数的终止条件: 如果n <= 4, 显然back_track(n) = n，初始条件也就是我们不用计算就能得到的。
  3. 下一步递归：对于长度n，我们需要减少递归参数n，如果第一段为1， 显然下一步递归为back_track(n-1),如果第一段为2， 则下一步递归为
    back_track(n-2)…因为要至少分2段，所以，最后一次可能的情况为最后一段为n-1, 下一步递归为back_track(1)，因此，每一步可能的结果为
    1 * back_track(n-1), 2 * back_track(n-2), …, (n-1) * back_track(1),在n-1种情况中取一个最大值即可。 这里我们不用关系back_track(n-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:
    int back_track(int n) {
        // n <= 4, 表明不分，长度是最大的
        if (n <= 4) {
            return n;
        }

        int ret = 0;
        for (int i = 1; i < n; ++i) {
            ret = max(ret, i * back_track(n - i));
        }
        return ret;
    }
    int cutRope(int number) {
        // number = 2 和 3 时，分 2 段和分 1 段的结果是不一样的，所以需要特判一下
        if (number == 2) {
            return 1;
        }
        else if (number == 3) {
            return 2;
        }
        return back_track(number);
    }
};

时间复杂度：O(n!)
空间复杂度：O(n), 最多分n段，每段长度为1， 所以递归深度为n

方法二：记忆化递归

根据方法一，假设求back_track(7)，如下图：
图片说明
我用f() 替代 back_track(),可知，红色的部分重复了。
因此，我们可以开一个数组，把计算过的结果存起来。
步骤如下：

  • 初始化一个大小为 n+1 的数组，初始值为 -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
    class Solution {
    public:
      int back_track(int n, vector<int> &mark) {
          if (n <= 4) {
              return n;
          }
          // 在方法一的基础上添加
          if (mark[n] != -1) {
              return mark[n];
          }

          int ret = 0;
          for (int i = 1; i < n; ++i) {
              ret = max(ret, i * back_track(n - i));
          }
          // 添加部分
          return mark[n] = ret;
      }
      int cutRope(int number) {
          if (number == 2) {
              return 1;
          }
          else if (number == 3) {
              return 2;
          }
          // 添加部分
          vector<int> mark(number, -1);
          return back_track(numberm, mark);
      }
    };

    时间复杂度：O(n^2)
    空间复杂度：O(n)

方法三：动态规划

有的书上认为方法二是一种递归版本的动态规划。
所以，我们可以将方法二修改为迭代版本的动态规划。

代码如下：

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:
    int cutRope(int number) {
        if (number == 2) {
            return 1;
        }
        else if (number == 3) {
            return 2;
        }

        vector<int> f(number + 1, -1);
        for (int i = 1; i <= 4; ++i) {
            f[i] = i;
        }
        for (int i = 5; i <= number; ++i) {
            for (int j = 1; j < i; ++j) {
                f[i] = max(f[i], j * f[i - j]);
            }
        }
        return f[number];
    }
};

时间复杂度：O(n^2)
空间复杂度：O(n)

总的来说，方法一是基础。方法二，方法三都是在方法一的基础上修改的。

Q:接下来，我们就可以开篇的问题了，什么样的题适合用动态规划？
A：一般，动态规划有以下几种分类：

  1. 最值型动态规划，比如求最大，最小值是多少
  2. 计数型动态规划，比如换硬币，有多少种换法
  3. 坐标型动态规划，比如在m*n矩阵求最值型，计数型，一般是二维矩阵
  4. 区间型动态规划，比如在区间中求最值

其实，根据此题的启发，我们可以换种想法，就是什么样的题适合用暴力递归？
显然就是，可能的情况很多，需要枚举所有种情况。只不过动态规划，只记录子结构中最优的解。

发表于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目描述

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

解答

快慢指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode EntryNodeOfLoop(ListNode pHead) {
    if (pHead == null || pHead.next == null || pHead.next.next == null) {
        return null;
    }
    ListNode slow = pHead.next, fast = pHead.next.next;
    while (fast != null) {
        if (slow == fast) {
            break;
        }
        slow = slow.next;
        if (fast.next == null) {
            return null;
        } else {
            fast = fast.next.next;
        }
    }
    fast = pHead;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4?answerType=1&f=discussion
来源：牛客网

方法一：哈希法

  1. 遍历单链表的每个结点

  2. 如果当前结点地址没有出现在set中，则存入set中

  3. 否则，出现在set中，则当前结点就是环的入口结点

  4. 整个单链表遍历完，若没出现在set中，则不存在环

    代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        unordered_set<ListNode*> st;
        while (pHead) {
            if (st.find(pHead) == st.end()) {
                st.insert(pHead);
                pHead = pHead->next;
            }
            else {
                return pHead;
            }
        }
        return nullptr;
    }
};

时间复杂度：O(n)
空间复杂度：O(n)，最坏情况下，单链表的所有结点都在存入set

方法二：双指针法

若不用辅助结构set，该怎么做呢？这里画了一张图

  1. 初始化：快指针fast指向头结点， 慢指针slow指向头结点
  2. 让fast一次走两步， slow一次走一步，第一次相遇在C处，停止
  3. 然后让fast指向头结点，slow原地不动，让后fast，slow每次走一步，当再次相遇，就是入口结点。
    如上解释：

    如果慢指针slow第一次走到了B点处，距离C点处还有距离Y，那么fast指针应该停留在D点处，且BD距离为Y（图中所示是假设快指针走了一圈就相遇，为了便于分析），
    也就是DB+BC=2Y，（因为fast一次走2步，慢指针一次走1步，并且相遇在C处）
    在C点处，此时慢指针slow走的点为ABC，距离为X+Y，而快指针fast走的点为ABCDBC，距离为2X+2Y，
    又因为：AB=X，BC=Y，快指针走了2次BC，所以CDB距离为X，而AB距离也为X。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode *fast = pHead;
        ListNode *slow = pHead;
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        if (!fast || !fast->next) return nullptr;
        fast = pHead;
        while (fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

发表于 分类于
本文字数： 955 阅读时长 ≈ 1 分钟

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

解答

1
2
3
4
5
6
7
8
public int Add(int num1, int num2) {
    while (num2 != 0) {//当进位为零时停止
        int c = (num1 & num2) << 1;//进位需要左移一次
        num1 = num1 ^ num2;
        num2 = c;
    }
    return num1;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/59ac416b4b944300b617d4f7f111b215?answerType=1&f=discussion
来源：牛客网

方法：位运算

知识补充：

  1. 按位与&，按位或|， 按位异或^
    图片说明
  2. 补码
    计算机中存整数n是用补码存的。
  • 如果n为正数，则原码=反码=补码
  • 如果n为负数，则补码=反码+1

本题是考察对位运算的运用，使用位运算来实现两数的加法。
设两数字的二进制形式 a，b ，其求和 s = a + b ，a(i) 代表 a 的二进制第 i 位，则分为以下四种情况：
图片说明

观察发现，无进位和运算就是按位异或结果，进位就是与运算结果但是需要左移一位，因为进位影响下一位的运算。
所以s = a + b,其实就是无进位和+进位的结果。
算法步骤：

  1. 计算a和b的无进位和，和进位
  2. 如果进位不为0，则说明a+b的结果等于无进位和+进位，此时，把无进位和作为a，进位作为b，继续计算
  3. 如果进位等于0， 说明此时a+b的结果就等于无进位和，返回无进位和即可。
    如图：
    图片说明

Q：你可能有疑问，如果是一个数为负数或者两个数都为负数怎么办？
A：上述补码的介绍，补码就是解决减法的问题，计算机把减法看做加法来运算。
所以代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int Add(int num1, int num2)
    {
        while (num2 != 0) {
            // 负数左移会在低位补1，所以转化为无符号整数
            int c = ((unsigned int)(num1 & num2)) << 1; 
            num1 ^= num2;
            num2 = c;
        }
        return num1;
    }
};

时间复杂度：O(1)
空间复杂度：O(1)

发表于 分类于
本文字数： 664 阅读时长 ≈ 1 分钟

题目描述

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

输出描述:

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

解答

等差数列公式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();

    for (int i = (int) Math.pow(2 * sum, 0.5); i > 1; i--) {
        int t = (2 * sum / i - i + 1);
        if (t % 2 != 0 || 2 * sum % i != 0) {
            continue;
        }
        ArrayList<Integer> tl = new ArrayList<>();
        t = t >> 1;
        for (int j = 0; j < i; j++) {
            tl.add(t + j);
        }
        ans.add(tl);
    }
    return ans;
}

发表于 分类于
本文字数： 637 阅读时长 ≈ 1 分钟

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表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
public ListNode deleteDuplication(ListNode pHead) {
    if (pHead == null) {
        return null;
    }
    ListNode p, pHeadAns = null, ptail = null;
    for (p = pHead; p != null; ) {
        int count = 0;//与p.val相等的节点数
        ListNode pp;
        for (pp = p; pp != null && pp.val == p.val; pp = pp.next) {
            count++;
        }
        if (count == 1) {//待加入新链表
            if (pHeadAns == null) {
                pHeadAns = p;//待返回的头结点
            } else {
                ptail.next = p;
            }
            ptail = p;//新链表当前的尾结点
            ptail.next = null;
        }
        //删除(跳过)连续的相等节点
        p = pp;
    }
    return pHeadAns;
}

发表于 分类于
本文字数： 522 阅读时长 ≈ 1 分钟

题目描述

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

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

解答

还有优化空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean IsBalanced_Solution(TreeNode root) {
    if (root == null) {
        return true;
    }
    int left = deepth(root.left) + 1;
    int right = deepth(root.right) + 1;

    return Math.abs(left - right) <= 1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}

private int deepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = deepth(root.left) + 1;
    int right = deepth(root.right) + 1;

    return Math.max(left, right);
}

发表于 分类于
本文字数： 582 阅读时长 ≈ 1 分钟

题目描述

牛客最近来了一个新员工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
public String ReverseSentence(String str) {
    if (str == null ) {
        return "";
    }
    if (str.trim().equals("")) {
        return str;//没有说明，只能试，有点坑
    }
    String[] strings = str.split(" ");

    StringBuilder builder = new StringBuilder(str.length());
    for (int i = strings.length - 1; i >= 0; i--) {
        builder.append(" ");
        builder.append(strings[i]);
    }
    return builder.toString().substring(1);
}