算法

每日leetcode-面试题51

面试题51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

解答

（已经发布在了中文leetcode网站

和官方解答里面一样，使用了归并排序的方法，在这个过程中添加了对应的逆序对的个数。

  • 用归并排序
  • 归并的时候，我们可以检测逆序对有多少个
  • 比如现在要归并【1,3,6,19】和【2,9,10,20】
    • 那么我们可以看到逆序数是：
    • 3和2，6和2，19和2,9,10
    • 如果是有两个指针，前一个指针需要移动的时候需要记录一下上一个数字。
    • 下面用一个例子说明，两个数字分别代表两个指针指向的数：
      • 1 2，之后移动了第一个指针，第二个指针的index是0（也就是1比后面几个大）
      • 3 2，之后移动第二个
      • 3 9，之后移动第一个，第二个指针的index是1（也就是3比后面几个大）
      • 6 9，之后移动第一个，第二个指针的index是1（也就是6比后面几个大）
      • 19 9，移动第二个
      • 19 10，移动第二个
      • 19 20，移动第一个，第二个指针的index是3（也就是19比后面几个大）
    • 这样我们把这几个数字对应的逆序对的个数都找到了！加起来就好了！
  • 如果是【1,3,6,19,90】和【2,9,10,20,30】，这时候到最后会发现两个指针分别指向90和结束的位置，这时候把第一个数组后面的元素加进来，一直加上第二个指针的index（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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    int merge_sort(vector<int>& nums, vector<int>& aux, int start, int end) {
        if (start >= end) {
            return 0;
        }
        int ans = 0;
        int mid = (end + start) / 2;
        ans += merge_sort(nums, aux, start, mid);
        ans += merge_sort(nums, aux, mid + 1, end);
        // merge
        int index1 = start;
        int index2 = mid + 1;
        int tar = start;
        while (index1 <= mid && index2 <= end) {
            if (nums[index1] <= nums[index2]) {
                // 移动第一个指针，这时候记录一下第二个指针指向的数字
                ans += index2 - mid - 1;
                aux[tar++] = nums[index1++];
            }
            else {
                aux[tar++] = nums[index2++];
            }
        }
        while (index1 <= mid) {
            ans += index2 - mid - 1;
            aux[tar++] = nums[index1++];
        }
        while (index2 <= end) {
            aux[tar++] = nums[index2++];
        }
        for (int i = start; i <= end; i++) {
            nums[i] = aux[i];
        }
        return ans;
    }

    int reversePairs(vector<int>& nums) {
        // 用归并排序
        // 归并的时候，我们可以检测逆序对有多少个
        // 比如现在要归并【1,3,6,19】和【2,9,10,20】
        // 那么我们可以看到逆序数是：
        // 3和2，6和2，19和2,9,10
        // 如果是有两个指针，前一个指针需要移动的时候需要记录一下上一个数字。
        // 下面用一个例子说明，两个数字分别代表两个指针指向的数：
          // 1 2，之后移动了第一个指针，第二个指针的index是0（也就是1比后面几个大）
          // 3 2，之后移动第二个
          // 3 9，之后移动第一个，第二个指针的index是1（也就是3比后面几个大）
          // 6 9，之后移动第一个，第二个指针的index是1（也就是6比后面几个大）
          // 19 9，移动第二个
          // 19 10，移动第二个
          // 19 20，移动第一个，第二个指针的index是3（也就是19比后面几个大）
        // 这样我们把这几个数字对应的逆序对的个数都找到了！加起来就好了！
        // 如果是【1,3,6,19,90】和【2,9,10,20,30】，这时候到最后会发现两个指针分别指向90和结束的位置，这时候把第一个数组后面的元素加进来，一直加上第二个指针的index（5，这时候指向空）就可以了。
        int len = nums.size();
        vector<int> aux(len, 0);
        return merge_sort(nums, aux, 0, len - 1);
    }
};
算法

每日leetcode-面试题-08-11

面试题 08.11. 硬币

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例1:

输入: n = 5
输出：2
解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例2:

输入: n = 10
输出：4
解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

说明：

注意:

你可以假设：

  • 0 <= n (总金额) <= 1000000

解法

这个和官方题解里面的方法一类似，但是有一点差别。

官方题解里面，最后得到的是：

$$f(i,v)=f(i−1,v)+f(i,v−c_i)$$

举例来说，如果我想要用4种硬币（分别是1、5、10、25）来凑成100分，那我可以先算出来用3种硬币（1、5、10）凑成100分的方法，再算出来用4种硬币（1、5、10、25）凑成75分的方法数，把他们加起来。

这样的好处是，我们可以只用前面$i-1$的数据算出来$i$的数据，就不用存所有行了。

我这里的解法稍微差一些，是记录了四个数组，分别表示：最大用了1分、最大用了5分、最大用了10分、最大用了25分的前提下的种类数。

如果我想要用4种硬币（分别是1、5、10、25）来凑成100分，那我可以先算出来：

  • 用最大为25的硬币（也就是说，用了4种硬币（1、5、10、25）并且必须有25）凑成75分的方法；
  • 用最大为10的硬币（也就是说，用了3种硬币（1、5、10）并且必须有10）凑成75分的方法；
  • 用最大为5的硬币（也就是说，用了2种硬币（1、5）并且必须有5）凑成75分的方法；
  • 用最大为1的硬币（也就是说，用了1种硬币（1）并且必须有1）凑成75分的方法。

最后加起来就是总的方法数。

不如csx大佬的官方题解，但是也是正确的做法。

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 waysToChange(int n) {
        if (n == 0) {
            return 1;
        }
        vector<int> dp_max_1(n + 1, 1);
        vector<int> dp_max_5(n + 1, 0);  // 必须有至少一个5
        vector<int> dp_max_10(n + 1, 0);
        vector<int> dp_max_25(n + 1, 0);
        for (int i = 5; i <= n; i++) {
            dp_max_5[i] = (dp_max_1[i - 5] + dp_max_5[i - 5]) % 1000000007;  // use one 5, will get dp_max_1[i - 5]; use two 5s, dp_max_5[i - 5]
        }
        for (int i = 10; i <= n; i++) {
            dp_max_10[i] = (dp_max_1[i - 10] + dp_max_5[i - 10] + dp_max_10[i - 10]) % 1000000007;
        }
        for (int i = 25; i <= n; i++) {
            dp_max_25[i] = (dp_max_1[i - 25] + dp_max_5[i - 25] + dp_max_10[i - 25] + dp_max_25[i - 25]) % 1000000007;
        }
        return (dp_max_1[n] + dp_max_5[n] + dp_max_10[n] + dp_max_25[n]) % 1000000007;
    }
};
算法

每日leetcode-466

已经发布在了leetcode中文版里面。

题目

466. 统计重复个数

由 n 个连接的字符串 s 组成字符串 S，记作 S = [s,n]。例如，["abc",3]=“abcabcabc”。

如果我们可以从 s2中删除某些字符使其变为 s1，则称字符串 s1可以从字符串 s2 获得。例如，根据定义，”abc” 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。

现在给你两个非空字符串 s1 和 s2（每个最多 100 个字符长）和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。

请你找出一个可以满足使[S2,M] 从 S1 获得的最大整数 M 。

示例：

输入：
s1 =”acb”,n1 = 4
s2 =”ab”,n2 = 2

返回：
2

总体思路

记录下来每个s1对应的位置，匹配的结果。每一次如果要求的匹配已经在数据中，就看可以匹配多少组。

比如，【baab, 40】里面要匹配【baba, 2】，那我就先找到应该匹配哪几位：

  • 第一次匹配：【baabbaabbaabbaabbaab】
  • 找到对应的：【ba b a】，是从s1的下标为0的位置开始匹配的
  • 第二次匹配：【baabbaabbaabbaabbaab】
  • 找到对应的：【 b a b a】，是从s1的下标为2的位置开始匹配的
  • 再往后匹配：【baabbaabbaabbaabbaab】
  • 这一次找对应的，还是从s1的下标为2的位置开始匹配的。

因此，我们就可以记录下来，每一次从s1的某一个位置进行匹配，会匹配到哪个地方。

匹配位置

匹配位置是说，使用一个数组/map，i对应的值为记录从s1的第i位开始，往后走到哪里可以匹配一个完整的s2。

比如：s1=”baab”, s2=”baba”，我用来记忆的map叫做memo，这样的话memo[0] = 6，表示从s1的下标为0的地方，往右走到下标为6的地方可以匹配完一个s2

  • 注：下标为6代表的是，s1重复之后得到的”baabbaabbaab……”这个数组的下标，也就是说其中的【baabba】（下标为0 ～ 5）这些部分可以匹配一个完整的s2。

如果是求memo[2]的话，那结果就等于10，代表下标为2～9的部分（ba【abbaabba】ab）可以匹配一个完整的s2。

因此，我这里设计了一个函数可以实现上述的功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int checkWhere(int n, string &s1, int len1, string &s2, int len2) {
    for (int i = 0; i < len2; i++) {
        int n_target = n + len1;
        bool found = false;
        for (; n < n_target; n++) {
            if (s1[n % len1] == s2[i]) {
                n++;
                found = true;
                break;
            }
        }
        if (!found) {
            return -1;
        }
    }
    return n;
}

找到循环体

比如刚才的例子，【baab, 40】里面要匹配【baba, 2】

到第二次寻找的时候，就是从下标为2开始，到下标为2结束。

  • 【baabbaabbaab】
  • 【 b a b a】

再往后一次也是一样的，这样就构成了循环结构。

我在这里使用了一个循环结构的检测，记录的时候不仅记录应该到哪个地方，而且记录了到这个地方的时候我匹配完了几个s2。

也就是说，memo[0] = [6, 1]，memo[2] = [10, 2]。

问题来了：

  • 那我一次匹配的之后，下一次应该匹配谁呢？
    • 结果除以s1的长度取余。比如，memo[0] = [6, 1]，那我下一次就应该去找memo[6 % s1.size()]也就是memo[2]
  • 什么时候发现有循环了？
    • 结果除以s1的长度，发现这个值对应位置已经有结果了。
    • 比如，memo[2] = [10, 2]，s1的长度为4，10%4==2，memo[2]刚才已经算出来了，所以就开始循环了！
  • 我们的循环需要计算什么？
    • 我们需要知道这个循环里面，消耗了多少s1，找到了多少s2
    • 实际上的做法，就是对memo进行处理，不断计算直到发现memo开始循环，记录下这时候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
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
class Solution {
public:
    int checkWhere(int n, string &s1, int len1, string &s2, int len2, map<int, pair<int, int>>& memo) {
        for (int i = 0; i < len2; i++) {
            int n_target = n + len1;
            bool found = false;
            for (; n < n_target; n++) {
                if (s1[n % len1] == s2[i]) {
                    n++;
                    found = true;
                    break;
                }
            }
            if (!found) {
                return -1;
            }
        }
        return n;
    }

    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        map<int, pair<int, int>> memo;
        int now_n = 0;  // from the nth letter of s1, to which will have one s2
        int len1 = s1.size(), len2 = s2.size();
        int max_n = len1 * n1;
        int now_num_s2 = 0;
        int n, temp;
        while (now_n < max_n) {
            n = now_n % len1;
            if (memo.find(n) != memo.end()) {
                // now already found
                // 之前用了now_n这么多个，也就是用了now_n//len1这么多个s1，并且找到了now_num_s2这么多个s2
                // 现在需要做什么？现在需要跳回到data[n][0]这个位置，并且可以得到now_num_s2 - memo[n][1]这么多个s2
                // 需要用到多少s1呢？
                int need_n = n / len1 * len1 + memo[n].first;
                while (need_n % len1 != n) {
                    need_n = need_n / len1 * len1 + memo[need_n % len1].first;
                }
                // 现在到了need_n这么多位的s1，也就是用了need_n/len1这么多个s1，就拿到了now_num_s2 - memo[n][1]这么多个s2
                // 还剩下max_n - now_n这么多个可以挥霍
                int add_whole = (max_n - now_n) / (need_n / len1 * len1);
                now_num_s2 += add_whole * (now_num_s2 - memo[n].second + 1);
                now_n += add_whole * (need_n / len1 * len1);
                while (now_n < max_n) {
                    temp = memo[now_n % len1].first;
                    now_n = now_n / len1 * len1 + temp;
                    if (now_n > max_n) {
                        break;
                    }
                    now_num_s2 += 1;
                }
                return now_num_s2 / n2;
            }
            temp = checkWhere(n, s1, len1, s2, len2, memo);
            if (temp == -1) {
                return 0;
            }
            now_n = now_n / len1 * len1 + temp;
            if (now_n > max_n) {
                break;
            }
            now_num_s2 += 1;
            memo[n] = pair<int, int>(temp, now_num_s2);
        }
        return now_num_s2 / n2;
    }
};
算法

每日leetcode-154

  1. 寻找旋转排序数组中的最小值 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5]
输出: 1

示例 2：

输入: [2,2,2,0,1]
输出: 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
class Solution {
public:
    int myMin(vector<int>& nums, int left, int right) {
        if (left >= right || nums[left] < nums[right]) {
            return nums[left];
        }
        int mid = (left + right) / 2;
        if (nums[left] == nums[right]) {
            if (nums[mid] < nums[left]) {
                return myMin(nums, left, mid);
            }
            if (nums[mid] > nums[left]) {
                return myMin(nums, mid + 1, right);
            }
            return min(myMin(nums, left, mid - 1), myMin(nums, mid + 1, right));
        }
        // left > right
        else {
            if (nums[mid] < nums[right]) {
                return myMin(nums, left, mid);
            }
            if (nums[mid] > nums[right]) {
                return myMin(nums, mid + 1, right);
            }
            // nums[mid] == nums[right]
            return min(myMin(nums, left, mid - 1), myMin(nums, mid + 1, right));
        }
    }

    int findMin(vector<int>& nums) {
        return myMin(nums, 0, nums.size() - 1);
    }
};

可以优化一下合并中间的对left right大小的判断：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int myMin(vector<int>& nums, int left, int right) {
        if (left >= right || nums[left] < nums[right]) {
            return nums[left];
        }
        int mid = (left + right) / 2;
        if (nums[mid] < nums[right]) {
            return myMin(nums, left, mid);
        }
        if (nums[mid] > nums[right]) {
            return myMin(nums, mid + 1, right);
        }
        // nums[mid] == nums[right]
        return min(myMin(nums, left, mid - 1), myMin(nums, mid + 1, right));
    }

    int findMin(vector<int>& nums) {
        return myMin(nums, 0, nums.size() - 1);
    }
};

非递归的做法

（题解里面提到的）在left、right、mid对应的都相等的时候，不是分别算求min，而是将r–

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (true) {
            if (left >= right || nums[left] < nums[right]) {
                return nums[left];
            }
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            }
            else if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
            else {
                right--;
            }
        }
    }
};
算法

每日leetcode-153

  1. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

解答

二分查找，里面涉及到两个判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMin(vector<int>& nums) {
        int len = nums.size();
        int l = 0, r = len - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[l] <= nums[r]) {
                return nums[l];
            }
            if (nums[mid] <= nums[r]) {
                r = mid;  // if mid == r, then l == r, so nums[l] == num[r]
            }
            else {
                l = mid + 1;  // l won't be bigger than r
            }
        }
        return nums[r];
    }
};

这里需要考虑：

  • 会不会越界（也就是会不会导致循环出去了但是没有返回的结果）
  • 会不会循环不停（就是更新完l和r之后，还是原来的范围）

官方题解

直接在二分之后判断mid和右侧的关系，通过这个来更新

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:
    int findMin(vector<int>& nums) {
        int len = nums.size();
        int l = 0, r = len - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[l] <= nums[r]) {
                return nums[l];
            }
            if (nums[mid] > nums[mid + 1]) { // 在l和r不相等时，mid+1的下标是在范围内的
                return nums[mid + 1];
            }
            if (nums[mid] > nums[l]) {
                l = mid + 1;  // l won't be bigger than r
            }
            else {
                r = mid;
            }
        }
        return nums[r];
    }
};
语言—Java

Gradle

官网：https://gradle.org

Gradle介绍

安装：直接看官网上面的说明 https://gradle.org/install/ 就好，Mac上面brew install gradle

环境变量配置：

添加 Gradle 依赖 https://blog.csdn.net/zxs9999/article/details/81484799

Re-download dependencies and sync project (requires network)

https://www.jianshu.com/p/8b76e3b52f5f

找到“Build,Execution,Deployment”下的“gradle”，选中“Use default gradle wrapper(recommended)”