博客

leetCode练习总目录

一、最长公共前缀

  /**
     *按从头到尾比较字符前缀
     * 1、取出第一字符串和第二个字符串，遍历找出两者公共前缀；
     * 2、利用上步返回的前缀与下一个字符串比较
     * 3、重复上步骤，直至最后一个字符串
     */
 public String longestCommonPrefix(String[] strArry) {
        if (strArry.length == 0) {
            return "";
        }
        if (strArry.length == 1) {
            return strArry[0];
        }
        //公共字符前缀
        String commonPrefix = strArry[0];
        String strNext = "";
        for (int i1 = 1; i1 < strArry.length; i1++) {
            //公共前缀
            strNext = strArry[i1];
            if (strNext.equals("")) {
                return "";
            }
            //比较公共前缀和预匹配字符
            commonPrefix = returnCommonPrefix(commonPrefix, strNext);
            if (commonPrefix.equals("")) {
                return "";
            }
        }
        return commonPrefix;

    }

    //判断两个字符相同公共前缀
    private String returnCommonPrefix(String strFirst, String strNext) {
        // StringBuffer sb = new StringBuffer();
        String sb = "";
        for (int i1 = 0; i1 < strFirst.length(); i1++) {
            if (i1 <= strNext.length() - 1 && strFirst.charAt(i1) == strNext.charAt(i1)) {
                //判断相同前缀
                //sb.append(strFirst.charAt(i1));
                sb += strFirst.charAt(i1);
            } else {
                //return sb.toString();
                return sb;
            }
        }
        //return sb.toString();
        return sb;
    }

 /**
     * 1、取出数组最短的字符串
     * 2、循环最短字符串，
     * 3、在第二步内循环中循环数组，取出数组的指定字符与最短字符串的字符对比
     * 4、如果第三步的内循环半途停止，这样可判断数组内存在字符串与最短字符串的字符不同，
     * 5、得到第四部的相同字符前缀即可
     * @param strArry
     * @return
     */
  public String longestCommonPrefix1(String[] strArry) {
        if (strArry.length == 0) {
            return "";
        }
        if (strArry.length == 1) {
            return strArry[0];
        }

       /* List<String> sortStr = Arrays.stream(strArry).sorted(
                Comparator.comparing(String::length)
        ).collect(Collectors.toList());*/
        //排序后的最短字段
        String shortStr = Arrays.stream(strArry).min(Comparator.comparing(String::length)).get();

        if (shortStr.equals("")) {
            return "";
        }
        char commonPrefix;
        int length = 0;
        int maxFor = shortStr.length();
        int maxSize = strArry.length;

        //for循环的长度
        for (int i = 0; i < maxFor; i++) {
            //公共字符前缀
            commonPrefix = shortStr.charAt(i);
            int forSize = 0;
            //从第二位开始，遍历集合每个节点与最短字符串节点字符是否相同
            for (int i1 = 0; i1 < maxSize; i1++) {
                //当前字符串长度一定大于最短字符串长度，只需判断当前字符串节点和最短字符串节点，不相同直接打断内循环
                if (commonPrefix != strArry[i1].charAt(i)) {
                    break;
                }
                forSize++;
            }
            if (forSize < maxSize) {
                //说明内部循环没走完，有不相同的节点字符，结束外循环
                break;
            }
            length++;
        }
        return length == 0 ? "" : shortStr.substring(0, length);
    }

二、字符串排列

 /**
     *
     * 字符串排列
     * s1 = "ab" s2 = "eidbaooo"
     * s2 包含 s1 的排列之一 ("ba")
     * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
     *
     */
    public boolean checkInclusionMethod1(String s1, String s2) {
        //s1,s2为空或null等情况均不考虑
        int s1Length = s1.length();
        int s2Length = s2.length();
        //1、s1比s2长直接返回
        if (s2Length < s1Length) {
            return false;
        }
        char[] s1Arry = s1.toCharArray();
        char[] s2Arry = s2.toCharArray();

        HashMap<Character, Integer> s1Hash = new HashMap<Character, Integer>();
        HashMap<Character, Integer> s2Hash = new HashMap<Character, Integer>();
        //2、遍历得到s1的字符组成情况
        for (int i = 0; i < s1Length; i++) {
            char s1Char = s1Arry[i];
            Integer orDefault = (s1Hash.getOrDefault(s1Char, 0))+1;
            s1Hash.put(s1Char, orDefault);
        }
        for (int i = 0; i < s2Length; i++) {
            char s2Char = s2Arry[i];
            //3、遍历向map2中存入s2字节，并计算是否已存在，如果已存在字符，将value+1
            Integer orDefault = s2Hash.getOrDefault(s2Char, 0)+1;
            s2Hash.put(s2Char, orDefault);
            if (i >= s1Length) {
                //4、当s2Hash存入的数据次数和s1的长度相等后，需要把前者移除，后者加入，保证s2hashmap里的数据次数等于s1的长度（这里注意是次数和长度的关系）
                Integer orDefault1 = s2Hash.get(s2Arry[i - s1Length]);
                orDefault1--;
                if (orDefault1 == 0) {
                    s2Hash.remove(s2Arry[i - s1Length ]);
                }else {
                    s2Hash.put(s2Arry[i - s1Length ], orDefault1);
                }
            }
            if (s2Hash.equals(s1Hash)) {
                return true;
            }
        }
        return false;
    }

//方法2
public String reverseWords1(String s) {
        StringBuffer result = new StringBuffer();
        //临时变量
        StringBuffer ls = new StringBuffer();

        //1、s中必存在单词,去除首位空格
        s = s.trim();
        for (int i =  s.length(); i > 0; i--) {
            //2、反向遍历目标字符串
            if(' '!=s.charAt(i-1)){
                //3、当未匹配到空格时代表是单词
                ls.append(s.charAt(i-1));
                if(i == 1){
                    //4、当遍历到最后时，将最后的单词加入结果集
                    ls.reverse();
                    result.append(ls.toString());
                    ls.setLength(0);
                }
            }else {
                //5、此时遇到空格，说明单词已读取完毕，判断大于0是防止下空格导致下一步多添加空格
                if(ls.length()>0){
                    ls.reverse();
                    result.append(ls.toString()).append(" ");
                    //6、处理完单词将临时字符串缓冲池清空
                    ls.setLength(0);
                }
            }
        }
        return result.toString();
    }