1. 赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
解题思路： 先遍历magazine，用hashmap存，key为字符，value为个数。然后遍历ransomnote，去找hashmap里面是否存在这个字符以及这个字符的个数，如果个数变成了0，则说明不存在，说明没办法构成，返回false，如果没变成0，则让个数减一。如果遍历完没返回false，则返回true。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
Map<Character,Integer> map = new HashMap<Character,Integer>();
char[] rn = ransomNote.toCharArray();
char[] mg = magazine.toCharArray();
for(char m : mg){
map.put(m,map.getOrDefault(m,0)+1);
}
for(char r : rn){
if(map.getOrDefault(r,0) == 0){
return false;
}else{
map.put(r,map.get(r) - 1);
}
}
return true;
}
}
2. 同构字符串
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
解题思路： 其实就是字符串之间的映射，看看后面映射的对不对，首先直接遍历这两个字符串，然后把每个字符的对应关系存在两个hashmap中，如果出现了重复的字符，则需要判断这个字符在两个hashmap中的对应关系，如果有一个不成立则直接报错。如果都成立则继续执行。
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> s2t = new HashMap<Character, Character>();
Map<Character, Character> t2s = new HashMap<Character, Character>();
int len = s.length();
for(int i = 0 ; i < len ; i++){
char a = s.charAt(i);
char b = t.charAt(i);
if(s2t.containsKey(a)&&s2t.get(a) !=b || t2s.containsKey(b) && t2s.get(b) != a){
return false;
}
s2t.put(a,b);
t2s.put(b,a);
}
return true;
}
}
3. 单词规律
给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
解题思路： 可以和上面那个题同理，只不过对应关系变为 字符对字符串，字符串对字符两个哈希表。
class Solution {
public boolean wordPattern(String pattern, String s) {
Map<Character,String> map2s = new HashMap<Character,String>();
Map<Character,String> s2map = new HashMap<Character,String>();
String[] si = s.split(" ");
char[] pt = pattern.toCharArray();
if(pattern.length() != si.length){
return false;
}
for(int i = 0 ; i < pattern.length() ; i++){
char a = pt[i];
String b = si[i];
if(map2s.containsKey(a) && !map2s.get(a).equals(b)|| s2map.containsKey(b) && !s2map.get(b).euquals(a)){
return false;
}
map2s.put(a,b);
s2map.put(b,a);
}
return true;
}
}
4. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的
字母异位词。
解题思路： 将两个字符串都变成数组，直接array.sort进行排列，看看是不是相等。
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1, str2);
}
}
5. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
解题思路： 遍历整个字符串数组，并对每个字符串数组进行排序，排序后接结果作为key（因为相同构造的单词，排序后的单词顺序是相同的，就对应到相同的key里面去了），value用于存储构成相同的所有单词，所以要用一个list来存，先把单词存到list里面，再把list存到hash里面。就解决了。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<String,List<String>>();
for(String str : strs){
char[] array = str.toCharArray();
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key,new ArrayList<String>());
list.add(str);
map.put(key,list);
}
return new ArrayList<List<String>>(map.values());
}
}
6. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
解题思路： 用hashmap存储 元素以及元素相关的位置，首先遍历整个数组，判断hashmap中是否存在 target - num[i]，如果存在则说明找到了，取出对应target-num[i]的对应索引值，还有当前遍历的i值，返回。如果还不存在，则把当前值放进map里面就可以了。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
int[] re = new int[2];
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])){
return new int[] {map.get(target - nums[i]),i};
}
map.put(nums[i],i);
}
return new int[0];
}
}
7. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
解题思路： 首先快乐数得求和，所以先定义一个函数，用于求所有位的平方和。然后用一个hashSet存储每次的平方和，hashset不重复并且平方和不为1，则把数放到set里，并且继续求下一个平方和。一旦有重复或者平方和为1了，则判断1和最终输出的平方和的关系。
class Solution {
// 转为数组
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<Integer>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
}
8. 存在重复元素
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
解题思路： 首先遍历，用hashmap存储遍历的数和位置。如果当前还没存在重复的key，则把当前遍历的存入map中，一旦有重复的，则需要计算两个重复之间的距离的最小值，也就是map.get(num[i]) - i ，因为需要算一个最小值，所以需要更新map，也就是把当前重复的元素更新到map当中，继续执行，遍历过一遍以后，得出最后结果。并最后判断是不是小于等于k。
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
int i;
int res = Integer.MAX_VALUE;
for(i = 0 ;i < nums.length; i++){
if(!map.containsKey(nums[i])){
map.put(nums[i],i);
}else{
res = Math.min(res,i - map.get(nums[i]));
map.put(nums[i],i);
}
}
return res <= k;
}
}
9.最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
解题思路： 首先遍历一遍，把所有的数都存到一个hashSet里面。然后遍历hashset，用if（！set.contains(num - 1))这样从而找到连续值的开头，因为这是遍历hashset，总有一个是连续值的头，找到之后保存当前连续值的头的值以及一个计数器（用于计数有多少个连续元素），然后用while（set.contains(连续值的头+1)),如果存在则连续值的头 = 连续值的头 + 1, 计数器+1，最后算一个最大长度。返回最大长度即可。
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
int longestStack = 0;
for (int num : num_set){
if (!num_set.contains(num-1)){
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum+1)){
currentNum = currentNum+1;
currentStreak = currentStreak+1;
}
longestStack = Math.max(longestStack,currentStreak);
}
}
return longestStack;
}
}