leetcode哈希表(python与c++)

1.整数转罗马数字

python:

class Solution:
    def intToRoman(self, num: int) -> str:
        dict_ = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}
        res = ''
        for key in dict_:
            count = num // key
            res += count * dict_[key]
            num %= key
        return res

c++: 

class Solution {
public:
    string intToRoman(int num) {
        int value[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string str_[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        string res;
        for(int i = 0; i < 13; i++){
            while(num >= value[i]){
                num -= value[i];
                res += str_[i];
            }
        }
        return res;
    }
};

2.电话号码的字母组合 

 python:

class Solution:
    def help(self, digits, track):
        if len(digits)==0:
            self.res.append(''.join(track))
            return
        for letter in self.dict_[digits[0]]:
            # store = track.copy()
            track.append(letter)
            self.help(digits[1:], track)
            # track.pop()
            track = store
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits)==0:
            return []
        self.dict_={"2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz"}
        self.res = []
        self.help(digits, [])
        return self.res

c++:

class Solution {
public:
    vector res;
    // unordered_map phoneMap;
    void help(string digits, vector track, unordered_map phoneMap){
        if(digits.empty()){
            string str(track.begin(), track.end());
            res.push_back(str);
        }
        for(int i=0; i < phoneMap[digits[0]].size(); i++){
            track.push_back(phoneMap[digits[0]][i]);
            help(digits.substr(1, digits.size() - 1), track, phoneMap);
            track.pop_back();
        }
    }
    vector letterCombinations(string digits) {
        if (digits.empty()) {
            return res;
        }
        unordered_map phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        vector track;
        help(digits, track, phoneMap);
        return res;

    }
};

3.有效的数独

思路用三个hash 记录即可

python:

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [{i:0} for i in range(9)]
        # print(rows)
        cols = [{i:0} for i in range(9)]
        boxs = [{i:0} for i in range(9)]
        for i in range(9):
            for j in range(9):
                box_index = (i // 3) * 3 + j // 3
                if board[i][j] != '.':
                    num = int(board[i][j])
                    rows[i][num] = rows[i].get(num, 0) + 1
                    cols[j][num] = cols[j].get(num, 0) + 1 
                    boxs[box_index][num] = boxs[box_index].get(num, 0) + 1
                    # print(rows)
                    # print('==i', i)
                    # print('==num', num)
                    if rows[i][num] > 1 or cols[j][num] > 1 or boxs[box_index][num] > 1:    
                        return False
        return True

c++: 

class Solution {
public:
    bool isValidSudoku(vector>& board) {
        vector> rows(9, vector(9, 0));
        vector> cols(9, vector(9, 0));
        vector> boxs(9, vector(9, 0));
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if (board[i][j] == '.') continue;
                int num = board[i][j] - '1';
                int box_index = (i / 3) * 3 + j / 3;
                rows[i][num]++;
                cols[j][num]++;
                boxs[box_index][num]++;
                if(rows[i][num] > 1 || cols[j][num] > 1 || boxs[box_index][num] > 1){
                    return false;
                }
            }
        }
        return true;
    }
};

4.字母异位词分组

python:

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dict_={}
        for i in range(len(strs)):
            str_ = ''.join(sorted(strs[i]))
            if str_ in dict_:
                dict_[str_].append(strs[i])
            else:
                dict_[str_] = [strs[i]]
        # print(dict_.values())
        return list(dict_.values())

c++:

class Solution {
public:
    vector> groupAnagrams(vector& strs) {
        vector> result;
        map> dict_; 
        for(int i = 0; i < strs.size(); i++){
            string s = strs[i];
            sort(s.begin(), s.end());
            dict_[s].push_back(strs[i]);
        }
        map> ::iterator it;
        for(it = dict_.begin(); it != dict_.end(); it++){
            result.push_back(it->second);
        }
        // for(auto x:dict_){ 
        //     result.push_back(x.second);
        // }
        return result;
    }
};