1. Two Sum
This problem we usually think to iterate over the array,this solution can solve this problem.We can use for twice,the solution time is $O(n^2)$
solution1
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int i1 = i + 1; i1 < nums.length; i1++) {
if (nums[i] + nums[i1] == target) {
result[0] = i;
result[1] = i1;
break;
}
}
}
return result;
}but this problem has a follow-up which is come up with an algorithm that is less than $O(n^2)$time complexity.Let's think about,if we search the second result one more time,the time is power of the first time.So we must marked in the first time.We can use HashMap,it can help us to marked number when we searching,so this time is$O(n)$
solution2
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
//the second number must not not equal to the first number,and add up to target
if (map.containsKey(target - nums[i]) && i != map.get(target - nums[i])) {
result[0] = i;
result[1] = map.get(target - nums[i]);
break;
}
map.put(nums[i], i);
}
return result;
}7. Reverse Integer
This problem is a bit operation.I think these problem looks very simple,but they have a same question Overflow and out-of-bounds.
As we all know the range of int is $-2147483648(-2^31)-->2147483647(2^31-1) $.But this problem is reverse number,For example there is a number $1147483649$,when it was reverse,it became $9463847411$,so it is overflow.
Positive number
The last digit must be less than $7$
negative number
The last digit must be greater than $-8$
Modulo operation
We use modulo operation can count the result
solution
public int reverse(int x) {
int result = 0;
//modulo operation
while (x != 0) {
int temp = x % 10;
//The last digit must be less than 7
if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && temp > 7)) {
return 0;
}
//The last digit must be greater than -8
if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && temp < -8)) {
return 0;
}
result = result * 10 + temp;
x /= 10;
}
return result;
}9. Palindrome Number
This's problem is same as Problem 7,it just only changed one place.If the number is a negative number,it will return false.So we just judge it at first.
solution
if (x < 0) {
return false;
}
int result = 0, x1 = x;
while (x != 0) {
int temp = x % 10;
if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && temp > 7)) {
return false;
}
result = result * 10 + temp;
x /= 10;
}
if (result == x1) {
return true;
} else {
return false;
}13. Roman to Integer
We must find a rule in the Roman number.We can see them one by one.There are made up of individual Roman number.
For example:
- $3=III=I+I+I=1+1+1$
- $4=IV=V-I=5-1=4$
- $9=IX=X-I=10-1=9$
- $58=LVIII=L+V+I+I+I=50+5+1+1+1=58$
We can find a rule:
The previous number is less than the next number is equal to the less number minus the previous number
- $IV=5-1=4$
The previous number is greater than or equal to the next number is equal to the less number plus the previous number
- $LVIII=50+5+1+1+1=58$
Because there is no number after the last number.So the last number must be plused at last.
solution
public int romanToInt(String s) {
int result = 0;
//count the first number to compare with the next number
int temp = getValue(s.charAt(0));
for (int i = 1; i < s.length(); i++) {
int now = getValue(s.charAt(i));
if (temp < now) {
result -= temp;
} else {
result += temp;
}
temp = now;
}
//plus the last number at last
result += temp;
return result;
}
/**
* make a switch method to judge the Roman number
*/
private int getValue(char c) {
switch (c) {
case 'I':
return 1;
case 'V':
return 5;
case 'X':
return 10;
case 'L':
return 50;
case 'C':
return 100;
case 'D':
return 500;
case 'M':
return 1000;
default:
return 0;
}
}14. Longest Common Prefix
Vertical scan
We can set the first str as the template str.Scan each char of the first str and compare with the after str one by one.While finish scan,it shows the whole first str is the common prefix
public String longestCommonPrefix(String[] strs) {
//Special case
if (strs.length == 0) {
return "";
}
//the Common Prefix can't longer than the shortest string
int StrsLength = strs.length;
//to count the compare number
int firstLength = strs[0].length();
for (int i = 0; i < firstLength; i++) {
char compare = strs[0].charAt(i);
for (int j = 1; j < StrsLength; j++) {
//compare with each one of them
if (i == strs[j].length() || compare != strs[j].charAt(i)) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}Sort the strs
We can use the API Arrays to sort this strs.
- Before sort:"flower","fsdsda","fl"
- After sort:"fl","flower","fsdsda"
We can just compare the first one with the last one.Most of this time is spent on sorting
public String longestCommonPrefix(String[] strs) {
//First strs:"flower","fsdsda","fl"
Arrays.sort(strs);
//Now strs:"fl","flower","fsdsda"
char[] array1 = strs[0].toCharArray();
char[] array2 = strs[strs.length - 1].toCharArray();
int i = 0;
while (i < array1.length && i < array2.length) {
if (array1[i] != array2[i]) {
break;
}
i++;
}
return strs[0].substring(0, i);
}20. Valid Parentheses
Let's analyze this problem.If the parenthese is a left bracket,we push into the Stack else we pop the Stack.Because the feature of the stack is first-in-last-out.But this problem has some place to be attention.
- We can't use
==operator to test the equality of strings,it will create bad Bugs in the program - Emptystackexception it will be appear.If the stack is empty but we still pop the stack,it will meet this Bug.
If you want to learn more the principle of the stack,you can read my data structure notes iamyqhp.com
solution
public boolean isValid(String s) {
if (s.length() % 2 == 1) {
return false;
}
//create a stack to storage parentheses
Stack<String> chars = new Stack<>();
for (int i = 0; i < s.length(); i++) {
//convert char to string
String currChar = String.valueOf(s.charAt(i));
/* judge the current character is a left parentheses.if is a left parentheses,push it onto
the stack*/
//to be attention,never be used "==",In order to avoid bad bugs in the program. On the surface, this kind of bug looks like a random intermittent error
if ("(".equals(currChar) || "{".equals(currChar) || "[".equals(currChar)) {
chars.push(currChar);
} else if (")".equals(currChar)) {
//if Stcak is empty,return false
if (chars.isEmpty()) {
return false;
}
String StringPop = chars.pop();
if (StringPop == null || !("(".equals(StringPop))) {
return false;
}
} else if ("}".equals(currChar)) {
if (chars.isEmpty()) {
return false;
}
String StringPop = chars.pop();
if (StringPop == null || !("{".equals(StringPop))) {
return false;
}
} else if ("]".equals(currChar)) {
if (chars.isEmpty()) {
return false;
}
String StringPop = chars.pop();
if (StringPop == null || !("[".equals(StringPop))) {
return false;
}
}
}
//if the chars still have,it means still have left bracket
if (chars.isEmpty()) {
return true;
} else {
return false;
}
}21. Merge Two Sorted Lists
This problem has two solutions
recursion
We can compare two number,if A is larger than B.So we can compare A.next with B get a answer C,and let A.next point to the answer C
Time complexity:$O(n+m)$
Space complexity:$O(n+m)$
solution1
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l2.next, l1);
return l2;
}
}Iteration
We can make a new ListNode.Head node's next is the question answer.Iterate from start to finish these two List.When they end let the point to the remaining numbers
solution2
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//make a New ListNode
ListNode preHead = new ListNode();
//let the head still the head,make a pre to be a mark to find the next
ListNode pre = preHead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
pre.next = l1;
l1 = l1.next;
} else {
pre.next = l2;
l2 = l2.next;
}
//update the pre
pre = pre.next;
}
//the remaining ListNode must larger than another one,so just point to it
pre.next = l1 == null ? l2 : l1;
//after the head is the answer
return preHead.next;
}Time complexity:$O(n+m)$
Space complexity:$O(1)$
