Leetcode Review(3)

Posted on | In |

Leetcode 3 Longest Substring Without Repeating Characters

Description:

Givena string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the lengthof 1.

Given “pwwkew”, the answer is “wke”, with the lengthof 3. Note that the answer must be a substring, “pwke” is a subsequenceand not a substring.

Method:

Remember that in “String” methods, there is a method named “indexOf(char c/String s) which can help to get the first occurrence index of the char or string.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        String result = "";
        int length = s.length();
        if(length<=1) return length;
        int max=0;
        
        for(int i=0;i<length;i++){
            int index = result.indexOf(s.charAt(i));
            if(index==-1){
                result = result+s.charAt(i);
                max = Math.max(max,result.length());
            }
            else
                result = result.substring(index+1)+s.charAt(i);
            
        }
        return max;       
    }
}

Leetcode 189 Rotate Array

Description:

Rotatean array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Methods:

This is awkward. I spent plenty of time doing this question.

There are two solutions. First one is easy to understanding while the second is in-place rotate.

  1. Use an auxiliary Array.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
     
    class Solution {
        public void rotate(int[] nums, int k) {
            int[] rev = new int[nums.length];
            
            for(int i=0;i<nums.length;i++){
                rev[(i+k)%nums.length]=nums[i];
            }
            
            for(int i=0;i<nums.length;i++){
                nums[i]=rev[i];
            }    
        }
    }

    ​

  2. Use reverse three times.

    rever(0,length-1);

    reverse(0,k-1);

    reverse(k,length-1);

    And I want to emphasize that how to reverse a array

    like A[start:end]

    1
    2
    3
    4
    5
    while(start<end){
      exchange A[start] with A[end];
      start++;
      end--;
    }

    So easy!! Why I spent so long to debug on it!

    And I also want to mention how to exchange two number without extra space.

    x=x-y

    y=x+y

    x=y-x

    The following is the whole code.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public void rotate(int[] nums, int k) {
           
            int length = nums.length;
            k%=length;
            if(length<=1) return;
            reverse(nums,0,length-1);
            reverse(nums,0,k-1);
            reverse(nums,k,length-1);
            
        }
        
        private void reverse(int[] nums,int start, int end){
            while(start<end){
                int tmp = nums[start];
                nums[start]=nums[end];
                nums[end]=tmp;
                start++;
                end--;
            }
        }
    }

    ​

Leetcode 5 Longest Palindromic Substring

Description:

Given a string s,find the longest palindromic substring in s. You may assumethat the maximum length of s is 1000.

Methods:

This is a very classic dynamic programming problem.

We can use 2d boolean array p, in which pij is used to check s.substring(i,j+1) is palindromic or not.

So,

Pij =( j-i<3 || pi+1j-1) &&s.charAt(i)==s.charAt(j);

In order to not calculate repeatedly. We need to cal p from the bottom to top.

Finally to pick the longest substring.

And we had better to write j-i<3 before pi+1j-1 otherwise it would cause outOfBoundary error.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        if(length<=1) return s;
        
        int maxl=0;
        String result="";
        
        boolean[][] p = new boolean[length][length];
        
        for(int i=0;i<length;i++)
            p[i][i]=true;
        
        for(int i=length-2;i>=0;i--){
            for(int j=i;j<length;j++){
                p[i][j] = s.charAt(i)==s.charAt(j) && ((j-i<=2) ||p[i+1][j-1] );
                if(p[i][j]==true && j-i+1>maxl){
                    result=s.substring(i,j+1);
                    maxl=j-i+1;
                }
                    
            }
        }
        return result;       
    }
}