Tag: 哈希表

解法一：递归判断

class Solution {
    public String intToRoman(int num) {
        return(toStr(num));
    }
    public String toStr(int num){
        StringBuilder temp = new StringBuilder();
        int x = 0;
        if(num <= 0){
            return "";
        }else if (num >= 1000) {
            x = num / 1000;
            for(int i = 0;i < x;i++){
                temp.append("M");
            }
            return temp.toString() + toStr(num % 1000);
        }else if (num >= 900 && num < 1000) {
            return "CM" + toStr(num - 900);
        }else if (num >= 500 && num < 1000){
            return "D" + toStr(num - 500);
        }else if (num >= 400 && num < 500) {
            return "CD" + toStr(num - 400);
        }else if (num >= 100 && num < 500) {
            x = num / 100;
            for(int i =0;i < x;i++) {
                temp.append("C");
            }
            return temp.toString() + toStr(num % 100);
        }else if(num >= 90 && num < 100){
            return "XC" + toStr(num - 90);
        }else if (num >= 50 && num < 100) {
            return "L" + toStr(num - 50);
        }else if (num >= 40 && num < 50 ) {
            return "XL" + toStr(num - 40);
        }else if (num >= 10 && num < 50) {
            x = num / 10;
            for(int i = 0;i < x;i++){
                temp.append("X");
            }
            return temp.toString() + toStr(num % 10);
        }else if (num == 9) {
            return "IX";
        }else if (num >= 5 && num < 10) {
            return "V" + toStr(num - 5);
        }else if(num == 4){
            return "IV";
        } else if (num < 5) {
            for(int i = 0;i < num;i++){
                temp.append("I");
            }
            return temp.toString();
        }
        return null;
    }
}

T4mako4/17/26About 2 min

013_罗马数字转整数

class Solution {
    public int romanToInt(String s) {
        int len = s.length();
        int[] num = new int[len];
        for(int i = 0;i < len;i++){
            switch(s.charAt(i)){
                case 'M': num[i] = 1000;break;
                case 'D': num[i] = 500;break;
                case 'C': num[i] = 100;break;
                case 'L': num[i] = 50;break;
                case 'X': num[i] = 10;break;
                case 'V': num[i] = 5;break;
                case 'I': num[i] = 1;break;
            }
        }
        int sum=0;
        for(int i = 0;i < len;i++){
            if(i+1 != len){
                if(num[i] < num[i+1]){
                num[i] = -num[i];
            }
            
            }
            sum += num[i];
        }
        return sum;
    }
}

T4mako4/17/26Less than 1 minute

017_电话号码的字母组合

解法一：

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList();
        if(digits.length() == 0){
            return res;
        }
        int len = digits.length();
        for(int i = 0;i < len;i++){
            String s = get(digits.charAt(i));
            int l = res.size();
            if(l == 0){
                for (int j = 0; j < s.length(); j++) {
                    res.add(String.valueOf(s.charAt(j)));
                }
            }else {
                ArrayList temp = new ArrayList();
                temp.addAll(res);
                for(int j = 0;j < s.length()-1;j++){
                    res.addAll(temp);
                }
                for(int k = 0;k < res.size();k++){
                    res.set(k,res.get(k) + s.charAt(k / l));
                }
            }
        }
        return res;
    }
    public String get(char i){
        switch(i){
            case '2' : return "abc";
            case '3' : return "def";
            case '4' : return "ghi";
            case '5' : return "jkl";
            case '6' : return "mno";
            case '7' : return "qprs";
            case '8' : return "tuv";
            case '9' : return "wxyz";
        }
        return null;
    }
}

T4mako4/17/26About 2 min

030_串联所有单词的子串

class Solution {
   public List<Integer> findSubstring(String s, String[] words) {
        ArrayList<Integer> res = new ArrayList();
        int strslen =  words.length * words[0].length();  //串联子串的长度
        if(s.length() < strslen){
            return res;
        }
        int slen = s.length();
        int wlen = words.length;
        int len = words[0].length();
        HashMap<String,Integer> map = new HashMap();
        //存放所有words，key对应words里的子串，value对应个数
        for(int i = 0;i < wlen;i++){
            if(map.containsKey(words[i])){
                map.put(words[i],map.get(words[i])+1);
            }else {
                map.put(words[i],1);
            }
        }
        for(int i = 0;i < slen;i++){
            //长度太短，直接返回
            if(slen - i < strslen){
                return res;
            }
            //与words[i]等长的字符串
            String temp;
            if(!map.containsKey(s.substring(i,i+len))){
                continue;
            }
            //复制一个map
            HashMap<String,Integer> clone = (HashMap<String, Integer>) map.clone();
            int index = i;
            while(index - i < strslen){
                temp = s.substring(index,index+len);
                //不包含，或者words里对应的的子串用完
                if(!clone.containsKey(temp) || clone.containsKey(temp) && clone.get(temp) == 0){
                    break;
                }else {
                    //value-1
                    clone.put(temp,clone.get(temp)-1);
                    index += len;
                }
            }
            if(index == i + strslen){
                res.add(i);
            }
        }
        return res;
    }
}

T4mako4/17/26About 1 min

036_有效的数独

解法一：

class Solution {
    public boolean isValidSudoku(char[][] board) {
        ArrayList<HashSet<Character>> list = new ArrayList<>();
        ArrayList<HashSet<Character>> list2 = new ArrayList<>();
        ArrayList<HashSet<Character>> list3 = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            list.add(new HashSet<Character>());
            list2.add(new HashSet<Character>());
            list3.add(new HashSet<Character>());
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                if(list.get(i / 3 * 3 + j / 3).contains(board[i][j])) return false;
                if(list2.get(j).contains(board[i][j])) return false;
                if(list3.get(i).contains(board[i][j])) return false;
                list.get(i / 3 * 3 + j / 3).add(board[i][j]);
                list2.get(j).add(board[i][j]);
                list3.get(i).add(board[i][j]);
            }
        }
        return true;
    }
}

T4mako4/17/26About 1 min

041_缺失的第一个正数

解法一：

class Solution {
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < len; i++) {
            if(nums[i] <= 0){
                continue;
            }
            set.add(nums[i]);
        }
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            if(!set.contains(i)){
                return i;
            }
        }
        return 0;
    }
}

T4mako4/17/26Less than 1 minute

049_字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        HashMap<String,Integer> map = new HashMap<>();
        for (String str : strs) {
            String temp = sort(str);
            if (!map.containsKey(temp)) {
                List<String> list = new ArrayList<>();
                list.add(str);
                res.add(list);
                map.put(temp, res.size() - 1);
            } else {
                res.get(map.get(temp)).add(str);
            }
        }
        return res;
    }
   public String sort(String s){
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    }
}

T4mako4/17/26Less than 1 minute

105_从前序与中序遍历序列构造二叉树

class Solution {
    TreeNode res = new TreeNode();
    HashMap<Integer,Integer> map = new HashMap();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }

        build(res,preorder,inorder,0,preorder.length - 1,0,inorder.length - 1,res);
        return res;
    }
    public void build(TreeNode node, int[] preorder, int[] inorder, int pre_left, int pre_right, int in_left, int in_right,TreeNode res){
        if(pre_left > pre_right || in_left > in_right){
            return;
        }
        node.val = preorder[pre_left];
        if(pre_right == pre_left || in_left == in_right) return;
        int i = map.get(node.val);
        int k = map.get(inorder[in_left]);
        i -= k;
        if(i != 0){
            node.left = new TreeNode();
            build(node.left,preorder,inorder,pre_left + 1,pre_left + i,in_left,in_left + i - 1,res);
        }
        if(in_left + i != in_right){
            node.right = new TreeNode();
            build(node.right,preorder,inorder,pre_left + i + 1,pre_right,in_left + i + 1,in_right,res);
        }
    }
}

T4mako4/17/26Less than 1 minute

139. 单词拆分

题目描述

解法：
引用：https://leetcode.cn/problems/word-break/solutions/302471/dan-ci-chai-fen-by-leetcode-solution/comments/2152649

以字符串 s = "leetcode" 和字典 wordDict = "leet", "code" 为例

首先，我们初始化一个长度为 9 的布尔数组 dp，所有元素都初始化为 false，除了 dp[0]，它表示空字符串，所以初始化为 true。

然后，我们开始遍历字符串 "leetcode" 的每个字符，同时对于每个字符，我们都会遍历从当前字符到字符串末尾的每个子字符串。

当 i = 0 时，我们检查子字符串 "l", "le", "lee", "leet", "leetc", "leetco", "leetcod", "leetcode"。当我们检查到 "leet" 时，> 我们发现 "leet" 在字典中，而且 dp[0] 是 true，所以我们将 dp[4] 设置为 true。

当 i = 1 时，我们检查子字符串 "e", "ee", "eet", "eetc", "eetco", "eetcod", "eetcode"。但是因为 dp[1] 是 false，所以我们不会> 更新任何 dp[j]。

当 i = 2 和 i = 3 时，同样因为 dp[2] 和 dp[3] 都是 false，所以我们也不会更新任何 dp[j]。

当 i = 4 时，我们检查子字符串 "c", "co", "cod", "code"。当我们检查到 "code" 时，我们发现 "code" 在字典中，而且 dp[4] 是 > true，所以我们将 dp[8] 设置为 true。

最后，我们返回 dp[8]，也就是 true，表示字符串 "leetcode" 可以被拆分为字典中的单词。

T4mako3/28/24About 1 min

146. LRU 缓存

解法

class LRUCache {

    private LinkedHashMap<Integer, Integer> cache;

    public LRUCache(final int capacity) {
        cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cache.put(key, value);
    }
}

T4mako3/23/24Less than 1 minute