您正在查看:HHR 发布的文章
2020-02-07 |HHR
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值index1 和 index2,其中 index1 必须小于 index2。
说明:
- 返回的下标值(index1 和 index2)不是从零开始的。
- 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
class Solution { public: vector<int> twoSum(vector<int> &numbers, int target) { int i = 0, j = numbers.size() - 1; while (target != numbers[i] + numbers[j]) { if (target > numbers[i] + numbers[j]) { i++; } else { j--; } } vector<int> ans; ans.push_back(i + 1); ans.push_back(j + 1); return ans; } };
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
2020-02-07 |HHR
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2] 输出: 3
说明:
- 不能更改原数组(假设数组是只读的)。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字,但它可能不止重复出现一次。
class Solution { public: int findDuplicate(vector<int> &nums) { int i = 1, j = nums.size() - 1; while (i != j) { int m = (i + j) / 2, count = 0; for (int num:nums) { if (num <= m) count++; } if (count > m) { j = m; } else { i = m + 1; } } return i; } };
/* * 5,1,2,3,4,5,5,7,8,9,10,11 * 在1-11中寻找 * 重复的数是6或更小嘛? * 数一数发现,<=6的数有7个,说明重复的数<=6 * 那去1-6中寻找 * 重复的数<=3嘛? * <=3的数只有三个,没问题,重复的数比3大 * 在4-5中寻找 * 重复的数<=4嘛? * 比4小的数有四个,重复的数比4大 * 所以,重复的数是5 */
2020-02-07 |HHR
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2,2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[4,9]
说明:
- 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
进阶:
- 如果给定的数组已经排好序呢?你将如何优化你的算法?
- 如果 nums1 的大小比 nums2 小很多,哪种方法更优?
- 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
#include <vector> #include <hash_map> using namespace std; using namespace __gnu_cxx; class Solution { public: vector<int> intersect(vector<int> &nums1, vector<int> &nums2) { hash_map<int, int> num, num2; vector<int> ans; for (auto n:nums1) { num[n]++; } for (auto n:nums2) { if (num.find(n) != num.end() && num[n] != 0) { num[n]--; ans.push_back(n); } } return ans; } };
使用hashmap存储第一个数组的内容,然后对数组2中的元素进行遍历,找到重复元素返回
https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/
2020-02-07 |HHR
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4 输出: 2
示例 2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
class Solution { public: static int mySqrt(int x) { int i = 0, j = x / 2 + 1; long long ans; while (i <= j) { ans = (i + j) / 2; if (ans * ans == x) { return ans; } else if (ans * ans > x) { j = ans - 1; } else { i = ans + 1; } } return j; } };
对分查找,注意选好上界
2020-02-06 |HHR
给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
示例 1:
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd" 输出: "bb"
class Solution { public: string longestPalindrome(string s) { if (s.length() == 0) return ""; bool dp[1000][1000] = {{false}}; int max = 0; string ans; for (int x = s.length(); x >= 0; x--) { for (int y = x; y < s.length(); y++) { if (y - x < 2) { dp[x][y] = s[x] == s[y]; } else { dp[x][y] = dp[x + 1][y - 1] && (s[x] == s[y]); } if (dp[x][y] && y - x + 1 > max) { max = y - x + 1; ans = s.substr(x, y - x + 1); } } } return ans; } };
第i到第j个char能否构成回文取决于 1.第i+1到第j-1个char是否回文 2.第i个char和第j个char是否相同 dp[i][j]=dp[i+1][j-1]&&s[i]==s[j] 注意考虑串为空的特殊情况 x自大到小,y从小到大,确保dp[x+1][y-1]已经完成定义
https://leetcode-cn.com/problems/longest-palindromic-substring/