# 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;
//if find the val,exchange the head
tail--;
} else {
}
}
}

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;
if (nums[mid] < target) {
} else {
tail = mid;
}
}
}

solution2

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

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) {
} 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 {
}

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--;
}
}
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;
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;
}

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;
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 (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;
}