微软面试高频算法题解析与代码实现（C++）

作为全球顶尖科技公司，微软对人才的招聘要求十分严格，尤其是在算法工程师的选拔上。算法面试是微软招聘流程中不可或缺的一环，考察候选人对算法和数据结构的理解和应用能力。本文将列举微软面试中出现频率较高的 10 道算法题，并使用 C++ 语言给出相应的代码实现，帮助大家更好地备战微软算法面试。

1. 两数之和

题目描述： 给定一个整数数组和一个目标值，找出数组中两个数的索引，使得它们的和等于目标值。

代码实现：

#include <vector>
#include <unordered_map>

std::vector<int> twoSum(const std::vector<int>& nums, int target) {
  std::unordered_map<int, int> num_index;
  for (int i = 0; i < nums.size(); ++i) {
    int complement = target - nums[i];
    if (num_index.count(complement)) {
      return {num_index[complement], i};
    }
    num_index[nums[i]] = i;
  }
  return {};
}

2. 寻找峰值

题目描述： 给定一个单调递增的数组，然后又单调递减。找出数组中的峰值元素。

代码实现：

#include <vector>

int findPeakElement(const std::vector<int>& nums) {
  int left = 0, right = nums.size() - 1;
  while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] > nums[mid + 1]) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return nums[left];
}

3. 旋转数组的最小值

题目描述： 给定一个排序数组，该数组被旋转过。找到数组中的最小值。

代码实现：

#include <vector>

int findMin(const std::vector<int>& nums) {
  int left = 0, right = nums.size() - 1;
  while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return nums[left];
}

4. 合并两个有序数组

题目描述： 给你两个有序整数数组 nums1 和 nums2，请将 nums2 合并到 nums1 中，使最终结果为一个有序数组。

代码实现：

#include <vector>

void merge(std::vector<int>& nums1, int m, std::vector<int>& nums2, int n) {
  int i = m - 1, j = n - 1, k = m + n - 1;
  while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[k--] = nums1[i--];
    } else {
      nums1[k--] = nums2[j--];
    }
  }
  while (j >= 0) {
    nums1[k--] = nums2[j--];
  }
}

5. 查找第一个和最后一个位置

题目描述： 给定一个已排序的数组和一个目标值，找到目标值在数组中出现的第一个和最后一个位置。

代码实现：

#include <vector>

std::vector<int> searchRange(const std::vector<int>& nums, int target) {
  int left = 0, right = nums.size() - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
      int start = mid, end = mid;
      while (start >= 0 && nums[start] == target) {
        start--;
      }
      while (end < nums.size() && nums[end] == target) {
        end++;
      }
      return {start + 1, end - 1};
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return {-1, -1};
}

6. 矩阵中的搜索

题目描述： 编写一个函数，输入是一个二维数组和一个整数，判断数组中是否包含该整数。

代码实现：

#include <vector>

bool searchMatrix(const std::vector<std::vector<int>>& matrix, int target) {
  int row = 0, col = matrix[0].size() - 1;
  while (row < matrix.size() && col >= 0) {
    if (matrix[row][col] == target) {
      return true;
    } else if (matrix[row][col] < target) {
      row++;
    } else {
      col--;
    }
  }
  return false;
}

7. 数组中的第K个最大元素

题目描述： 在未排序的数组中找到第 k 个最大的元素。

代码实现：

#include <vector>
#include <queue>

int findKthLargest(std::vector<int>& nums, int k) {
  std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
  for (int num : nums) {
    min_heap.push(num);
    if (min_heap.size() > k) {
      min_heap.pop();
    }
  }
  return min_heap.top();
}

8. 字符串中的最长无重复子字符串

题目描述： 给定一个字符串，找出其中不包含重复字符的最长子字符串的长度。

代码实现：

#include <string>
#include <unordered_set>

int lengthOfLongestSubstring(const std::string& s) {
  int max_len = 0, start = 0, end = 0;
  std::unordered_set<char> char_set;
  while (end < s.size()) {
    if (char_set.count(s[end]) == 0) {
      char_set.insert(s[end]);
      end++;
      max_len = std::max(max_len, end - start);
    } else {
      char_set.erase(s[start]);
      start++;
    }
  }
  return max_len;
}

9. 最长公共子序列

题目描述： 给定两个字符串，找到两个字符串的最长公共子序列。

代码实现：

#include <string>
#include <vector>

int longestCommonSubsequence(const std::string& text1, const std::string& text2) {
  int m = text1.size(), n = text2.size();
  std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (text1[i - 1] == text2[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];
}

10. 括号匹配

题目描述： 给定一个只包含括号的字符串，判断该字符串是否为有效括号字符串。

代码实现：

#include <string>
#include <stack>

bool isValid(const std::string& s) {
  std::stack<char> char_stack;
  for (char c : s) {
    if (c == '(' || c == '[' || c == '{') {
      char_stack.push(c);
    } else {
      if (char_stack.empty() || (c == ')' && char_stack.top() != '(') || (c == ']' && char_stack.top() != '[') || (c == '}' && char_stack.top() != '{')) {
        return false;
      }
      char_stack.pop();
    }
  }
  return char_stack.empty();
}

总结

以上 10 道算法题是微软面试中出现频率较高的题目，掌握它们的解法和代码实现能够帮助你更好地备战微软算法面试。除了熟练掌握这些算法之外，还需要注意以下几点：

• 算法面试考察的是你的逻辑思维能力和代码实现能力，所以要注重代码的简洁性和可读性。
• 面试官可能会问一些关于算法复杂度和空间复杂度的问题，所以要了解算法的时间复杂度和空间复杂度。
• 面试官可能会让你解释你的代码，所以要能够清晰地解释你的代码逻辑。

希望这篇文章能够帮助你更好地备战微软算法面试！