2. Add Two Numbers
This question is mathematics question. Each of us must have learned addition.So this is a carry sums of addition question.The question becomes clear.
- Addition of the same rank from left to right,when there is one carry left,ten digits will be added in the next calculation
- When the last number is reached,it is also necessary to judge whether to carry
Solution
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//create a ListNode of head
ListNode head = new ListNode(0);
//move pointer
ListNode pre = head;
//n is tens digit,cur is to judge the last number whether plus 1
int n = 0, cur = 0;
while (l1 != null || l2 != null) {
//if l1 ot l2 is to the end,just let it 0
int n1 = 0, n2 = 0;
if (l1 != null) {
n1 = l1.val;
}
if (l2 != null) {
n2 = l2.val;
}
//count the sum of all this location number
int sum = n1 + n2 + n;
//refresh n,otherwise the last result will retained
n = 0;
//judge whether it is greater than 10
if (sum >= 10) {
//tens digit
n = 1;
//digit
sum = sum - 10;
}
//if n is 0,don't need add 1 at last
cur = n;
//create the new node
pre.next = new ListNode(sum);
//update the move pointer and two ListNode
pre = pre.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
//whether to add 1 at last
if (cur == 1) {
pre.next = new ListNode(cur);
}
return head.next;
}3. Longest Substring Without Repeating Characters
This question is a dynamic window problem.We need begin from the head,use two pointer.If the right pointer find the repeating character.Just move the left pointer one step.Record the distance between the left pointer and the right pointer each time.The max value is the answer.
Solution
public int lengthOfLongestSubstring(String s) {
//use HashSet to mark the character
HashSet<Character> hashSet = new HashSet<>();
//if j is 0,j++ is 1,equivalent to ignoring the first,so j must -1
int j = -1, length = 0;
for (int i1 = 0; i1 < s.length(); i1++) {
//this situation must find a repeating characters,so remove the first,if still repeating,
// just continue
if (i1 != 0) {
hashSet.remove(s.charAt(i1 - 1));
}
//if don't find the repeating characters,just continue move right pointer
while (j + 1 < s.length() && !hashSet.contains(s.charAt(j + 1))) {
hashSet.add(s.charAt(j + 1));
j++;
}
//calculate the length of each time,marked the max length
length = Math.max(length, j - i1 + 1);
}
return length;
}5. Longest Palindromic Substring
This question is not easy to think about.The most basic method is enumeration,list every different string.Verify whether it is a palindrome string.So you can get the begin location and the end location of the maximum length string.But this solution time is $O(n^2)$.It will be time out,so we must consider another solution.
We can find a pattern.If this string is palindromic string.It must have a symmetry point.
athe symmetry point is odd numbera athe symmetry point is even number
So we can begin from the string head,verify each characters whether is the symmetry point.
Solution
public String longestPalindrome(String s) {
//special cases
if (s == null || s.length() < 1) {
return "";
}
//record every palindromic string location
int left = 0, right = 0, length = 0;
for (int i = 0; i < s.length(); i++) {
//odd number
int len1 = findLength(s, i, i);
//even number
int len2 = findLength(s, i, i + 1);
length = Math.max(len1, len2);
if (length > right - left) {
//-1 is distinguish between odd and even cases
left = i - (length - 1) / 2;
right = i + length / 2;
}
}
return s.substring(left, right + 1);
}
private int findLength(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
//if there is only have a character,if do not -1,it will return false
return right - left - 1;
}6. ZigZag Conversion
This question is hard to understand at first.Because you have no idea to how to change it shape. But after you come down and observe carefully,you can find a law.
Each layer is like an array,start traversing from the top,return to the top after reaching the bottom,move back and forth.Let's find out its law.
- We can find when the law is
0andnumRows,it will reverse.
The result need us return a string,so we need use StringBuilder.And each row is a list.
Solution
public String convert(String s, int numRows) {
//special cases "AB" "A"
if (numRows < 2) {
return s;
}
//each row is a arraylist to store each element,so StringBuilder
ArrayList<StringBuilder> list = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
list.add(new StringBuilder());
}
//row1 begin is 0
int i = 0, reverse = -1;
for (char c : s.toCharArray()) {
//each element add to their own row list
list.get(i).append(c);
//will row number is 0 or numRows -1.switch direction
if (i == 0 || i == numRows - 1) {
reverse = -reverse;
}
i += reverse;
}
//connect each row of the list
StringBuilder Builder = new StringBuilder();
for (StringBuilder s1 : list) {
Builder.append(s1);
}
return Builder.toString();
}8. String to Integer (atoi)
This is a simulate development issues,we will meet it usually in our work.We should calm down analysis the question.Understand its needs and think about how to meet its need.Write down the flow chart if necessary.It's much easier to write code again.
In fact,many times work requirements are similar to this kind of problem,if you encounter
- There are ready-made tools and libraries that need to be used as much as possible,because they have better performance,have undergone more rigorous testing,and are relatively reliable.
- It can be extracted into tools and tool methods as much as possible,highlighting the main logic,and facilitating code reuse in the future
- When you have to write more cumbersome and lengthy,you need to write clear notes and reflect the logical level to troubleshoot problems and follow-up maintenance after going online
- There may be characters that are not plus or minus signs or numbers in front,remove theme.
- When you encounter the first number,you can add a minus again,if it is not a plus sign but a positive number,the default is a positive number.
- How to verify whether a symbol is encountered,we can set a boolean,the default value is true,if is a negative symbol,we change it into false.
- Every time you read a new number,you need to verify whether its value is out of range
- Stop when reading a non-number,and return to the number read if it does not out of range
Solution
public int myAtoi(String s) {
//change it into array
char[] array = s.toCharArray();
//pointer
int index = 0;
//remove the character which is not number of "+" "-"
while (index < array.length && array[index] == ' ') {
index++;
}
//the special situation
if (index == array.length) {
return 0;
}
//default situation
boolean positive = true;
//if find the sign,judge whether is negative or positive sign
if (array[index] == '+') {
index++;
} else if (array[index] == '-') {
positive = false;
index++;
}
//judge whether out of range
int result = 0, overflow = 0;
while (index < array.length) {
char c = array[index];
//if not number,just end the search
if (c < '0' || c > '9') {
break;
}
int temp = c - '0';
result = overflow;
overflow = overflow * 10 + temp;
//if out of range,just return
if (result != overflow / 10) {
return positive == true ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
index++;
}
//add symbol
return positive == true ? overflow : 0 - overflow;
}11. Container With Most Water
This question is a very clever thought.We all know the bucker effect,The volume of the bucket is dominated by the smaller side.We can imagine that the length of both sides of this barrel is the same,and the length is n.The distance between the two sides is m.So the volume of the barrel is n*m.
But the both sides of this barrel maybe not be the same.So we can just use the smaller side.
I write a picture to describe the situation.We can find the that the side length of the rectangle is getting smaller and smaller.So we can use two pointers,if one pointer is smaller than another pointer,just need update the smaller one.Just like the picture i draw.If the area of the current rectangle is larger than the previous area,update the area value.
Solution
public int maxArea(int[] height) {
//two pointer,area value
int left = 0, right = height.length - 1, result = 0, temp = 0;
//while thery did,t meet,just update the smaller pointer
while (left < right) {
temp = result;
//count the current rectangle area
if (height[left] < height[right]) {
temp = height[left] * (right - left);
left++;
} else {
temp = height[right] * (right - left);
right--;
}
//update the larger rectangle area
if (temp > result) {
result = temp;
}
}
return result;
}12. Integer to Roman
This question is opposite of 13. Roman to Integer.If you under stand that question,so you can understand this question easily.
We can finde a pattern:In Roman numerals,the number composition is the big number on the left and then decreases to the right.
num = 1994=MCMXCIV M = 1000, CM = 900, XC = 90 and IV = 4num = 58=LVIII L = 50, V = 5, III = 3
So we can use enmu,enumerate every special roman numeral.Start subtracting from the largest Roman numeral and finally concatenate it to get the answer.
Solution
public String intToRoman(int num) {
StringBuilder builder = new StringBuilder();
//1 4 5 9 10 40 50 90 100 400 500 900 1000
String[] Roman = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
while (num > 0) {
if (num >= 1000) {
builder.append(Roman[12]);
num -= 1000;
} else if (num >= 900) {
builder.append(Roman[11]);
num -= 900;
} else if (num >= 500) {
builder.append(Roman[10]);
num -= 500;
} else if (num >= 400) {
builder.append(Roman[9]);
num -= 400;
} else if (num >= 100) {
builder.append(Roman[8]);
num -= 100;
} else if (num >= 90) {
builder.append(Roman[7]);
num -= 90;
} else if (num >= 50) {
builder.append(Roman[6]);
num -= 50;
} else if (num >= 40) {
builder.append(Roman[5]);
num -= 40;
} else if (num >= 10) {
builder.append(Roman[4]);
num -= 10;
} else if (num >= 9) {
builder.append(Roman[3]);
num -= 9;
} else if (num >= 5) {
builder.append(Roman[2]);
num -= 5;
} else if (num >= 4) {
builder.append(Roman[1]);
num -= 4;
} else if (num >= 1) {
builder.append(Roman[0]);
num -= 1;
}
}
return builder.toString();
}