【Day30】LeetCode算法 [769. 最多能完成排序的块 ] [2131. 连接两字母单词得到的最长回文串]

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int total = 0;       //记录最多块数量
        int max = 0;         //记录遍历到当前位置，最大的元素值
        for(int i = 0;i < arr.length;++i){  //遍历数组
            max = Math.max(max,arr[i]);     //获取当前最大值

            //当前最大值=当前位置下标，说明排序后是与原数组升序后是相等的，块数+1
            if(max == i) total++;           
        }
        return total;         //返回记录下来的块数
    }
}

class Solution {
    public int longestPalindrome(String[] words) {
        //创建双列集合map，存档Key-Value键值对
        //主键值Key我们存放String数组中出现的字符串。
        //Value值我们存放对应字符串出现的次数
        Map<String,Integer> map = new HashMap<>(); 
        int total = 0;

        for(String s : words){      //遍历字符串数组
            if(!map.containsKey(s)){//若集合中未记录，创建记录，出现次数为1
                 map.put(s,1);
            }else{                  //集合中以及存在记录，出现次数+1
                map.replace(s,map.get(s).intValue() + 1);
            }
        }

        boolean flag = false;  //设置标记，，默认false
        
        //利用构造器，遍历map集合，同时获取集合中每个键值对的主键Key以及Value值
        Iterator<Map.Entry<String,Integer>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<String,Integer> entry = iterator.next();

            String key  = entry.getKey(); //主键：出现的字符串
            int value = entry.getValue(); //Value：字符串出现的次数

            StringBuffer sb = new StringBuffer();  //创建StringBuffer对象
            sb.append(key);                        //字符串存入可变字符串序列对象中
            String rev = sb.reverse().toString();  //调用reverse()获取逆串

            if(key.equals(rev)){                   //原串逆串相等，是字符相等的串
                total += value/2 * 4;              //每对串为回文串增加4个长度
                if(value%2 == 1) flag = true;      //如果字符相等串出现奇数次，设置标记为true
            }
            
            else if(map.containsKey(rev)){         //字符不相等的串
                int value_2 = map.get(rev);        //获取逆串出现的次数
                int min = Math.min(value,value_2); //出现较小次数即使对应的对数
                //每对为回文串提供4个长度，遍历过程会获取两次长度(原串一次，逆串一次)，所以需要/2
                total += min*4/2;                  
            }
        }
        if(flag) total += 2;             //如果标记为true，需要加上中心的两个长度
        return total;                    //返回最长的回文串长度
    }
}