算法面经
数组88. 合并两个有序数组
经典 逆向双指针
void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
for (int i = m - 1, j = n - 1, k = m + n - 1; ~j; k--) {
nums1 = i >= 0 && nums1 > nums2 ? nums1 : nums2;
}
}4. 寻找两个正序数组的中位数
困难，hot100，必会题，重点是求两个数组中第k大的数
double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
int m = nums1.size(), n = nums2.size();
int a = getKth(0, 0, (m + n + 1) / 2, nums1, nums2);
int b = getKth(0, 0, (m + n + 2) / 2, nums1, nums2);
return (a + b) / 2.0;
}
int getKth(int i, int j, int k, vector<int> &nums1, vector<int> &nums2) {
int m = nums1.size(), n = nums2.size();
if (i >= m) {
return nums2;
}
if (j >= n) {
return nums1;
}
if (k == 1) {
return min(nums1, nums2);
}
int p = k / 2;
int x = i + p - 1 < m ? nums1 : INT_MAX;
int y = j + p - 1 < n ? nums2 : INT_MAX;
return x < y ? getKth(i + p, j, k - p, nums1, nums2) : getKth(i, j + p, k - p, nums1, nums2);
}15. 三数之和
两数之和升级版，方法完全不一样，还用hash的话，会有很多特殊情况需要考虑，推荐使用 排序+双指针 法。字节常考题，必会。
vector<vector<int>> threeSum(vector<int> &nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n - 2 && nums <= 0; i++) {
if (i && nums == nums) continue;
int j = i + 1, k = n - 1;
while (j < k) {
int x = nums + nums + nums;
if (x < 0) {
j++;
} else if (x > 0) {
k--;
} else {
ans.push_back({nums, nums, nums});
while (j < k && nums == nums) {
j++;
}
while (j < k && nums == nums) {
k--;
}
}
}
}
return ans;
}字符串
5. 最长回文子串
必须掌握，方法1:动态规划，方法2:中心扩展法
/* f 即 s是否为回文串
* if s=s,f=f */
string longestPalindrome(string s) {
int n = s.size();
vector<vector<bool>> f(n, vector<bool>(n, true));
int k = 0, mx = 1;
for (int i = n - 2; i >= 0; i++) {
for (int j = i + 1; j < n; j++) {
f = false;
if (s == s) {
f = f;
if (f && mx < j - i + 1) {
mx = j - i + 1;
k = i;
}
}
}
}
return s.substr(k, mx);
}
// 中心扩展发
class Solution1 {
public:
string palindrome(string s, int l, int r) {
int n = s.size();
while (l >= 0 && r < n && s == s) {
l--;
r++;
}
return s.substr(l + 1, r - l - 1);
}
string longestPalindrome(string s) {
string res = "";
for (int i = 0; i < s.length(); i++) {
string s1 = palindrome(s, i, i);
string s2 = palindrome(s, i, i + 1);
res = res.size() > s1.size() ? res : s1;
res = res.size() > s2.size() ? res : s2;
}
return res;
}
};2的1000次方
字符串乘法，腾讯面试题
#include #include using namespace std; string multiplyByTow(const string &num) { string res; int carry = 0; for (int i = num.size() - 1; i >= 0; i--) { int digit = num - '0'; int product = digit * 2 + carry; carry = product / 10; res.insert(res.begin(), '0' + (product % 10)); } while (carry > 0) { res.insert(res.begin(), '0' + (carry % 10)); carry /= 10; } return res;} int main() { string res = "1"; for (int i = 0; i < 1000; i++) { res = multiplyByTow(res); } cout
页:
[1]