菜鸡的原地踏步史08(◐‿◑)

技巧题

只出现一次的数字

class Solution {
    /** 
        HashMap统计num和次数
        前面一天用堆魔怔了，也用堆进行排列...
    */
    public int singleNumber(int[] nums) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for(var node : map.entrySet()) {
            int[] temp = new int[2];
            temp[0] = node.getKey();
            temp[1] = node.getValue();
            pq.offer(temp);
        }
        return pq.peek()[0];
    }
}

多数元素

class Solution {
    /** 
        HashMap统计?
    */
    public int majorityElement(int[] nums) {
        int res = 0;
        int n = nums.length / 2;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for(var node: map.entrySet()) {
            if(node.getValue() > n) {
                res =  node.getKey();
            }
        }
        return res;
    }
}

颜色分类

class Solution {
    /** 
        使用堆不就秒了?
    */
    public void sortColors(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int num : nums) {
            pq.offer(num);
        }
        int i = 0;
        while(!pq.isEmpty()) {
            nums[i] = pq.poll();
            i++;
        }
    }
}

芜湖~ 力扣200题打卡！

下一个排列

class Solution {
    /** 
    i = 0 1 2 3
        2 1 4 3 从后向前搜索
        2|1 3 4 搜到第一个i > i - 1的，记录i，排序i到末尾
        2|3 1 4 找到排序后第一个 > i - 1的，交换

        需要注意Arrays.sort(nums, i, j) 是左闭右开的区间
        对nums进行从i到末尾的sort需要(nums, i, len(而不是len - 1))
    */
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        for(int i = len - 1; i >= 0; i--) {
           if( i > 0 && nums[i] > nums[i - 1]) {
                Arrays.sort(nums, i, len);
                for(int j = i; j < len; j++) {
                    if(nums[j] > nums[i - 1]) {
                        int temp = nums[i - 1];
                        nums[i - 1] = nums[j];
                        nums[j] = temp;
                        return;
                    }
                }
            }
            else if(i == 0) {
                Arrays.sort(nums);
            } 
        }
    }
}

寻找重复数

class Solution {
    /** 
        hashmap直接秒了啊
    */
    public int findDuplicate(int[] nums) {
        int res = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for(var node: map.entrySet()) {
            if(node.getValue() > 1) {
                res = node.getKey();
            }
        }
        return res;
    }
}

图论

岛屿数量

class Solution {
    /** 
        深度优先搜索dfs
        类似和寻找字符串
        逐行逐列遍历判断
    */
    public int numIslands(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int island = 0;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] == '1') {
                    island++;
                    dfs(grid, i, j);
                }
            }
        }
        return island;
    }
    public void dfs(char[][] grid, int i, int j) {
        int row = grid.length;
        int col = grid[0].length;
        if(i >= row || i < 0 || j >= col || j < 0 || grid[i][j] == '0') {
            return;
        }
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }
}

腐烂的橘子

class Solution {
    /** 
        用2覆盖grid网格
        2表示初始化时间
    */
    public int orangesRotting(int[][] grid) {
        if(grid == null || grid.length == 0) {
            return 0;
        }
        int row = grid.length;
        int col = grid[0].length;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] == 2) {
                    dfs(grid, i, j, 2);
                }
            }
        }
        int maxtime = 0;
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] == 1) {
                    return -1;
                }
                else {
                    maxtime = Math.max(maxtime, grid[i][j]);
                }
            }
        }
        return maxtime == 0 ? 0 : maxtime - 2;
    }
    public void dfs(int[][] grid, int i, int j, int time) {
        int row = grid.length;
        int col = grid[0].length;
        if(i >= row || i < 0 || j >= col || j < 0) {
            return;
        }
        if(grid[i][j] != 1 && grid[i][j] < time) { // 没新鲜橘子，且时间更少，倒回去
            return;
        }
        grid[i][j] = time;

        dfs(grid, i + 1, j, time + 1);
        dfs(grid, i, j + 1, time + 1);
        dfs(grid, i - 1, j, time + 1);
        dfs(grid, i, j - 1, time + 1);
    }
}

课程表

实现Trie 前缀树

class Trie {
    Map<Character, Map> map, t;
    public Trie() {
        map = new HashMap<>();
    }
    
    public void insert(String word) {
        t = map;
        for(char w: word.toCharArray()) {
            if(!t.containsKey(w)) {
                t.put(w, new HashMap<Character, Map>());
            }
            t = t.get(w);
        }
        t.put('#', null);
    }
    
    public boolean search(String word) {
        t = map;
        for(char w: word.toCharArray()) {
            if(!t.containsKey(w)) {
                return false;
            }
            t = t.get(w);
        }
        return t.containsKey('#');
    }
    
    public boolean startsWith(String prefix) {
        t = map;
        for(char w: prefix.toCharArray()) {
            if(!t.containsKey(w)) {
                return false;
            }
            t = t.get(w);
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */