百度算法面试题（一）

废话不多说 该题是在百度面试中需要手动写代码实现一个包含容器、排序、字符、遍历为考查点一道题（lecode 也有）

题目要求

/*** * 根据字符出现频率排序 * 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。 * * 示例 1: * * 输入: * “tree” * * 输出: * “eert” * * 解释: * e’出现两次，r’和’t’都只出现一次。 * 因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。 * 示例 2: * * 输入: * “cccaaa” * * 输出: * “cccaaa” * * 解释: * c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。 * 注意"cacaca"是不正确的，因为相同的字母必须放在一起。 * 示例 3: * * 输入: * “Aabb” * * 输出: * “bbAa” * * 解释: * 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。 * 注意’A’和’a’被认为是两种不同的字符。 * public String frequencySort(String s) { * } */

实现方案代码

package org.cloud_common.practice;

import com.google.protobuf.MapEntry;

import java.util.*;

/**
 * @ClassName BaiDuTest_01
 * @Description: TODO
 * @Author drj
 * @Date 2021/3/7
 * @Version V1.0
 **/
public class BaiDuTest_01 {
          
   

   
    public static String  frequencySort(String s) {
          
   

        /**
         * 1、获取字符数组
         *
         */
        char[] chars = s.toCharArray();
        /**
         * 2、存放字符key和出现次数value
         */
        Map<Character,Integer> map = new HashMap<>();
        /**
         * 3、遍历字符数组 存在的 Map 中value累加+1 存放到map，不存在的默认1
         */
        for (int i = 0; i < chars.length; i++){
          
   
            if(map.containsKey(chars[i])){
          
   
                map.put(chars[i],map.get(chars[i]) + 1);
            }else{
          
   
                map.put(chars[i],1);
            }
        }
        /**
         * 4、map 转list 目前是通过Collections.sort排序 通过o2.getValue() - o1.getValue() 从大到小排序
         * compare 返回大于1 说明第二个大于第一个元素  sort 归并排序 源码得出 要是按照从大到小排序 通过o2.getValue() - o1.getValue() 来返回比较值
         */
        List<Map.Entry<Character,Integer>> list = new ArrayList<>(map.entrySet());

        Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {
          
   
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
          
   
                return o2.getValue() - o1.getValue();
            }
        });
        /**
         * 存放最终排序的字符串
         */
        StringBuffer buffer = new StringBuffer();

        /**
         * 遍历list map.Entry 对象 根据value 循环 key 追加次数
         */
        list.stream().forEach(action ->{
          
   
            Integer value = action.getValue();
            for(int i = 0; i < value; i++){
          
   
                buffer.append(action.getKey());
            }
        });
        return buffer.toString();
      }

    public static void main(String[] args) {
          
   
        String tree = frequencySort("tree");
        System.out.printf("结果：" + tree);
    }
}