LeetCode|LeetCode 432. 全 O(1) 的数据结构（双向链表+哈希表） / 720. 词典中最长的单词 / 2043. 简易银行系统 leetcode|java

432. 全 O(1) 的数据结构 2022.3.16 每日一题
题目描述请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
实现 AllOne 类：
AllOne() 初始化数据结构的对象。
inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 “” 。
getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 “” 。
示例：

输入
[“AllOne”, “inc”, “inc”, “getMaxKey”, “getMinKey”, “inc”, “getMaxKey”, “getMinKey”]
[[], [“hello”], [“hello”], [], [], [“leet”], [], []]
输出
[null, null, null, “hello”, “hello”, null, “hello”, “leet”]

解释
AllOne allOne = new AllOne();
allOne.inc(“hello”);
allOne.inc(“hello”);
allOne.getMaxKey(); // 返回 “hello”
allOne.getMinKey(); // 返回 “hello”
allOne.inc(“leet”);
allOne.getMaxKey(); // 返回 “hello”
allOne.getMinKey(); // 返回 “leet”

提示：

1 <= key.length <= 10
key 由小写英文字母组成
测试用例保证：在每次调用 dec 时，数据结构中总存在 key
最多调用 inc、dec、getMaxKey 和 getMinKey 方法 5 * 10^4 次

【LeetCode|LeetCode 432. 全 O(1) 的数据结构（双向链表+哈希表） / 720. 词典中最长的单词 / 2043. 简易银行系统】来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-oone-data-structure
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路一个哈希表用于存放个数，另一个哈希表按个数排序，这里放入和删除如果排序的话，时间复杂度不是O1
所以还是用官解给出的双向链表和哈希表的组合，更为妥当，这里就不写了

class AllOne { //乍一看，好像不太难的样子 //两个map，一个键是字符串，值是个数 //更新个数的时候，更新另一个map，放着个数和setMap, Integer> count; TreeMap> map; public AllOne() { count = new HashMap<>(); map = new TreeMap<>(); }public void inc(String key) { count.put(key, count.getOrDefault(key, 0) + 1); int num = count.get(key); if(num > 1){ Set> set = map.get(num - 1); set.remove(key); //如果set为空了，删去这个值 if(set.isEmpty()){ map.remove(num - 1); }else map.put(num - 1, set); } Set> set = map.getOrDefault(num, new HashSet<>()); set.add(key); map.put(num, set); }public void dec(String key) { count.put(key, count.get(key) - 1); int num = count.get(key); if(num == 0) count.remove(key); Set> set = map.get(num + 1); set.remove(key); if(set.isEmpty()){ map.remove(num + 1); }else map.put(num + 1, set); //如果没有这个字符串了，那么就不用放了 if(num > 0){ Set> set2 = map.getOrDefault(num, new HashSet<>()); set2.add(key); map.put(num, set2); } }public String getMaxKey() { if(map.isEmpty()) return ""; int key = map.lastKey(); Set> set = map.get(key); for(String s : set){ return s; } return null; }public String getMinKey() { if(map.isEmpty()) return ""; int key = map.firstKey(); Set> set = map.get(key); for(String s : set){ return s; } return null; } }/** * Your AllOne object will be instantiated and called as such: * AllOne obj = new AllOne(); * obj.inc(key); * obj.dec(key); * String param_3 = obj.getMaxKey(); * String param_4 = obj.getMinKey(); */

720. 词典中最长的单词 2022.3.17 每日一题
题目描述给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。
若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
示例 1：

输入：words = [“w”,“wo”,“wor”,“worl”, “world”]
输出：“world”
解释：单词"world"可由"w", “wo”, “wor”, 和 "worl"逐步添加一个字母组成。

示例 2：

输入：words = [“a”, “banana”, “app”, “appl”, “ap”, “apply”, “apple”]
输出：“apple”
解释：“apply” 和 “apple” 都能由词典中的单词组成。但是 “apple” 的字典序小于 “apply”

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 30
所有输入的字符串 words[i] 都只包含小写字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-word-in-dictionary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路字符串比较大小，用compareTo
官解排序的时候是和我相反的，然后添加到set集合中的时候只添加前缀能在集合中找到的，这样可以保证后面的字符串如果满足条件的话只需要找一个前缀，太巧妙了

class Solution { public String longestWord(String[] words) { //逐步添加一个字母 //可以先排序，按照长度大小排序，字典序排序int n = words.length; Arrays.sort(words, new Comparator>(){ public int compare(String a, String b){ if(a.length() == b.length()){ return a.compareTo(b); }else{ return b.length() - a.length(); } } }); Set> set = new HashSet<>(); for(String w : words) set.add(w); for(int i = 0; i < n; i++){ String temp = words[i]; String t = ""; for(int j = 0; j < temp.length(); j++){ t = t + temp.charAt(j); if(!set.contains(t)) break; if(j == temp.length() - 1) return temp; } } return ""; } }

2043. 简易银行系统 2022.3.18 每日一题
题目描述你的任务是为一个很受欢迎的银行设计一款程序，以自动化执行所有传入的交易（转账，存款和取款）。银行共有 n 个账户，编号从 1 到 n 。每个账号的初始余额存储在一个下标从 0 开始的整数数组 balance 中，其中第 (i + 1) 个账户的初始余额是 balance[i] 。
请你执行所有有效的交易。如果满足下面全部条件，则交易有效：

指定的账户数量在 1 和 n 之间，且
取款或者转账需要的钱的总数小于或者等于账户余额。

实现 Bank 类：

Bank(long[] balance) 使用下标从 0 开始的整数数组 balance 初始化该对象。
boolean transfer(int account1, int account2, long money) 从编号为 account1 的账户向编号为 account2 的账户转帐 money 美元。如果交易成功，返回 true ，否则，返回 false 。
boolean deposit(int account, long money) 向编号为 account 的账户存款 money 美元。如果交易成功，返回 true ；否则，返回 false 。
boolean withdraw(int account, long money) 从编号为 account 的账户取款 money 美元。如果交易成功，返回 true ；否则，返回 false 。

示例：

输入：
[“Bank”, “withdraw”, “transfer”, “deposit”, “transfer”, “withdraw”]
[[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]]
输出：
[null, true, true, true, false, false]
解释：
Bank bank = new Bank([10, 100, 20, 50, 30]);
bank.withdraw(3, 10); // 返回 true ，账户 3 的余额是 $20 ，所以可以取款 $10 。
// 账户 3 余额为 $20 - $10 = $10 。
bank.transfer(5, 1, 20); // 返回 true ，账户 5 的余额是 $30 ，所以可以转账 $20 。
// 账户 5 的余额为 $30 - $20 = $10 ，账户 1 的余额为 $10 + $20 = $30 。
bank.deposit(5, 20); // 返回 true ，可以向账户 5 存款 $20 。
// 账户 5 的余额为 $10 + $20 = $30 。
bank.transfer(3, 4, 15); // 返回 false ，账户 3 的当前余额是 $10 。
// 所以无法转账 $15 。
bank.withdraw(10, 50); // 返回 false ，交易无效，因为账户 10 并不存在。

提示：

n == balance.length
1 <= n, account, account1, account2 <= 105
0 <= balance[i], money <= 1012
transfer, deposit, withdraw 三个函数，每个最多调用 104 次

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/simple-bank-system
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路不知道出这个题是什么意思，直接在数组中加减就完成了啊，也不是考多线程

class Bank { //用一个map就搞定了啊long[] balance; int n; public Bank(long[] balance) { this.balance = balance; n = balance.length; }public boolean transfer(int account1, int account2, long money) { if(account1 > n || account2 > n) return false; if(balance[account1 - 1] < money) return false; balance[account1 - 1] -= money; balance[account2 - 1] += money; return true; }public boolean deposit(int account, long money) { if(account > n) return false; balance[account - 1] += money; return true; }public boolean withdraw(int account, long money) { if(account > n) return false; if(balance[account - 1] < money) return false; balance[account - 1] -= money; return true; } }/** * Your Bank object will be instantiated and called as such: * Bank obj = new Bank(balance); * boolean param_1 = obj.transfer(account1,account2,money); * boolean param_2 = obj.deposit(account,money); * boolean param_3 = obj.withdraw(account,money); */