26. Remove Duplicates from Sorted Array

This problem is a two points problem.Because this problem require remover the duplicates in-place.So we can only have the existing array.We can make two points.Compare with these two points,if one is smaller than another one.So update the nums.

solution

public int removeDuplicates(int[] nums) {
    //Because it must have a result,the answer is the head of the nums,such as [1,1,1,1]
    int result = 1;
    //make a faster point,it always larger than head point
    int j = 1;
    for (int i = 0; i < nums.length - 1; i++) {
      //if meet a new number
      if (nums[i] < nums[j]) {
        //update the result,and let it +1
        nums[result] = nums[j];
        result++;
      }
      //whether you find it or not,must update i and j
      j++;
    }
    return result;
  }

27. Remove Element

This problem is the same as problem 26.We also can use two points to solve this problem.

We can get information which is no requirement on the order.So wo can set two point.One point is from the nums head another one is from the nums tail.I listed the example process

  • $3(head)->2->2->3(tail)$
  • $3(head)->2->2(tail)->3$​
  • $2(head)->2(tail)->2->3$
  • $2->2(head,tail)-2->3$

solution

public int removeElement(int[] nums, int val) {
    //make two points
    int head = 0, tail = nums.length;
    while (head < tail) {
      //if find the val,exchange the head
      if (nums[head] == val) {
        nums[head] = nums[tail - 1];
        tail--;
      } else {
        head++;
      }
    }
    return head;
  }

We can also scratch from the start.

  • $3(find)->2->2->3$
  • $2->2(find)->2->3$

solution

public int removeElement(int[] nums, int val) {
    int find = 0;
    for (int num : nums) {
      if (num != val) {
        nums[find] = num;
        find++;
      }
    }
    return find;
  }

28. Implement strStr()

This question is a classic string single-mode matching model.This question we use Knuth-Morris-Pratt algorithm is the best.But KMP algorithm is a little complex,so i will explain the KMP algorithm in a separate chapter.

We can match each letter from the beginning of the haystack. If one of the letter is equal to the needle.Just return the beginning location.

solution

public int strStr(String haystack, String needle) {
    //special case
    if (needle.length() == 0) {
      return 0;
    }
    int L1 = haystack.length();
    int L2 = needle.length();
    //if L1="aaa",L2="aaa",L1-L2 will be 0,so it is a special case
    if (L1 == L2) {
      if (haystack.equals(needle)) {
        return 0;
      } else {
        return -1;
      }
    }
    for (int i = 0; i <= L1 - L2; i++) {
      String str = haystack.substring(i, i + L2);
      if (str.equals(needle)) {
        return i;
      }
    }
    return -1;
  }

35. Search Insert Position

This problem is a simple binary-search problem.It looks simple,but it has some places we should be notice.

  • writewhile(head<tail),when exiting the loop,we don't have to judge return head or return tail
  • distinguish [head tail] has two situations

    • [head mid] and [mid+1 tail],each corresponding to [tail=mid] and [head=mid+1]
    • [head mid-1] and [mid tail],each corresponding to [tail=mid-1] and [head=mid],this situation we need change int mid=head+(tail-head)/2 to int mid=head+(tail-head+1)/2.Otherwise there will be an infinite loop.You can print the value of head and tail to prove

solution1

public int searchInsert(int[] nums, int target) {
    int head = 0, tail = nums.length;
    int mid;
    while (head < tail) {
      mid = (tail - head) / 2 + head;
      if (nums[mid] < target) {
        head = mid + 1;
      } else {
        tail = mid;
      }
    }
    return head;
  }

solution2

public int searchInsert(int[] nums, int target) {
    int head = 0, tail = nums.length;
    int mid = 0;
    while (head < tail) {
      mid = head + (tail - head + 1) / 2;
      if (nums[mid - 1] < target) {
        head = mid;
      } else {
        tail = mid - 1;
      }
    }
    return head;
  }

This problem has a very important place we should be attention

In solution1,we write like this

mid = (tail - head) / 2 + head;
      if (nums[mid] < target) {
        head = mid + 1;
      } else {
        tail = mid;
      }

if we write like this,it looks equal to solution1,but it is fault

mid = (tail - head) / 2 + head;
      if (nums[mid] > target) {
        tail = mid;
      } else {
        head = mid + 1;
      }

We give a example.There are five numbers 1 2 3 4 5,mid=(5-0)/2=2,if the result is 3,so head=mid+1=3 is fault.

This is a same attention in solution2,i think we don't need remember this.If you forget about,just make a example just this.

53. Maximum Subarray

This is a typical dynamic programming problem.We use a sum to save the last result.And if the answer is less than 0.So plus the next number is meaningless.Because negative number plus any number is less than that number.We only need traverse the array once to get the result.

solution

public int maxSubArray(int[] nums) {
    int sum = nums[0], result = 0;
    //traverse the array
    for (int num : nums) {
      if (result > 0) {
        //update the result
        result += num;
      } else {
        //if result<=0,get a new result
        result = num;
      }
      //save the maximum
      sum = Math.max(sum, result);
      //you can use this to Watch the whole process
      //System.out.println("sum :" + sum + " " + "result :" + result);
    }
    //get the max
    return sum;
  }

58. Length of Last Word

This problem have two situations.

  1. "world "like this.The following characters are all spaces.
  2. "luffy is still joyboy",The following characters are all letters.

We should search from behind.Get the letters' tail location and the head location.Subtract the two is the answer.

solution1

public int lengthOfLastWord(String s) {
    //length is the tail,i is the head
    int i = s.length() - 1, length = 0;
    while (i >= 0) {
      //find the tail
      if (s.charAt(i) != ' ') {
        length = i;
        break;
      } else {
        i--;
      }
    }
    //find the head
    while (i >= 0) {
      if (s.charAt(i) == ' ') {
        break;
      } else {
        i--;
      }
    }
    //subtract the two
    return length - i;
  }

solution2

public int lengthOfLastWord(String s) {
    int end = s.length() - 1;
    int start;
    //find the word tail
    while (end >= 0 && s.charAt(end) == ' ') {
      end--;
    }
    //if have no word
    if (end < 0) {
      return 0;
    }
    //begin from the tail
    start = end;
    //find the head
    while (start >= 0 && s.charAt(start) != ' ') {
      start--;
    }
    return end - start;
  }

66. Plus One

This problem is a easy math problem.I give some example.

  • $4->4+1->5$
  • $9->9+1->10$
  • $14->14+1->15$
  • $99->99+1->100$

You can find if a letter is $9$,it will become $0$,and next digit plus one.And if all add one, the first letter will become $1$

So we can solve this problem easily.

solution

public int[] plusOne(int[] digits) {
    for (int i = digits.length - 1; i >= 0; i--) {
      //this letter plus 1
      digits[i]++;
      //judge this letter whether 9 or other number"0-8"
      digits[i] = digits[i] % 10;
      //if this letter is 9,so the next digit plus one,or not just return the new digits
      if (digits[i] != 0) {
        return digits;
      }
    }
    //if all letters are 9,the first letter must 1,"999" "1000"
    digits = new int[digits.length + 1];
    digits[0] = 1;
    return digits;
  }

# 67. Add Binary

This problem is very same as Problem 66.We have two solutions.

  • Use math to count.I give you some example

    • a = "11"="3" b="1" a+b="100"=4
    • a="1010"="10" b="1011"="11" a+b="10101"="21"
    • We can use binary conversion to decimal to count the result.And convert the decimal result to binary
    • But this is not a good solutions.Because it will face the problem of crossing the boundary.

So we can think this problem we can use the same method as Problem 66.

  • "0+0=0"
  • "0+1=1"
  • "1+1=10"

We can use StringBuilder to build a new string.And compare every digit.If this digit dose not exist,it is treated as 0

solution

public String addBinary(String a, String b) {
    StringBuilder sb = new StringBuilder();
    //get a and b length
    int i = a.length() - 1;
    int j = b.length() - 1;
    //judge whether add 1 to the next digit
    int result = 0;
    //from tail to head
    while (i >= 0 || j >= 0) {
      //get the two digit sum
      int sum = result;
      //if a is end
      if (i >= 0) {
        //'1'-'0'=1,'0'-'0'=0
        sum += a.charAt(i) - '0';
      }
      //if i is end
      if (j >= 0) {
        sum += b.charAt(j) - '0';
      }
      //judge sum whether is 1 or 2 or 3
      sb.append(sum % 2);
      //if sum is 0 or 1,just continue,if i is 3,should +1
      result = sum / 2;
      i--;
      j--;
    }
    //if new add 1
    if (result != 0) {
      sb.append(result);
    }
    //return the new string
    return sb.reverse().toString();
  }

# 69. Sqrt(x)

This problem we can use Math method,but i think if we used essentially unchanged.So we can use Binary search one more time

solution

public int mySqrt(int x) {
    int head = 0, tail = x, result = 0;
    while (head <= tail) {
      int mid = head + (tail - head) / 2;
      //such as 3*3=9,2*2<9
      if ((long) mid * mid <= x) {
        //to record last mid
        result = mid;
        head = mid + 1;
      } else {
        tail = mid - 1;
      }
    }
    return result;
  }
Last modification:August 14th, 2021 at 06:18 pm