[数据结构与算法]1.LeetCode刷题班Day01

LeetCode刷题班day1

1.题目1：绳子最多覆盖几个点

【思路】贪心策略 + 滑动窗口：将数组中每个点放在绳子最左侧，看看每个点能放几个点，答案一定在其中。滑动窗口left每次来到绳子最左侧的点的下标，right来到绳子最长能够到点的下标，由于left和right都单调不递减，因此时间复杂度为O(N)。

【做题模型】遍历过程中左边界和有边界都不需要回退的模型。

【代码】

int getMaxNodes(vector<int> &nums, int L) {
    int res = INT32_MIN;
    int left = 0, right = 0;
    for (; left < nums.size(); ++left) {
        while (right < nums.size() - 1 && nums[right + 1] - nums[left] + 1 <= 5) {
            ++right;
        }
        res = max(res, right - left + 1);
    }
    return res;
}

2.题目2：用最少的袋子正好装n个苹果

【思路】贪心： 先全用8袋子装看最多需要几个袋子，省下的苹果用6袋子装，如果能装下直接返回结果；如果不能，则8袋子-1，继续试，一直试到最多的八袋子 - 3（因为如果最多的八袋子减3使不出来结果，那么就是24个苹果，24个苹果会被4个6袋子装下，实际情况和一开始一样）。

【代码】

int minBags(int apple) {
    if (apple % 2) { //奇数个苹果一定不能被装下
        return -1;
    }
    int bag6 = -1;
    int bag8 = apple / 8;
    int rest = apple - 8 * bag8;
    while (bag8 >= 0 && rest < 24) { //24是8和6的最小公倍数
        int restUse6 = rest % 6 == 0 ? (rest / 6) : -1;
        if (restUse6 != -1) {
            bag6 = restUse6;
            break;
        }
        rest = apple - 8 * (--bag8);
    }
    return bag6 == -1 ? -1 : bag6 + bag8;
}

3.题目3：正方形染色

【思路】将s分为左右两部分，左侧全染成R，右侧全染成G。以s = RGRGR为例，有以下几种情况：

1. 左侧长度为0，右侧长度为5，那么结果就是GGGGG，需要染3次
2. 左侧长度为1，右侧长度为4，那么结果就是RGGGG，需要染2次
3. 左侧长度为2，右侧长度为3，那么就是RRGGG，需要染3次
4. 左侧长度为3，右侧长度为2，那么就是RRRGG，需要染2次
5. 左侧长度为4，右侧长度为1，那么就是RRRRG，需要染3次
6. 左侧长度为5，右侧长度为0，那么就是RRRRR，需要染2次

可以生成一个数组recordL用来存放[0…i]上一共有几个G，recordR从右往左遍历用来存放[i + 1…N]上有几个R。遍历的时候直接查询左侧部分有几个G，右侧部分有几个R就染色多少次就行。

【做题技巧】预处理数据，如果某一块查询是频繁的，可以生成一个查询结构。

【代码】

int minPaint(string s) {
    int n = s.size();
    //生成辅助数组
    vector<int> recordL(n + 1, 0), recordR(n + 1, 0);
    int countR = 0, countG = 0;
    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] == 'G') {
            ++countR;
        }            
        recordL[i] = countR;
        if (s[n - i] == 'R') {
            ++countG;
        }
        recordR[i] = countG;
    }

    //遍历求最少染色次数
    int res = INT32_MAX;
    for (int i = 0; i <= n; ++i) {
        res = min(res, recordL[i] + recordR[n - i]);
    }
    return res == INT32_MAX ? 0 : res;
}

4.题目4：矩阵中边框最大的正方形

【思路】N*N的矩阵的子矩阵规模是O(N’4)个，矩形任意点两个点A和B时间复杂度都是O(N’2),任意两个点构成一个子矩阵，因此时间复杂度为O(N’2) ×O（N’2）=O(N’4);而子矩阵是正方形的规模是O(N‘3)，任意点一个点作为正方形子矩阵的左上顶点，时间复杂度为O(N’2),枚举这个点为左上顶点情况下正方形的边长为O(N),因此时间复杂度为O(N’3)。

我们可以对是正方形的子矩阵进行验证是否边框都是1，那么需要4个顺序的for循环，时间复杂度为O(N),那么这题的时间复杂度就是O(N’4)。然而我们可以用空间换时间，省去验证的时间复杂度，需要生成两个N×N的矩阵right和down，用来记录每个点右边和下边连续是1的点的个数，这样时间复杂度就是O(N’3)。

【代码】

int maxAllOneBorder(vector<vector<int>>& m) {
    int M = m.size(), N = m[0].size();
    int res = 1;
    //生成查询矩阵
    vector<vector<int>> right(M, vector<int>(N));
    vector<vector<int>> down(M, vector<int>(N));
    for (int i = 0; i < M; ++i) {
        int count = 0;
        for (int j = N - 1; j >= 0; --j) {
            if (m[i][j] == 1) {
                ++count;
            }
            else {
                count = 0;
            }
            right[i][j] = count;
        }
    }
    for (int j = 0; j < N; ++j) {
        int count = 0;
        for (int i = M - 1; i >= 0; --i) {
            if (m[i][j] == 1) {
                ++count;
            }
            else {
                count = 0;
            }
            down[i][j] = count;
        }
    }
    //遍历每个正方形的子矩阵是不是边框都为1
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < N; ++j) {
            //枚举边长
            for (int k = 1; k <= min(M - i, N - j); ++k) {
                //注意是都是大于等于k，因为每个顶点可能大于k
                if (right[i][j] >= k && down[i][j] >= k && down[i][j + k - 1] >= k && right[i + k - 1][j] >= k) {
                    res = max(res, k);
                }
            }
        }
    }

    return res;
}

5.题目5：生成等概率的函数

【思路】我们可以先利用f函数生成一个等概率返回0和1的函数；再利用0和1的函数拼成我们需要的函数，例如返回1~7，相当于返回0 - 6 + 1，需要3个0和1的函数来拼，1 × 4 + 1 × 2 + 1× 1 = 7 > 6.

int f(); //调用f函数等概率返回0~5

//等概率返回0和1函数
int r01() {
    int res = 0;
    res = f();
    while (res == 3) {
        res = f();
    }
    return res < 3 ? 0 : 1;
}

//等概率返回1~7的函数
int g() {
    int res = 0;
    res = (r01() << 2) + (r01() << 1) + r01();
    while (res == 7) {
        res = (r01() << 2) + (r01() << 1) + r01();
    }
    return res + 1;
}

6.题目1：结点个数能形成多少种二叉树的结构

【思路】动态规划，假设N个结点有F(N)种结构，则F(N) = 1 × F(N - 1) + F(1) × F(N - 2) + … F(i) × F(N - i - 1) + …F(N - 2) × 1

【暴力递归法】

int numTrees(int n) {
    if (n == 0 || n == 1) { //空树或一个结点
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    int res = 0;
    for (int leftNum = 0; leftNum <= n - 1; ++leftNum) {
        int leftWays = numTrees(leftNum);
        int rightWays = numTrees(n - leftNum - 1);
        res += leftWays * rightWays;
    }
    return res;
}

【动态规划】

int numTrees(int n) {
    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        int res = 0;
        for (int leftNum = 0; leftNum <= n - 1; ++leftNum) {
            int leftWays = dp[leftNum];
            int rightWays = dp[n - leftNum - 1];
            res += leftWays * rightWays;
        }
        dp[i] = res;
    }
    return dp[n];
}

7.题目2：添加括号形成完整括号字符串

【思路】从左往右遍历数组，如果遇到左括号count + 1，遇到右括号count - 1，任意时刻count < 0则说明左侧缺一个左括号，用ans记录缺的左括号数，++ans，并且使得count重新变成0（表示左侧缺的括号数已经加上了），最后count表示缺的右括号数，结果就是count + ans。

【代码】

int needParentheses(string str) {
    int count = 0;
    int ans = 0;
    for (int i = 0; i < str.size(); ++i) {
        if (str[i] == '(') {
            ++count;
        } else { //遇到的右括号
            if (count == 0) {
				++ans;
            } else {
                --count;
            }
        }
    }
    return count + ans;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖