43. Multiply Strings
This question is very similar with question 2. Add Two Numbers.It's all math problems,if you want to understand this question clearly.You should draw a picture first.
We can find that one number is multiplied by each digit of another number in turn.So we can think of using double for.Because we traverse the multiplier from right to left,so the whole process involves adding more strings.So we can use an array to instead of a string to store the result.
And how long do we set the array?This is a very important question.We can set num1's length is m and num2's length is n,and both are them are not 0.
- If the num1 and num2 lengths are all take the minimum.So $num1=10^(m-1)$,$num2=10^(n-1)$,so $num1\times num2=10^(m+n-2)$,the length of the result is $m+n-1$
- If the num1 and num2 lengths are all take the maximum.So $num1=10^m-1$,$num2=10^n-1$,$num1 \times num2 = 10^(m+n)-10^m-10^n+1$,the length of the result is $m+n$
So we can set a array which its length is $m+n$,and judge it at last.If it's first digit is 0,so we jump this digit.
Solution
public String multiply(String num1, String num2) {
//the special situation
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
//we can use StringBuffer to create the result
StringBuffer sb = new StringBuffer();
//n+m
int[] array = new int[num1.length() + num2.length()];
for (int i = num1.length() - 1; i >= 0; i--) {
//we can get the number
int n1 = num1.charAt(i) - '0';
for (int i1 = num2.length() - 1; i1 >= 0; i1--) {
int n2 = num2.charAt(i1) - '0';
int sum = array[i + i1 + 1] + n1 * n2;
//make a example,8*4=32 32/10=3 32%10=2
array[i + i1 + 1] = sum % 10;
array[i + i1] += sum / 10;
}
}
//judge the first digit whether is 0
int index = array[0] == 0 ? 1 : 0;
while (index < array.length) {
sb.append(array[index]);
index++;
}
return sb.toString();
}45. Jump Game II
This question is a Greedy question.And what is greedy?Greedy is a very interesting solution.When we meet a problem of finding the optimal solution,we can regard result as collection of many optimal solutions.
The most important thought of greedy is to find the optimal solution for the current situation.So we analyze this problem.Our goal is to reach the last index in the minimum number of jumps.So how to get the minimum number,of course is jump the largest number as much as possible.
In order not to cause cross-border problems,we can make two boundaries.One is the farthest point the pointer can actually reach.The other is the farthest point reached by this pointer theory.When the pointer reach the farthest,just need to update the point.
Solution
public int jump(int[] nums) {
//count is number of the jump
int i = 0, count = 0, maxMove = 0, endIndex = 0;
// five element,have four intervals,so is nums.length-1
while (i < nums.length - 1) {
//the farthest pointer theory
maxMove = Math.max(maxMove, i + nums[i]);
//while reach the farthest,just need to update the point
if (i == endIndex) {
endIndex = maxMove;
count++;
}
i++;
}
return count;
}46. Permutations
This question is also a backtracking question,it is very similar with 40. Combination Sum II and 17. Letter Combinations of a Phone Number.The main idea is backtracking.That's the thought to come back at the end,so what is at the end?This question told us all the integers of nums are unique.So the end is all the numbers are in the list.list.size()=nums.length is the end.This question becomes simple.
Solution
List<List<Integer>> result = new ArrayList<>();
ArrayList<Integer> rls = new ArrayList<Integer>();
public List<List<Integer>> permute(int[] nums) {
backTracking(nums);
return result;
}
private void backTracking(int[] array) {
//find reaching the end,just add the rls into the result
if (rls.size() == array.length) {
result.add(new ArrayList<Integer>(rls));
return;
}
for (int i = 0; i < array.length; i++) {
//if the number had been added,just continue
if (!rls.contains(array[i])) {
//add the number into the rls
rls.add(array[i]);
backTracking(array);
//the main code,just meaning backtracking,revocation processing node
rls.remove(rls.size() - 1);
}
}
}47. Permutations II
This question is a updated version of 46. Permutations.This question has a difficulty,it is how to avoid repetition.The entire linked list node graph is like a tree branch,we should prune.
We all know the use of backtracking,we should clear our thought.
- if
rls.size() == array.lengthjust need to return therlsto theresult.It means we found one of the solutions - if
rls.size() < array.length,it means we need search continue,but we can't find the numbers we have found.So we can use a boolean array.If the element is false,it means we found it last time,when it is true,it means we find it this time.You can watch the picture,it shows backtracking process.When searching for nodes in the same layer,we need to check whether the previous layer has been searched.i > 0 && array[i] == array[i - 1] && !hadFound[i - 1]If the elements are the same and the last one has been searched,so just continue.
Solution
List<List<Integer>> result = new ArrayList<>();
ArrayList<Integer> rls = new ArrayList<Integer>();
public List<List<Integer>> permuteUnique(int[] nums) {
//to avoid special situation,we should sort the nums first
Arrays.sort(nums);
boolean[] hadFound = new boolean[nums.length];
backTracking(nums, hadFound);
return result;
}
private void backTracking(int[] array, boolean[] hadFound) {
//find reaching the end,just add the rls into the result
if (rls.size() == array.length) {
result.add(new ArrayList<Integer>(rls));
return;
}
for (int i = 0; i < array.length; i++) {
//if this number is finding,just continue
if (hadFound[i]) {
continue;
}
//If the elements are the same and the last one has been searched,so just continue
if (i > 0 && array[i] == array[i - 1] && !hadFound[i - 1]) {
continue;
}
rls.add(array[i]);
hadFound[i] = true;
backTracking(array, hadFound);
//the main code,just meaning backtracking,revocation processing node,and let this number
// become false
hadFound[i] = false;
rls.remove(rls.size() - 1);
}
}48. Rotate Image
This question is a very very interesting question.If you have played Rubik's Cube,you can solve this problem easily.As we all know the middle point of the odd number is unchanged.In the Rubik's Cube,we call it the center point.We need to rotate the image with the center point as the reference.So this problem has two solutions,one is rotate and another one is fold.
fold
public void rotate(int[][] matrix) {
int l = matrix.length;
//fold in half
for (int i = 0; i < l / 2; i++) {
for (int j = 0; j < l; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[l - i - 1][j];
matrix[l - i - 1][j] = temp;
}
}
//fold in half along the center line
for (int i = 0; i < l; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}rotate
public void rotate(int[][] matrix) {
int l = matrix.length;
for (int i = 0; i < l / 2; i++) {
for (int j = 0; j < (l + 1) / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[l - j - 1][i];
matrix[l - j - 1][i] = matrix[l - i - 1][l - j - 1];
matrix[l - i - 1][l - j - 1] = matrix[j][l - i - 1];
matrix[j][l - i - 1] = temp;
}
}
}49. Group Anagrams
This problem is typical statistical classification problem.It requires us find the same anagram.Such as "ate" "eat" "tea".Let us observe how they differ from others anagram.They have three characters,we arrange the three characters from small to large a e t.An the other anagrams are "bat" or "nat" "tan".We still arrange the three characters from small to large.a b t,a n t.So we find the difference between them.At this time,we need to group together those with the same characteristics.We can think of using HashMap.key is the arrange the three characters from small to large.And the values are the same anagrams.
Solution
public List<List<String>> groupAnagrams(String[] strs) {
//creat the HashMap,key values
HashMap<String, List<String>> map = new HashMap<>();
//traversal the strs
for (String s : strs) {
//change the string to the char array
char[] array = s.toCharArray();
//sort the arry,arrange the letters from small to large,get the key
Arrays.sort(array);
String symbol = new String(array);
//if doesn't have the key,just add the (key,value)
if (!map.containsKey(symbol)) {
ArrayList<String> list = new ArrayList<>();
list.add(s);
map.put(symbol, list);
} else {
//have the key,so just need to get the value,and add into the value
map.get(symbol).add(s);
}
}
//return all values
return new ArrayList<>(map.values());
}50. Pow(x, n)
This problem is a mathematic problem.As we all know $x^n=x\times x \times ... \times x$.And if n<0,we will count $1/x^n$.This problem seems to be solved on the surface.But if you submit,the time will limit exceeded.Last executed input:1.00000 2147483647.Because the number of n is so large.So how do we reduce the computing time of n?
As we all know $x^4=x^2 \times x^2$.$x^3 = x^1 \times x^2$.So we can get a rule.If n is even,$x^n = x^(n/2) \times x^(n/2)$.If n is odd,$x^n = x^(n/2) \times x^(n/2) \times x^1$.So the time cost becoming $O(logn)$.So this problem we can use recursion to solve it.The condition for the end of recursion is $n==0$,just return 1.0;
Solution
public double myPow(double x, int n) {
return n > 0 ? recursion(x, n) : 1 / recursion(x, -n);
}
/**
* the function of recursion
*/
private double recursion(double x, int y) {
//the condition for the end of recursion
if (y == 0) {
return 1.0;
}
double result = recursion(x, y / 2);
//judge whether the even or the odd
return y % 2 == 0 ? result * result : result * result * x;
}