您正在查看：2020年2月
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/
2020-02-06 |HHR
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2:
输入: [7,6,4,3,1] 输出: 0 解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution {
public:
int maxProfit(vector<int> &prices) {
if (prices.empty()) return 0;
int ans = 0, min = prices[0];
for (int price:prices) {
ans = max(ans, price - min);
if (price < min) min = price;
}
return ans;
}
};到某天为止的最大盈利=max(前一天为止的最大盈利,如果今天卖出的最大盈利) 注意没有任何交易日的特殊情况
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/