2021 【阿里】面试真题

**阿里2021 面试真题**

**一、前言**

阿里是中国最大的互联网公司之一，拥有多个业务平台，如淘宝、天猫、支付宝等。阿里的面试过程通常包括编程题、系统设计题和行为面试三个部分。在本文中，我们将分享一些常见的阿里面试真题，包括代码示例和注释。

**二、编程题**

###1. 最长公共子序列（LCS）

问题：给定两个字符串 `s1` 和 `s2`，求出它们的最长公共子序列（LCS）。

cpp#include <iostream>
#include <vector>
#include <string>

int lcs(const std::string& s1, const std::string& s2) {
 int m = s1.size();
 int n = s2.size();

 // dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的 LCS 长度 std::vector<std::vector<int>> dp(m +1, std::vector<int>(n +1));

 for (int i =0; i <= m; ++i) {
 for (int j =0; j <= n; ++j) {
 if (i ==0 || j ==0) {
 dp[i][j] =0;
 } else if (s1[i -1] == s2[j -1]) {
 dp[i][j] = dp[i -1][j -1] +1;
 } else {
 dp[i][j] = std::max(dp[i -1][j], dp[i][j -1]);
 }
 }
 }

 return dp[m][n];
}

cpp#include <iostream>
#include <vector>

int minSpanningTree(const std::vector<std::pair<int, int>>& edges) {
 int n = edges.size();

 // parent[i] 表示 i 的父节点 std::vector<int> parent(n);

 for (int i =0; i < n; ++i) {
 parent[i] = i;
 }

 // rank[i] 表示 i 的树的高度 std::vector<int> rank(n,1);

 int mstWeight =0;

 for (const auto& edge : edges) {
 int u = edge.first;
 int v = edge.second;
 int weight = edge.weight();

 int rootU = find(parent, u);
 int rootV = find(parent, v);

 if (rootU != rootV) {
 mstWeight += weight;

 // union parent[rootU] = rootV;
 }
 }

 return mstWeight;
}

int find(const std::vector<int>& parent, int i) {
 while (parent[i] != i) {
 i = parent[i];
 }

 return i;
}

cpp#include <iostream>
#include <vector>

int maxInWindow(const std::vector<int>& nums, int windowSize) {
 if (nums.empty() || windowSize > nums.size()) {
 return -1;
 }

 int left =0;
 int right =0;

 int maxVal = nums[0];

 while (right < nums.size()) {
 // 移动右边界 while (right < nums.size() && right - left +1 <= windowSize) {
 maxVal = std::max(maxVal, nums[right]);
 ++right;
 }

 // 移动左边界 if (right == nums.size()) {
 break;
 }

 while (left < right && nums[left] <= nums[right]) {
 left++;
 }

 maxVal = std::max(maxVal, nums[left]);

 // 移动右边界 ++left;
 }

 return maxVal;
}

cpp#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& nums, int target) {
 int left =0;
 int right = nums.size() -1;

 while (left <= right) {
 int mid = left + (right - left) /2;

 if (nums[mid] == target) {
 return mid;
 } else if (nums[mid] < target) {
 left = mid +1;
 } else {
 right = mid -1;
 }
 }

 return -1;
}

cpp#include <iostream>
#include <vector>

struct ListNode {
 int val;
 ListNode* next;
};

bool isPalindrome(ListNode* head) {
 if (head == nullptr || head->next == nullptr) {
 return true;
 }

 // 快慢指针 ListNode* slow = head;
 ListNode* fast = head;

 while (fast != nullptr && fast->next != nullptr) {
 slow = slow->next;
 fast = fast->next->next;
 }

 // 反转后半段链表 ListNode* prev = nullptr;
 ListNode* curr = slow;
 while (curr != nullptr) {
 ListNode* nextTemp = curr->next;
 curr->next = prev;
 prev = curr;
 curr = nextTemp;
 }

 // 比较前后两半段链表 while (prev != nullptr && head != nullptr) {
 if (head->val != prev->val) {
 return false;
 }
 head = head->next;
 prev = prev->next;
 }

 return true;
}

cpp#include <iostream>
#include <vector>

class MinStack {
public:
 void push(int x) {
 stack.push_back(x);
 if (minStack.empty()) {
 minStack.push_back(x);
 } else {
 int minVal = minStack.back();
 if (x <= minVal) {
 minStack.push_back(x);
 }
 }
 }

 void pop() {
 stack.pop_back();
 minStack.pop_back();
 }

 int top() {
 return stack.back();
 }

 bool empty() {
 return stack.empty();
 }

private:
 std::vector<int> stack;
 std::vector<int> minStack;
};

cpp#include <iostream>
#include <vector>

class MaxHeap {
public:
 void insert(int x) {
 heap.push_back(x);
 int index = heap.size() -1;
 while (index >0) {
 int parentIndex = (index -1) /2;
 if (heap[parentIndex] >= heap[index]) {
 break;
 }
 swap(parentIndex, index);
 index = parentIndex;
 }
 }

 void remove(int x) {
 int index = find(x);
 if (index == -1) {
 return;
 }

 // 将最后一个元素移到该位置 heap[index] = heap.back();
 heap.pop_back();

 while (index >0) {
 int parentIndex = (index -1) /2;
 if (heap[parentIndex] >= heap[index]) {
 break;
 }
 swap(parentIndex, index);
 index = parentIndex;
 }
 }

private:
 std::vector<int> heap;

 void swap(int i, int j) {
 int temp = heap[i];
 heap[i] = heap[j];
 heap[j] = temp;
 }

 int find(int x) {
 for (int i =0; i < heap.size(); ++i) {
 if (heap[i] == x) {
 return i;
 }
 }
 return -1;
 }
};

cpp#include <iostream>
#include <vector>

class MinHeap {
public:
 void insert(int x) {
 heap.push_back(x);
 int index = heap.size() -1;
 while (index >0) {
 int parentIndex = (index -1) /2;
 if (heap[parentIndex] <= heap[index]) {
 break;
 }
 swap(parentIndex, index);
 index = parentIndex;
 }
 }

 void remove(int x) {
 int index = find(x);
 if (index == -1) {
 return;
 }

 // 将最后一个元素移到该位置 heap[index] = heap.back();
 heap.pop_back();

 while (index >