Convert a string to an integer and don't double it

️ Convert a string to an integer ️

Topic details

Convert a string to an integer , Library functions that require that integers cannot be converted using strings .  Values for  0  Or if the string is not a valid value, it returns  0

Data range ： The string length satisfies  

Advanced ： Spatial complexity  O(1) , Time complexity  O(n)

Be careful ：

① Any symbol... May appear in the string , Occurrence Division  +/-  Output directly when other symbols  0

② Possible in string  +/-  And can only appear at the beginning of the string .

Input description ：

Enter a string , Including alphanumeric symbols , Can be null

Return value description ：

If it is a legal numeric expression, it returns the number , Otherwise return to 0

Example 1

Input ：

"[phone]"


Return value ：

2147483647


Example 2

Input ：

"1a33"


Return value ：

0


Topic link ：

Convert a string to an integer

Their thinking

The basic idea ：

  simulation

Their thinking 1：

Let's look at the problem , It says let's convert strings to integers , And library functions cannot be used ,emmm, It says you don't need it if you can't use it ？ I have to use ! So the first idea is to use library functions , That's not enough .

Their thinking 2：

A special case , When judging the first character of a string , If

-

, We can design a tag

isPos

Indicates whether this number is a positive number , If not , take

isPos

Set to

false

, Instead of

true

, If

+

No need to deal with it , If it is other non numeric characters , return

0

that will do .

For other characters on the string , Directly judge whether it is a number , That is to judge whether the size of characters is between

['0', '9']

Between , If not satisfied , Go straight back to

0

.

Source code

Their thinking 2：

import java.util.*;
public class Solution {
 public int StrToInt(String str) {
 char[] cs = str.toCharArray();
 int n = cs.length;
 int ans = 0;
 boolean isPos = true;
 
 for (int i = 0; i < n; i++) {
 char c = cs[i];
 if (c > '0' && c < '9') {
 ans = ans * 10 + (c - '0');
 } else if (i == 0 && c == '-') {
 isPos = false;
 continue;
 } else if (i == 0 && c == '+') {
 continue;
 } else {
 return 0;
 }
 }
 // Not positive.
 if (!isPos) {
 ans = -ans;
 }
 return ans;
 }
}


summary

This is a string simulation question , In essence, it is to judge whether a character is a number .

️ No two ️

Topic details

Er Huo Xiaoyi has one W*H Grid box , The row number of the grid is 0 ~ H-1, The column number of the grid is 0 ~ W-1. At most one cake can be placed in each grid , The Euclidean distance between any two cakes cannot be equal to 2. For two lattice coordinates (x1,y1),(x2,y2) Euclidean distance of :

  Xiao Yi wants to know how many cakes can be put in the grid box at most .

Input description ：

Each array contains the length and width of the grid W,H, Split with spaces .(1 ≤ W、H ≤ 1000)

Output description ：

Output a maximum number of cakes

Example 1

Input ：

3 2


Output ：

4


Topic link ：

No two

Their thinking

The basic idea ：

  Mathematical reasoning

Their thinking ：

  From the aspect of the problem , It feels like a pen test of Netease , anyway , Let's analyze , The distance between any two cakes cannot be equal to 2, According to the distance calculation formula given in the topic, we can get the following equation ：

. Because the coordinates given by the topic will not be decimal , Therefore, if the above formula holds , that

  And  

It must also be an integer , Then it's easy , Let's put the results first

Split ：$4 = 1+3

4=2+2

4=4+0

(x1-x2)

(y1-y2)

(x1-x2) * (x1-x2)

(y1-y2) * (y1-y2)

4=0+4$

namely

  Not for

or

, 

  Not for

or

, namely

perhaps

, When this condition is met, the corresponding grid can put the cake .

We can define a size as

h*w

A two-dimensional array to indicate whether the cake can be placed in the corresponding position , If you can , The corresponding position is set to

0

, Otherwise, set to

1

, First , Create a 2D array , And set all elements to

0

, It means you can put a cake , We go from left to right , Traverse the two-dimensional array from top to bottom , If the value of the traversal result is

0

, Counter plus

1

, And turn the lower direction

(i+2, j)

And right direction

(i, j+2)

Set the position to

1

, Because we traverse right and down , So modify the mesh results on the right and bottom , Of course, you can also change the grid around you , But there is no need to .

Source code

import java.util.*;

public class Main {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 
 int w = sc.nextInt();
 int h = sc.nextInt();
 
 // Mark , by 0 Means to place the cake , Not 0 Means no cake
 int[][] f = new int[h][w];
 int ans = 0;
 for (int i = 0; i < h; i++) {
 for (int j = 0; j < w; j++) {
 if (f[i][j] == 0) {
 ans++;
 // The update distance is 2 The location of the for 1
 if (i + 2 < h) {
 f[i + 2][j] = 1;
 } 
 if (j + 2 < w) {
 f[i][j + 2] = 1;
 }
 }
 }
 }
 System.out.println(ans);
 }
}


summary

This problem belongs to mathematical reasoning problem , When deriving the coordinate relationship that cannot put the cake , We can build a W*H Two dimensional array , Set the State

0

It means you can put cake , Initially, all meshes are marked as ready for cake , Then we iterate over the array , Mark the position where the cake cannot be placed as

1

, Finally, we can calculate the number of grids that can put the cake in real time during the traversal .