LeetCode Online Judge-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, and there exists one unique longest palindromic substring.

//Java Program: Longest Palindromic Substring
public class Solution {
    public String longestPalindrome(String s) {
        
        //In this program, there is no empty string acturally.
        if (s.length()==0) {
return null;
}

String result = s.substring(0, 1);

//Axis of symmetry: i/2.0
for(int i=1,j;i<2*s.length()-2&&(s.length()-1-i/2)*2+1>result.length();++i) {
for(j=0;(i-1)/2-j>=0&&i/2+1+j<s.length();++j) {
if (s.charAt((i-1)/2-j)!=s.charAt(i/2+1+j)) {
break;
}
}
String temp = s.substring((i-1)/2-j+1, i/2+1+j);
if (temp.length()>result.length()) {
result = temp;
}
}

return result;

    }

}

LeetCode Online Judge-4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

//Java Program: Median of Two Sorted Arrays

public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

if (nums1.length == 0) {

switch(nums2.length % 2) {

case 0: 

return (nums2[nums2.length / 2 - 1] + nums2[nums2.length / 2]) / 2.0;

case 1:

return nums2[nums2.length / 2];

}

}

if (nums2.length == 0) {

switch(nums1.length % 2) {

case 0: 

return (nums1[nums1.length / 2 - 1] + nums1[nums1.length / 2]) / 2.0;

case 1:

return nums1[nums1.length / 2];

}

}

int[] array = new int[2];

int i = 0, j = 0;

while (i + j <= (nums1.length + nums2.length + 1) / 2) {

int next;

if (i < nums1.length && j < nums2.length) {

next = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++];

} else if (i == nums1.length) {

next = nums2[j++];

} else {

next = nums1[i++];

}

            if (i + j >= (nums1.length + nums2.length + 1) / 2) {

   array[i + j - (nums1.length + nums2.length + 1) / 2] = next;

            }

}

if ((nums1.length + nums2.length) % 2 == 0) {

return (array[0] + array[1]) / 2.0;

} else {

return array[0];

}

    }

    

}

Though this program is accepted, I think it's not very good.

Firstly, it can't deal with two empty arrays nums1 and nums2.

Secondly, the logic of this program is hard to understand, especially the loop condition. Acturally, I just want to make the element(s) of array to participate in final compution. If you, what the loop condition will be? After thinking, you may understand my program better. And next is to find next minimum number. Note that the second if sentence in the while loop is behind i++ or j++, so you need to be careful with the condition.

In fact, I have optimized this program a lot during writing this post, which indicates the importance of summary. If you have better solution and are glad to share, just post your comment and laugh at me.

LeetCode Online Judge-3. Longest Substring Without Repeating Characters

Given a 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 length of 1.

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.

//Java Program: Longest Substring Without Repeating Characters

public class Solution {

    public int lengthOfLongestSubstring(String s) {

        

        int longestLength = 0;

ArrayList<Character> list = new ArrayList<Character>();

for(int i=0;i<s.length();++i) {

if (list.contains(s.charAt(i))) {

while(list.get(0)!=s.charAt(i)) {

list.remove(0);

}

list.remove(0);

}

list.add(s.charAt(i));

if (list.size() > longestLength) {

   longestLength = list.size();

}

}

return longestLength;

    }

}