54. Spiral MatrixThis problem is a two-dimensional array processing problem.The test point is how to loop and iterate when facing different situations.We can draw a picture to better understand.We can get the the array location [row,col].So we only need to proceed according to the requirements of the question.The difficulty of this question is that every time the position of the element is determined,it is easy to confirm the error.When we search for a complete row or column,we must subtract the current row or column,otherwise an error will occur.Solution public List<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> list = new ArrayList<>(); //define row and col int rowStart = 0, rowEnd = matrix.length - 1; int colStart = 0, colEnd = matrix[0].length - 1; //the number of all elements int allElement = (rowEnd + 1) * (colEnd + 1); //count the number of the elements what we add int counter = 0; while (rowStart <= rowEnd || colStart <= colEnd) { //top from left to right for (int i = colStart; i <= colEnd; i++) { list.add(matrix[rowStart][i]); counter++; } //we must subtract the current row or column,otherwise an error will occur rowStart++; if (counter == allElement) { break; } //right from top to bottom for (int i = rowStart; i <= rowEnd; i++) { list.add(matrix[i][colEnd]); counter++; } colEnd--; if (counter == allElement) { break; } //bottom from right to left for (int i = colEnd; i >= colStart; i--) { list.add(matrix[rowEnd][i]); counter++; } rowEnd--; if (counter == allElement) { break; } //left from bottom to top for (int i = rowEnd; i >= rowStart; i--) { list.add(matrix[i][colStart]); counter++; } colStart++; if (counter == allElement) { break; } } return list; }55. Jump GameIf you have already written the question 45. Jump Game II.So you can know this problem is also a greedy problem.The main idea to solve this question is the farthest distance every time you jump.The distance that each position can jump out is i+nums[i].So we can set a value maxMove,but we can;t judge the maxMove at last.For example [0,2,3].The maxMove is larger than the array's length,but we will stuck at first.So we will set another value endIndex.This value is we can actually reach the location.If we reach the endIndex,we just need to update this value and judge this value whether larger than the array's length.Solution public boolean canJump(int[] nums) { //for example [0,2,3],the maxMove is larger than the array's length,but we will stuck at first int l = nums.length - 1, maxMove = 0, endIndex = 0; for (int i = 0; i < nums.length - 1; i++) { //the farthest you can reach in theory maxMove = Math.max(maxMove, i + nums[i]); //if you reach the actual end location,just update the end location if (i == endIndex) { endIndex = maxMove; } } return endIndex >= l; }56. Merge IntervalsThis problem is an abstract double pointer porblem.First of this we must sort this Two-dimensional array.Why we must sort,i will draw a picture to describe it.Why can merge [1,3] to [2,6],for convenience,we call it A B array.Because A[1] is larger than B[0],so we can merge theme.But if this array is unordered,it will very difficult.For example [1,3] [8,10] [2,6] [15,18],so that's why we should sort it at first.We can override the sort function,the comparison is the size of the first element of each array.We must pay attention to one small point,which is the end of the new array.For example [1,8] [5,7] the new array is [1,8].So the new array's end is Math.max(A[1],B[1]).Why i say this problem is an abstract double pointer porblem.Because we can treat each small array as a pointer.We set the current pointer is slow pointer,and set the next position pointer is the faster pointer.And use double pointer can traverse all the arrays.Solution public int[][] merge(int[][] intervals) { //the special situation if (intervals.length == 1) { return intervals; } //override the sort function Arrays.sort(intervals, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0] - o2[0]; } }); //because we don't know how long the result will be,so we use arraylist ArrayList<int[]> list = new ArrayList<>(); //set a slow pointer int[] current_interval = intervals[0]; //and add it at first,if don't add it,we will miss the first of the result array list.add(current_interval); //traverse the array for (int[] interval : intervals) { //because we don't need to judge the current[0],we just need to judge the current[1],so we // don't need this step //int current_begin = current_interval[0]; int current_end = current_interval[1]; //the faster pointer int next_begin = interval[0]; int next_end = interval[1]; //merge the two arrays to be a new result array if (current_end >= next_begin) { current_interval[1] = Math.max(current_end, next_end); } else { //we just need to update the two pointers current_interval = interval; list.add(current_interval); } } return list.toArray(new int[list.size()][]); }57. Insert IntervalThis problem is very similar with problem 56. Merge Intervals.If you want to understand this problem easier.You should understand that problem at first.This problem has three situations.I will use pictures to explain.There has two special situations,one is array interval are all less than new,another situation is new are all less than array interval.I circled it in the picture.The last situation is merger two arrays into a new array.As long as the two arrays have intersecting parts,so just merge it.The result of the merge is the new newInterval.So we only need to traversal this array,from the head to the end can get the result.Solution public int[][] insert(int[][] intervals, int[] newInterval) { //we don't know how long the result will be,so use arraylist to store ArrayList<int[]> list = new ArrayList<>(); //special situation if (intervals.length == 0 && intervals == null) { list.add(newInterval); return list.toArray(new int[list.size()][]); } //traversal the intervals for (int[] interval : intervals) { //situation1,interval < new if (interval[1] < newInterval[0]) { list.add(interval); } else if (newInterval[1] < interval[0]) { //situation2,new < interval list.add(newInterval); newInterval = interval; } else { //situation3,merge the two arrays into a new array newInterval[0] = Math.min(interval[0], newInterval[0]); newInterval[1] = Math.max(interval[1], newInterval[1]); } } //if we don't add it at last,we will lose the last answer of array list.add(newInterval); return list.toArray(new int[list.size()][]); }59. Spiral Matrix IIThis problem is the same as problem 54. Spiral Matrix.If you want to solve this problem,just need to create a counter.Because each step moves to the position you need to fill in a number.But this number is exactly the number of steps you move.Solution public int[][] generateMatrix(int n) { int[][] matrix = new int[n][n]; int rowStart = 0, rowEnd = n - 1; int colStart = 0, colEnd = n - 1; int allElement = n * n; //creat the counter int counter = 0; while (rowStart <= rowEnd || colStart <= colEnd) { for (int i = colStart; i <= colEnd; i++) { //because the first number is 1,the counter is 0,so need +1 matrix[rowStart][i] = counter + 1; counter++; } if (counter == allElement) { break; } rowStart++; for (int i = rowStart; i <= rowEnd; i++) { matrix[i][colEnd] = counter + 1; counter++; } if (counter == allElement) { break; } colEnd--; for (int i = colEnd; i >= colStart; i--) { matrix[rowEnd][i] = counter + 1; counter++; } if (counter == allElement) { break; } rowEnd--; for (int i = rowEnd; i >= rowStart; i--) { matrix[i][colStart] = counter + 1; counter++; } if (counter == allElement) { break; } colStart++; } return matrix; }61. Rotate ListThis problem is a list problem,let's take a closer look.If the k is larger than the list's length.So it is equivalent to doing it all over again.So in order to go around and search for the unnecessary ones,we should get the list's length L.And k%L can get the position of the node that needs to be rotated.This problem is very easy,we just make a new node key point to head,and the list last position is temp,just just let temp point to head,and key point to rotate position.At last,don't forget to make the cut note point to null,otherwise it will create a circle.Solution public ListNode rotateRight(ListNode head, int k) { //the special situation if (head == null || k == 0) { return head; } //get the list's length ListNode temp = head; int length = 1; while (temp.next != null) { temp = temp.next; length++; } //get the position of the node that needs to be rotated k %= length; //special situation if (k == 0) { return head; } //find the position before the rotating node ListNode cut = head; for (int i = 0; i < length - k - 1; i++) { cut = cut.next; } ListNode rotate = cut.next; ListNode key = new ListNode(0); //key point to rotate key.next = rotate; //temp point to head temp.next = head; //cut point to null cut.next = null; //key -> rotate -> temp -> head ->cut -> null return key.next; }62. Unique PathsThis problem is a very interesting problem.It has a very important requirement,the robot can only move either down or right at any point in time.I draw a picture to explain.The start point can only move either down or right.If the down point has m possible unique paths and the right point has n unique paths.So obviously,the start point has m+n unique paths. When the point moves to the bottom or the right.Because it can only move either down or right,so it can just only move follow the yellow arrow. So we make a summary.[m][n] possible = [m-1][n] possible + [m][n-1] possibleWe can write down the possibility of each position.Solution public int uniquePaths(int m, int n) { int[][] array = new int[m][n]; //the bottom or the right,it can only move either down or right,so the possible are all 1 for (int i = 0; i < array.length; i++) { array[i][0] = 1; } for (int i = 0; i < array[0].length; i++) { array[0][i] = 1; } //[m][n]=[m-1][n]+[m][n-1] for (int i = 1; i < array.length; i++) { for (int j = 1; j < array[0].length; j++) { array[i][j] = array[i - 1][j] + array[i][j - 1]; } } return array[m - 1][n - 1]; }63. Unique Paths IIThis problem caused me a lot of trouble.Because it's an incomplete description of the problem.There may be a lot of obstacles,there may be more than oneThe obstacles' location may be anywhere,it may appear in the start,or it may be at the target place.This problem's main idea are very same with problem 62,but there are some differences.Because if the obstacles appear the bottom place or the right place,so we can't go that way.We should mark all the.And set the initial value of 1 for the boundary between the bottom and the right,if the position is a marked obstacle,set it to -1.There is a note here,in the boundary,if one location is marked it can't walk there,so the next boundary location beside it also can't walk.When we judge the location,we need to judge the down location and the right location.If one of them is marked,we can't add it.Solution public int uniquePathsWithObstacles(int[][] obstacleGrid) { //creat the array,and mark the obstacle int rowNumber = obstacleGrid.length; int colNumber = obstacleGrid[0].length; int[][] array = new int[rowNumber][colNumber]; for (int i = 0; i < rowNumber; i++) { for (int i1 = 0; i1 < colNumber; i1++) { if (obstacleGrid[i][i1] == 1) { array[i][i1] = -1; } } } //the special situation,the target is obstacle array[0][0] = obstacleGrid[0][0] == 1 ? -1 : 1; //judge this location and beside location,if is marked,it also marked for (int i = 1; i < rowNumber; i++) { array[i][0] = obstacleGrid[i][0] == 1 ? -1 : array[i - 1][0] == -1 ? -1 : 1; } for (int i = 1; i < colNumber; i++) { array[0][i] = obstacleGrid[0][i] == 1 ? -1 : array[0][i - 1] == -1 ? -1 : 1; } //judge location,have four situation,we need also judge down and right for (int i = 1; i < rowNumber; i++) { for (int j = 1; j < colNumber; j++) { //is marked if (array[i][j] == -1) { continue; } else if (array[i - 1][j] != -1 && array[i][j - 1] != -1) { array[i][j] = array[i - 1][j] + array[i][j - 1]; } else if (array[i - 1][j] != -1) { array[i][j] = array[i - 1][j]; } else { array[i][j] = array[i][j - 1]; } } } //the special situation,the start place is marked return array[rowNumber - 1][colNumber - 1] == -1 ? 0 : array[rowNumber - 1][colNumber - 1]; }64. Minimum Path SumThis problem is a very interesting problem.We can find an interesting phenomenon,no matter how to move the target,the number of steps we have to reach the end must be the same.So we don't need to consider whether to go down or to the right to save steps.We only need to consider which side to go has less value.We can find the boundary first,because it can only go down or to the right,so the boundary value should be unique.When at the top boundary,just continue move right.When on the left boundary,just continue move down.When in the matrix,just move to the lower value sideSolution public int minPathSum(int[][] grid) { for (int i = 0; i < grid.length; i++) { for (int i1 = 0; i1 < grid[0].length; i1++) { //the start place,just continue if (i == 0 && i1 == 0) { continue; } else if (i == 0) { //the top boundary grid[i][i1] = grid[i][i1 - 1] + grid[i][i1]; } else if (i1 == 0) { //the left boundary grid[i][i1] = grid[i - 1][i1] + grid[i][i1]; } else { //in the matrix,add the lower value grid[i][i1] = Math.min(grid[i - 1][i1], grid[i][i1 - 1]) + grid[i][i1]; } } } //return the value of end place return grid[grid.length - 1][grid[0].length - 1]; }
43. Multiply StringsThis 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 IIThis 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. PermutationsThis 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 IIThis 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.length just need to return the rls to the result.It means we found one of the solutionsif 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 ImageThis 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 AnagramsThis 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; }
29. Divide Two IntegersThis question is a very interesting question.It does a lot of conditional restrictions.So we can only go back to the simplest mathematical method to think.What is division.7/3=2int count=0,7-3=4>3 count=1 4-3=1<3 count=2So this is division.Division is an optimization of subtraction.We can simplify this question.3*n=7 or 3*n-1<7 3*n>7The n is what we need to get.But when the dividend becomes extremely large,and the divisor becomes extremely small,it will cost so much time.So how do we optimize the addition operation?We know that double that multiplying growth is very fast.So we can use recursion to solve this question.There is one thing we must be notice.That's the problem of out-of bounds overflow.For example,if the dividend is Integer.MIN_VALUE and the divisor is 1,the result will overflow.Therefore,in order to facilitate the calculation,we make the situation where the dividend and the divisor are different,and turn both numbers into negative numbers.The box I drew is like multiplication,doubling.Solution public int divide(int dividend, int divisor) { //the special situation if (dividend == 0) { return 0; } if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } //mark the different situation boolean sign = true; if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) { sign = false; } //change them both into negative number dividend = dividend > 0 ? -dividend : dividend; divisor = divisor > 0 ? -divisor : divisor; //if there are different,so it must be a negative number,just 0 minus the result return sign == false ? 0 - count(dividend, divisor) : count(dividend, divisor); } /** * This recursion main code is while,it just likes optimization of subtraction */ private int count(int a, int b) { //if 3*n==7 just plus 1,or 3*n>7 just plus 0 if (a >= b) { return a > b ? 0 : 1; } //the default number is 1,and 2,4,8...doubling int n = 1; // int result = 0; int temp = b; while (a <= temp && temp < 0) { a -= temp; result += n; temp += temp; n += n; } return result + count(a, b); }31. Next PermutationThis question is a mathematic question.Let me give an example to explain the reason.I have three numbers 1 2 3,they can be combined into these combinations.1 2 31 3 22 1 32 3 13 1 23 2 1So this question is give you a number,and let you use this number to find the next location number.And we can easily find a special situation.The situation is each digit is greater than its next digit.Just like 3 2 1.So the next number we just need to reverse this number to get.And how to get the next greater permutation of number?I also make some example.2 33 2We can start from the end,if one digit is smaller than the digits we found,so mark this digit's location.just like n n+5 n+3 n+2.And we start from the end again,find the first digit that is larger than the small digit.We can swap these two digits.So the digit at the same position is just a bit bigger than before.At last we reverse all the numbers after this digit. Solution public void nextPermutation(int[] nums) { //the special situation,just reverse the nums boolean max = true; for (int i = 1; i < nums.length; i++) { if (nums[i] > nums[i - 1]) { max = false; break; } } if (max) { reverse(nums, 0, nums.length - 1); } else { //find the small digit's location int i = nums.length - 2; //find i while (i > 0) { if (nums[i] < nums[i + 1]) { break; } i--; } //find the larger than small digit int n = nums.length - 1; while (n > i) { //swap these two digits,and revers the digits after the small digit if (nums[n] > nums[i]) { swap(nums, i, n); reverse(nums, i + 1, nums.length - 1); break; } n--; } } } /** * the function of swap */ private void swap(int[] array, int a, int b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; } /** * the function of reverse the nums */ private void reverse(int[] array, int a, int b) { while (a < b) { swap(array, a, b); a++; b--; } }33. Search in Rotated Sorted ArrayThis question is a update version of binary search.If you want to understand this question,i think you should understand the most basic of binary search first.The difficulty of this question is how to move the pointers at the both ends.Because this array is not always arranged in ascending order.We can think of this array as two connected arrays,array A and array B.And there are two situations we will meet.One situation is the first element of A is smaller than the nums[mid].The another situation is the first element of A is bigger than the nums[mid].Because the length of A and the length of B are different.So we can judge nums[mid] is in A or B.The situation one.If target<nums[0].Because A array is sorted in ascending order.So all elements of A is smaller than target.So we can get the left pointer boundary.And we can also judge the size of the two values of target and nums[mid].So we can get the right pointer boundary.Solution public int search(int[] nums, int target) { //the special situation if (nums.length == 1) { return nums[0] == target ? 0 : -1; } //create the two pointers int left = 0, right = nums.length - 1; //use binary search while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } //judge left side or right side if (nums[0] <= nums[mid]) { //nums[0] target nums[mid] if (target >= nums[0] && target < nums[mid]) { right = mid - 1; } else { //nums[0] nums[mid] target left = mid + 1; } } else { //nums[mid] target nums[nums.length-1] if (target > nums[mid] && target <= nums[nums.length - 1]) { left = mid + 1; } else { //target nums[mid] nums[nums.length-1] right = mid - 1; } } } return -1; }34. Find First and Last Position of Element in Sorted ArrayThis question is also a Binary Search question.The difficulty of Binary Search is how to determine the boundary so as to prevent the problem of crossing the boundary.This question requires time cost $O(logn)$,so we can't just only use traversal to solve it. As we all know Binary Search can only find one element.So how can we find the both ends of the target.left ... n target1 target2....targetn m .... rightWe can use Binary Search twice.The first time we search for n,the element before the target1.The second time we search for m,the element after the targetn.Let us think about what we usually add when we use binary search.We usually add if(array[mid]==target) return mid;So this make us only find one element.So we need to delete this and change it.Solution public int[] searchRange(int[] nums, int target) { //boundary problem,you can use DeBug,it is clear to understand the double pointer int lower = BinarySearch(nums, target, true); int higher = BinarySearch(nums, target, false) - 1; //exclude the special situation if (higher < nums.length && lower <= higher && nums[lower] == target && nums[higher] == target) { return new int[]{lower, higher}; } return new int[]{-1, -1}; } private int BinarySearch(int[] array, int target, boolean small) { //just like usually binary search int left = 0, right = array.length - 1, arrayLength = array.length; while (left <= right) { int mid = left + (right - left) / 2; //why use boolean,because if boolean is true,it means to find the lower target if (array[mid] > target || (small && array[mid] >= target)) { right = mid - 1; arrayLength = mid; } else { left = mid + 1; } } //the target location is the mid location return arrayLength; }36. Valid SudokuThis question is a very interesting question.It requires us to judge whether it is a valid sudoku.So what are the conditions for valid sudoku?Each row must contain the digits 1-9 without repetition.Each column must contain the digits 1-9 without repetition.Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.So we can make three function to judge these three conditions.And these question has 9 little sudoku.So we can verify each whether it is a valid sudoku.If one of them is not,just return false.And this question is obviously using HashSet.Determine whether there are duplicate numbers.Solution /** * definite a HashSet to store the numbers */ HashSet<Character> sudo = new HashSet<Character>(); public boolean isValidSudoku(char[][] board) { //judge the lists for (int i = 0; i < 9; i++) { sudo.clear(); if (!list(board, i)) { return false; } } //judge the rows for (int i = 0; i < 9; i++) { sudo.clear(); if (!row(board, i)) { return false; } } //judge the little sudoku for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { sudo.clear(); if (!sudoku(board, i, j)) { return false; } j += 2; } i += 2; } return true; } /** * just judge the list function,00,01,02,03...08 */ private boolean list(char[][] board, int n) { for (int i = 0; i < 9; i++) { if (board[n][i] != '.') { if (sudo.contains(board[n][i])) { return false; } sudo.add(board[n][i]); } } return true; } /** * just judge the row function,00,10,20...80 */ private boolean row(char[][] board, int n) { for (int i = 0; i < 9; i++) { if (board[i][n] != '.') { if (sudo.contains(board[i][n])) { return false; } sudo.add(board[i][n]); } } return true; } /** * just judge the the little sudoku,begin form 00,30,60,03,33 */ private boolean sudoku(char[][] board, int n, int m) { for (int i = n; i < n + 3; i++) { for (int j = m; j < m + 3; j++) { if (board[i][j] != '.') { if (sudo.contains(board[i][j])) { return false; } sudo.add(board[i][j]); } } } return true; }38. Count and SayThis question is a recursion question.If we want to write the recursion code.We must know the conditions of recursion.But fortunately,this question have told us the conditon.We just need to start from 1,and make a counter,until the counter is equal to the n. And we can use two pointers,and is faster and another one is slower. So we can get the number of the same elements.Solution public String countAndSay(int n) { //the basic of recursion if (n == 1) { return "1"; } //we can use StringBuilder to get the result string String lastCount = countAndSay(n - 1); StringBuilder sb = new StringBuilder(); //begin from the head of string for (int i = 0; i < lastCount.length(); i++) { //must have at least one element int count = 1; //avoids crossing boundaries while (i + 1 < lastCount.length() && lastCount.charAt(i) == lastCount.charAt(i + 1)) { count++; i++; } //get the result string sb.append(count).append(lastCount.charAt(i)); } return sb.toString(); }39. Combination SumThis question is backtracking problem,it is very similar with problem 17. Letter Combinations of a Phone Number.These problems have a very similar feature.They all recurse,but not just pure recursion.When they encounter the end,they will delete the result of the last recursion.This is the meaning of backtracking.And this question is also very similar with problem 15. 3Sum.So you can combine these two questions to help understand this question.Solution /** * define a global traversal for easy return */ List<List<Integer>> result; public List<List<Integer>> combinationSum(int[] candidates, int target) { //sort the array first,convenient for backtracking,otherwise errors may occur Arrays.sort(candidates); result = new ArrayList<>(); //start backtracking backTracking(new ArrayList<>(), candidates, 0, target); return result; } /** * backtracking function */ private void backTracking(List<Integer> path, int[] candidates, int start, int remain) { //if the result of addition is equals to target,just return if (remain == 0) { result.add(new ArrayList<Integer>(path)); return; } //begin from the head of the array for (int i = start; i < candidates.length; i++) { if (candidates[i] > remain) { return; } //the main step of backtracking function //add the element path.add(candidates[i]); backTracking(path, candidates, i, remain - candidates[i]); //this is the most important step of backtracking,return the previous state path.remove(path.size() - 1); } }40. Combination Sum IIThis question is a combination of 15. 3Sum and 39. Combination Sum.If you understand that two question,you can make a slight change in the code of 39 to solve this question.This question requires each number in array may only be used once.So how do we avoid repetition?When we are looking for the next element,we cannot start from the current position,we should start from behind the current positon.And if the behind elements are equal to the element at the current position,we should skip these elements.Solution /** * define a global traversal for easy return */ List<List<Integer>> result; public List<List<Integer>> combinationSum2(int[] candidates, int target) { //sort the array first,convenient for backtracking,otherwise errors may occur Arrays.sort(candidates); result = new ArrayList<>(); //start backtracking backTracking(new ArrayList<>(), candidates, 0, target); return result; } /** * backtracking function */ private void backTracking(List<Integer> path, int[] candidates, int start, int remain) { //if the result of addition is equals to target,just return if (remain == 0) { result.add(new ArrayList<Integer>(path)); return; } //begin from the head of the array for (int i = start; i < candidates.length; i++) { if (candidates[i] > remain) { return; } //because we can't use the number twice,so we can't start at 0,we must start a new location if (i > start && candidates[i] == candidates[i - 1]) { continue; } //the main step of backtracking function //add the element path.add(candidates[i]); //move to the next location backTracking(path, candidates, i + 1, remain - candidates[i]); //this is the most important step of backtracking,return the previous state path.remove(path.size() - 1); } }
15. 3SumThis question is similar with 1. Two Sum.But they have some different,the main different is this question is the solution set must not contain duplicate triplets.So we can't just use enumeration method,we need to think about how to avoid duplication.In the past,there were two main ways to avoid duplication.One is use HashMap,the other one is this array is ordered.If we just use enumeration method to traverse the entire array and then use HashMap.It will cost a lot of time and lost of space.So we should sort this array at first.And we can set center pointn.There three pointer are n,n+1,nums.length-1.Because this array is ordered,so if the n is the head of the array,so it means the all elements after n are all >0.So we don't need to traverse all the elements.But this is just a special situation.And how can we avoid duplication?This is a easy question,there three pointercenter n,left n+1,right nums.length-1.If the value of their next position is equal to the current,we move the current position to the next.Solution public List<List<Integer>> threeSum(int[] nums) { ArrayList<List<Integer>> lists = new ArrayList<>(); //the special situation if (nums.length < 3) { return lists; } //sort the array Arrays.sort(nums); //traversal the array for (int i = 0; i < nums.length; i++) { //if the smallest element is larger than 0,so all the elements are larger than 0,just break if (nums[i] > 0) { break; } //repetitive situation,just update the location if (i > 0 && nums[i] == nums[i - 1]) { continue; } //use two pointers,search from both sides int left = i + 1, right = nums.length - 1; while (left < right) { //find the 3sum if (nums[i] + nums[left] + nums[right] == 0) { //use Arrays.aslist make array to list lists.add(Arrays.asList(nums[i], nums[left], nums[right])); //repetitive situation,just update the location while (left < right && nums[left] == nums[left + 1]) { left++; } while (left < right && nums[right] == nums[right - 1]) { right--; } //update location left++; right--; } else if (nums[i] + nums[left] + nums[right] > 0) { //if larger than 0,it means right pointer is too bigger right--; } else { //if smaller than 0,it means left pointer is too smaller left++; } } } return lists; }16. 3Sum ClosestThis question is very similar with question 15. 3Sum.But it does not query to repeat this step,you can use double pointers directly.So i think this question is easier than question 15.Solution public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int result = 0, min = Integer.MAX_VALUE; for (int i = 0; i < nums.length; i++) { //if find the same number,just continue if (i > 0 && nums[i - 1] == nums[i]) { continue; } int left = i + 1, right = nums.length - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; //if find the target,just return if (sum == target) { return sum; } //find the closest if (Math.abs(sum - target) < min) { min = Math.abs(sum - target); result = sum; } //move the double pointers if (sum > target) { right--; } else { left++; } } } return result; }17. Letter Combinations of a Phone NumberThis question is a little difficult,the difficulty lies in how to stitch different letters together.It cannot use enumeration methods,because we don't know how many digits it will enter. So we can't use how many for to use enumeration methods.At this time,we should think of the problem of finding all branches of a binary tree.We didn't know the number of layers of the binary tree at the time.We need to judge the left subtree and the right subtree whether is null.And use recursive methods to return the values found in each layer.So we can use the same method in this problem.First traverse the value of digits,each of its values is a layer.Finally,concatenating the traversed values is one of the answer.And how do we associate phone numbers with letters.We can use HashMap,and use StringBuilder to connect the letters.Solution public List<String> letterCombinations(String digits) { ArrayList<String> list = new ArrayList<>(); //the special situation if (digits.length() == 0) { return list; } //create the HashMap HashMap<Character, String> map = new HashMap<>(); map.put('2', "abc"); map.put('3', "def"); map.put('4', "ghi"); map.put('5', "jkl"); map.put('6', "mno"); map.put('7', "pqrs"); map.put('8', "tuv"); map.put('9', "wxyz"); backTracking(0, list, map, new StringBuffer(), digits); return list; } /** * use recursion to connect the letters */ private void backTracking(int i, ArrayList<String> list, HashMap<Character, String> map, StringBuffer buffer, String digits) { //if it reaches the end,just return the letters you find if (i == digits.length()) { list.add(buffer.toString()); } else { //such as digits.charAt(i) is '2',and search 2 in HashMap String s = map.get(digits.charAt(i)); //traverse the number for (int i1 = 0; i1 < s.length(); i1++) { //add the last letters buffer.append(s.charAt(i1)); //recursion backTracking(i + 1, list, map, buffer, digits); /*it also writes buffer.deleteCharAt(buffer.length()-1),if you don't write,StringBuilder will pollute the buff,StringBuilder passes in the same object, so the last operation must be withdrawn after the recursion is completed, and the last added character needs to be deleted*/ buffer.deleteCharAt(i); } } }18. 4SumThis problem is an upgraded version of 15. 3Sum.The main idea to the original question is the same as question 13.It also use double pointer.But i think if this question change to nSum,are there still double pointers used?Because this question is already very complicated to solve with double pointers.So i want to use recursion to solve this question.There are two situations in recursion.First we still sort the array,and we remove the first element of the array every time.the result we want include the nums[0]the result we want does not include nums[0]So this question becomesfindtarget-nums[0] from nums[1] to nums[nums.length]find target from nums[1] to nums[nums.length]But if the elements behind the first element are the same as the first element.We must skip all the elements in this paragraph.Because recursion takes more time and space.So we must reduce the time spent.nums[0]>target/n is a good thinking.But we do LeetCode question not only to solve the problem,but to learn this kind of thinking,just like recursion.Will make the code we write more code robustness.Solution public List<List<Integer>> fourSum(int[] nums, int target) { //this question requires us 4 return nSum(nums, target, 4); } /** * n is the number of digits we need */ private List<List<Integer>> nSum(int[] nums, int target, int n) { //first sort the array Arrays.sort(nums); //then use recursion return nSum(nums, target, n, 0, new ArrayList<Integer>(), new ArrayList<List<Integer>>()); } /** * startIndex is position to start looking for */ private List<List<Integer>> nSum(int nums[], int target, int n, int startIndex, ArrayList<Integer> preArray, ArrayList<List<Integer>> result) { //if length is 5,start begin 4,we need find 3 numbers,this is impossible,so just return if (nums.length - startIndex < n) { return result; } //if only find one element,we just traversal the array,until we find the element if (n == 1) { for (int i = startIndex; i < nums.length; i++) { if (nums[i] == target) { preArray.add(target); result.add(preArray); break; } } return result; } //special situation if (nums[startIndex] > target / n) { return result; } //filter out the same elements at the beginning int same = 0; for (int i = startIndex + 1; i < nums.length; i++) { if (nums[i] == nums[i - 1]) { //record the number of identical elements same++; } else { break; } } //the situation 2,the first element is not we need to find nSum(nums, target, n, startIndex + same + 1, preArray, result); //the situation 1,the first element is we need to find ArrayList<Integer> copyPre = new ArrayList<>(preArray); copyPre.add(nums[startIndex]); nSum(nums, target - nums[startIndex], n - 1, startIndex + 1, copyPre, result); return result; }19. Remove Nth Node From End of ListThis question is a very interesting question,as we all know how to remove the n node.But how to remove the node from the end of the list.Search from the beginning,but delete from the end.This situation reminds me about Stack FILO .So we can push elements into stack at first,and pop n-1 elements.So we can remove the n element.There is one thing we must be notice,If the n node from the end of the list.The number n is the list's length.So we remove the head,so we can't return the head,we must return the n next node.Solution1 public ListNode removeNthFromEnd(ListNode head, int n) { //create a stack,and push all elements into stack Stack<ListNode> stackNode = new Stack<>(); ListNode temp = head; while (temp != null) { stackNode.push(temp); temp = temp.next; } //pop n-1 elements for (int i = 0; i < n - 1; i++) { stackNode.pop(); } //pop the n element ListNode node = stackNode.pop(); //if the n is the first of the lists,so this stack is empty,just return the node.next //else just remove the n element if (!stackNode.isEmpty()) { ListNode deleteNode = stackNode.peek(); deleteNode.next = deleteNode.next.next; } else { return node.next; } return head; }This question we also can use two pointers.The fast pointer moves n more nodes than slow pointer.When they move together,when the fast pointer reaches the tail node,the slow pointer also reaches the n node.Solution2 public ListNode removeNthFromEnd(ListNode head, int n) { //the slow pointer is one node slower than the fast pointer ListNode pre = new ListNode(0); pre.next = head; ListNode fast = head; ListNode slow = pre; //fast pointer moves n more nodes than slow for (int i = 0; i < n; i++) { fast = fast.next; } //because fast move to tail node,still move to the null node,so move one more step while (fast != null) { fast = fast.next; slow = slow.next; } //if the n node the head of the list,so we can't return the head,we must return the pre next slow.next = slow.next.next; return pre.next; }22. Generate ParenthesesThis question is very similar with Binary Tree traversal.As we all know ( must match ).And the number of ( is the same as the number of ).If the number of ) is bigger than the number of (,it is a wrong match.So we can summarize 2 points.If the n bracket combinations,there are n ( and n )If at this time the number of ( is m.The number of ) at most mSo we can use the same solution in Binary Tree.We start at a root node,this node is empty.We can add ( or ) latter.( is just like the left subtree.) is just like the right subtree.When the number of subtree is less than n,it will continue to depth first traversal.Solution /** * define a ArrayList to store the parentheses */ ArrayList result = new ArrayList<String>(); public List<String> generateParenthesis(int n) { //the default number of left subtree and right subtree are all 0 dfs(n, 0, 0, ""); return result; } /** * Depth first traversal */ private void dfs(int n, int left, int right, String str) { if (left == n && right == n) { //traversed to the bottom of the tree,just return the result result.add(str); } else { if (left < n) { //add the `(` dfs(n, left + 1, right, str + "("); } //the number of `)` at most the number of `(` if (right < n && right < left) { dfs(n, left, right + 1, str + ")"); } } }24. Swap Nodes in PairsThis question is a very interesting question,because it has many solutions.Can develop our thinking to think more.QueueOf course,we can use Queue.Because the characteristic of Queue is first in first out.I make a example.1 2 3 4Queue1:1 3Queue2:2 4First we create two Queues,and alternate each element.And then take out each element alternately.Queue:1 3Queue:42Queue1:3Queue2:42 1Queue1:3Queue2:2 1 4Queue1Queue22 1 4 3This difficulty of this solution is when to put it in Queue1 and when to put it in Queue2.And when to pop out. public ListNode swapPairs(ListNode head) { //the special situation if (head == null || head.next == null) { return head; } //make two Queue LinkedList<ListNode> list1 = new LinkedList<>(); LinkedList<ListNode> list2 = new LinkedList<>(); //we can use boolean,if it is true,add Queue1,if it is false,add Queue2 boolean add = true; while (head != null) { if (add) { list1.add(head); add = false; } else { list2.add(head); add = true; } head = head.next; } //We must remove a node to be the head of the result listnode ListNode res = list2.remove(); ListNode temp = res; //we also can make a boolean to minus each Queue,if it is true,minus Queue1,else minus Queue2 boolean minus = true; while (!list1.isEmpty() || !list2.isEmpty()) { if (!list1.isEmpty() && minus == true) { temp.next = list1.remove(); minus = false; } else { //there are two situations in else,one is list2 is empty,we just need to minus Queue1 at // last,the another one is list1 is not empty if (!list2.isEmpty()) { temp.next = list2.remove(); minus = true; } else if (!list1.isEmpty()) { temp.next = list1.remove(); } } //update temp node temp = temp.next; } //if don't add this,it will happen infinite loop if (temp != null) { temp.next = null; } return res; }recursionWe can also use recursion.Let's analyze this question.We can decompose the problem intoA B CB A CSo this fake code is//swap is like B swap = A.next; //swap.next is like C A.next=recursion(swap.next); swap.next=A; return swap; public ListNode swapPairs(ListNode head) { //the special situation if (head == null || head.next == null) { return head; } ListNode swap = head.next; head.next = swapPairs(swap.next); swap.next = head; return swap; }IterationIn iteration,we can also consider ABC as a group.Iteration is very complicated to tell,but it will be easy to understand if it is shown in a diagram. public ListNode swapPairs(ListNode head) { //the special situation if (head == null || head.next == null) { return head; } //make a result node,to point to head ListNode result = new ListNode(0); result.next = head; ListNode temp = result; //iteration while (temp.next != null && temp.next.next != null) { ListNode list1 = temp.next; ListNode list2 = temp.next.next; temp.next = list2; list1.next = list2.next; list2.next = list1; temp = list1; } //return the head return result.next; }
2. Add Two NumbersThis 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 calculationWhen the last number is reached,it is also necessary to judge whether to carrySolution 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 CharactersThis 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 SubstringThis 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.a the symmetry point is odd numbera a the symmetry point is even numberSo 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 ConversionThis 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 0 and numRows,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 encounterThere 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 futureWhen 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 onlineThere 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 rangeStop when reading a non-number,and return to the number read if it does not out of rangeSolution 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 WaterThis 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 RomanThis 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 = 3So 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(); }