29. Divide Two Integers
This 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=2
So this is division.Division is an optimization of subtraction.We can simplify this question.
3*n=7 or 3*n-1<7 3*n>7
The 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 Permutation
This 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 1
So 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 2
We 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 Array
This 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 Array
This 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 .... right
We 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 Sudoku
This 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-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without 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 Say
This 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 Sum
This 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 II
This 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);
}
}