Polaris-hzn8

外观数列 原题链接：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/remove-element/ 1.巧妙的移动元素1234567891011121314class Solution {public: int removeElement(vector<int>& nums, int val) { int count = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[i] == val) { count++; } else { nums[i - count] = nums[i]; } } return nums.size() - count; }}; 2.重复项删除类似12345678910111213class Solution {public: int removeElement(vector<int>& nums, int val) { int black = 0; for (int red = 0; red < nums.size(); ++red) { if (nums[red] != val) { nums[black] = nums[red]; black++; } } return black; }};

删除有序数组中的重复项 原题链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ 不要使用额外的空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。 1.双指针1234567891011121314class Solution {public: int removeDuplicates(vector<int>& nums) { if (nums.size() == 0) return 0; int black = 0; for (int red = 1; red < nums.size(); ++red) { if (nums[red] != nums[black]) { black++; nums[black] = nums[red]; } } return black + 1; }};

最长公共前缀 原题链接：https://leetcode.cn/problems/longest-common-prefix/ 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串。 1.substr解法1：暴力循环 + substr字符串截取 runtime beats 73.15 % of cpp submissions memory usage beats 27.86 % of cpp submissions (9 MB) 12345678910111213class Solution {public: string longestCommonPrefix(vector<string>& strs) { if (strs.size() == 0) return ""; string ans = strs[0]; for (int i = 1; i < strs.size(); ++i) { int index = 0; for (;index < max(strs[i].length(), ans.length()) && ans[index] == strs[i][index]; ++index); ans = strs[i].substr(0, index); } return ans; }}; 2.+=操作解法2：暴力循环 + 字符串的+=操作（取消了对substr的引用，性能更优） runtime beats 73.15 % of cpp submissions memory usage beats 92.63 % of cpp submissions (8.8 MB) 1234567891011121314151617181920class Solution {public: string longestCommonPrefix(vector<string>& strs) { ...

罗马数字转整数 原题链接：https://leetcode.cn/problems/roman-to-integer/ 罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。 12345678字符 数值I 1V 5X 10L 50C 100D 500M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII 而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值。同样地数字9表示为 IX。 这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给定一个罗马数字，将其转换成整数。 1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution {public: int romanToInt(string s) { int ans = 0; for (int i = 0; i < s.length(); ++i) { if (s[i] == 'I') { //特殊判断 if (s[i + 1] == 'V' || s[i + 1] == 'X') { ans += (s[i + 1] == 'V' ...

回文数 原题链接：https://leetcode.cn/problems/palindrome-number/ 给你一个整数 x ，如果 x 是一个回文整数，返回 true；否则返回 false。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 提示：-231 <= x <= 231 - 1 1.整数反转利用整数反转的思想，来处理回文数字问题 12345678910111213class Solution {public: bool isPalindrome(int x) { if (x < 0) return false; long long ans = 0; long long raw = x; while (x) { ans = ans * 10 + x % 10; x /= 10; } return raw == ans; }}; 2.字符串反转1234567891011121314class Solution {public: bool isPalindrome(int x) { if (x < 0) return false; string raw = to_string(x); string ans = raw; for (int i = 0, j = raw.length() - 1; i < j; ++i, --j) { char c = ans[i]; ans[i] = ans[j]; ans[j] = c; } return raw == ans; }};

整数反转 原题链接：https://leetcode.cn/problems/reverse-integer/ 给你一个 32 位的有符号整数 x ，返回其数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。 假设环境不允许存储 64 位整数（有符号或无符号）（只允许使用int类型的变量） 提示：-231 <= x <= 231 - 1 1234input:120output:21input:0output:0 123456789101112131415161718class Solution {public: int reverse(int x) { int ans = 0; while (x) { if (ans > INT_MAX / 10 || ans < INT_MIN / 10 || ans == INT_MAX / 10 && x % 10 > 7 || ans == INT_MIN / 10 && x % 10 < -8 ) { ans = 0; break; } ans = ans * 10 + x % 10; x /= 10; } return ans; }};

两数之和 原题链接：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 ...

字符串括号匹配 原题链接：https://oj.haizeix.com/problem/377 给出一个字符串，判断其中的左右圆括号是否匹配， 注：需同时判断左右圆括号 ( 和 ) ，左右中括号 [ 和 ]，左右大括号 { 和 } 不需要考虑括号之间的优先级的问题，也就是说，小括号包含大括号，也是被允许的 输入： 一行一个字符串，以字符@为结尾 输出： 若匹配，输出 YES，若不匹配，则输出 NO 样例： 1a(cc[])bbb()@ YES 1a(cc[)]bbb()@ NO 代码1234567891011121314151617181920212223242526272829303132333435363738394041#include<iostream>#include<string>#include<stack>using namespace std;bool isValid(string str) { stack<char> stack; for (int i = 0; i < str.length(); ++i) { switch (str[i]) { case '(': case '[': case '{': stack.push(str[i]); break; case ')': if (stack.empty() || stack.top() != '(') return false; stack.pop(); break; case '}': if (stack.empty() || stack.top() != '{') return false; stack.pop(); break; case ']': if (stack.empty() || stack.top() != &# ...