DAY 6
补充哈希表写代码相关知识：
String s = “123”; char[] array = s.toCharArray() //123
toCharArray() 方法将字符串转换为字符数组。
Arrays.sort(数组名)：为数组排序的操作。统一是由小到大
Arrays.equals（a,b）: 在数组类型中，只比较内容相同; 换句话说，只要两个数组元素的顺序和内容都相同，则输出true。
String s = "123";
char[] array = s.toCharArray();
System.out.println(array);
int[] a = {1,2,3,4,5,8,11,44,-11};
int[] b= {8,11,44,-11};
Arrays.sort(a);
Arrays.toString(a);
System.out.println(Arrays.equals(a, b));
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(b));
补充ASCII相关知识
‘a’~'z’的ASCII是 97 - 122
‘A’~'Z’的ASCII是 65 - 90
补充HashMap的相关操作（java）：
题目要求：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词
s与t中只有小写字母
输入: s = “anagram”, t = “nagaram”
输出: true
思路一：
既然要判断两个字符串中字符出现的次数是不是相同，因此如果将两个字符串按照从小到大的顺序排好，再去判断这两个字符串是不是完全相同，则就可以判断是不是s与t串是字母异位词了。
代码：
class Solution {
public boolean isAnagram1(String s, String t) {
char[] sChars = s.toCharArray();
char[] tChars = t.toCharArray();
Arrays.sort(sChars);
Arrays.sort(tChars);
return Arrays.equals(sChars, tChars);
}
}
思路二：
定义一个record数组，记录的是两个char数组的ASCLL的差值 ：
步骤：
1 定义一个数组记录 数组最大长度为26 因为26个字母 不会再超过26了
2 分别将这两个字符串的形式转换为char类型数组的形式
3 对arrayS进行遍历 record 下标就是记录s字符串中的字母的所在位置，出现一次就加一次。因此record[]其实就是记录这个字母在字符串中出现了几次；同样再次遍历T字符串，对record[]做–操作，如果最后record[]为空了 就说明这两个字符串字符出现的次数是相同的！！！
4 最后对hash数组进行遍历 record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int[26];
char[] arrayS = s.toCharArray();
char[] arrayT = t.toCharArray();
for(int i=0;i<arrayS.length;i++){
record[arrayS[i]-'a']++;
}
for(int i=0;i<arrayT.length;i++){
record[arrayT[i]-'a']--;
}
for(int i=0;i<record.length;i++){
if(record[i]!=0){
return false;
}
}
return true;
}
}
补充思路二中的遍历操作：也可以直接用增强for循环进行遍历：
for (char c : s.toCharArray()) {
record[c - 'a'] ++;
}
思路三:
如果直接用java中的hsahmap来做，首先自己先去IDEA中去了解hashmap怎么新建怎么用，以上内容在博文开头回头补充；要知道hashmap是k-v存放的，因此我们可以根据字符串中出现的字符为key，出现的次数为value，然后再去比较：
class Solution {
public boolean isAnagram(String s, String t) {
char[] array = s.toCharArray();
HashMap<Character, Integer> hashMap = new HashMap<>();
char[] array2 = t.toCharArray();
HashMap<Character, Integer> hashMap2 = new HashMap<>();
for (int i = 0; i < array.length; i++) {
hashMap.put(array[i],hashMap.getOrDefault(array[i],0)+1);
}
for (int i = 0; i < array2.length; i++) {
hashMap2.put(array2[i],hashMap2.getOrDefault(array2[i],0)+1);
}
return hashMap.equals(hashMap2);
}
}
上面写的不好 ，等会修改下,
class Solution {
public boolean isAnagram(String s, String t) {
HashMap<Character, Integer> hashMap = new HashMap<>();
for (char c:s.toCharArray()) {
hashMap.put(c, hashMap.getOrDefault(c, 0) + 1);
}
for (char ch : t.toCharArray()) {
Integer value = hashMap.get(ch);
if(value == null || value<1) {
return false;
}else if(value>1){
hashMap.put(ch,value-1);
}else{
hashMap.remove(ch);
}
}
return hashMap.isEmpty();
}
}
题目描述:
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
思路：
用到了HashSet，要去熟悉一下HashSet在java中的一些相关操作
代码：
自己AC的 做法 不是很好
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] ==nums2[j]){
set.add(nums1[i]);
break;
}
}
}
int[] resArr = new int[set.size()];
int index = 0;
for (int i : set) {
resArr[index] = i;
index++;
}
return resArr;
}
}
**改进代码2 **
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int[0];
}
Set<Integer> set1 = new HashSet<>();
Set<Integer> resSet = new HashSet<>();
for (int i : nums1) {
set1.add(i);
}
for (int i : nums2) {
if (set1.contains(i)) {
resSet.add(i);
}
}
int[] resArr = new int[resSet.size()];
int index = 0;
for (int i : resSet) {
resArr[index] = i;
index++;
}
return resArr;
}
}
题目要求:
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1，那么这个数就是快乐数。如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
解题思路:
求余数.关于%的法则,当左边的绝对值小于右边的绝对值的时候,结果是左边!结果是: 1%10=1.
代码：【不太会，回头看】
class Solution {
public boolean isHappy(int n) {
Set<Integer> record = new HashSet<>();
while (n != 1 && !record.contains(n)) {
record.add(n);
n = getNextNumber(n);
}
return n == 1;
}
private static int getNextNumber(int n) {
int res = 0;
while (n > 0) {
int temp = n % 10;
res += temp * temp;
n = n / 10;
}
return res;
}
}
题目要求：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
输入：nums = [3,2,4], target = 6
输出：[1,2]
输入：nums = [3,3], target = 6
输出：[0,1]
思路1：
自己AC的 不好：
代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] anwer= new int[2];
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
anwer[0]=i;
anwer[1]=j;
return anwer;
}
}
}
return anwer;
}
}
改进：
思路2
本题呢，则要使用map，那么来看一下使用数组和set来做哈希法的局限。
- 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
- set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。用了Map HashMap集合
代码：
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
if(nums == null || nums.length == 0){
return res;
}
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
int temp = target - nums[i];
if(map.containsKey(temp)){
res[1] = i;
res[0] = map.get(temp);
}
map.put(nums[i], i);
}
return res;
}
|