免费行情软件网站mnw,一个网站大概多少钱,微信小程序怎么上架商品,老河口网站设计盛最多雨水的容器 数组的第 i i i个数字表示这个位置隔板的高度#xff0c;选择哪两块板子可以装最多的水#xff0c;返回可以存储的最大水量。 有一种双指针的贪心策略#xff1a;如果左边的指针所在的挡板低#xff0c;就将左边的指针右移#xff0c;否则将右边的指针左…盛最多雨水的容器 数组的第 i i i个数字表示这个位置隔板的高度选择哪两块板子可以装最多的水返回可以存储的最大水量。 有一种双指针的贪心策略如果左边的指针所在的挡板低就将左边的指针右移否则将右边的指针左移。
每次移动完之后计算当前能存储的水量并和结果值相比较。
证明假设最优解对应的两条线的下标是 i ′ , j ′ ( i ′ j ′ ) i^′,j^′(i^′j^′) i′,j′(i′j′)在 i , j i,j i,j 不断靠近的过程中不妨假设 i i i 先走到 i ′ i^′ i′则此时有 j ′ j j^′j j′j。反证如果此时 a i ≤ a j a_i≤a_j ai≤aj设 S S S 表示 i , j i,j i,j 能盛多少水 S ′ S^′ S′ 表示 i ′ , j ′ i^′,j^′ i′,j′ 能盛多少水则 $$ Smin(a_i,a_j)∗(j−i) a_i∗(j−i) a_i∗(j^′−i) \geq min(ai,aj′)∗(j′−i)S^′ $$ 与 S ′ S^′ S′ 是最优解矛盾因此 a i a j a_ia_j aiaj所以 j j j 会一直走到 j ′ j^′ j′从而得到最优解。 int maxArea(vectorint height) {int res 0;for(int l 0, r height.size() - 1; l r; ) {res max(res, (r - l) * min(height[l], height[r])); // 先计算当前状态再转移if(height[l] height[r]) l ;else r --;}return res;
}整数转罗马数字 在罗马数字中有如下规则 I 1
V 5
X 10
L 50
C 100
D 500
M 1000通常罗马数字中小的数字在大的数字的右边如XV表示 15 15 15。但也存在特例如IV表示 4 4 4但这只有如下六种情况 I 可以放在 V (5) 和 X (10) 的左边来表示 4 和 9。X 可以放在 L (50) 和 C (100) 的左边来表示 40 和 90。C 可以放在 D (500) 和 M (1000) 的左边来表示 400 和 900。 将给定的数字转化为罗马数字。 1 2 3 4 5 6 7 8 9
I II III IV V VI VII VIII IX
10 20 30 40 50 60 70 80 90
x XX XXX XL L LX LXX LXXX XC
100 200 300 400 500 600 700 800 900
c CC CCC CD D DC DCC DCCC CM
1000 2000 3000
M MM MMM分别枚举个十百千位的数值如何表示我们不难发现 1 − 3 1-3 1−3 6 − 8 6-8 6−8的表示比较显然其余的则比较特殊。
以 100 − 900 100-900 100−900为例以 100 , 400 , 500 , 900 100,400,500,900 100,400,500,900为界若 x 900 x900 x900则 x − 900 x-900 x−900若 x 500 x500 x500则 x − 500 x-500 x−500直至循环结束。
所以只需要打表打出 1 , 4 , 5 , 9 1,4,5,9 1,4,5,9系列的值即可然后从大到小依次减。
string intToRoman(int num) {vectorint key {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};vectorstring value {M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I};string ans ;// 2649 - 1649 - 649 - 149 - 49 - 9 - 0// M MM MMD MMDC MMDCXL MMDCXLIXfor(int i 0; i key.size(); i ) {while(num key[i]) {num - key[i];ans value[i];}}return ans;
}罗马数字转整数 将给定的罗马数字转化为整数。 和上一题类似的打表思想但是将罗马数字转化为整数时注意到一个特性
若大数在小数左边则为大数小数若大数在小数右边则为大数-小数。并且本题只需要存储7个罗马数字即可。
int romanToInt(string s) {unordered_mapchar, int mp;mp[I] 1; mp[V] 5; mp[X] 10; mp[L] 50;mp[C] 100; mp[D] 500; mp[M] 1000;int ans 0;for(int i 0; i s.size(); i ) {if(i 1 s.size() mp[s[i]] mp[s[i 1]])ans - mp[s[i]];elseans mp[s[i]];}return ans;
}最长公共前缀 求字符串数组中的最长公共前缀。 可以用trie树来做但是太麻烦。
可以直接枚举字符串的每一位看所有字符串的这一位是否都相同如果不同就返回当前结果否则继续下一轮判断。
string longestCommonPrefix(vectorstring strs) {string ans ;for(int i 0; i strs[0].size(); i ) { // 枚举第i位char c strs[0][i];bool flag true;for(auto str : strs) { // 判断所有字符串的第i位是否都相同if(str.size() i || str[i] ! c) {flag false;break;}}if(flag) ans c;else break;}return ans;
}三数之和 给定整数数组找出满足 i ≠ j ≠ k i \neq j \neq k ijk且nums[i]nums[j]nums[k]0的所有三元组。 先对整数数组排序然后枚举 i i i的所有位置再对 j , k j,k j,k使用双指针算法。
当 i i i的位置固定后 n u m s [ j ] n u m s [ k ] − n u m s [ i ] nums[j]nums[k]-nums[i] nums[j]nums[k]−nums[i]当 j j j右移时 k k k必然左移因此时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
由于答案中不能包含重复的三元组可以使用set来对答案进行去重。
vectorvectorint threeSum(vectorint nums) {setvectorint res;sort(nums.begin(), nums.end());for(int i 0; i nums.size() - 2; i ) { // 固定ifor(int j i 1, k nums.size() - 1; j k; j ) { // 每次移动j,对j找到满足条件的kwhile(j k - 1 nums[i] nums[j] nums[k] 0) k --;if(nums[i] nums[j] nums[k] 0)res.insert({nums[i], nums[j], nums[k]});}}vectorvectorint ans; // 去重for(auto p : res) ans.push_back(p);return ans;
}对于1 1 2 2 -3这种情况来说第1个1和第2个1所呈现出的组合是一样的所以对于相同的数i和j都只需要遍历一次即可。
也可以通过这种方法来去重会大大降低时间复杂度。
vectorvectorint threeSum(vectorint nums) {vectorvectorint ans;sort(nums.begin(), nums.end());for(int i 0; i nums.size() - 2; i ) { // 固定iif(i nums[i] nums[i - 1]) continue; // i不能重复判断 for(int j i 1, k nums.size() - 1; j k; j ) { // 每次移动j,对j找到满足条件的kif(j i 1 nums[j] nums[j - 1]) continue; // j不能重复判断// 因为i和j都不会重复,所以k也必然不会重复,所以不需要额外特判kwhile(j k - 1 nums[i] nums[j] nums[k] 0) k --;if(nums[i] nums[j] nums[k] 0)ans.push_back({nums[i], nums[j], nums[k]});}}return ans;
}
