# **LeetCode**

#### Solve progres:
- 1.two_numAdd:
```java
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0]+ nums[1] = 2 + 7 = 9,
return [0, 1].
```
## answer:
- 1. Brute:
```java
for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
```
#### <span style="color:red">☆★Time complexity : O(n^2)、Space complexity : O(1)。☆★</span>

- 2. Advanced:
```java
Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement)};
        }
    }
```
#### <span style="color:red">☆★Time complexity : O(n)、Space complexity : O(n) because the map。☆★</span>

- 2.addTwoNumbers:
## answer:
```java
 ListNode h = new ListNode(0);
        ListNode p3=h;
        int r=0;
        while(l1 !=null || l2!=null){
            if(l1 !=null){
                r+=l1.val;
                l1=l1.next;
            }
            if(l2 !=null){
                r+=l2.val;
                l2=l2.next;
            }
            p3.next= new ListNode(r%10);
            r/=10;
            p3=p3.next;
        }
        if(r==1)
        p3.next=new ListNode(1);

        return h.next;
```
declarate two ListNode(p3,h),p3 use to set value ,and h is final result. The Last r==1 is used to deal with carry.
#### <span style="color:red">☆★Time complexity : O(max(m,n))、Space complexity : O(max(m,n))。☆★</span>

- 3. Longest Substring Without Repeating Characters:
```java
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "pwwkew", the answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
```
## answer:
- 1:
```java
String temp="";
String result="";
for(int i=0;i<s.length();i++) {
 String	curr = String.valueOf(s.charAt(i));
    if(!temp.contains(curr)) {
		temp+=curr;
    }else {
	    temp = temp.substring(temp.indexOf(curr)+1, temp.length())+curr;
    }
    if(temp.length() > result.length()) {
	result = temp;
    }
}
return result.length();
```
Hint: `temp.substring(temp.indexOf(curr)+1, temp.length())+curr` . the substring method splits after first duplicated character to end of the temp,length()-1 and add new character. EX: ori: abca -> a|bca.
#### <span style="color:red">☆★Time complexity : O(n)、Space complexity : O(min(m,n))。☆★</span>

- 2:
```java
int maxLenth=0;
HashSet<Character> set = new HashSet<>();
int i=0,j=0;

while(j<s.length()) {
    if(!set.contains(s.charAt(j))) {
	    set.add(s.charAt(j));
	    j++;
            maxLenth=Math.max(maxLenth, j-i);
    }else {
    set.remove(s.charAt(i));
    i++;
    }
}
return maxLenth;
```
Hint: `set.remove(s.charAt(i))` . It remove  duplicated character in the set until not  duplicated character. Thus add new character
#### <span style="color:red">☆★Time complexity:O(n)、Space complexity:O(min(m,n))。☆★</span>


- 5. Longest Palindromic Substring:
###### Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
```java
Input: "BANANA"
Output: "ANANA"
```
## answer:
- 1. Dynamic Programming:
```java
 int len = s.length();
 boolean[][] isP = new boolean[len][len];
 int left=0,right=0;
 for(int j=1;j<len;j++) {
     for(int i=0;i<j;i++) {
	 boolean innerP = isP[i+1][j-1]||j-i<=2;
	     if(s.charAt(i)==s.charAt(j)&&innerP) {
	         isP[i][j]=true;
		    if(j-i > right-left) {
			left=i;
			right=j;
		    }
	     }
	}
 }
 return s.substring(left, right+1);
```
Hint: `boolean innerP = isP[i+1][j-1]||j-i<=2;` =>First: `j-i<=2;` is true,it means compare element and next element, EX:AN,NA,AN,NA,ANA,NAN. Second:`isP[i+1][j-1]`, it will saved the palindromic substring between [i][j]. For instance: [0][5] it need to find the result of String [1]~[4] is palindromic substring or not.
#### <span style="color:red">☆★Time complexity : O(n^2)、Space complexity : O(n^2)。☆★</span>
- 7. Reverse Integer:
###### Given a 32-bit signed integer, reverse digits of an integer. EX:
| Input | Output |
| ------| ------ |
| 123   | 321    |
| -123  | -321   |
| 120   | 21     |


## answer:
```java
public static int reverse(int x) {
boolean sign=false;
    if(x<0) {
	sign=true;
	x=Math.abs(x);
	}
	int result=0;
	char[] ori=String.valueOf(x).toCharArray();
	String str="";
	if(x>0 && !sign ) {
	    str+=common(ori.length,ori);
	}else {
	    str+="-";
	    str+=common(ori.length,ori);
	}
	try{
	    result=Integer.valueOf(str);
		return result;
	}catch(NumberFormatException e){
		return 0;
	}
}
public static String common(int s_len,char[] ori) {
    String str="";
	for(int i=s_len-1;i>=0;i--) {
	    str+=ori[i];
	}
	return str;
}
```
#### <span style="color:red">☆★Time complexity : O(1)、Space complexity : O(n)。☆★</span>

- 11. Container With Most Water:
###### Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). EX: [9,8,6,5,3]
| Input | Output |
| ------| ------ |
|9      | (9,0),(9,9)|
|8      | (8,0),(8,8)|
|6      | (6,0),(6,6)|
|5      | (5,0),(5,5)|
|3      | (3,0),(3,3)|


## answer:
```java
public static int maxArea(int[] height) {
    int maximum=0,tmp=0;
    int i=0,j=height.length-1;
while(i<j) {
        tmp = Math.min(height[i], height[j])*Math.abs(i-j);
	    if(tmp > maximum) {
			maximum = tmp;
    	}
    	if(height[i] < height[j]) {
		i++;
	}else {
		j--;
	}
}
	return maximum;
}
```
#### <span style="color:red">☆★Time complexity : O(n)、Space complexity : O(1) only Constant space。☆★</span>

- 11. Roman to Integer:
###### Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.
| Symbol| Value  |
| ------| ------ |
|I      | 1      |
|V      | 5      |
|X      | 10     |
|L      | 50     |
|C      | 100    |
|D      | 500    |
|M      | 1000   |

| Input | Output |
| ------| ------ |
|III    | 3      |
|IV     | 4      |
|IX     | 9      |
|MCMXCIV|1994    |



## answer:
- 1.method one:
```java
public static int romanToInt(String s) {
int result=0;
List<Integer> result_list = new ArrayList<Integer>();
	for(int i=0;i<s.length();i++) {
		if(i==0) {
    		result_list.add(rToi(s.charAt(i)));
		}else {
	    	if(rToi(s.charAt(i-1)) >= rToi(s.charAt(i))){
    		result_list.add(rToi(s.charAt(i)));
		}
		else {
		result_list.set(i-1, result_list.get(i-1)*-1);
		result_list.add(rToi(s.charAt(i)));
	    	}
		}
	}
	for(int i=0;i<result_list.size();i++) {
	    result+=result_list.get(i);
	}
return result;
}
```
- 2.method two:
```java
public static int romanToInt(String s) {
int result=0;
int temp=0;
    for(int i=0;i<s.length();i++) {
	int data = rToi(s.charAt(i));
	if(temp >= data)
	    result+=data;
	else
           result=data+(result+temp*-2);
	temp=data;
	}
return result;
}
```

#### <span style="color:red">☆★Time complexity : O(n)、Space complexity : O(1) only Constant space。☆★</span>