[数据结构与算法]504. 七进制数 / 45. 跳跃游戏 II / 692. 前K个高频单词

504. 七进制数【简单题】【每日一题】

思路：

1. 新建一个StringBuilder类型变量sb，布尔标志位flag=true。
2. 如果num<0，则将num转为它的相反数，并将flag置为false。
3. 将num对7取余，求余数yu，同时求除数num/7。当除数chu>0时，将余数添加到sb中，并将余数更新为chu % 7，将除数更新为 chu / 7；当除数chu=0时，跳出循环，并将最后一次更新的余数添加到sb中。
4. 如果flag为false，说明这个转为七进制的数应是负数，在sb后添加一个负号。
5. 将翻转后的sb转为字符串返回即可。

代码：

class Solution {
    public String convertToBase7(int num) {
        StringBuilder sb = new StringBuilder();
        boolean flag = true;
        if (num<0){
            num = -num;
            flag = false;
        }
        int yu = num % 7,chu = num / 7;
        while (chu > 0){
            sb.append(yu);
            yu = chu % 7;
            chu /= 7;
        }
        sb.append(yu);
        if (!flag){
            sb.append('-');
        }
        return sb.reverse().toString();
    }
}

用时：

45. 跳跃游戏 II【中等题】

思路：

1. 定义跳跃的边界bound，初值为0，定义当前能跳的最远位置maxPos，初值为0，定义需要跳跃的步数step，初值为0。
2. 循环遍历nums，当我们未到边界时，更新我们可以跳的最远位置，当到达边界时，跳一步，即step++，同时更新新的边界为当前位置能跳的最远位置。
3. 返回step。

代码：

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        int bound = 0,maxPos = 0,i = 0,step = 0;
        while (i<len-1){
            maxPos = Math.max(maxPos,nums[i]+i);
            if (i == bound){
                step++;
                bound = maxPos;
            }
            i++;
        }
        return step;
    }
}

692. 前K个高频单词【中等题】

思路：

1. 先把每个单词出现的次数用哈希表存起来，存入map，key为单词，value为出现次数。
2. 遍历map中每个value，将每个出现次数对应的单词存入哈希表kmap中，key为单词出现次数，value为出现当前次数的单词集合，用哈希set去重。
3. 将kmap中的所有key即单词的出现次数用list集合nums存储，对其按从大到小的顺序排序，然后倒序遍历nums，即为所有单词的出现频次中，由大到小进行遍历。
4. 记当前遍历到的出现次数对应的单词列表为temp，记have为temp的长度，对temp进行字典序排序。
5. 定义要返回的列表为list，那么如果have=k，那么将temp添加到list中，退出循环；如果have大于k，那么将temp中的前k个添加到list中，退出循环；如果have小于k，那么将temp添加到list中，k更新为k-have，继续下一次循环。
6. 最后返回答案list。

代码：

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        List<String> list = new ArrayList<>();
        Map<String,Integer> map = new HashMap<>();
        for (String key : words) {
            if (!map.containsKey(key)){
                map.put(key,1);
            }else {
                map.put(key,map.get(key)+1);
            }
        }
        Map<Integer,Set<String>> kmap = new HashMap<>();
        for (String s : map.keySet()) {
            int value = map.get(s);
            Set<String> temp;
            if (!kmap.containsKey(value)){
                temp = new HashSet<>();
            }else {
                temp = kmap.get(value);
            }
            temp.add(s);
            kmap.put(value,temp);
        }
        List<Integer> nums = new ArrayList<>(kmap.keySet());
        Collections.sort(nums);
        for (int i = nums.size()-1; i >= 0 ; i--) {
            List<String> temp = new ArrayList<>(kmap.get(nums.get(i)));
            int have = temp.size();
            Collections.sort(temp);
            if (have == k){
                list.addAll(temp);
                break;
            }else if (have > k){
                for (int j = 0; j < k; j++) {
                    list.add(temp.get(j));
                }
                break;
            }else {
                list.addAll(temp);
                k -= have;
            }
        }
        return list;
    }
}

用时：