做网站一个月30ip,微信会员卡管理系统,自做美食哪些网站,个人网站建什么类型的目录 哈希1. 两数之和1.1 解法11.1 解法2 2. 字母异位词分组2.1 解法12.2 解法2 3. 最长连续序列3.1 解法 小结 双指针4. 移动零4.1 解法14.2 解法2 5. 盛最多水的容器5.1 解法一5.2 解法二 6. 三数之和6.1 解法16.2 解法2 7. 接雨水7.1 解法1 小结 滑动窗口8. 无重复字符的最长… 目录 哈希1. 两数之和1.1 解法11.1 解法2 2. 字母异位词分组2.1 解法12.2 解法2 3. 最长连续序列3.1 解法 小结 双指针4. 移动零4.1 解法14.2 解法2 5. 盛最多水的容器5.1 解法一5.2 解法二 6. 三数之和6.1 解法16.2 解法2 7. 接雨水7.1 解法1 小结 滑动窗口8. 无重复字符的最长子串8.1 解法1 9. 找到字符串中所有字母异位词9.1 解法一9.2 解法二 子串10 和为k的子数组解法1解法2 11. 滑动窗口最大值解法一解法二 12. 最小覆盖子串解法1 数组13 最大子数组和解法1 14. 合并区间解法1 15. 轮转数组解法1解法2 15. 除自身以外数组的乘积解法1 哈希
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
1.1 解法1
依次取第i个数与第j个数相加判断是否等于目标值若相等则返回索引号ij。两个for循环嵌套时间复杂度On^2。
class Solution {
public:vectorint twoSum(vectorint nums, int target){int num size(nums);int i,j;for(i 0 ; i num ; i){for(j i1; j num ; j){if((nums[i]nums[j]) target){return vector({i,j});}}}return {}; }
};1.1 解法2
索引数组每个元素每次从哈希表中寻找target与该元素的差值。若不存在则将元素值作为key索引号作为value放入哈希表中若存在则返回当前元素的索引号i和找到的对应key的value。由于只需要遍历一次数组时间复杂度为On。
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, int hashtable;int num nums.size();for (int i 0; i num ; i) {auto it hashtable.find(target - nums[i]);if (it ! hashtable.end()) {return {it-second, i};}hashtable[nums[i]] i;}return {};}
};2. 字母异位词分组
给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
2.1 解法1
采用排序法、哈希表。字母异位词排序后的字符串一定相等可以将其作为keyvalue为存放key对应的所有字母异位词每发现一个符合条件的新字母异位词则在value中添加该元素之后遍历哈希表即可得到分组。
//采用unordered_map
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring, vectorstring mp;for (string str: strs) {string key str;sort(key.begin(), key.end());mp[key].emplace_back(str);}vectorvectorstring ans;for (auto it mp.begin(); it ! mp.end(); it) {ans.emplace_back(it-second);}return ans;}
};//or
//采用unordered_multimap
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_multimapstring, vectorstring mp;for (string str: strs) {string key str;sort(key.begin(), key.end());//mp[key].emplace_back(str);//vstr {str};auto it mp.find(key);if(it ! mp.end()){it-second.push_back(str);}else{vectorstring v;v.push_back(str);mp.emplace(key, v);}}vectorvectorstring ans;for (auto it mp.begin(); it ! mp.end(); it) {ans.emplace_back(it-second);}return ans;}
};
2.2 解法2
采用计数法、哈希表。记录每个词每个字母的出现频次在一个26大小的数组中可以将数组作为keyvalue为存放key对应的所有字母异位词每发现一个符合条件的新字母异位词则在value中添加该元素之后遍历哈希表即可得到分组。由于C 哈希表不知道如何计算26数组的哈希值因此还需传入一个hash function函数对象lambda表达式。
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {// 自定义对 arrayint, 26 类型的哈希函数auto arrayHash [fn hashint{}] (const arrayint, 26 arr) - size_t {return accumulate(arr.begin(), arr.end(), 0u, [](size_t acc, int num) {return (acc 1) ^ fn(num);});};unordered_maparrayint, 26, vectorstring, decltype(arrayHash) mp(0, arrayHash);for (string str: strs) {arrayint, 26 counts{};int length str.length();for (int i 0; i length; i) {counts[str[i] - a] ;}mp[counts].emplace_back(str);}vectorvectorstring ans;for (auto it mp.begin(); it ! mp.end(); it) {ans.emplace_back(it-second);}return ans;}
};3. 最长连续序列
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
3.1 解法
采用基于哈希表实现的容器unordered_set对元素不继续排序key需不同存储所有整数可以去除重复元素。之后遍历容器中整数依次查看当前整数是否为一个序列的开头整数即判断x-1是否存在于容器中。如果存在则跳过并遍历下一个整数如果不存在则说明该元素是一个序列的首元素则开始依次判断x1x2…是否存在同时记录序列最长长度。容器unordered_map是基于哈希表实现插入与判断key是否存在均为O(1)外层遍历元素次数为n每个整数被外层循环访问了一次内部中对于单个无连续的整数访问一次因为x1不存在对于存在连续的整数序列也仅对序列中每个整数从小到大遍历一次所以外层循环内部总共也只访问了n次。总共2n次所以时间复杂度O(n) 。
class Solution {
public:int longestConsecutive(vectorint nums) {unordered_setint num_set;for (const int num : nums) {num_set.insert(num);}int longestStreak 0;for (const int num : num_set) {if (!num_set.count(num - 1)) {int currentNum num;int currentStreak 1;while (num_set.count(currentNum 1)) {currentNum 1;currentStreak 1;}longestStreak max(longestStreak, currentStreak);}}return longestStreak; }
};小结
针对算法实现过程中需要插入、查找或判断元素是否存在的功能可以考虑基于哈希表实现的容器unordered_mapunordered_set。unordered_map需要选择合适的数据分别作为key和vaule。unordered_set仅需要一个key即可主要也是为了迅速判断key是否存在。
双指针
4. 移动零
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。 请注意 必须在不复制数组的情况下原地对数组进行操作。
4.1 解法1
遍历数组中每个元素并记录前方已经出现了几个0元素以便明确后续非0元素需要往前移几位。首先判断该元素是否为0如果为0则0元素计数加一如果不为0则按照之前出现的0个数zeronum将当前非0元素前移zeronum位并将该位置0当遍历到第一个元素时非0元素需进行移动前面0个数为0时非0元素也无序移动。
class Solution {
public:void moveZeroes(vectorint nums) {int zeronum 0;int i 0;for(auto num:nums){if(num 0){zeronum 1;}else{if(i !0 zeronum ! 0 ) {nums[i-zeronum] num;num 0;}}i 1;}}
};4.2 解法2
使用双指针左指针指向当前已经处理好的序列的尾部右指针指向待处理序列的头部。只有当右指针所指元素非0则需要将该元素放到已处理好的序列尾部交换。
class Solution {
public:void moveZeroes(vectorint nums) {int n nums.size(), left 0, right 0;while (right n) {if (nums[right]) {swap(nums[left], nums[right]);left;}right;}}
};5. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明你不能倾斜容器
5.1 解法一
采用双for循环依次计算出两垂线之间的容水体积并找出最大值。虽然通过比较当前最大容量与当前左垂线的最大容量潜力减少不必要的计算但双for循环最坏情况依然需要n*n。
class Solution {
public:int maxArea(vectorint height) {int max_capacity 0;int n height.size();int tmp;for(int i 0; i n-1 ; i){if(max_capacity height[i]*(n-i-1)) continue;for(int j i1; j n ; j){tmp min(height[i],height[j]) * ( j - i );if( tmp max_capacity ){max_capacity tmp;}}}return max_capacity;}
};5.2 解法二
采用双指针分别指向数组两端每次让短板一端的指针往中间收拢一格依次计算两指针所指垂线间的容水体积并保留最大值总共只用遍历一次数组。该方法关键在于向内移动短板容水体积可能增大也可能减小向内移动长板容水体积必然减小因为容水体积主要由短板决定向内移动长板后短板可能不变或者变得更短同时两板距离必然缩短所以容水体积必然缩短。
class Solution {
public:int maxArea(vectorint height) {int i 0, j height.size() - 1, res 0;while(i j) {res height[i] height[j] ? max(res, (j - i) * height[i]): max(res, (j - i) * height[j--]); }return res;}
};6. 三数之和
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。
6.1 解法1
直接用三层for循环每次取其中一个元素求和再判断。由于可能存在多个相同的三元组因此还需要去重。时间复杂度On^3.
6.2 解法2
采用排序双指针。为了便于实现取得不重复的三元组对数组先进行排序从而保证后续三元组a,b,c中a b c 就不会出现c,a,b、b,c,a…重复三元组。其次排序后可以利用有序的特性结合双指针减少计算次数。(当我们需要枚举数组中的两个元素时如果我们发现随着第一个元素的递增第二个元素是递减的那么就可以使用双指针的方法将枚举的时间复杂度从O(n^2)减少至 O(n)。使用双指针有一个必要的步骤就是左右指针碰面时即停止使得n个元素只被遍历n次)。固定第一个参数a左指针元素为b右指针元素为c一开始指向尾端abc0则右移重复至abc0此时右指针不用回退由于左指针下一个遍历元素一定大于等于前一个遍历的元素所以abc必然比之前大此时右指针要么不动要么往左移动三者之和大于0直至左指针右指针碰面结束第二层for循环。此外还需注意若前一个b和后一个b相等则无需重复遍历记录三元组。总时间复杂度为O(n^2)。
class Solution {
public:vectorvectorint threeSum(vectorint nums) {int n nums.size();sort(nums.begin(), nums.end());vectorvectorint ans;// 枚举 afor (int first 0; first n; first) {// 需要和上一次枚举的数不相同if (first 0 nums[first] nums[first - 1]) {continue;}// c 对应的指针初始指向数组的最右端int third n - 1;int target -nums[first];// 枚举 bfor (int second first 1; second n; second) {// 需要和上一次枚举的数不相同if (second first 1 nums[second] nums[second - 1]) {continue;}// 需要保证 b 的指针在 c 的指针的左侧while (second third nums[second] nums[third] target) {--third;}// 如果指针重合随着 b 后续的增加// 就不会有满足 abc0 并且 bc 的 c 了可以退出循环if (second third) {break;}if (nums[second] nums[third] target) {ans.push_back({nums[first], nums[second], nums[third]});}}}return ans;}
};7. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
7.1 解法1
class Solution {
public:int trap(vectorint height) {int i0,j1,k0;int h_size height.size();int tmp 0;int capacity 0;while(j h_size){if(height[i] 0){i;j;}if( ((j-i) 1) || (height[j] height[i]) ){if( height[j] height[i] ){i j;tmp 0;}else{tmp height[j];}j;}else{capacity height[i]*(j-i-1)-tmp capacity;tmp 0;i j;j;}}if(tmp ! 0){tmp 0;k j-1; j j-2;// i i-1;while(k ! i){if(height[k] 0){k--;j--;}if( ((k-j) 1) || (height[j] height[k]) ){if( height[j] height[k] ){k j;tmp 0;}else{tmp height[j];}j--;}else{capacity height[k]*(k-j-1)-tmp capacity;tmp 0;k j;j--;}}}return capacity;}
};小结
双指针主要用于需要遍历两次时左右指针分别指向头尾两者依次往中间靠拢可以找到某一规律例如计算规律使得两个指针不用回溯直至两者碰面结束。将遍历两次的复杂度O(n^2)降至O(n)。
滑动窗口
8. 无重复字符的最长子串
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
示例 1: 输入: s “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”所以其长度为 3。 示例 2:
输入: s “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”所以其长度为 1。 示例 3:
输入: s “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。
8.1 解法1
采用哈希表记录已出现且不重复的字符key为每个字符value为每个不同字符当前最大的索引号方便移动指针到刚好除去旧的重复字符的位置。采用双指针一个指向当前搜索子串的前一个位置一个指向当前搜索子串字符的最后一个字符位置一直从头找到尾。当有重复字符出现下一个搜索的子串开头则是该重复字符上次出现的位置的后一个位置。
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_mapchar, int dic;int i -1, res 0, len s.size();for(int j 0; j len; j) {if (dic.find(s[j]) ! dic.end())i max(i, dic.find(s[j])-second); // 更新左指针dic[s[j]] j; // 哈希表记录保证当有重复字符出现时i能直接指到重复字符上次出现的位置res max(res, j - i); // 更新结果}return res;}
};9. 找到字符串中所有字母异位词
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串包括相同的字符串。
示例 1:
输入: s “cbaebabacd”, p “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。 示例 2:
输入: s “abab”, p “ab” 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
9.1 解法一
时间超出限制。
class Solution {
public:vectorint findAnagrams(string s, string p) {unordered_mapchar,int mp;vectorint result;int i 0, psize p.size();int ssize s.size();if(psize ssize) return result;//将p中的字符存储至哈希表中,key为单个字符value为该字符出现的次数while(i psize ){if(mp.find(p[i]) mp.end())mp[p[i]] 1;elsemp[p[i]] 1; i;}unordered_mapchar,int tmpmp;for(int j 0; j ssize - psize 1; j){tmpmp mp;for(i 0; i psize; i){if(tmpmp.find(s[ji]) ! tmpmp.end()){if(tmpmp[s[ji]] 0){break;}else{tmpmp[s[ji]] - 1;}}else{j j i;break;}}if(i psize){result.push_back(j);}}return result;}
};9.2 解法二
用一个数组记录p字符串中26个字母出现频次记录每个字符还需要几个为0则表示刚好满足条件且不需要负数则表示已经出现的太多了采用左右指针分别指向搜索s字符串的当前子串的头和尾整数count记录剩余所需继续匹配字符个数。左右指针均先指向s的首个字符右指针依次往右移动同时对应的字符在数组中的频次减1仍待匹配的字符频次为正数无需匹配的字符频次为非正数每次检查右指针所指字符是否在p串中即p中对应的字符频次大于0若在则说明找到匹配的字符则count–。当count为0时则说明当前字串已经完全匹配p返回子串首位置。当已经核验过的字符数量与p串的字符数量相等时搜索窗口已经到达最大因此需要收缩一下窗口则左指针需要往右移丢掉前面的一个字符对应的也需增加被丢掉字符的频次。如果被丢掉字符所需要匹配的频次大于等于0只有是p串中出现的字符频次才会有可能大于等于0可能为负数则表明该字符本应该只需要n次子串中却已经有n1个则直接丢掉即可未出现在p串中的字符一定是负数因为前面会对索引过的字符频次进行减一0-1-1则count需要加1。由于对每个被右指针索引过的字符频次均会被减1因此丢掉该字符时频次均需要加1。
class Solution {
public:vectorint findAnagrams(string s, string p) {int sLen s.length(), pLen p.length();vectorint result;if (sLen pLen) {return result; // 如果输入为空或者s的长度小于p的长度则直接返回空结果}int pFreq[26] {0}; // 数组记录字符出现频率长度为26表示小写字母的26个字符// 记录p中每个字符的出现次数for (char c : p) {pFreq[c - a]; // 将字符映射到数组的索引增加出现次数}int left 0, right 0, count pLen; // 初始化左右指针和计数器while (right sLen) {// 步骤一if (pFreq[s[right] - a] 0) {count--; // 如果当前字符在p中存在则减少count计数}pFreq[s[right] - a]--; // 更新频率数组出现过的字符频率值-1right; // 右指针向右移动// 步骤二 if (count 0) {result.push_back(left); // 如果找到一个异位词记录起始索引}// 步骤三if (right - left pLen) { // 当窗口大小等于p的长度时if (pFreq[s[left] - a] 0) {count; // 如果左边界对应字符在p中则增加count计数}pFreq[s[left] - a]; // 恢复频率值left; // 左指针向右移动}}return result; // 返回结果}
};子串
10 和为k的子数组
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
解法1
暴力求解法采用双for循环遍历每一个子数组看是否满足条件和为k。时间复杂度为On^2。
解法2
序号[0…j…i…n]的数组当[j…i]子数组之和等于k时可以看作前i个数之和-前j-1个数之和。因此通过这一点可以实现仅用i遍历一遍数组即可求得所有满足条件的子数组个数。
每次将前i个元素的和pre[i]作为哈希表的keyvalue用来记录第i个元素之前有几个子数组【0…j-1】的和等于key。每当遍历到第i个元素时则会寻找第i个元素前面有哪些【0…j-1】子数组j i的和满足pre[i] - k pre[j-1]找到的话即表示存在【j…i】的子数组之和等于k。
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint, int mp;mp[0] 1;int count 0, pre 0;for (auto x:nums) {pre x;if (mp.find(pre - k) ! mp.end()) {count mp[pre - k];}mp[pre];//可能有不同的【0...j-1】子数组和相同}return count;}
};11. 滑动窗口最大值
给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
解法一
不妥虽然速度快
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {int i 0,j k-1,p,maxorder;int max -2147483647;int flag 0;int flag2 0; int numsize nums.size();vectorint result;while(j numsize){p i;max -2147483647;if(flag 1) flag2 1;//若上次得到窗口内是单调递减的序列则表示可以开始利用前一次的全是单调递减特性进行优化if(i 0 || maxorder i)//若目前为第一个窗口或上次最大值已不在窗口内{if(flag 1)//若上次得到窗口内是单调递减的序列{if(nums[j] nums[j-1]){max nums[i];maxorder i;}else{flag 0;}}if(flag2 1 i k)//若之前有过窗口内是单调递减的序列的情况{if(nums[i] nums[j])//则直接拿新加入窗口的值与当前窗口的第一个值比较{result.push_back(nums[i]);i;j;continue;}}if(flag 0){while(p j)//遍历窗口里所有元素获取最大值同时记录单调性{if(nums[p] max ) {max nums[p];maxorder p;}if(i p ) flag 1;else if(nums[p-1] nums[p] flag ! 0 )flag 1; //单调递减elseflag 0;p;}}}else//若前一个窗口的最大值仍在当前窗口内则只需拿出前一个窗口的最大值与新加入窗口的值进行比较{max result.back() nums[j] ? result.back():nums[j];if(result.back() nums[j]){max result.back();}else{max nums[j];maxorder j;}}result.push_back(max);i;j;}return result;}
};
解法二
采用单调队列。
假设第i个元素在第j个元素的前面【0…i…j…n】并且第i个元素不大于第j个元素nums[j] nums[i]。当滑动窗口向右移动时只要第i个元素还在窗口中那么第j个元素一定也还在窗口中。因此由于 nums[j]的存在nums[i]一定不会是滑动窗口中的最大值了我们可以将 nums[i]永久地移除。可以用一个队列存储这些不被永久移出的元素下标每次将一个新元素入队时严格循环检查该新元素是不是比队列的最后一个元素要大如果是的则可以永久地移出目前处于队尾的元素在进行反复判断至队列为空或有比新元素更大的元素在队尾如果不是直接将新元素插入队尾。这个队列将严格保证元素序列时单调递减的因此队首元素是整个队列的最大值。窗口右移过程中当队列的队首元素已经离开窗口后则需要及时将该队首元素弹出。
class Solution {
public:vectorint maxSlidingWindow(vectorint nums, int k) {int n nums.size();dequeint q;for (int i 0; i k; i) {while (!q.empty() nums[i] nums[q.back()]) {q.pop_back();}q.push_back(i);}vectorint ans {nums[q.front()]};for (int i k; i n; i) {while (!q.empty() nums[i] nums[q.back()]) {q.pop_back();}q.push_back(i);while (q.front() i - k) {q.pop_front();}ans.push_back(nums[q.front()]);}return ans;}
};12. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。
注意 对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串我们保证它是唯一的答案。
解法1
哈希表双指针。
首先用哈希表存储t串中的字符以及出现的次数用双指针ij指向当前子串的首尾。j 依次向右移动至 i 到 j 的子串中出现了 t 串的所有字符且频次更大于或等于则 i 就往右移开始收缩子串至子串中字符出现频次小于 t 串中的则 j 继续右移循环往复记录满足条件的最短子串。
class Solution {
public:unordered_mapchar,int mp,tmpmp;bool check() {for (const auto p: mp) {if (tmpmp[p.first] p.second) {return false;}}return true;}string minWindow(string s, string t) {int tsize t.size();int ssize s.size();int i 0,j 0;int si-1,sj-1;int minlenth 10000000;for(i 0;i tsize; i){mp[t[i]] mp.find(t[i]) mp.end()? 1: mp[t[i]] 1 ;}i j 0;while(j ssize){if(tmpmp.find(s[j]) ! tmpmp.end()){tmpmp[s[j]];}else{if(mp.find(s[j]) ! mp.end()) tmpmp[s[j]] 1;}while(check()){if(minlenth j-i1 ){si i;sj j;minlenth j-i1;}if(tmpmp.find(s[i]) ! tmpmp.end()){tmpmp[s[i]]--;}i;}j;}if(si -1) return string();return s.substr(si, sj-si1);}
};数组
13 最大子数组和
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。
解法1
动态规划法:
每次计算以第 i 个元素结尾的最大子数组和。如果第 i - 1 个元素结尾的最大子数组和为负数则说明第 i 个元素加上前面最大子数组的总和肯定更小因此直接放弃前面的所有子数组以第 i 个元素当作以第 i 个元素结尾的最大子数组和自立门户如果第 i - 1 个元素结尾的最大子数组和为正数则说明第 i 个元素加上前面最大子数组的总和肯定更大可以组成以第 i 个元素结尾最大的子数组和。
class Solution {
public:int maxSubArray(vectorint nums) {int pre 0, maxAns nums[0];for (const auto x: nums) {pre max(pre x, x);maxAns max(maxAns, pre);}return maxAns;}
};14. 合并区间
以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
解法1
首先按照每个区间的第一个元素进行排序之后遍历每个区间每次检查当前第 i 个 区间[a,b]的右侧是否大于等于下一个第 i 1个区间[c,d]的左侧。如果是则表示可以融合为更大的区间[a,d]如果不是则表明两者不可融合后面要重新开启一个新的区间。
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {sort(intervals.begin(), intervals.end());vectorvectorint ans;for (int i 0; i intervals.size();) {int t intervals[i][1];int j i 1;while (j intervals.size() intervals[j][0] t) {t max(t, intervals[j][1]);j;}ans.push_back({ intervals[i][0], t });i j;}return ans;}
};15. 轮转数组
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
解法1
利用vector特性先插入数组后k个元素到数组的首段之后再删除数组后k个元素。
class Solution {
public:void rotate(vectorint nums, int k) {if(nums.size() 1 || nums.size() k) return;k k % nums.size();nums.insert(nums.begin(),nums.end()-k,nums.end());nums.erase(nums.end()-k,nums.end());}
};解法2
数组多次反转
class Solution {
public:void reverse(vectorint nums, int start, int end) {while (start end) {swap(nums[start], nums[end]);start 1;end - 1;}}void rotate(vectorint nums, int k) {k % nums.size();reverse(nums, 0, nums.size() - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.size() - 1);}
};15. 除自身以外数组的乘积
给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法且在 O(n) 时间复杂度内完成此题。
解法1
所有的结果如下图所示。根据规律可采用两次循环分别遍历数组计算下三角的累乘和上三角的累乘。
第一次for循环计算下三角的累乘并存储下来到B数组中。第二次for循环可以从n至1遍历计算下三角每层的累乘顺便直接与B数组中对应层相乘直接计算出该层的最终结果值。 class Solution {
public:vectorint productExceptSelf(vectorint nums) {int len nums.size();if (len 0) return {};vectorint ans(len, 1);ans[0] 1;int tmp 1;for (int i 1; i len; i) {ans[i] ans[i - 1] * nums[i - 1];}for (int i len - 2; i 0; i--) {tmp * nums[i 1];ans[i] * tmp;}return ans;}
};
