面试算法题

记录部分手撕题目，给出核心代码，一般是从头开始写

1、相交链表

class Solution { // lc 160
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *A = headA, *B = headB;while (A != B) {A = A != nullptr ? A->next : headB;B = B != nullptr ? B->next : headA;}return A; // 交点或者空指针}
};

2、三数之和

class Solution { // lc 15
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(), nums.end()); // 排序后用双指针for (int i = 0; i < nums.size(); i++) {if (nums[i] > 0) return res; // 超出范围if (i > 0 && nums[i] == nums[i - 1]) continue;int left = i + 1;int right = nums.size() - 1; // 双指针，结合去重while (left < right) { // 有两个数，所以无等号if (nums[i] + nums[left] + nums[right] < 0) left++;else if (nums[i] + nums[left] + nums[right] > 0) right--;else {res.push_back({nums[i], nums[left], nums[right]});while (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;// 找到答案后左右收缩right--;left++;}}}return res;}
};

3、数组中第k个最大元素

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(), nums.end());return nums[nums.size() - k]; // 直接排序，时间复杂度O(nlogn)}
};// 提高时间复杂度，快速排序加筛选
class Solution {
public:int findKthLarrgest(vector<int>& nums, int k) {return quickSelect(num, k);}int quickSelect(vector<int>& nums, int k) {int pivot = nums[rand() % nums.size()];vector<int> big, equal, small;for (int num : nums) {if (num > pivot) big.push_back(num);else if (num < pivot) small.push_back(num);else equal.push_back(num); // 去除重复元素}if (k <= big.size()) return quickSelect(big, k); // 第k大的元素在big中if (nums.size() - small.size() < k) return quickSelect(small, k - (nums.size() - small.size())); // 第k大的元素在small中return pivot; // 第k大的元素在equal中，直接返回}
};