1. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int searchInsert(vector<int> &nums, int target) { int lo = -1; int hi = nums.size(); while (lo + 1 < hi) { int mid = lo + (hi - lo) / 2; if (target > nums[mid]) { lo = mid; } else { hi = mid; } } return hi; } }; int main() { Solution s; vector<int> nums = {1,3,5,6}; cout << s.searchInsert(nums, 5) << endl; cout << s.searchInsert(nums, 2) << endl; cout << s.searchInsert(nums, 7) << endl; cout << s.searchInsert(nums, 0) << endl; return 0; }
输出：
2
1
4
0
二分查找，其它写法：
class Solution { public: int searchInsert(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) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; } };
完整代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: int searchInsert(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) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; } }; int main() { Solution s; vector<int> nums = {1,3,5,6}; cout << s.searchInsert(nums, 5) << endl; cout << s.searchInsert(nums, 2) << endl; cout << s.searchInsert(nums, 7) << endl; cout << s.searchInsert(nums, 0) << endl; return 0; }
2. 结合两个字符串
写一个结合两个字符串的方法，从第一个字符串中取出一个字符，然后从第二个字符串中取出一个字符，以此类推。一旦一个字符串没有字符，它就应该继续使用另一个字符串
输入：两个字符串，如s1="day"和s2="time"
输出：一个结果字符串，对于上面的输入情况，它将是“dtaiyme”。
出处：
https://edu.csdn.net/practice/23719159
代码：
#include <iostream> #include <string> using namespace std; string StrCon(const string& a, const string& b) { string c; int n = a.size(), m = b.size(); if (0 == n) return a; if (0 == m) return b; int i, j; for (i = 0, j = 0; i < n && j < m; ++i, ++j) { c += a[i]; c += b[i]; } while (i < n) c += a[i++]; while (j < m) c += b[j++]; return c; } int main() { string s = "day", t = "time"; cout << StrCon(s, t) << endl; system("pause"); return 0; }
输出：
dtaiyme
3. 同构字符串
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例 1:
输入：s = "egg", t = "add"
输出：true
示例 2：
输入：s = "foo", t = "bar"
输出：false
示例 3：
输入：s = "paper", t = "title"
输出：true
提示：
可以假设 s 和 t 长度相同。
出处：
https://edu.csdn.net/practice/23719160
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: bool isIsomorphic(string s, string t) { vector<int> m(128, -1); for (int i = 0; i < s.size(); ++i) { if (m[s[i]] != -1) { if (m[s[i]] != t[i]) return false; } else { for (auto v : m) { if (v == t[i]) return false; } m[s[i]] = t[i]; } } return true; } }; int main() { Solution sol; string s = "egg", t = "add"; cout << (sol.isIsomorphic(s, t) ? "true" : "false") << endl; s = "foo", t = "bar"; cout << (sol.isIsomorphic(s, t) ? "true" : "false") << endl; s = "paper", t = "title"; cout << (sol.isIsomorphic(s, t) ? "true" : "false") << endl; return 0; }
输出：
true
false
true
