仅供个人复习
- 1.两数相加
- 2.寻找峰值
- 3.寻找旋转排序数组中的最小值
- 4.寻找旋转排序数组中的最小值II
- 5.搜索旋转排序数组
- 6.岛屿的最大面积
- 7.最大数
- 8.会议室
- 9.最长连续序列
1.两数相加
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
/*
因为两个链表都是逆序,相当于个位数在最前面,所以可以直接相加,多余的十位数、百位数 用 temp 记录下来,加到下一个节点
*/
class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//构建新链表的头节点和尾节点ListNode* head = nullptr;ListNode* tail = nullptr;int tmp = 0; //相加的进位,比如7+8=15,tmp=1while (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) 的算法来解决此问题。
二分法,注意mid+1可能越界
class Solution {
public:int findPeakElement(vector<int>& 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;}
};
3.寻找旋转排序数组中的最小值
按照二分法的模板,right = nums.size(),但是这里必须是right = nums.size() - 1.
我还没明白
class Solution {
public:int findMin(vector<int>& nums) {int left = -1, right = nums.size() - 1;while(left + 1 != right){int mid = (left + right) / 2;if(nums[mid] < nums.back()) right = mid;else left = mid;}return nums[right];}
};
4.寻找旋转排序数组中的最小值II
可能存在 重复 元素值的数组 nums !!!
class Solution {
public:int findMin(vector<int> &nums) {int left = -1, right = nums.size() - 1; // 开区间 (-1, n-1)while (left + 1 < right) { // 开区间不为空int mid = left + (right - left) / 2;if (nums[mid] < nums[right]) right = mid; // 蓝色else if (nums[mid] > nums[right]) left = mid; // 红色else --right;}return nums[right];}
};
5.搜索旋转排序数组
整数数组 nums 按升序排列,数组中的值 互不相同 。
在某个点旋转之后,找target下标
class Solution {
public:int findMin(vector<int>& nums){int left = -1, right = nums.size() - 1;while(left + 1 != right){int mid = (right + left) / 2;if(nums[mid] < nums.back()) right = mid;else left = mid;}return right;}int lower_bound(vector<int>& nums, int left, int right, int target){while(left + 1 != right){int mid = (left + right) / 2;if(nums[mid] < target) left = mid;else right = mid;}if(right == nums.size()) return -1;return nums[right] == target ? right : -1;}int search(vector<int>& nums, int target) {int index = findMin(nums);if(target > nums.back()){int ans = lower_bound(nums, -1, index, target);return ans;}return lower_bound(nums, index - 1, nums.size(), target);}
};
6.岛屿的最大面积
class Solution {
public:int dir[4][2] = {-1, 0, 0, -1, 1, 0, 0, 1};int count;void dfs(vector<vector<int>>& grid, vector<vector<bool>>& 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(vector<vector<int>>& grid) {int res = 0;vector<vector<bool>> visited(grid.size(), vector<bool>(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;}};
7.最大数
给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
class Solution {
public:string largestNumber(vector<int>& nums) {vector<string> 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;}
};
8.会议室
给你一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ,返回 所需会议室的最小数量 。
输入:intervals = [[0,30],[5,10],[15,20]]
输出:2
可以把他理解为上车下车问题
同时在车上最多人数就是需要的会议室数量
挺巧的这个做法
class Solution {
public:int minMeetingRooms(vector<vector<int>>& intervals) {map<int, 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中是有序的,即元素按照键的升序排列。用他才能用上车下车的写法。
9.最长连续序列
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
class Solution {
public:int longestConsecutive(vector<int>& nums) {unordered_set<int> 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;}
};