1-9-13-14-20

1/* 给定一个整数数组 nums 和一个整数目标值 target 请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。 示例 1 输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。 示例 2 输入nums [3,2,4], target 6 输出[1,2] 示例 3 输入nums [3,3], target 6 输出[0,1] 提示 2 nums.length 104 -109 nums[i] 109 -109 target 109 只会存在一个有效答案 进阶你可以想出一个时间复杂度小于 O(n2) 的算法吗 */ class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hashtable; int index 0; for (auto i : nums) { auto it hashtable.find(target - i); if (it hashtable.end()) { hashtable.insert({i, index}); } else { return {it-second, index}; } } return {}; } }; // unordered_map 是 C 标准模板库STL的一部分提供了一种基于哈希表的键值对容器。 // 与 std::map 不同unordered_map 不保证元素的排序但通常提供更快的查找速度。9/* 9. 回文数 已解答 简单 相关标签 premium lock icon 相关企业 提示 给你一个整数 x 如果 x 是一个回文整数返回 true 否则返回 false 。 回文数是指正序从左向右和倒序从右向左读都是一样的整数。 例如121 是回文而 123 不是。 示例 1 输入x 121 输出true 示例 2 输入x -121 输出false 解释从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3 输入x 10 输出false 解释从右向左读, 为 01 。因此它不是一个回文数。 提示 -231 x 231 - 1 进阶你能不将整数转为字符串来解决这个问题吗 */ class Solution { public: bool isPalindrome(int x) { // % 取余运算符 if (x 0 || (x % 10 0 x ! 0)) { return false; } int revertedNumber 0; while (revertedNumber x) { revertedNumber revertedNumber*10 x % 10; x / 10; } return x revertedNumber || x revertedNumber / 10; } }; int main() { Solution().isPalindrome(121); }13/* 13. 罗马数字转整数 已解答 简单 相关标签 premium lock icon 相关企业 提示 罗马数字包含以下七种字符: I V X LCD 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如 罗马数字 2 写做 II 即为两个并列的 1 。12 写做 XII 即为 X II 。 27 写做 XXVII, 即为 XX V II 。 通常情况下罗马数字中小的数字在大的数字的右边。 但也存在特例例如 4 不写做 IIII而是 IV。 数字 1 在数字 5 的左边所表示的数等于大数 5 减小数 1 得到的数值 4 。 同样地数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况 I 可以放在 V (5) 和 X (10) 的左边来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边来表示 400 和 900。 给定一个罗马数字将其转换成整数。 示例 1: 输入: s III 输出: 3 示例 2: 输入: s IV 输出: 4 示例 3: 输入: s IX 输出: 9 示例 4: 输入: s LVIII 输出: 58 解释: L 50, V 5, III 3. 示例 5: 输入: s MCMXCIV 输出: 1994 解释: M 1000, CM 900, XC 90, IV 4. 提示 1 s.length 15 s 仅含字符 (I, V, X, L, C, D, M) 题目数据保证 s 是一个有效的罗马数字且表示整数在范围 [1, 3999] 内 题目所给测试用例皆符合罗马数字书写规则不会出现跨位等情况。 IL 和 IM 这样的例子并不符合题目要求49 应该写作 XLIX999 应该写作 CMXCIX 。 关于罗马数字的详尽书写规则可以参考 罗马数字 - 百度百科。 */ #include string #include iostream #include unordered_map using namespace std; class Solution { public: int romanToInt(string s) { unordered_mapchar, int char_to_num{ {I, 1}, {V, 5}, {X, 10}, {L, 50}, {C, 100}, {D, 500}, {M, 1000}, }; int res 0; auto len s.size(); for (size_t i 0; i len; i) { auto current char_to_num[s[i]]; // 不是最后一个且前面的数小于后一个 就减,否则加 if (i len - 1 current char_to_num[s[i 1]]) { res - current; } else { res current; } } return res; } }; int main() { std::cout Solution().romanToInt(MCMXCIV) std::endl; }14/* 14. 最长公共前缀 已解答 简单 相关标签 premium lock icon 相关企业 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀返回空字符串 。 示例 1 输入strs [flower,flow,flight] 输出fl 示例 2 输入strs [dog,racecar,car] 输出 解释输入不存在公共前缀。 提示 1 strs.length 200 0 strs[i].length 200 strs[i] 如果非空则仅由小写英文字母组成 */ #include string #include iostream #include vector using namespace std; class Solution { public: string longestCommonPrefix(vectorstring strs) { auto v_len strs.size(); if (v_len 0) { return ; } string res strs[0]; // 关键思路水平扫描法 - 将第一个字符串作为初始前缀然后逐个与后续字符串比较 // 从第二个串开始 for (size_t i 1; i v_len; i) { // 关键将当前前缀与下一个字符串比较更新前缀 update_prefix(res, strs[i]); // 优化如果前缀已经为空提前终止循环 if (res.size()0) { break; } } return res; } void update_prefix(string prefix, string next_string) { // 确定比较的最大长度取两个字符串长度的较小值 auto max_index min(prefix.size(), next_string.size()); size_t compare_index 0; // 算法逐个字符比较直到找到第一个不匹配的位置 while (compare_index max_index prefix[compare_index]next_string[compare_index]) { compare_index; } // 更新前缀为匹配部分的前缀 prefix prefix.substr(0,compare_index); } }; int main() { vectorstring strs {dog,racecar,car}; cout Solution().longestCommonPrefix(strs) endl; return 0; }20/* 20. 有效的括号 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。 有效字符串需满足 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 示例 1输入s ()输出true 示例 2输入s ()[]{}输出true 示例 3输入s (]输出false 示例 4输入s ([])输出true 示例 5输入s ([)]输出false 提示 1 s.length 104 s 仅由括号 ()[]{} 组成 */ #include string #include iostream #include stack using namespace std; class Solution { public: bool isValid(string s) { // 一个空栈,遇到左括号入栈,遇到右括号匹配栈顶, // 匹配不上返回false,匹配上栈顶弹出,最后为空就true stackchar symbol_stak; for (auto i : s) { switch (i) { case (: case {: case [: symbol_stak.push(i); break; default: if (symbol_stak.empty()) { return false; } if ((i ) symbol_stak.top() () || (i } symbol_stak.top() {) || (i ] symbol_stak.top() [)) { symbol_stak.pop(); } else { return false; } break; } } return symbol_stak.empty(); } }; int main() { string s ()[]{}; std::cout Solution().isValid(s) std::endl; return 0; }