程序员进阶之算法练习(九十二)leetcode

2023-12-02 10:13:17 浏览数 (1)

题目1 最后一块石头的重量

题目链接 题目大意: 有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎; 如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。 最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0。

示例: 输入:[2,7,4,1,8,1] 输出:1 解释: 先选出 7 和 8,得到 1,所以数组转换为 [2,4,1,1,1], 再选出 2 和 4,得到 2,所以数组转换为 [2,1,1,1], 接着是 2 和 1,得到 1,所以数组转换为 [1,1,1], 最后选出 1 和 1,得到 0,最终数组转换为 [1],这就是最后剩下那块石头的重量。

提示: 1 <= stones.length <= 30 1 <= stones[i] <= 1000

题目解析: 模拟题目操作,用优先队列,每次取出头部两个元素进行操作,如果元素不相同则把石头差放回队列。 代码比较简单:

代码语言:javascript复制
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> q;
        for (int i = 0; i < stones.size();   i) q.push(stones[i]);
        while (q.size() >= 2) {
            int first = q.top();
            q.pop();
            int second = q.top();
            q.pop();
            if (first - second) q.push(first - second);
        }
        return q.empty() ? 0 : q.top();
    }
}ac;

题目2 两地调度

题目链接 题目大意: 公司计划面试 2n 人。给你一个数组 costs ,其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ,飞往 b 市的费用为 bCosti 。 返回将每个人都飞到 a 、b 中某座城市的最低费用,要求每个城市都有 n 人抵达。

示例 1: 输入:costs = [[10,20],[30,200],[400,50],[30,20]] 输出:110 解释: 第一个人去 a 市,费用为 10。 第二个人去 a 市,费用为 30。 第三个人去 b 市,费用为 50。 第四个人去 b 市,费用为 20。

最低总费用为 10 30 50 20 = 110,每个城市都有一半的人在面试。

提示: 2 * n == costs.length 2 <= costs.length <= 100 costs.length 为偶数 1 <= aCosti, bCosti <= 1000

题目解析: 如果不考虑复杂度,可以直接使用搜索的方式,每个人有2个选择,总共会有2^2n种选择,这个复杂度明显超过题目限制; 注意到每个人有2个选择,那么用dp[i][j]来表示前i个人,有j个选择a城市的最小费用,对于第i个人: 如果第i个人选择a城市,那么有dp[i][j]=dp[i-1][j-1] aCost[i]; 如果第i个人选择b城市,那么有dp[i][j]=dp[i-1][j] bCost[i];

总的复杂度是O(N^2);

代码语言:javascript复制
class Solution {
    int dp[110][110];
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int n = costs.size();
        for (int i = 1; i <= n;   i) {
            dp[i][0] = dp[i - 1][0]   costs[i-1][1]; // bCost[i]
            dp[i][i] = dp[i - 1][i - 1]   costs[i-1][0]; // aCost[i]
            for (int j = 1; j < i;   j) {
                dp[i][j] = min(dp[i - 1][j - 1]   costs[i - 1][0], dp[i - 1][j]   costs[i - 1][1]);
            }
        }
        return dp[n][n/2];
    }
}ac;

题目3 两个非重叠子数组的最大和

题目链接 题目大意: 给出非负整数数组 A ,返回两个非重叠(连续)子数组中元素的最大和,子数组的长度分别为 L 和 M。(这里需要澄清的是,长为 L 的子数组可以出现在长为 M 的子数组之前或之后。)

从形式上看,返回最大的 V,而 V = (A[i] A[i 1] ... A[i L-1]) (A[j] A[j 1] ... A[j M-1]) 并满足下列条件之一:

0 <= i < i L - 1 < j < j M - 1 < A.length, 或 0 <= j < j M - 1 < i < i L - 1 < A.length.

示例 1: 输入:A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2 输出:20 解释:子数组的一种选择中,[9] 长度为 1,[6,5] 长度为 2。 示例 2: 输入:A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2 输出:29 解释:子数组的一种选择中,[3,8,1] 长度为 3,[8,9] 长度为 2。 示例 3: 输入:A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3 输出:31 解释:子数组的一种选择中,[5,6,0,9] 长度为 4,[0,3,8] 长度为 3。

提示: L >= 1 M >= 1 L M <= A.length <= 1000 0 <= A[i] <= 1000

题目解析: 题目要求是找到两个子数组并且要求和最大,我们可以先简化题目要求; 假如只考虑找到一个最大子数组的情况,此时可以从左到右遍历数组,就可以得到每个位置结尾的最大子数组和left[i];在这个过程中,可以持续计算得到该位置往左所有left[i]的最大值maxLeft[i]; 这样我们就可以O(N)的复杂度,在数组中找到某个长度的最大值。 同理,可以从右到左遍历,得到right[i]和maxRight[i]。

现在要寻找长度L和M的子数组,那么问题可以拆分为: 1、假设有位置k,那么[1, k]中会产生L数组,[k 1, n]会产生M数组;此时可以枚举k的位置; 2、LR的位置是反过来的,按照1的做法把L和R交换一下; 时间和空间复杂度都是O(N);

代码语言:javascript复制
class Solution {
    int search(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size(), sum = 0;
        vector<int> left(n), maxLeft(n);
        for (int i = 0; i < n;   i) {
            sum  = nums[i];
            if (i >= firstLen) {
                sum -= nums[i - firstLen];
            }
            left[i] = sum;
            if (i > 0) maxLeft[i] = maxLeft[i - 1];
            maxLeft[i] = max(maxLeft[i], left[i]);
        }
        vector<int> right(n), maxRight(n);
        sum = 0;
        for (int i = n - 1; i >= 0; --i) {
            sum  = nums[i];
            if (i   secondLen <= n - 1) {
                sum -= nums[i   secondLen];
            }
            right[i] = sum;
            if (i < n - 1) maxRight[i] = maxRight[i   1];
            maxRight[i] = max(maxRight[i], right[i]);
        }
        
        int ret = 0;
        for (int i = firstLen - 1; i   secondLen < n;   i) {
            ret = max(ret, maxLeft[i]   maxRight[i   1]);
        }
        return ret;
    }
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        return max(search(nums, firstLen, secondLen), search(nums, secondLen, firstLen));
    }
}leetcode;

题目4 每个元音包含偶数次的最长子字符串

题目链接 题目大意: 给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。

示例 1: 输入:s = "eleetminicoworoep" 输出:13 解释:最长子字符串是 "leetminicowor" ,它包含 e,i,o 各 2 个,以及 0 个 a,u 。 示例 2: 输入:s = "leetcodeisgreat" 输出:5 解释:最长子字符串是 "leetc" ,其中包含 2 个 e 。 示例 3: 输入:s = "bcbcbc" 输出:6 解释:这个示例中,字符串 "bcbcbc" 本身就是最长的,因为所有的元音 a,e,i,o,u 都出现了 0 次。

提示: 1 <= s.length <= 5 x 10^5 s 只包含小写英文字母。

题目解析:

从简单的开始思考,假如要求只有一个字母a出现偶数次; 那么如果数组中字母a出现偶数次,则直接满足;如果a出现奇数次,那么去掉最左边的a及左边的部分,或者去掉最右边a及右边的部分;(复杂度O(N) ) 由此我们知道,肯定是去掉最初出现的字母a,或者最后出现的字母a。

现在要求变成字母a、o出现偶数次,能否延续上面的思路:去掉最左边或者最右边的某一些部分,使得剩下部分满足要求? 理论上是可行的,左边去掉部分,可能是奇数或者偶数个a,有可能是奇数或者偶数个o,右边同理;剩下的部分要求a和o都是偶数。

对于左边来说,去掉的部分有4种可能:偶数a偶数o,偶数a奇数o,奇数a偶数o,奇数a奇数o; 为了方便描述我们用0表示偶数,1表示奇数,那么上面的状态可以表示为00、01、10、11,刚好可以用数字0、1、2、3来表示这4个状态。 假如原始字符串,最开始的状态是state;最终剩下的字符串,状态应该是00,假如左边去掉字符串的状态是leftState,右边去掉字符串的状态是rightState,那么就有 leftState ^ rightState ^ state = 0;(这里采用异或操作符,可以用实际操作例子感受下)

当字母扩展为a、e、i、o、u之后,同样可以用上面的方式。

代码语言:javascript复制
class Solution {
public:
    int findTheLongestSubstring(string s) {
        char aoe[] = "aeiou";
        int state = 0;
        int left[33] = {0}, right[33] = {0};
        for (int i = 0; i < s.length();   i) {
            char c = s[i];
            int k = -1;
            for (int j = 0; j < 5;   j) {
                if (aoe[j] == c) {
                    k = j;
                    break;
                }
            }
            if (k >= 0) {
                state = state ^ (1 << k);
                if (state && !left[state]) {
                    left[state] = i   1;
//                    cout << "left " << state << " " << i   1 << endl;
                }
            }
        }
        
        state = 0;
        right[state] = s.length();
        for (int i = s.length() - 1; i >= 0; --i) {
            char c = s[i];
            int k = -1;
            for (int j = 0; j < 5;   j) {
                if (aoe[j] == c) {
                    k = j;
                    break;
                }
            }
            if (k >= 0) {
                state = state ^ (1 << k);
                if (state && !right[state]) {
                    right[state] = i;
//                    cout << "right " << state << " " << i   1 << endl;
                }
            }
        }
//        cout << "state " << state << endl;
        
        int ans = 0;
        for (int j = 0; j < 32;   j) {
            int leftState = j;
            int rightState = j ^ state;
//            cout << leftState << " " << rightState << " " << s.length() - (s.length() - right[rightState]) - left[leftState] << endl;
            ans = max(ans, right[rightState] - left[leftState]);
        }
        
        return ans;
    }
}leetcode; 

题目5 删除子数组的最大得分

题目链接 题目大意: 给你一个正整数数组 nums ,请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。

返回 只删除一个 子数组可获得的 最大得分 。

如果数组 b 是数组 a 的一个连续子序列,即如果它等于 a[l],a[l 1],...,a[r] ,那么它就是 a 的一个子数组。

示例 1: 输入:nums = [4,2,4,5,6] 输出:17 解释:最优子数组是 [2,4,5,6] 示例 2: 输入:nums = [5,2,1,2,5,2,1,2,5] 输出:8 解释:最优子数组是 [5,2,1] 或 [1,2,5]

提示: 1 <= nums.length <= 105 1 <= nums[i] <= 104

题目解析: 从数组中找到一个连续的区间,区间不能包括相同的数字,要求区间的数字和尽可能大。 从左到右遍历数组,维护一个区间[left, right],区间没有相同元素,我们用map<int, int> 来记录数组中出现的数字,sum记录数组的和; 假设遍历到数字a[i],如果map中没有数字a[i],则直接添加到map中,右区间右移right=right 1,sum=sum a[i]; 假设遍历到数字a[i],如果map中存在数字a[i],则左区间右移sum=sum-a[left],left=left 1,直到发现数字a[i],这样得到包括数字a[i]的区间[left, right]和区间和sum;

遍历过程中的最大和所在区间,就是答案。复杂度O(N)。

代码语言:javascript复制
class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int sum = 0, left = 0, right = 0;
        int ans = 0;
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size();   i) {
            if (mp[nums[i]]) {
                while (mp[nums[i]]) {
                    sum -= nums[left];
                    mp[nums[left]]--;
                      left;
                }
            }
            right  = 1;
            sum  = nums[i];
              mp[nums[i]];
            ans = max(ans, sum);
        }
        return ans;
    }
}leetcode;

0 人点赞