笔试强训之每日一题(六)

笔试强训每日一题(六)

文章目录

不要二

题目链接

题目描述

二货小易有一个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;
    }
};
上一篇:双线性插值


下一篇:acwing-798. 差分矩阵