lc面试经典150练习
脱下长衫的第四天
383. 赎金信
给你两个字符串：
ransomNote和magazine，判断ransomNote能不能由magazine里面的字符构成。如果可以，返回
true；否则返回false。
magazine中的每个字符只能在ransomNote中使用一次。示例 1：
输入：ransomNote = \"a\", magazine = \"b\"输出：false示例 2：
输入：ransomNote = \"aa\", magazine = \"ab\"输出：false示例 3：
输入：ransomNote = \"aa\", magazine = \"aab\"输出：true
class Solution { public boolean canConstruct(String ransomNote, String magazine) { if (ransomNote.length() > magazine.length()) { return false; } int[] cnt = new int[26]; for(char a : magazine.toCharArray()){ cnt[a - \'a\']++; } for(char a : ransomNote.toCharArray()){ cnt[a - \'a\']--; if((cnt[a - \'a\'])<0){ return false; } } return true; }}注解 首先，如果 ransomNote 的长度比 magazine 长，说明 magazine 的字符数量不足以构成 ransomNote，直接返回 false。接着，定义一个长度为 26 的数组 cnt，用于统计 magazine 中每个字母的出现次数。遍历 magazine 的每个字符，计算其与 \'a\' 的差值作为索引，并在 cnt 数组对应位置进行计数。然后，遍历 ransomNote 的每个字符，同样计算索引，并在 cnt 数组中减少对应字符的计数。如果在减少过程中，某个字符的计数值变为负数，说明 magazine 中该字符的数量不足，无法满足 ransomNote 的需求，此时返回 false。如果所有字符都满足要求，最终返回 true。
205. 同构字符串
给定两个字符串
s和t，判断它们是否是同构的。如果
s中的字符可以按某种映射关系替换得到t，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例 1:
输入：s = \"egg\", t = \"add\"输出：true示例 2：
输入：s = \"foo\", t = \"bar\"输出：false示例 3：
输入：s = \"paper\", t = \"title\"输出：true
class Solution { public boolean isIsomorphic(String s, String t) { for(int i = 0; i < s.length(); i++){ if(s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))){ return false; } } return true; }}注解 s.indexOf他返回的是所给参数值第一次出现的索引，这个解法巧妙地利用indexOf()方法来验证两个字符串是否同构。其核心思想是：对于同构字符串来说，两个字符串中每个对应位置的字符，它们在各自字符串中首次出现的位置索引必须一致。具体来说，在遍历字符串时，我们比较s.charAt(i)在s中第一次出现的索引和t.charAt(i)在t中第一次出现的索引，如果不一致就立即返回false。这个方法之所以有效，是因为它确保了字符的重复模式完全匹配 - 如果一个字符在某个位置重复出现，另一个字符串对应位置的字符也必须在相同的位置重复出现。比如\"egg\"和\"add\"是同构的，因为\'e\'和\'a\'都首次出现在0位置，\'g\'和\'d\'都首次出现在1位置；而\"foo\"和\"bar\"不是同构的，因为第二个\'o\'在1位置首次出现，而\'r\'是在2位置首次出现。这种方法既简洁又高效，无需额外的存储空间就能完成同构验证。
class Solution { public boolean isIsomorphic(String s, String t) { Map st= new HashMap(); Map ts= new HashMap(); for(int i = 0; i<s.length();i++){ if(st.containsKey(s.charAt(i))&&st.get(s.charAt(i))!=t.charAt(i)||ts.containsKey(t.charAt(i))&&ts.get(t.charAt(i))!=s.charAt(i)){ return false; } st.put(s.charAt(i),t.charAt(i)); ts.put(t.charAt(i),s.charAt(i)); } return true; }}注解 用两个map相互他们的字符， Map st= new HashMap()；第一个Character用于发现字符key再次出现（st.containsKey(s.charAt(i))）
