242.有效的字母异位词 （easy） 2021-01-18
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
题解：如果只是26个小写字母，那么建立一个长度为26的数组记录每个字母出现的频次信息就够了。如果包含unicode字符，需要使用map来存储。
class Solution { public boolean isAnagram(String s, String t) { char[] sarr = s.toCharArray(); char[] tarr = t.toCharArray(); if(sarr.length != tarr.length){ return false; } Map<Character, Integer> map = new HashMap<>(); for(int i = 0; i < sarr.length; i++){ map.put(sarr[i], map.getOrDefault(sarr[i], 0) + 1); } for(int i = 0; i < sarr.length; i++){ if(!map.containsKey(tarr[i])){ return false; }else if(map.get(tarr[i]) == 1){ map.remove(tarr[i]); }else{ map.put(tarr[i], map.get(tarr[i]) - 1); } } if(map.isEmpty()){ return true; }else{ return false; } } }
409.最长回文串 （easy） 2021-01-18
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。示例 1:
输入:
"abccccdd"输出:
7
这个题我的做法是将元素存放哈希表中，记录频次信息，然后取出所有的values值进行操作。
这个题遇到了一个bug记录一下：
map.values( ) 返回的是Collection类型。Collection被定义为接口，需要进行实例化，但是将其强转成（List）又会报错。
最后使用的是ArrayList的一个构造方法，ArrayList(Collection<? extends E> 。
class Solution { public int longestPalindrome(String s) { Map<Character, Integer> map = new HashMap<>(); for(char i : s.toCharArray()){ map.put(i, map.getOrDefault(i, 0) + 1); } //Collection<Integer> coll = map.values(); //map的values值是以collection的形式返回 List coll = new ArrayList<Integer>(map.values()); Iterator iterator = coll.iterator(); int flag = 0; //记录回文串是否为奇数的标志 int sum = 0; while(iterator.hasNext()){ int temp = (int)iterator.next(); if(flag == 0 && temp % 2 != 0){ flag = 1; } sum = sum + temp / 2; } return sum * 2 + flag; } }
205.同构字符串
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例 1:
输入：s = "egg", t = "add"
输出：true
class Solution { public boolean isIsomorphic(String s, String t) { char[] sarr = s.toCharArray(); char[] tarr = t.toCharArray(); Map<Character, Character> map = new HashMap<>(); if(sarr.length != tarr.length) return false; for(int i = 0; i < sarr.length; i++){ if(!map.containsKey(sarr[i]) && !map.containsValue(tarr[i])){ map.put(sarr[i], tarr[i]); }else if((map.containsKey(sarr[i]) && map.get(sarr[i]) == tarr[i])){ }else{ return false; } } return true; } }
使用数组来记录好像更简单。
class Solution { public boolean isIsomorphic(String s, String t) { int[] preIndexOfS = new int[256]; int[] preIndexOfT = new int[256]; for (int i = 0; i < s.length(); i++) { char sc = s.charAt(i), tc = t.charAt(i); if (preIndexOfS[sc] != preIndexOfT[tc]) { return false; } preIndexOfS[sc] = i + 1; preIndexOfT[tc] = i + 1; } return true; } }
647.回文子串 （medium） 2021-01-18
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
感觉思路是一致的，我的代码四十多行，大佬的代码就十几行，我/(ㄒoㄒ)/~~
class Solution { public int countSubstrings(String s) { char[] arr = s.toCharArray(); int sum = 0; for(int i = 0; i < arr.length; i++){ sum += sum1(i, arr); sum += sum2(i, arr); } return sum; } //以i为中心的回文子串的个数 public int sum1(int i, char[] arr){ int k = 0; int sum = 0; boolean continual = true; //判断是否连续地标志 while(i - k >= 0 && i + k < arr.length){ if(continual == true && arr[i - k] == arr[i + k]){ sum++; }else{ continual = false; } k++; } return sum; } //以i + 0.5为中心的回文子串的个数 public int sum2(int i, char[] arr){ int k = 1; int sum = 0; boolean continual = true; while(i + 1 - k >= 0 && i + k < arr.length){ if(continual == true && arr[i + 1 - k] == arr[i + k]){ sum++; }else{ continual = false; } k++; } return sum ; } }
class Solution { private int cnt = 0; public int countSubstrings(String s) { for (int i = 0; i < s.length(); i++) { extendSubstrings(s, i, i); // 奇数长度 extendSubstrings(s, i, i + 1); // 偶数长度 } return cnt; } private void extendSubstrings(String s, int start, int end) { while (start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) { start--; end++; cnt++; } } }
9.回文数 （easy） 2021-01-18
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
你能不将整数转为字符串来解决这个问题吗？
使用字符串确实简单。
class Solution { public boolean isPalindrome(int x) { String str = String.valueOf(x); for(int i = 0 ; i < str.length() / 2; i++){ if((int)str.charAt(i) != (int)str.charAt(str.length() - 1 - i)){ return false; } } return true; } }
·不使用字符串，更多的使用数学的方式。不停地使用余数成十以致两个数长度差在1以内。
class Solution { public boolean isPalindrome(int x) { if (x == 0) { return true; } if (x < 0 || x % 10 == 0) { return false; } int right = 0; while (x > right) { right = right * 10 + x % 10; x /= 10; } return x == right || x == right / 10; } }
696.计数二进制子串 （easy） 2021-01-18
给定一个字符串 s，计算具有相同数量0和1的非空(连续)子字符串的数量，并且这些子字符串中的所有0和所有1都是组合在一起的。
重复出现的子串要计算它们出现的次数。
示例 1 :
输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。请注意，一些重复出现的子串要计算它们出现的次数。
另外，“00110011”不是有效的子串，因为所有的0（和1）没有组合在一起。
这个题不容易，忙碌了几个小时的菜鸟程序员发现运行时间超出限制。
写程序确实需要脑袋清醒，之前的思路正确但是嵌套循环太浪费运行时间。换换思路还是事半功倍。
class Solution { public int countBinarySubstrings(String s) { int sum = 0; for(int i = 0; i < s.length(); i++){ if(s.charAt(i) != ‘0‘ && s.charAt(i) != ‘1‘){ i++; } int k = 1; while(i - k + 1 >= 0 && i + k < s.length()){ if(s.charAt(i - k + 1) == s.charAt(i) && s.charAt(i + k) != s.charAt(i) ){ sum++; k++; }else{ break; } } } return sum; } }
贴一个大佬的做法，算法确实妙。
class Solution { public int countBinarySubstrings(String s) { int preLen = 0, curLen = 1, count = 0; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == s.charAt(i - 1)) { curLen++; } else { preLen = curLen; curLen = 1; } if (preLen >= curLen) { count++; } } return count; } }
原文：https://www.cnblogs.com/nobita/p/14295200.html
