笔试强训每日一题(六)
文章目录
不要二
题目链接
题目描述
二货小易有一个W*H的网格盒子，网格的行编号为0~H-1，网格的列编号为0~W-1。每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。
对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为:
( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) ) 的算术平方根
小易想知道最多可以放多少块蛋糕在网格盒子里。
输入描述
每组数组包含网格长宽W,H，用空格分割.(1 ≤ W、H ≤ 1000)
输出描述
输出一个最多可以放的蛋糕数
题目解析
W*H的一个盒子，其实就是一个二维数组，题目的关键信息是每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。我们先求欧几里得距离等于2的情况：欧几里得距离为:( (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) ) 的算术平方根，所以我们两边同时平方得：
（x1-x2）*（x1-x2）+（y1-y2）* （y1-y2） = 4
前半部分相乘一定是正数，后半部分相乘也一定是正数，所以两部分的取值有以下情况：
0+4=4
1+3=4
2+2=4
3+1=4
4+0=4
又因为x1，x2，y1，y2是正数，一个整数的平方不可能是2和3，所以排除了3个情况，只剩下两种情况：
1、0+4=4
2、4+0=4
代入表达式得：
1、x1=x2，y1=y2+2
2、y1=y2，x1=x2+2
所以如果[i][j]这个位置放了小蛋糕，[i][j+2]和[i+2][j]这两个位置就不可以放小蛋糕了。注意处理这里需要防止越界
题目代码
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int w,h,count = 0;
cin>>w>>h;
vector<vector<int>> vv;
vv.resize(h);
for(auto& e : vv)
{
e.resize(w,1);
}
for(int i = 0;i < h;i++)
{
for(int j = 0;j < w;j++)
{
if(vv[i][j]==1)
{
count++;
if(i+2 < h)//防止越界
{
vv[i+2][j] = 0;
}
if(j+2 < w)
{
vv[i][j+2] = 0;
}
}
}
}
cout << count << endl;
return 0;
}
字符串转成整数
题目链接
题目描述
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为 0 或者字符串不是一个合法的数值则返回 0
数据范围：字符串长度满足 0 <=n <=100
进阶：空间复杂度O(1) ，时间复杂度O(n)注意：
①字符串中可能出现任意符号，出现除 +/- 以外符号时直接输出 0
②字符串中可能出现 +/- 且仅可能出现在字符串首位。
输入描述
输入一个字符串,包括数字字母符号,可以为空
返回值描述
如果是合法的数值表达则返回该数字，否则返回0
题目解析
这道题核心先要知道一个字符串怎么转成整形：
"123"，我们进行遍历它，首先看到得是’1’，怎么把字符1转换成数字1，‘1’-‘0’ = 1，字符1减去字符0就等于数字1，我们定义一个sum = 0，循环中：sum = sum*10+*it -‘0’，第一次sum = 1，第二次sum等于12，第三次sum等于123。其次我们还要考虑首字符是不是’+’ ‘-’，用一个flag来记录，是’+‘就让flag = 1，是’-'就让flag = -1，在循环当中我们还要确定是不是非法字符，是非法字符直接return 0。
题目代码
class Solution {
public:
int StrToInt(string str)
{
if(str.size() == 0)
{
return 0;
}
string::iterator it = str.begin();
int flag = 1;
if(*it == '-')
{
flag = -1;
}
if(*it == '-'||str[0] == '+')
{
it++;
}
//遍历
int sum = 0;
while(it!=str.end())
{
if(*it <'0' || *it > '9')
{
return 0;//非法字符
}
else
{
sum = sum*10 + *it-'0';
}
it++;
}
return flag*sum;
}
};