Question Profile
Programming ideas
- Fill in symbol information, data string information during string traversal.
- Strongly convert to a valid number based on the symbol and the last string information.
- To prevent crossing borders, direct data is stored and represented using long-type data.
- Validity query.
Programming Implementation
programming
First version
public int myAtoi(String s) {
char[] chars = s.toCharArray();
int sign = 1;
StringBuilder numberBuilder = new StringBuilder();
int i = 0;
while (i < chars.length && chars[i] == ' ') {
i++;
}
s = s.substring(i);
if (s.charAt(0) == '-') {
sign = -1;
s = s.substring(1);
} else if (s.charAt(0) == '+') {
sign = 1;
s = s.substring(1);
}
i = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
numberBuilder.append(s.charAt(i));
i++;
}
String numberStr = numberBuilder.toString();
if (numberStr.isEmpty()) {
return 0;
}
long value = Long.valueOf(numberStr) * sign;
if (value < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
if (value > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
return (int) value;
}
AC Version
public int myAtoi(String s) {
char[] chars = s.toCharArray();
int sign = 1;
StringBuilder numberBuilder = new StringBuilder();
int i = 0;
while (i < chars.length && chars[i] == ' ') {
i++;
}
s = s.substring(i);
if (s.isEmpty()) {
return 0;
}
if (s.charAt(0) == '-') {
sign = -1;
s = s.substring(1);
} else if (s.charAt(0) == '+') {
sign = 1;
s = s.substring(1);
}
i = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
numberBuilder.append(s.charAt(i));
i++;
}
String numberStr = numberBuilder.toString();
if (numberStr.isEmpty()) {
return 0;
}
i = 0;
while (i < numberStr.length() && numberStr.charAt(i) == '0') {
i++;
}
numberStr = numberStr.substring(i);
if (numberStr.isEmpty()) {
return 0;
}
if (numberStr.compareTo(String.valueOf(Long.MAX_VALUE)) > 0 || numberStr.length()>=20) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
long value = Long.valueOf(numberStr) * sign;
if (value < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
if (value > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
return (int) value;
}
AC Version Prefix Extraction Function - Use Existing Functions Without Efficiency
public int myAtoi(String s) {
int sign = 1;
StringBuilder numberBuilder = new StringBuilder();
int i = 0;
s = removeStartPrefix(s, " ");
s = s.substring(i);
if (s.isEmpty()) {
return 0;
}
if (s.charAt(0) == '-') {
sign = -1;
s = s.substring(1);
} else if (s.charAt(0) == '+') {
sign = 1;
s = s.substring(1);
}
i = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
numberBuilder.append(s.charAt(i));
i++;
}
String numberStr = numberBuilder.toString();
if (numberStr.isEmpty()) {
return 0;
}
String prefix = "0";
numberStr = removeStartPrefix(numberStr, prefix);
if (numberStr.isEmpty()) {
return 0;
}
if (numberStr.compareTo(String.valueOf(Long.MAX_VALUE)) > 0 || numberStr.length()>=20) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
long value = Long.valueOf(numberStr) * sign;
if (value < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
if (value > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
return (int) value;
}
private String removeStartPrefix(String numberStr, String prefix) {
while (numberStr.startsWith(prefix)) {
numberStr = numberStr.substring(1);
}
return numberStr;
}
Problems encountered
Cross-border issues
_The problem with out-of-bounds is that memory overflow occurs when i++ is not executed while fetching all the digital data into the container numberBuilder.
_Then there is a code snippet that does not contain a check for length that results in a break, and the problem is as follows:
i = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
numberBuilder.append(s.charAt(i));
i++;
}
String numberStr = numberBuilder.toString();
Program cannot handle empty string of boundary conditions
No empty string was considered,**fetching charAt(0)** from an empty string threw an exception
This is because
public int myAtoi(String s) {
char[] chars = s.toCharArray();
int sign = 1;
StringBuilder numberBuilder = new StringBuilder();
int i = 0;
while (i < chars.length && chars[i] == ' ') {
i++;
}
s = s.substring(i);
if (s.isEmpty()) {
return 0;
}
// If the incoming string s is empty, the bit 0 is not fetched, and s.charAt(0) throws an exception, so a return of 0 if s is empty was added earlier.
if (s.charAt(0) == '-') {
sign = -1;
s = s.substring(1);
} else if (s.charAt(0) == '+') {
sign = 1;
s = s.substring(1);
}
Unable to process ** "20000000000000000"**
_In use of Long.parseLong's time, to determine if the number is out of bounds, is based on Long's longest 19 digits.
if (numberStr.length()>=20) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
Unable to process "00000-42a1234"
_After removing invalid leading zeros, returning to''may cause problems.
_Therefore, after removing the leading 0, the empty string is judged.
i = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
numberBuilder.append(s.charAt(i));
i++;
}
String numberStr = numberBuilder.toString();
if (numberStr.isEmpty()) {
return 0;
}
i = 0;
while (i < chars.length && chars[i] == '0') {
i++;
}
numberStr = numberStr.substring(i);
if (numberStr.isEmpty()) {
return 0;
}
if (numberStr.length()>=20) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
Unable to process'-000000000000000000000000000000000000001'
Unable to process ** "20000000000000000"**
The previous process of processing this number is still not valid and the final modification procedure is as follows:
i = 0;
while (i < numberStr.length() && numberStr.charAt(i) == '0') {
i++;
}
numberStr = numberStr.substring(i);
if (numberStr.isEmpty()) {
return 0;
}
if (numberStr.compareTo(String.valueOf(Long.MAX_VALUE)) > 0 || numberStr.length()>=20) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
long value = Long.valueOf(numberStr) * sign;
if (value < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
if (value > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
return (int) value;
numberStr.compareTo(String.valueOf(Long.MAX_VALUE)) > 0 || numberStr.length()>=20
_This expression returns the maximum and minimum values of Integer by symbol when the length of comparison is >=20 by comparing strings. But compare 19 bits to Long. MAX_ The maximum value of VALUE is compared by strings before the comparison is finally completed.
summary
_The answer to the basic question of this topic is relatively simple, and the basic framework of the program is not complex, but in dealing with cross-border problems, leading 0 problems, there are really many pits. Leading 0 issues can be handled in the following ways:
while(str.startWith('0')) {
str = str.substring(1);
}
_This is relatively simple, do not consider efficiency, at first, especially when programming topics, correctness is greater than efficiency.
_We refine the above method into a function and inline it, and the resulting code is as follows:See AC version prefix refining function - use existing function without efficiency
_From above, you can see that the memory consumption is 0.1M more, which is indifferent, and the correctness is much greater than the efficiency. Debugging takes a lot of time, so it is very important to sort out the basic process of the program, understand the input and output, and process the logic.
_The most important benefit of this program is the problem of comparing Long's maximum values.
_is not particularly entangled. It is very tired and the eyes are painful. Tomorrow I will go to Nanyang. Hope to be in a good mood.