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=2
  • int 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 3
  • 1 3 2
  • 2 1 3
  • 2 3 1
  • 3 1 2
  • 3 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 3
  • 3 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?

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. 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 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);
    }
  }
Last modification:November 8th, 2021 at 05:28 pm