leetcode3-6

LeetCode 3

Ques: Find the length of longest substring without repeating characters.

思路：用table记录出现char字符的次数，256个ASCII字符初始化为-1.如果遇到重复，则记录在table里面，

我的代码:

int lengthOfLongestSubstring(string s) {
        int tables[256];
        fill(tables,tables+256,-1);
        int result=0,lastRepeatedPos=-1;
        for(int i=0;i<s.size();i++)
        {
            //当找到重复元素且lastRepeatedPos小于找到重复元素的下表时，更新lastRepeatedPos
            if(tables[s[i]]!=-1&&lastRepeatedPos<tables[s[i]])
                lastRepeatedPos=tables[s[i]];
                
            //更新最大值
            result=max(result,i-lastRepeatedPos);
            //元素插入表中
            tables[s[i]]=i;
        }
        return result;
    }

官方解题：
LeetCode 3 Solution

AP 1

暴力破解，但超时了,TC = O(N^3),对于字符串中的每个子串都去扫，是否子串为独立的。

// JAVA VERSION
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j <= n; ++j)
            	//是否存在唯一的子串，记录最长值
                if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
        return ans;
    }

    public boolean allUnique(String s, int start, int end) {
        Set<Character> set = new HashSet<>();
        //将串S从头到尾的放入set匹配一次是否重复
        for (int i = start; i < end; ++i) {
            Character ch = s.charAt(start);
            if (set.contains(ch)) return false;
            set.add(ch);
        }
        return true;
    }

AP 2

基于上述，我们重复扫了很多子串，假设固定开始位置一个个扫的话，可以减少重复扫串的运算。这样可以使TC = O(N^2),LEFT-CLOSED AND RIGHT OPEN

// SLIDING WINDOW 
// JAVA VERSION
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        //固定i，先把j搜完，再加i
        while (i < n && j < n) {
            // try to extend the range [i, j]
            if (!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            }
            else {
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }

AP 3

SLDING WINDOW OPTIMIZED, TC=N = O(N)，SC=m=O(1). m为charset大小

public int lengthOfLongestSubstring(String s) {
       int n = s.length(), ans = 0;
       Map<Character, Integer> map = new HashMap<>(); // current index of character
       // try to extend the range [i, j]
       for (int j = 0, i = 0; j < n; ++j) {
           if (map.containsKey(s.charAt(j))) {
               i = Math.max(map.get(s.charAt(j)), i);
           }
           ans = Math.max(ans, j - i + 1);
           map.put(s.charAt(j), j + 1);
       }
       return ans;
   }

LEETCODE 4

QUES: 找两个有序数组中的中位数
解法：1.暴力地将两个数组合并然后排序，直接得到中位数
2.求得数组大小，用堆排的合并方法，找到中位数。复杂度O(log(m+n))

// My Code
//合并两个数组排序，再根据大小分为奇偶情况输出中位数
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int l1 = nums1.size();
        int l2 = nums2.size();
        vector<int> res;
        for(int i=0;i<l1;i++)
            res.push_back(nums1[i]);
        for(int i=0;i<l2;i++)
            res.push_back(nums2[i]);
        sort(res.begin(),res.end());
        if(res.size()%2==0)
        {
            return (double)(res[(l1+l2-1)>>1]+res[(l1+l2 >>1)])/2.0;
        }
        else
        {
            return (double)(res[(l1+l2)>>1]);
        }
    }

LEETCODE 5

问题：给一个串S,找出其中最长的回文子串

官方使用DP的方法以及EXPAND AROUNG CENTER，其中我的代码就是EXPAND AROUND CENTER。还有一个Manacher’s Algorithm,它通过在字母间加#和以$作为起始符，使得串不再分为奇偶的情况，有效地统一起来，核心思想还是基于中央字母的展开策略。
官方解法

我的解法：分为奇偶情况判断，遍历串，寻找以该字符为中心，两边的回文串最大长度，把最长的情况的信息保留，然后返回。TC=O(N^2)

string longestPalindrome(string s) {
        int len = s.length();
        int i,j;
        int subTempLength=0;
        int subMax=0,subMaxIndex=0;
        for(i=0 ; i< len;i++)
        {
            //Odd
            for(j=0;(i-j)>=0&&(i+j)<len;j++)
            {
                if(s[i-j]!=s[i+j])
                    break;
                subTempLength = j*2+1;
            }
            if(subTempLength > subMax)
            {
                subMax = subTempLength;
                subMaxIndex = i;
            }
            //Even
            for(j=0;(i-j)>=0&&(i+j+1)<len;j++)
            {
                if(s[i-j]!=s[i+j+1])
                    break;
                subTempLength = j*2 +2;
            }
            if(subTempLength > subMax)
            {
                subMax = subTempLength;
                subMaxIndex = i;
            }
            
            
        }
        int startIndex ;
        if(subMax % 2 ==0)
            startIndex= subMaxIndex - subMax/2 +1;
        else
            startIndex = subMaxIndex - subMax/2;
        string result(s,startIndex,subMax);
        return result;
    }

LEETCODE 6

问题：ZigZag Conversion
一开始没看懂，将串转化成蛇形，然后输出，有点点加密的味道
思路：关键理解到蛇形转化的过渡的字母是怎么在数组表示即可

//My Code
string convert(string s, int nRows) {
        if(s.length()==0||nRows <=0)
            return "";
        if(nRows ==1)
            return s;
        string res;
        //蛇形过渡的位置和行的关系
        int size = 2 * nRows - 2;
        //逐行输出蛇形字符
        for( int i=0;i<nRows;i++)
        {
        	//根据原长转换
            for(int j=i;j<s.length();j+=size)
            {	//输出竖直的字符
                res+=s[j];
                //输出斜形的字符
                if(i!=0&&i!=nRows-1&& j+size-2*i<s.length())
                    res+=s[j+size-2*i];
            }
        }
        return res;
    }