常见算法的实现

问题描述：
给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。
例如：输入：[2,3,4,5] 输出：4 输入：[2,2,3,4,3] 输出：3

public int maxLength (int[] arr) {
        // write code here
        Map<Integer,Integer> map = new LinkedHashMap<>();
        if(arr==null || arr.length==0) return 0;
        if(arr.length==1)return 1;
        int left = 0,right = 0,max=0;
        for(int tmp = 0;right<arr.length;right++){
            int cur = arr[right];
            if(map.containsKey(cur) && map.get(cur) >= left){
                tmp = right-left;
                left = map.get(cur)+1;
            }
            if(max==0 && tmp == 0 && (right+1)== arr.length){
                // 解决数组从第一个到最后一个都是不一样的数据长度问题
                max = right-left+1;
            }
            map.put(cur,right);
            max = tmp>max?tmp:max;
        }
        return max;
 }

题目描述:
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba

import java.util.*;
public class Solution {
    ArrayList<String> result = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        if(str == null || str.length()==0) return result;
       char[] ch = str.toCharArray();
        Arrays.sort(ch);
        int[] flag = new int[ch.length];
        StringBuilder newStr = new StringBuilder();
        getStr(ch,newStr,flag);
        return result;
    }
    
    public void getStr(char[] ch,StringBuilder newStr,int[] flag){
        if(newStr.length()==ch.length){
            result.add(newStr.toString());
            return;
        }
        for(int i = 0;i<ch.length;i++){
            if(flag[i]==1) continue;
            if(i != 0 && ch[i] == ch[i-1] && flag[i-1] != 1) continue;
            newStr.append(ch[i]);
            flag[i] = 1;
            getStr(ch,newStr,flag);
            newStr.deleteCharAt(newStr.length()-1);
            flag[i]  = 0;
        }
        return ;
    }
}

题目描述
给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）例如：给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> result  = new ArrayList<>();
        if(root!=null){
            Queue<TreeNode> que = new LinkedList<>();
            que.offer(root);
            while(!que.isEmpty()){
                ArrayList<Integer> list = new ArrayList<>();
                Queue<TreeNode> que2 = new LinkedList<>();
                while(!que.isEmpty()){
                    TreeNode tmp = que.poll();
                    list.add(tmp.val);
                    if(tmp.left!=null){
                        que2.offer(tmp.left);
                    }      
                    if(tmp.right!=null){
                         que2.offer(tmp.right);
                    }
                } 
                result.add(list);   
                que = que2;
            }
        }
        return result;
    }
    
   
}

题目描述一个重复字符串是由两个相同的字符串首尾拼接而成，例如abcabc便是长度为6的一个重复字符串，而abcba则不存在重复字符串。给定一个字符串，请编写一个函数，返回其最长的重复字符子串。若不存在任何重复字符子串，则返回0。

public int solve (String a) {
        // write code here
       int mid = a.length()/2;
        for(;mid>0;mid--){
            loop:for(int i = 0;i+mid*2<=a.length();i++){
                for(int j = i;j<i+mid;j++){
                    if(a.charAt(j)!=a.charAt(j+mid)){
                        continue loop;
                    }
                }
                return mid*2;
                
            }
        }
        return 0;
    
    }