【C/C++ 力扣leetcode】4道简单题

**力扣 LeetCode 简单题解析**

本文将为你介绍四个简单的 C/C++ 题目，包括查找两个数组的交点、最长公共子序列、最小基因变化和最长回文子串。这些问题都是常见的算法面试题目。

###1. 查找两个数组的交点**题目描述**

给定两个有序整数数组 `nums1` 和 `nums2`，找到它们的交点。返回交点的下标，如果没有交点，则返回一个空列表。

**示例**

* 输入:`nums1 = [1,5,9,4,3], nums2 = [6,5,3,8]`
输出：`[1,5,3]`

**解决方案**

cppclass Solution {
public:
 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
 // 使用set进行交集计算 set<int> s(nums1.begin(), nums1.end());
 set<int> t(nums2.begin(), nums2.end());

 // 将两个集合的交集存入vector中 vector<int> res;
 for (auto it = s.begin(); it != s.end(); ++it) {
 if (t.find(*it) != t.end()) {
 res.push_back(*it);
 }
 }

 return res;
 }
};

###2. 最长公共子序列**题目描述**

给定两个字符串 `s1` 和 `s2`，找到它们的最长公共子序列（LCS）。返回 LCS 的长度。

**示例**

* 输入:`s1 = "abcde", s2 = "ace"`
输出：`3`

**解决方案**

cppclass Solution {
public:
 int longestCommonSubsequence(string s1, string s2) {
 // 使用动态规划计算LCS的长度 int m = s1.size();
 int n = s2.size();

 vector<vector<int>> dp(m +1, 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] = max(dp[i -1][j], dp[i][j -1]);
 }
 }
 }

 return dp[m][n];
 }
};

###3. 最小基因变化**题目描述**

给定两个字符串 `s` 和 `t`，它们代表两种生物的基因序列。找到将 `s` 转换为 `t` 的最少基因变化次数。

**示例**

* 输入:`s = "bab", t = "aba"`
输出：`1`

**解决方案**

cppclass Solution {
public:
 int minMutation(string s, string t, vector<string>& bank) {
 // 使用BFS计算最小基因变化次数 queue<string> q;
 unordered_set<string> visited;

 q.push(s);
 visited.insert(s);

 int step =0;

 while (!q.empty()) {
 int size = q.size();

 for (int i =0; i < size; ++i) {
 string cur = q.front();
 q.pop();

 if (cur == t) {
 return step;
 }

 for (auto& str : bank) {
 if (visited.find(str) != visited.end()) {
 continue;
 }

 int diff =0;

 for (int j =0; j < cur.size(); ++j) {
 if (cur[j] != str[j]) {
 diff++;
 }
 }

 if (diff ==1) {
 q.push(str);
 visited.insert(str);
 }
 }
 }

 step++;
 }

 return -1;
 }
};

###4. 最长回文子串**题目描述**

给定一个字符串 `s`，找到最长的回文子串。

**示例**

* 输入:`s = "babad"`
输出：`"bab"`

**解决方案**

cppclass Solution {
public:
 string longestPalindrome(string s) {
 // 使用动态规划计算最长回文子串 int n = s.size();

 vector> dp(n, vector(n));

 int maxLen =1;
 int start =0;

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

 for (int len =2; len <= n; ++len) {
 for (int l =0; l <= n - len; ++l) {
 int r = l + len -1;

 if (s[l] == s[r] && dp[l +1][r -1]) {
 dp[l][r] = true;
 if (len > maxLen) {
 maxLen = len;
 start = l;
 }
 }
 }
 }

 return s.substr(start, maxLen);
 }
};

以上是四个简单的 C/C++ 题目的解决方案。这些问题都是常见的算法面试题目，希望通过本文，你可以更好地理解这些问题的解析和解决方案。