当前位置：首页 > article >正文

C/C++每日一练(20230325)

article 2025/1/25 9:08:29

1. 搜索插入位置 🌟

2. 结合两个字符串 🌟

3. 同构字符串 🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

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