ARTS Week 3
Algorithm
This week’s LeetCode problem is 8. String to Integer (atoi).
Description: Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).
Solution Idea: Because int
may have overflow, you can use long
variable to store the result first and then determine whether there is overflow. The string matching rules are as follows.
- (optional) It can be skipped automatically if start with spaces(
- (Optional)
+/-
can be used to record whether the number is positive or negative. - (mandatory)
isDigit(ch) == true
is the number One thing to note is. - (Must be wrong) after receiving the
+/-
sign, the next character must be a number, any other character in between is not legal (including spaces) - (must be wrong) once you start receiving numbers, the next must be a number, any other characters are not legal.
Accepted Code
class Solution {
public int myAtoi(String s) {
long ans = 0;
boolean isPositive = true;
boolean isStart = false;
int isOutOfRange = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '-') {
if (isStart == false) {
isPositive = false;
} else {
break;
}
isStart = true;
} else if (s.charAt(i) == '+') {
if (isStart == true) {
break;
}
isStart = true;
} else if (Character.isDigit(s.charAt(i)) == true) { if (isStart == true) { break; } isStart = true; } else if (Character.isDigit(s.charAt(i)) == true)
if (isStart == false) {
isStart = true;
}
ans = ans * 10 + Character.digit(s.charAt(i), 10);
if ((isPositive == false) && (-ans <= Integer.MIN_VALUE)) {
isOutOfRange = -1;
break;
} else if (ans > Integer.MAX_VALUE) {
isOutOfRange = 1;
break;
}
else {
continue;
}
} else {
if ((isStart == false) && s.charAt(i) == ' ' ) {
continue;
}
break;
}
}
switch (isOutOfRange) {
case 1:
return Integer.MAX_VALUE;
case -1:
return Integer.MIN_VALUE;
default:
if (isPositive == false) {
return (int) -ans;
} else {
return (int) ans;
}
}
}
}
In addition to the conventional solution, this problem can also be solved by deterministic finite automaton (DFA)
, the specific solution can be found in another article (currently not updated).
Review
This week’s Review is for the following article: Social networks: It’s worse than you think.
In this essay, author introduced that message propagation also follows a power law : If a meme has less number of words, its probability of being shared will increase. This means that as the number of messages in the network rises, the quality of those which propagate falls. In our life, there are more and more news today for us, the quality of information we propagate is going to fall.
In fact, I think that all the information we see today, we will forget about 50% tomorrow and 80%+ in a week. That is less is more, while more is less.
Tip
For each class loaded, the JVM creates an instance of type Class
for it and associates the two. The Class
instance is unique in the JVM, so you can use the Class
instance to determine if it is of the same type. Also, the built-in keyword instanceof
in Java can be used to determine if it is of the same type. What is the difference between the Class
instance and the instanceof
keyword?
instanceof
: This keyword not only matches the type, but it also matches if it is a subclass of the type.Class
: By using==
to determine whether two types ofClass
are equal, only the exact data type can be determined, but not for subtype comparison.
Example code is as follows.
public class Main {
public static void main(String[] args) {
Integer n = new Integer(123); boolean b11 = n instanceof Integer; // true, because n(Integer)'s type is Integer
boolean b12 = n instanceof Number; // true, because n(Integer) is a subclass of Number class
boolean b13 = n instanceof Double // false, because n(Integer) has no inheritance relationship with the Double class boolean b3 = n.getClass() == Integer.class; // true, because n.getClass() returns Integer.class
boolean b4 = n.getClass() == Number.class; // false, because Integer.class!=Number.class
}
}
If you want to determine whether two Class
s can be transformed upwards, you need to call isAssignableFrom()
. Example code is as follows.
// The Integer class is inherited from the Number class
public class Main {
public static void main(String[] args) {
Integer.class.isAssignableFrom(Integer.class); // true, because Integer can be assigned to Integer
Number.class.isAssignableFrom(Integer.class); // true, because Integer is a subclass of Number class
Object.class.isAssignableFrom(Integer.class); // true, because all classes are subclasses of Object class
Integer.class.isAssignableFrom(Number.class); // false, because Integer is a subclass of Number and cannot be assigned to a child class using the parent class.
}
}
Share
Learn to make good use of schedule software. There are all kinds of things that need to be taken care of every day in daily life, and somethings only occur at certain times. In the past, I used to use my brain to remember what to do and when in the next few days, but as I get older and have more things to deal with, my memory is not as good as it used to be, and I forget things from time to time, and sometimes I need to be reminded by others. However, it may disrupt my schedule and be passively pushed around by time. In order to keep myself from forgetting things, I have been trying to use a schedule for the last two weeks, so that I can know in advance what time will be taken up, as well as scheduling things without making things conflicts. After using the schedule, I found that there is another advantage of using the schedule, it can release part of the brain capacity space. So that the brain capacity is not rich can store more useful information, as to when to do what, or leave it to the computer phone and other devices to remember :)