笔试强训每日一题(六)

不要二

题目链接

题目描述

二货小易有一个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 = sum10+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;
    }
};