做网站用什么配置的笔记本,常州溧阳市建设局网站,对比色的网站,好用的网页编辑器仅供个人复习 1.两数相加2.寻找峰值6.岛屿的最大面积3.最大数4.会议室5.最长连续序列6.寻找两个正序数组的中位数 1.两数相加
给你两个 非空 的链表#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的#xff0c;并且每个节点只能存储 一位 数字。
请… 仅供个人复习 1.两数相加2.寻找峰值6.岛屿的最大面积3.最大数4.会议室5.最长连续序列6.寻找两个正序数组的中位数 1.两数相加
给你两个 非空 的链表表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的并且每个节点只能存储 一位 数字。
请你将两个数相加并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外这两个数都不会以 0 开头。
/*
因为两个链表都是逆序相当于个位数在最前面所以可以直接相加多余的十位数、百位数 用 temp 记录下来加到下一个节点
*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//构建新链表的头节点和尾节点ListNode* head nullptr;ListNode* tail nullptr;int tmp 0; //相加的进位比如7815tmp1while (l1 ! nullptr || l2 ! nullptr) {int val1 l1 ! nullptr ? l1-val : 0; // l1不为空取节点的值为空则取0int val2 l2 ! nullptr ? l2-val : 0;int sum val1 val2 tmp;// 往相加的链表后拼接节点if (head nullptr) {head new ListNode(sum % 10);tail head;} else {tail-next new ListNode(sum % 10);tail tail-next;}tmp sum / 10; //除了个位数剩下的是进位放入tmpif (l1 ! nullptr) l1 l1-next;if (l2 ! nullptr) l2 l2-next;}//最后如果 tmp ≠ 0说明还有进位需要一个节点存放if (tmp 0) tail-next new ListNode(tmp);return head;}
};2.寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] nums[n] -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
二分法注意mid1可能越界
class Solution {
public:int findPeakElement(vectorint nums) {int L -1, R nums.size();if(nums.size() 1) return 0;while(L 1 ! R){int mid (L R) / 2;if(mid nums.size() - 1){R nums.size() - 1;break;}if(nums[mid] nums[mid 1]) R mid;else L mid;}return R;}
};6.岛屿的最大面积
class Solution {
public:int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1};int count;void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y){for(int i 0; i 4; i ){int nextx x dir[i][0];int nexty y dir[i][1];if(nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue;if(!visited[nextx][nexty] grid[nextx][nexty] 1){visited[nextx][nexty] true;count;dfs(grid, visited, nextx, nexty);}}}int maxAreaOfIsland(vectorvectorint grid) {int res 0;vectorvectorbool visited(grid.size(), vectorbool(grid[0].size(), false));for(int i 0; i grid.size(); i ){for(int j 0; j grid[0].size(); j ){if(grid[i][j] 1 !visited[i][j]){count 1;//每个岛屿重置countvisited[i][j] true;dfs(grid, visited, i, j);res max(res, count);}}}return res;}};3.最大数
给定一组非负整数 nums重新排列每个数的顺序每个数不可拆分使之组成一个最大的整数。
注意输出结果可能非常大所以你需要返回一个字符串而不是整数。
class Solution {
public:string largestNumber(vectorint nums) {vectorstring str;for(auto i : nums){str.push_back(to_string(i));}auto cmp [](string left, string right){return left right right left;};sort(str.begin(), str.end(), cmp);string ans ;for(auto c : str){ans c;}if(ans[0] 0) return 0;return ans;}
};4.会议室
给你一个会议时间安排的数组 intervals 每个会议时间都会包括开始和结束的时间 intervals[i] [starti, endi] 返回 所需会议室的最小数量 。
输入intervals [[0,30],[5,10],[15,20]] 输出2
可以把他理解为上车下车问题 同时在车上最多人数就是需要的会议室数量 挺巧的这个做法
class Solution {
public:int minMeetingRooms(vectorvectorint intervals) {mapint, int umap;for(auto it : intervals){umap[it[0]];umap[it[1]]--;}int ans 0, cnt 0;for(auto itt : umap){cnt itt.second;ans max(ans, cnt);}return ans;}
};用map而不是unordered_map因为键值对在map中是有序的即元素按照键的升序排列。用他才能用上车下车的写法。
5.最长连续序列
给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
class Solution {
public:int longestConsecutive(vectorint nums) {unordered_setint set(nums.begin(), nums.end());int res 0;for(int num : set){if(set.find(num - 1) ! set.end()) continue;//不是第一个就跳过因为我们要找第一个int curNum num;int curLen 1;while(set.find(curNum 1) ! set.end()){curNum 1;curLen 1;}res max(res, curLen);}return res;}
};6.寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
输入nums1 [1,3], nums2 [2] 输出2.00000 解释合并数组 [1,2,3] 中位数 2
碎碎念除了学然后背还能怎样呢这篇已经接近终章了最后应该到不了一百题剩余不多的时间给自己复习吧反正都是背学了没背住就太亏了。
有难度但可能是因为题解看多了看懂并不难。。。笑 简单点来说要找第k小的咱每次排除k / 2个元素两个有序数组分别找他们的第k/2 - 1个数比较较小的那个数所在的数字的第0~k/2-1个数都不可能是答案所以就排除掉了这个数字的index另一个数组的index怎么办
首先明确咱不断比较的是有可能存在答案的数组的前k/2 - 1没被排除的数组从下标0开始都有可能他们的index仍然是 k/2 - 1从index开始的
其次注意边界问题假如数组顺序是完全无缝衔接的那么就会遇到越界问题越界的时候说明中位数在另一个数组中直接加上剩余的k即可
class Solution {
public:int getKthElement(vectorint nums1, vectorint nums2, int k){int m nums1.size();int n nums2.size();int index1 0, index2 0;while(true){if(index1 m) return nums2[index2 k - 1];if(index2 n) return nums1[index1 k - 1];if(k 1) return min(nums1[index1], nums2[index2]);int newIndex1 min(index1 k/2 - 1, m - 1);//防止越界int newIndex2 min(index2 k/2 - 1, n - 1);int pivot1 nums1[newIndex1];int pivot2 nums2[newIndex2];if(pivot1 pivot2){k - newIndex1 - index1 1;index1 newIndex1 1;}else{k - newIndex2 - index2 1;index2 newIndex2 1;}}}double findMedianSortedArrays(vectorint nums1, vectorint nums2) {int totalLength nums1.size() nums2.size();if(totalLength % 2 1) return getKthElement(nums1, nums2, (totalLength 1) / 2);else{return (getKthElement(nums1, nums2, totalLength / 2) getKthElement(nums1, nums2, totalLength / 2 1)) / 2.0;}}
};
