- 12023 Google 开发者大会：将大型语言模型部署到你的手机_谷歌大语言
- 2笔记：CentOS Linux release 7.6.1810安装 CUDA Toolkit_compute/cuda/repos/rhel7/x86_64/cuda-rhel7.repo
- 3unity中Input的几个方法_input.mousepresent
- 4使用 Elasticsearch 和 LlamaIndex 进行高级文本检索：句子窗口检索_liamaindex liama
- 5QT各版本源码下载_qt5.12.10源码下载
- 6软件工程填空题（50题）
- 7前端开发者：如何在没有UI设计图的情况下做出更好的前端页面_前端怎么看ui设计图
- 8YOLOv8详解代码实战，附有效果图_yolov8代码详解
- 9以太坊区块链网络部署及验证实验_以太坊私链 区块链网络实验
- 10别闹，程序员哪来的35岁危机？
LeetCode中级刷题_输入一个n*n的矩阵,然后将其右上半部分的元素置零。 输入 第一行输入n,然后输入n*
赞
踩
前言：由于开题好长时间不刷题了，中级的算法题好难啊！一定要再次坚持下去。
数组与字符串
1、三数之和
1）题目：
2）解析：排序+双指针（参考官方解法）
注意关键词：不重复。要用三重循环来解决此题
如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0。当第二重循环往后枚举一个元素 b’时，由于 b’ > b，那么满足 a+b’+c’=0的 c’ 一定有 c’ < c，即 c’在数组中一定出现在 c的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。
有了这样的发现，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针，
这个方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N^2) 减少至 O(N)。
总结：
a、把数组排序
b、三重循环，第一重从0 到length-2 遍历数组；第二重从i+1开始遍历；第三重从length-1开始遍历
c、比较nums[left] + nums[right] 与 nums[i]的关系；若相等，推入数组；若小于，left指针右移；若大于，right指针左移。
d、注意两次“去重”，第一次是三重循环，第二重从小到大，第三重从大到小；第二次，若比较相等left右移找到不等的值，right左移。
vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int length = nums.size(); vector<vector<int>> vec; for (int i = 0; i < length-2; i++) { //过滤重复 if (i > 0 && nums[i] == nums[i - 1]) continue; //第二重循环从小到大枚举 int left = i + 1; //第三重循环从大到小枚举 int right = length - 1; while (left < right) { if (nums[left] + nums[right] + nums[i] == 0) { vec.push_back(vector<int>()); vec.back().push_back(nums[left]); vec.back().push_back(nums[right]); vec.back().push_back(nums[i]); //过滤重复 //注意left与他的下一个left+1比较，不是前一个left-1哦，刚开始想的left-1一直不对， while (left < right && nums[left] == nums[left + 1]) { left++; } //过滤重复 //注意right与他的上一个right-1比较，不是前一个right+1哦，刚开始想的right+1一直不对， while (left < right && nums[right] == nums[right - 1]) { right--; } left++; right--; } //因为已经排序过了，(-nums[i])作为目标元素，如果nums[left] + nums[right]小于目标值，让left向右移动就会变大 else if (nums[left] + nums[right] < (-nums[i])) { left++; } else { //right向左移动相加值就会变小 right--; } } } return vec; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
2、矩阵置零
1）题目： 给定一个n*n的矩阵，如果一个元素为0，则将其所在行和列的元素都设为0，请使用“原地”算法。
2)思路一：
第一次循环把是0的位置的行数和列数存在队列里，（pair可以把两个元素合并成一个元素）；第二次循环把对应元素置0。
//空间复杂度：O(m + n) void setZeroes2(vector<vector<int>>& matrix) { //第一次遍历把0元素的行和列存在队列中 //pair 将两个数据组合成一个数据 //当一个函数需要两个数据时，也可以用pair queue<pair<int, int>> rot; //行数 int line = matrix.size(); //列数 int row = matrix[0].size(); for (int i = 0; i < line; i++) { for (int j = 0; j < row; j++) { if (matrix[i][j] == 0) rot.emplace(i, j); } } //第二次遍历把对应元素改为0 while (!rot.empty()) { //行 int h = rot.front().first; //列 int l = rot.front().second; rot.pop(); for (int i = 0; i < line; i++) { matrix[i][l] = 0; } for (int j = 0; j < row; j++) { matrix[h][j] = 0; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
3）思路二：
用两个标记数组代替思路一的队列，一个标记行，一个标记列。如果元素为0，就把元素对应的行数和列数标记为true。第二次遍历，再把行数或列数为true的元素置0。
//空间复杂度：O(m + n) //用两个标记数组代替下面的队列 void setZeroes3(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); vector<int> row(m), col(n); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (!matrix[i][j]) { row[i] = col[j] = true; } } } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (row[i] || col[j]) { matrix[i][j] = 0; } } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
4）思路三：
把矩阵的第一行和第一列作为标记数组。
第一次遍历所有元素，如果matrix[i][j]是0就把第一行第一列对应的行和列（matrix[i][0] matrix[0][j]）置0，如果第一行或第一列原本就有0，用flag_row或flag_col标记一下。
第二次遍历除第一行第一列以外的其他元素，如果他所在对应的matrix[i][0] matrix[0][j]为0，则把该元素置为0。
如果第一行或第一列原本就有0（flag_row或flag_col为true），就把第一行或第一列置0。
//我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间。 void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); int n = matrix[0].size(); //标记第一行是否有数字0 int flag_row = false; //标记第一列是否有数字0 int flag_col = false; for (int i = 0; i < m; i++) { //如果matrix[i][j]是0就把第一行第一列对应的行和列（matrix[i][0] matrix[0][j]）置0 for (int j = 0; j < n; j++) { if (matrix[i][j] == 0) { //如果第一行或第一列原本就有0，标记一下 if (i == 0) flag_row = true; if (j == 0) flag_col = true; matrix[i][0] = matrix[0][j] = 0; } } } //遍历除第一行第一列以外的其他元素，如果他所在对应的matrix[i][0] matrix[0][j]为0，则把该元素置为0 for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (!matrix[i][0] || !matrix[0][j]) { matrix[i][j] = 0; } } } //如果第一行原本就有0，就把第一行置0 if (flag_row) { for (int i = 0; i < n; i++) { matrix[0][i] = 0; } } //如果第一列原本就有0，就把第一列置0 if (flag_col) { for (int j = 0; j < m; j++) { matrix[j][0] = 0; } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
3、字母异位词
1）题目：
2）思路：由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
vector<vector<string>> groupAnagrams(vector<string>& strs) { //对字符串数组中的每一个字符串排序，排序结果相同的就是字母异位词 //键值是源字符串，键是排序后的字符串。妙妙妙！！! //unordered_map 哈希映射 无序 map是有序容器 unordered_map<string, vector<string>> stp; vector<vector<string>> res; int length = strs.size(); //注意是 string& 不是 string for (string& str : strs) { string key = str; sort(key.begin(), key.end()); stp[key].emplace_back(str);//stp[key]表示key这组异位词的集合 } //unordered_map 前向迭代期 for (auto it = stp.begin(); it != stp.end(); ++it) { res.emplace_back(it->second);//遍历哈希表，将字母异位词的集合存入结果集中 } return res; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
4、无重复字符的最长子串
1）题目：
2）思路：
定义一个bool型的标记数组str[255]，字母s[i]出现以后，对应的str[s[i]]=true；当字母再次出现时，追溯到第一次出现的位置j，无重复字符的长度就是 i-j+1;
int lengthOfLongestSubstring(string s) { //双指针，i指针是遍历字符串，j指针回溯 int length = s.size(); bool nums[255] = { false }; int j = 0,maxnum=0; for (int i = 0; i < length; i++) { //2、访问到重复字符，将其推移,直到找到第一个重复字符 while (nums[s[i]]) { nums[s[j]] = false; ++j; } //1、每访问一个新的字符，就将其进行标记 nums[s[i]] = true; maxnum = max(maxnum, i - j + 1); } return maxnum; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
5、最长回文子串
1）题目：
2）思路：中心扩散法
回文子串中心互为镜像，因此，回文可以从他的中心展开，奇数有一个中心点，偶数有两个中心点。
//最长回文串（毫无头绪啊！！！！！！） //中心扩展法 string longestPalindrome(string s) { int length = s.size(); if (length < 2) return s; int start = 0;//最长回文串起始位置 int end = 0;//终止位置 int maxlength = 0; for (int i = 0; i < length; i++) { int odd = strlength(s, i, i);//奇数中心 int even = strlength(s, i, i + 1);//偶数中心 maxlength = max(max(odd, even), maxlength); if (maxlength > (end - start + 1)) { start = i - (maxlength - 1) / 2; end = i + maxlength / 2; } } return s.substr(start, maxlength); //该函数的意思是获取从start开始长度为mlen长 度的字符串 } //以left和right为中心的回文串长度 int strlength(string s, int left, int right) { //注意left可以取到0 while ( left>=0 && right<s.size() && s[left] == s[right]) { left--; right++; } return right - left - 1;//返回回文子串的长度 }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
6、递增的三元子序列
1）题目：
2）思路：注意一点三元子序列只要是递增的就可以，可以连续也可以不连续。
定义两个变量，一个用来存储最小值，一个用来存储中间值，注意他们的初始值是 INT_MAX。扫描数组：
如果当前数字小于等于最小值，就更新最小值；
如果当前数字大于最小值但小于等于中间值，就更新中间值；
如果当前值既不小于等于最小值也不小于等于中间值，则说明找到了三个递增子序列，直接返回true。
//子序列可以不连续 bool increasingTriplet(vector<int>& nums) { int length = nums.size(); if (length < 3) return false; int minnum = INT_MAX, mid = INT_MAX; for (int i = 0; i < length; i++) { if (nums[i] <= minnum) minnum = nums[i]; else if (nums[i] <= mid ) { mid = nums[i]; } else { return true; } } return false; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
链表
1、两数相加
1）题目：
2）错误思路：
刚开始想的是先把两个链表转化成对应的数字，然后两个数字相加计算出和，最后把和转化成链表输出。由于长时间不做链表的题导致都不会常见链表了，废了好多时间。而且这种方法还没有通过测试，因为两数之和超出了INT的范围。
3）正确思路：
由于输入的两个链表都是 逆序 存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
我们同时遍历这两个链表，逐位计算他们的和，并与当前位置的进位值相加。
此处有两点注意：a、最终结果也是逆序存储 b、进位值的处理
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { //创建list链表存出结果 ListNode* list = new ListNode; //ptr是临时链表，存储每一位数字，再把他插入list ListNode* ptr = list; int number = 0; while (number || l1!=nullptr || l2 != nullptr) { if (l1 != nullptr) { number += l1->val; l1 = l1->next; } if (l2 != nullptr) { number += l2->val; l2 = l2->next; } //number % 10只取末位数字存入链表 //在list末尾插入数据，保证最终结果也是逆序存储（最低位是个位） ptr->next = new ListNode(number % 10, nullptr); ptr = ptr->next; //进位值 number = number / 10; } return list->next; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
2、奇偶链表
1）题目：
2）思路： 双指针（链表经常应用双指针）——参考“数据结构和算法”的解题思路
一个指针把奇数位置串联起来，另一个指针把偶数位置连起来，再把偶数位置链表头部接到奇数位置指针尾部。
所以需要定义几个变量：
记录奇数位置的头部指针：oddhead
奇数位置扫描指针：oddcur
记录偶数位置的头部指针：evenhead
偶数位置扫描指针：evencur
ListNode* oddEvenList(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } //分别记录奇数链表的头节点和尾节点，偶数链表的头节点和尾节点 //奇数链表的头结点 ListNode* odd = head; //奇数链表的当前节点 ListNode* oddcur = odd; //偶数链表的头结点 ListNode* even = head->next; //偶数链表的当前节点 ListNode* evencur = even; while (evencur !=nullptr && evencur->next!=nullptr)//注意这是偶数当前节点，不能是奇数;因为偶数在奇数后面 { //奇数节点串在一起 oddcur->next = oddcur->next->next; //偶数节点串在一起 evencur->next = evencur->next->next; //奇偶指针往后移动 oddcur = oddcur->next; evencur = evencur->next; } //最后把偶数链表的头部串在奇数链表的尾部 oddcur->next = even; //返回奇数指针的头部 return odd; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
3、相交链表
1）题目：
2）思路：这道题看起来说的很多，很复杂是的，其实就是找两个链表的交点。我首先想到的是先遍历一个链表，并把它的值存入哈希表中，再遍历另一个链表，如果哈希表中存在此链表中的当前值，当前值就是两个链表的焦点。但是哈希表存两个值，此处只需要保存一个值就够了，用哈希表浪费空间。参考评论区，选用的是集合不是哈希表。
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { //把headA链表遍历一遍，把值存在集合中；再遍历headB链表，若果在集合中存在headB中的值就返回该值 set<ListNode*> mac; while (headA !=nullptr) { mac.insert(headA); headA = headA->next; } while (headB !=nullptr) { if (mac.count(headB)) { return headB; } headB = headB->next; } return nullptr; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
3）思路2：先计算两个链表的长度，如果两个链表的长度不相等就让长的先走，直到两个链表一样长了再同时走。同时比较当前节点是否相同，如果不同就同时继续往后移动。
//计算链表长度 int length(ListNode* head) { int n = 0; while (head!=nullptr) { head = head->next; n++; } return n; } ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { int length1 = length(headA); int length2 = length(headB); //如果两个链表长度不相等，长度长的先走 while (length1!=length2) { if (length1 > length2) { headA = headA->next; length1--; } else { headB = headB->next; length2--; } } //两个长度相等了再开始比较 while (headA!=headB) { headA = headA->next; headB = headB->next; } //走到最后，最终会有两种可能，一种是headA为空， //也就是说他们俩不相交。还有一种可能就是headA //不为空，也就是说headA就是他们的交点 return headA; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
4）思路：双指针——参考“数据结构与算法”解法
假设A有5个节点，B有8个节点
因为A和B的总节点数是不变的13，A指针把A链表走完以后就开始从B链表头部开始走，同时B指针把B链表走完了就开始从A链表头部开始走。如果A链表和B链表相交，A、B指针肯定会在相交点相遇，因为到相交点出A、B指针走过的路一样长，都刚好吧整个链表 完整的走了 一遍。
下面这条评论简洁又有趣的概括了这种思路：
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) { //双指针:A指针如果把A链表走完了，然后就从B链表开始走；B指针如果把B链表走完了就从A开始走； //如此循环，只要A和B链表相交，总会相遇 ListNode* listA = headA; ListNode* listB = headB; while (listA!=listB) { //如果指针listA不为空，listA就往后移一步。 //如果指针listA为空，就让指针listA指向headB（注意这里是headB不是listB） listA = listA == nullptr ? headB : listA->next; listB = listB == nullptr ? headA : listB->next; } //listA要么是空，要么是两链表的交点 return listA; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
