628. 三个数的最大乘积
给定一个整型数组,在数组中找出由三个数组成的最大乘积,并输出这个乘积。
示例 1:
输入: [1,2,3]
输出: 6
示例 2:
输入: [1,2,3,4]
输出: 24
注意:
- 给定的整型数组长度范围是[3,104],数组中所有的元素范围是[-1000, 1000]。
- 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
第一版,自己写的
执行用时 :68 ms, 在所有 cpp 提交中击败了75.20%的用户
内存消耗 :10.8 MB, 在所有 cpp 提交中击败了86.46%的用户
int maximumProduct(vector<int>& nums) { if (nums.size() == 3) return nums[0] * nums[1] * nums[2]; sort(nums.begin(), nums.end()); int result=0,max = nums[nums.size() - 1], lastMax = nums[nums.size() - 2]; int secondMin = nums[1]; if (secondMin < 0) { int temp = nums[0] * secondMin * max; result = max * lastMax * nums[nums.size() - 3]; result = result > temp ? result : temp; } else { result = max * lastMax * nums[nums.size() - 3]; } return result; }
830. 较大分组的位置
在一个由小写字母构成的字符串 S
中,包含由一些连续的相同字符所构成的分组。
例如,在字符串 S = "abbxxxxzyy"
中,就含有 "a"
, "bb"
, "xxxx"
, "z"
和 "yy"
这样的一些分组。
我们称所有包含大于或等于三个连续字符的分组为较大分组。找到每一个较大分组的起始和终止位置。
最终结果按照字典顺序输出。
示例 1:
输入: "abbxxxxzzy"
输出: [[3,6]]
解释: "xxxx" 是一个起始于 3 且终止于 6 的较大分组。
示例 2:
输入: "abc"
输出: []
解释: "a","b" 和 "c" 均不是符合要求的较大分组。
示例 3:
输入: "abcdddeeeeaabbbcd"
输出: [[3,5],[6,9],[12,14]]
说明: 1 <= S.length <= 1000
第一版,自己写的,比较慢
执行用时 :16 ms, 在所有 cpp 提交中击败了35.69%的用户
内存消耗 :9.3 MB, 在所有 cpp 提交中击败了82.42%的用户
vector<vector<int>> largeGroupPositions(string S) { if (S.size() <= 2) return {}; vector<vector<int>> res; int len = S.size(), count = 0; char ch; for (int i = 0; i < len; ) { if (S[i] == S[i + 1]) { if (S[i + 1] == S[i + 2]) { count = 0; ch = S[i]; while (S[i] == ch) { count++; i++; } res.push_back({ i - count,i - 1 }); } else i++; } else i++; } return res; }