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.
- write
while(head<tail),when exiting the loop,we don't have to judge returnheador returntail 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 changeint mid=head+(tail-head)/2toint mid=head+(tail-head+1)/2.Otherwise there will be an infinite loop.You can print the value ofheadandtailto 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.
- "world "like this.The following characters are all spaces.
- "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
StringBuilderto build a new string.And compare every digit.If this digit dose not exist,it is treated as0solution
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; }
