leetcode 刷题日记 1

				time:2021/7/10

question one(leetcode:3):

		给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度

最终用时:1小时

 public int lengthOfLongestSubstring(String s) {
        
        char[] num=s.toCharArray();
        if(num.length==0)
        {
            return 0;
        }
        if(num.length==1)
        {
            return 1;
        }
        if(s.equals(" "))
        {
            return 1;
        }
        int first=0;
        int end=0;
        int result=0;
        for(int i=1;i<num.length;i++)
        {
            end=i;
              for(int j=first;j<i;j++)
            {
                if(num[i]==num[j])
                {
                    first=j+1;
                    break;
                }
            }
            if(end-first+1>result)
            {
                result=end-first+1;
            }
           
           

        }
        return result;
    }

总结

toCharArray方法的使用.
如果字符串的长度为1,则可以输出结果
如果字符串长度为0,也可以输出结果
长度>2时如以上的代码所示
思路:所以以上方法是end从下标1到num.length遍历,然后内循环从first到end进行再一次的遍历,所以如果end之前的子串出现与end重复的字符,就说明first之前的子串已经为最大值,并且新的first和end之间没有重复的数值.详见代码.

执行用时：2 ms 在所有 Java 提交中击败了99.98%的用户
内存消耗：38.2 MB, 在所有 Java 提交中击败了91.96%的用户

翻看大家题解找出另一种思路:
经典的滑动窗口方法,思路差不多,都是运用枚举的方法,只是上述的方法我是end开始枚举,而窗口滑动是从first开始枚举

question2(leetcode:5):

  	给你一个字符串 s，找到 s 中最长的回文子串

最终用时:1小时半

class Solution {

    public String longestPalindrome(String s) {
        char[] num=s.toCharArray();
        int len=0;
        int[] result=new int[2];
        System.out.println(num.length);
        for(int i=0;i<num.length;i++)
        {
            System.out.println("begin");
            System.out.println("i:"+i);
            int[] beginend={i,i};
            beginend=ifequal(num,beginend);
            int a=beginend[1]-beginend[0];
            if(a>len)
            {
                len=a;
                result[0]=beginend[0];
                result[1]=beginend[1];
            }

            if(i!=num.length-1)
            {

                int[] beginend2={i,i+1};
                beginend2=ifequal(num,beginend2);
                a=beginend2[1]-beginend2[0];
                System.out.println("begin2:"+a);
                if(a>=len){
                    len=a;
                    result[0]=beginend2[0];
                    result[1]=beginend2[1];

                }
            }

        }
        return s.substring(result[0]+1,result[1]);
    }



    public int[] ifequal(char[] num,int[] beginend)
    {
        if(!(beginend[0]<0||beginend[1]>num.length-1)&&num[beginend[0]]==num[beginend[1]])
        {
            beginend[0]-=1;beginend[1]+=1;
            return ifequal(num,beginend);
        }
        return beginend;
    }

}

总结:

最大回文数子串,则有两种情况,第一为奇数,第二为偶数.
构造方法ifequal,通过此方法beginend是一个两元素的数组,两个元素对应目标数组num的两个下标,当然还存在-1和num.length的下标,所以处理结果的时候要小心数组越界,总之,两个下标包起来的序列,则为所求序列.
ifequal函数运用了递归的方法
有个bug,我们仅处理了beginend[0]为-1的情况,当beginend[1]为num.length-1的时候我们没有处理.但substring似乎支持这种方法.

执行用时：527 ms, 在所有 Java 提交中击败了8.40%的用户
内存消耗：38.9 MB, 在所有 Java 提交中击败了56.69%的用户

改进:
这个方法循环了一次,并且每次调用了递归函数,时间复杂度为O(n),空间复杂度较高,但执行时间却太长.
官方列举了动态规划方法和中心扩展算法.

官方方法展示
思路:动态规划,