算法题（一）——字符串

以你之姓@ 2021-11-17 09:06 237阅读 0赞

### 一、给定一整型字符串入“1”，“4”，“-3”，“-2”，“2”,请出连续和最大的子串 ###

public static String[] subMax(String[] strArr ) {
            //需要记录开始位置
            int start = 0;
            //记录结束位置
            int end = 0;
            //记录一个临时位置
            int temp = 0;
            //记录一个临时最大值
            int tempMax = Integer.MIN_VALUE;
            //记录最大值
            int max = Integer.MIN_VALUE;
            //记录最大叠加值
            int k = Integer.MIN_VALUE;
    
            for (int i = 0; i < strArr.length; i++) {
    
                int num = Integer.parseInt(strArr[i]);
    
                if ( k > 0) {
                    k += num;
                }else {
                    //当出现负值的时候考虑可能存在子串起始值偏移的情况，需要记录临时起始位和临时最大值
                    k = num;
                    temp = i;
                    tempMax = max;
                }
                if (max < k) {
                    max = k;
                    end = i;
                    //新最大值大于原来最大值时，起始值偏移
                    if (max > tempMax) {
                        start = temp ;
                    }
                }
    
            }
            System.out.println(max);
            return Arrays.copyOfRange(strArr,start,end + 1);
    
        }

### 二、给定两个字符串str1，str2。如果两者字符种类和相应出现次数一致，则称为变形词。请实现函数来判断两个字符串是否为变形词。 ###

/**
     * 给定两个字符串str1，str2。如果两者字符种类和相应出现次数一致，则称为变形词。请实现函数来判断两个字符串是否为变形词。
     *
     * @author sunyiran
     * @createTime 2019-07-31 10:12
     */
    public class Test1 {
        private static Boolean checkoutStr(String str1, String str2) {
            //如果存在空或者二者长度不一致,那么判断毫无意义，直接返回false
            if (isEmpty(str1) || isEmpty(str2) || str1.length() != str2.length()) {
                return false;
            }
            /* 利用hashMap(假定限制了字符范围，那么采用数组来记录更好)来判断字符是否重复出现，且次数一致。
             * 针对str1,字符作为key,出现次数作为v,出现一次+1；
             * 针对str2,字符作为key,出现次数作为v,出现一次-1；
             */
            HashMap<Character,Integer> map = new HashMap<>();
            for (int i = 0; i < str1.length() ; i++) {
                char c1 = str1.charAt(i);
                char c2 = str2.charAt(i);
    
                if (!map.containsKey(c1)) {
                    map.put(c1,1);
                }else {
                    map.put(c1,map.get(c1) + 1);
                }
    
                if (!map.containsKey(c2)) {
                    map.put(c2,-1);
                }else {
                    map.put(c2,map.get(c2) -1);
                }
            }
            System.out.println(map);
            //假定map的值都为0，则代表两个字符串字符种类一致，出现次数一致
            return  map.values().stream().allMatch(x->x == 0);
        }
    
    
        /**
         * 判断字符是否为空
         */
        private static Boolean isEmpty(String str) {
            if (str == null || str.length() == 0) {
                return true;
            }
            str = str.replaceAll("\\s", "");
            return str.length() == 0;
    
        }
    
        public static void main(String[] args) {
            System.out.println(checkoutStr("ace1","aec1"));
        }
    
    }

### 三、给定一个字符串，求所有数字串的数字之和，要求：小数点分割的数字，不作为分数，而是两个数字；单个-为负数，--为正数 ###

/**
     * 给定一个字符串，求所有数字串的数字之和，要求：小数点分割的数字，不作为分数，而是两个数字；单个-为负数，--为正数
     *
     * @author sunyiran
     * @createTime 2019-07-31 10:43
     */
    public class Test2 {
    
        private static Integer sumSubNumStr(String str) {
            if (isEmpty(str)) {
                return 0;
            }
    
            int sum = 0;
            //子串值
            int num = 0;
            //符号
            Boolean symbol = true;
    
            List<Integer> result = new ArrayList<>();
    
            for (int i = 0; i < str.length(); i++) {
                String temp = str.substring(i, i + 1);
                if (temp.matches("\\d")) {
                    //每右移一位，原有数字增大10倍
                    num = num * 10 + (symbol ? Integer.parseInt(temp) : -Integer.parseInt(temp));
                } else {
                    //如果不是数字，则上一子串结束，把上一子串添加到总和
                    sum += num;
                    //重新统计子串
                    num = 0;
                    //如果是-则开始判断符号位，为下一子串统计做准备
                    if (temp.equals("-")) {
                        if (i == 0 || str.charAt(i - 1) != '-') {
                            symbol = false;
                        } else {
                            symbol = true;
                        }
                    }
                }
            }
            //防止最后一位是数字时，未能加上最后一个数字子串
    
            sum += num;
    
            return sum;
        }
    
        /**
         * 判断字符是否为空
         */
        private static Boolean isEmpty(String str) {
            if (str == null || str.length() == 0) {
                return true;
            }
            str = str.replaceAll("\\s", "");
            return str.length() == 0;
    
        }
    
        public static void main(String[] args) {
    
            System.out.println(sumSubNumStr("123a-123--1"));
        }
    }

### 四、去掉字符串中连续出现K次指定字符c的子串  ###

/**
     * 去掉字符串中连续出现K次指定字符c的子串
     * @author sunyiran
     * @createTime 2019-07-31 14:09
     */
    public class Test3 {
    
        private static String removeTagetSubStr(String str,char c,int k) {
            if (isEmpty(str) || k < 1) {
                return str;
            }
    
            int count = 0;
    
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < str.length() ; i++) {
                //如果是字符c,那么我们需要开始统计它出现次数
                if (str.charAt(i) == c) {
                    count++;
                }else {
                    //如果不是字符c,那么对c出现次数的统计结束，如果统计值不等于k,那么说明【i-count,i-1】这个范围的子串为有效子串
                    if (count != k) {
                    sb.append(str, i-count , i);
                    }
                    sb.append(str.charAt(i));
                    count = 0;
                }
            }
    
            if (count != k) {
                sb.append(str, str.length() -count, str.length());
            }
    
            return sb.toString();
        }
    
        /**
         * 判断字符是否为空
         */
        private static Boolean isEmpty(String str) {
            if (str == null || str.length() == 0) {
                return true;
            }
            str = str.replaceAll("\\s", "");
            return str.length() == 0;
    
        }
    
        public static void main(String[] args) {
            System.out.println(removeTagetSubStr("a1a1a1aaa",'a',2));
        }
    }

### 五、判断两个字符串是否为旋转词，即字符串str1为字符串str2一部分子串放在最后面，如abed与edab ###

/**
     * 判断两个字符串是否为旋转词，即字符串str1为字符串str2一部分子串放在最后面，如abed与edab
     * @author sunyiran
     * @createTime 2019-07-31 15:01
     */
    public class Test4 {
    
        private static Boolean isRotateStr(String str1,String str2) {
            if (isEmpty(str1) || isEmpty(str2) || str1.length() != str2.length()) {
                return false;
            }
    
            for (int i = 0; i < str1.length() ; i++) {
                if (str1.charAt(i) == str2.charAt(0)) {
                    String temp = str1.substring(i)+str1.substring(0,i);
                    if (temp.equals(str2)) {
                        return true;
                    }
                }
            }
            return false;
        }
    
    
        /**
         * 判断字符是否为空
         */
        private static Boolean isEmpty(String str) {
            if (str == null || str.length() == 0) {
                return true;
            }
            str = str.replaceAll("\\s", "");
            return str.length() == 0;
    
        }
    
        public static void main(String[] args) {
            System.out.println(isRotateStr("baaaa", "bbaaa"));
        }
    }

### 六、替换字符串中连续出现的指定字符串，比如给出字符串adc123，目标子字符串abc,更换为新字符串X，则结果为X123，要求重复的子字符串只替换一次 ###

package com.syr.test;
    
    
    /**
     * 替换字符串中连续出现的指定字符串<br/>
     * 比如给出字符串adc123，目标子字符串abc,更换为新字符串X，则结果为X123，要求重复的子字符串只替换一次
     *
     * @author sunyiran
     */
    public class Test5 {
    
        private static boolean strIsEmpty(String str) {
            return str == null || str.length() == 0;
        }
    
        public static String replaceTargetStr(String str, String from, String to) {
    
            //排除异常情况
            if (strIsEmpty(str) || strIsEmpty(from) || to == null) {
                return str;
            }
    
            //标记是否已经替换过
            boolean flag = false;
    
            //单次比较所需长度
            int len = from.length();
    
            StringBuilder sb = new StringBuilder();
    
            for (int i = 0; i < str.length(); ) {
                //判断首位是否相等
                if (str.charAt(i) != from.charAt(0)) {
                    sb.append(str.charAt(i));
                    i++;
    
                } else {
                    String temp = str.substring(i, i + len);
                    if (temp.equals(from)) {
                        if (!flag) {
                            sb.append(to);
                            flag = true;
                        }
                        i += len;
                    }
                }
            }
    
            return sb.toString();
        }
    
        public static void main(String[] args) {
            String result = replaceTargetStr("123abcabc", "abc", "X");
            System.out.println(result);
        }
    }

### 七、给定一个字符串str,返回str的统计字符串，比如，“aaabbadddffc”的统计字符串为“a\_3\_b\_2\_a\_1\_d\_3\_f\_2\_c\_1” ###

/**
     * 给定一个字符串str,返回str的统计字符串</br>
     * 比如，“aaabbadddffc”的统计字符串为“a_3_b_2_a_1_d_3_f_2_c_1”
     *
     * @author sunyiran
     * @createTime 2019-10-15 22:18
     */
    public class Test6 {
    
        private static boolean strIsEmpty(String str) {
            return str == null || str.length() == 0;
        }
    
        private static String countStr(String str) {
            if (strIsEmpty(str)) {
                return null;
            }
    
            char[] chars = str.toCharArray();
    
            StringBuilder sb = new StringBuilder();
    
            int len = 0;
            for (int i = 0; i < chars.length ; i++) {
                len++;
    
                //某位特殊判断
                if (i == chars.length - 1) {
                    sb.append(chars[chars.length-1]).append("_").append(len);
                    break;
                }
                if (chars[i] != chars[i +1]) {
                    sb.append(chars[i]).append("_").append(len).append("_");
                    len = 0;
                }
            }
    
            return sb.toString();
        }
    
        public static void main(String[] args) {
            System.out.println(countStr("aaabbadddffcc"));
        }
    }