难度2

删除链表的倒数第 n 个结点 原题链接：https://leetcode.cn/problems/SLwz0R/ 给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 1.计算链表长度一种最容易想到的方法：（无虚拟头结点） 首先从头节点开始对链表进行一次遍历，得到链表的长度length 然后从头节点开始对链表进行一次遍历，当遍历到第L−n+1个节点时，其下一个就是需要删除的节点 1234567891011121314151617181920212223242526272829303132333435363738class Solution {public: int getLength(ListNode *head) { int length = 0; while (head) { head = head->next; length++; } return length; } ListNode* removeNthFromEnd(ListNode *head, int n) { if (head == nullptr) return nullptr; int listSize = getLength(head); if (n < 1 || n > listSize) return nullptr;// 1 <= n <= len ListNode* deleteNode; if (n == listSize) { //delete the firstNode deleteNode = head; head = head->next; } else { ListNode* p = head; int ind = listSize - n - 1; while (ind--) p = p->n ...

二维子矩阵的和 原题链接：https://leetcode.cn/problems/O4NDxx/ 给定一个二维矩阵 matrix，以下类型的多个请求： 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。 实现 NumMatrix 类： NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。 1.二维前缀和1234567891011121314151617181920class NumMatrix {public: vector<vector<int>> prefix; NumMatrix(vector<vector<int>>& matrix) { /* 初始化前缀和数组 */ if (matrix.size() == 0) return; int m = matrix.size(); int n = matrix[0].size(); prefix.assign(m + 1, vector<int>(n + 1, 0)); //prefix.resize(m + 1, vector<int>(n + 1)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) prefix[i + 1][j + 1] = prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j] + matrix[i][j]; } int sumRegion(int x1, int y1, int x2, int y2) { /* 利用前缀和数组进行面积和su ...

左右两边子数组和相等 原题链接：https://leetcode.cn/problems/tvdfij/solutions/ 给你一个整数数组 nums ，请计算数组的中心下标。 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于最左端，那么左侧数之和视为0，因为在下标左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。 如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标返回-1 1.前缀和12345678910111213141516171819202122class Solution {public: int pivotIndex(vector<int>& nums) { int ans = INT32_MAX; int len = nums.size(); //1.初始化前缀和数组 int *prefix = new int[len + 10](); for (int i = 1; i <= len; ++i) prefix[i] = prefix[i - 1] + nums[i - 1]; //2.开始计算首先处理首位两种特殊情况 if (prefix[len] - prefix[1] == 0) return 0; if (prefix[len - 1] == 0) ans = min(ans , len - 1); //3.处理一般情况 for (int i = 1; i < len - 1; ++i) { if (prefix[i] == prefix[len] - prefix[i + 1]) ans = min(ans, i); } return ans == INT32_MAX ? -1 : ans; }}; 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 2.前缀和优化利用一些简单的数学知识知识，可以对前缀和的思路进行进一步的优 ...

排序数组中两个数字之和 原题链接：https://leetcode.cn/problems/kLl5u1/ 给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。 1.双指针1234567891011121314151617181920class Solution {public: vector<int> twoSum(vector<int>& numbers, int target) { vector<int> ans; int low = 0, high = numbers.size() - 1; while (low < high) { int sum = numbers[low] + numbers[high]; if (sum == target) { ans.push_back(low); ans.push_back(high); break; } else if (sum < target) { low++; } else if (sum > target) { high--; } } return ans; }}; 时间复杂度：$O(n)$ 空间复杂度：$O(1)$ 2.二分查找12345678910111213141516171819202122class S ...

有效的括号 原题链接：https://leetcode.cn/problems/valid-parentheses/ 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 1.化简思维可以将问题先简化为1种括号的匹配问题（判断左括号、右括号的数量是否相等），再扩展括号匹配的种类： +1可以等价为进入，-1可以等价为出去 一对()可以等价为一个完整的事件 (())可以看做事件与事件之间的完全包含关系 1种括号匹配123456789101112131415//写法1bool isValid(char *s) { int lum = 0, rnum = 0; int len = strlen(s); for (int i = 0; i < len; ++i) { switch (s[i]) { case '(' : ++lnum; break; case ')' : ++rnum; break; default : return flase; } if (lnum >= rnum) continue; return false; } return lnum = rnum;} 123456789101112131415//写法2bool isValid(char *s) { int lum = 0; int len = strlen(s); for (int i = 0; i < len; ++i) { switch (s[i]) { case '(' : ++lnum; break; ...

外观数列 原题链接：https://leetcode.cn/problems/count-and-say/ 给定一个正整数 n，输出外观数列的第 n 项。 外观数列是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列： countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。 前五项如下： 123456789101. 12. 113. 214. 12115. 111221第一项是数字 1 描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221" 要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。 对于每个组，先描述字符的数量然后描述字符，形成一个描述组。 要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。 例如，数字字符串 "3322251" 的描述如下图： 1.遍历上个字符串得到下个遍历前一个字符串 得到后一个字符串 1234567891011121314151617181920212223242526class Solution {public: void work(string &str, int cnt, char c) { str += (char)(cnt + '0');//数字数量 str += c;//数字字符 } void func(string &str1, string &str2) { int cnt = 0; for ( ...

搜索插入位置 原题链接：https://leetcode.cn/problems/search-insert-position/ 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 1.暴力法123456789class Solution {public: int searchInsert(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); ++i) { if (nums[i] >= target) return i; } return nums.size(); }}; 2.二分查找12345678910111213141516class Solution {public: int searchInsert(vector<int>& nums, int target) { if (nums[nums.size() - 1] < target) return nums.size(); int l = 0, r = nums.size() - 1; while (l != r) { int mid = (l + r) / 2; if (nums[mid] >= target) { r = mid; } else { l = mid + 1; } } return l; }};

两数之和 原题链接：https://leetcode.cn/problems/two-sum/ 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 1.暴力法1234567891011121314class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { int i, j; for (i = 0; i < nums.size(); ++i) { for (j = i + 1; j < nums.size(); ++j) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {i, j}; }}; 2.二分查找思想：sort排序 + 二分查找 使用for循环遍历数组中的每一个数字 在for循环内部，使用target值减去当前遍历的数字值获取配对值ret，使用二分查找该数字ret 如果找到该数字则直接输出其下标(初始若有序的情况下) 实际是无序的！难点在于如何联系被sort打乱下标后的vec与未打乱的nums，并从其中找出目标数字的下标？ 1234for (int j = 0; j < n; j++) { if (nums[j] == vec[i] || nums[j] == ret) result.push_back(j); if(result.size() == 2) return result;} 12345678910111213141516171819202122 ...

谁拿了最多奖学金 原题链接：http://oj.haizeix.com/problem/381 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同： 院士奖学金，每人 8000 元，期末平均成绩高于 80 分（>80），并且在本学期内发表 1 篇或 1 篇以上论文的学生均可获得； 五四奖学金，每人 4000 元，期末平均成绩高于 85 分（>85），并且班级评议成绩高于 80 分（>80）的学生均可获得； 成绩优秀奖，每人 2000 元，期末平均成绩高于 90 分（>90）的学生均可获得； 西部奖学金，每人 1000 元，期末平均成绩高于 85 分（>85）的西部省份学生均可获得； 班级贡献奖，每人 850 元，班级评议成绩高于 80 分（>80）的学生干部均可获得； 只要符合条件就可以得奖，每项奖学金的获奖人数没有限制，每名学生也可以同时获得多项奖学金。 现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高。 输入： 第一行是 1 个整数 N（1 ≤ N ≤ 100），表示学生的总数。 接下来的 N 行每行是一位学生的数据，从左向右依次是姓名、期末平均成绩、班级评议成绩、是否是学生干部、是否是西部省份学生、以及发表的论文数。 是否是学生干部和是否是西部省份学生分别用 1 个字符表示，Y 表示是，N 表示不是；发表的论文数是 0 到 10 的整数。 输出： 包括 3 行。 第 1 行是获得最多奖金的学生的姓名。 第 2 行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。 第 3 行是这 N 个学生获得的奖学金的总数。 样例： 123454YaoLin 87 82 Y N 0ChenRuiyi 88 78 N Y 1LiXin 92 88 N N 0ZhangQin 83 87 Y N 1 123ChenRuiyi900028700 思路： 构造student结构体，包含编号num、姓名name、期末平均成绩avg、班级评议成绩cla_avg、学生干部position、西部身份west、论文数量paper、奖学金money 进行学生信息的录入，并通过func()函数计算某个学生的奖学金money 利用sort函 ...