• 欢迎光临~

算法题目(1)

开发技术 开发技术 2022-10-02 次浏览

题目1

给定一个有序数组arr,代表坐落在X轴上的点
给定一个正数K,代表绳子的长度
返回绳子最多压中几个点?
即使绳子边缘处盖住点也算盖住

输入:
第一行 arr的size,k
第二行 arr
输出:
最多覆盖的点

思路

滑动窗口,窗口不回退模型。窗口左边界L,右边界R,初始值都是0,R每次往右移动到最右的位置,统计一次压中的点数,然后L往右移动一次,R继续,直到L越界。

代码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, k;
	cin >> n;
	cin >> k;
	vector<int> vec(n);
	for (int i = 0; i < n; i++)
	{
		cin >> vec[i];
	}

	int l = 0;
	int r = 0;
	int Max = 0;
	for (; l < vec.size(); l++)
	{
		while (r < vec.size() && vec[r] - vec[r] <= k)
		{
			r++;
		}
		Max = max(Max, r - l);    //由于while的特点,r最后会位于能移动到的最右位置+1的位置,所以少统计一个
	}
	cout << Max << endl;
        return 0;
}

题目2

一个数组中只有两种字符'G'和'B'
想让所有的G都放在左侧,所有的B都放在右侧
但是只能在相邻字符之间进行交换操作
返回至少需要交换几次

思路

贪心。策略是第i次出现的G只用移动到数组下标为i-1的位置。比如第一次出现的G只用移动到0位置。

代码

int main()
{
	string str;
	cin >> str;
	int L = 0;
	int i = 0;
	int ans = 0;
	for (; i < str.size(); i++)
	{
		if (str[i] == 'G')
		{
			ans += i - L;
			L++;
		}
	}
	cout << ans << endl;
	return 0;
}

题目3(leetcode494)

给定一个数组arr,你可以在每个数字之前决定 + 或者 - ,但是必须所有数字都参与
再给定一个数target,请问最后数组中所有数字按照给定的+和-算出target的方法数是多少?

思路

  1. 暴力递归尝试。
  2. 优化后思路:
    1.不管给定的arr中有没有负数,方法数结果都跟全部都取绝对值时相同。原因是因为负数加上 - 后就变成了负数,与正数加上 + 一样,无非就是原来是 - 现在变成了 + 。所以一开始把所有数字都处理成正数
    2.因为所有的数字都要用上,假设arr所有数字的绝对值的和为sum,则sum必须大于target,否则不可能算出target,且sum的奇偶性与target一样。
    3.假设加上符号后所有正数集合的和为P,负数集合的和为N,一定有P - N = sum,P + N = target,第一个式子两边同时加上P + N,得到2P = sum + P + N = sum + target,P = (sum + target) / 2 。sum和target的值都是已知的,所以只要从arr中任取数字拼凑出P(此时arr中的数已经被全部处理为正数了,拼凑是指只做相加操作,所以满足P是所有正数的集合这个要求),剩下的都拼成负数即可获得target,这种优化思路下,把问题转换成了经典背包问题。而且dp数字的规模也减小了,原来的dp列规模是-sum到sum,现在是0~sum(因为target最大取sum),减小了一半
    4.空间压缩技巧

代码

暴力递归

int process(vector<int> arr, int index, int rest)
{
	if (index == arr.size())
	{
		return rest == 0 ? 1 : 0;
	}
	return process(arr, index + 1, rest - (arr[index] - '0')) + process(arr, index + 1, rest + (arr[index] - '0'));
}

int main()
{
	int n, tar;
	cin >> n;
	cin >> tar;
	vector<int> arr(n);
	cout << process(arr, 0, tar) << endl;
        return 0;
}

优化后动态规划(没有做空间压缩)

int subset(vector<int> nums, int s)
{
	vector<vector<int>> dp(nums.size() + 1, vector<int>(s + 1));
	dp[nums.size()][0] = 1;
	for (int i = nums.size() - 1; i >= 0; i--)
	{
		for (int j = 0; j < dp[0].size(); j++)
		{
			if (j - nums[i] >= 0)
			{
				dp[i][j] = dp[i + 1][j - nums[i]] + dp[i + 1][j];
			}
		}
	}
	return dp[0][s];
}

int main()
{
	int n, tar;
	cin >> n;
	cin >> tar;
	vector<int> arr(n);
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		arr[i] = abs(arr[i]);
		sum += arr[i];
	}
	if (sum < abs(tar) || ((sum & 1) ^ (tar & 1)) != 0)
	{
		cout << 0 << endl;
	}
	else
	{
		cout << subset(arr, (tar + sum) / 2) << endl;
	}
	return 0;
}

题目4

现有司机N*2人,调度中心会将所有司机平分给A、B两个区域(注意是平分)
第i个司机去A可得收入为income[i][0],
第i个司机去B可得收入为income[i][1],
返回所有调度方案中能使所有司机总收入最高的方案,是多少钱

思路

暴力递归,详细看代码

暴力递归代码

int process(vector<vector<int>> &income, int index, int rest)  //index:当前来到的司机的位置,rest:A区域还剩多少个司机可以分配
{
	if (index = income.size())
	{       //越界了返回0元
		return 0;
	}
	if (income.size() - index == rest)    //剩下的只能选A区域
	{
		return income[index][0] + process(income, index + 1, rest - 1);
	}
	if (rest == 0)      //剩下的只能选B区域
	{
		return income[index][1] + process(income, index + 1, rest);
	}

        //A区域和B区域都可以选,选钱最多的
	int p1 = income[index][0] + process(income, index + 1, rest - 1);
	int p2 = income[index][1] + process(income, index + 1, rest);
	return max(p1, p2);
}

int main()
{
	int N;
	cin >> N;	//N一定是2的倍数
	vector<vector<int>> income(N, vector<int>(2));
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			cin >> income[i][j];
		}
	}
	cout << process(income, 0, N / 2) << endl;
        return 0;
}

题目5

给哈希表添加一个setAll操作,setAll(int n)的功能是将哈希表内所有value都改成n,要求setAll操作的时间复杂度是O(1),可以使用stl的哈希模板实现

思路

假设要求实现的哈希表叫hashmap,hashmap的内部有一个哈希表,一个当前时间(初始值为0,每存入一个key,时间++),一个setAll时间(初始值为0,当进行setAll时更新成当前时间),一个setAll值(setAll操作时更新为setAll传入的参数)。在hashmap的内部储存value时储存pair形式,pair的第一个值为用户存入的value,第二个值为存入时间,当进行setAll操作时,更新setAll值、setAll时间,当用户想要拿到他存入的key对应的value时,判断存入时间是否小于setAll时间,如果是,则返回setAll值给他,如果不是则返回用户自己存入的value。

题目6

求一个字符串中,最长无重复子串的长度

思路

动态规划,准备一个辅助字符数组(或哈希表),储存从前往后遍历字符串时当前字符出现的上一个位置。dp[i]的含义是以i位置的字符结尾,最长无重复子串的长度。dp[i]有两个瓶颈,一个是i位置字符上一次出现的位置,在辅助字符数组(或哈希表)中有记录,另一个是dp[i-1]的值,取两个瓶颈离自己最近的即可更新dp[i],提前准备一个max变量,边更新dp边比较最大值,最后返回max。

代码

int main()
{
	string str;
	cin >> str;
	unordered_map<char, int> map;
	vector<int> dp(str.size());
	dp[0] = 1;
	map[str[0]] = 0;
	int max = 1;
	for (int i = 1; i < dp.size(); i++)
	{
		if (map.count(str[i]) == 0)
		{
			dp[i] = dp[i - 1] + 1;
		}
		else
		{
			dp[i] = min(i - map[str[i]], dp[i - 1] + 1);
		}
		map[str[i]] = i;
		max = max > dp[i] ? max : dp[i];
	}
	cout << max << endl;
	return 0;
}

题目6

给定一个数组arr,代表每个人的能力值。再给定一个非负数k
如果两个人能力差值正好为k,那么可以凑在一起比赛
一局比赛只有两个人
返回最多可以同时有多少场比赛

思路

窗口。先从小到大排序,准备一个bool类型的数组,大小与arr一样,初始值全为false,i位置上如果为true则代表i已经分配过比赛了,不能再次分配了。窗口两个边界分别为L和R,初始值都是0。首先判断L所处的位置是否已经被分配过比赛,如果是,L右移进下一次循环。如果不是,则判断L与R是否是同一位置,如果是,R向右移动进下一次循环,如果不是,先判断R位置的能力值减去L位置的能力值是否等于K,如果是,R位置false置为true,L与R同时右移进下一次循环,如果小于k,R右移,大于K,L右移。直到L或R越界

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;


int main()
{
	int n, k;
	cin >> n;
	cin >> k;
	vector<int> c(n);
	for (int i = 0; i < n; i++)
	{
		cin >> c[i];
	}
	sort(c.begin(), c.end());
	int L = 0;
	int R = 0;
	vector<bool> used(n);
	int ans = 0;
	while (L < n && R < n)
	{
		if (used[L])
		{
			L++;
		}
		else if (L == R)
		{
			R++;
		}
		else
		{
			int dis = c[R] - c[L];
			if (dis == k)
			{
				ans++;
				used[R] = true;
				L++;
				R++;
			}
			else if (dis < k)
			{
				R++;
			}
			else
			{
				L++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

题目7

给定一个正数数组arr,代表若干人的体重
再给定一个正数limit,表示所有船共同拥有的载重量
每艘船最多坐两人,且不能超过载重
想让所有的人同时过河,并且用最好的分配方法让船尽量少
返回最少的船数

思路

代码

题目8

思路

代码

题目9

思路

代码

题目10

思路

代码

题目11

思路

代码

题目12

思路

代码

程序员灯塔
转载请注明原文链接:算法题目(1)
喜欢 (0)
违法和不良信息举报电话:022-22558618 举报邮箱:dljd@tidljd.com