- hash相关
- 链表操作
1. hash相关
1.1 hash在java中的使用
主要有两种一个是HashMap，一个是HashSet。
HashSet: HashSet集合元素具有唯一性。这其实就是根据对象的hashCode和equals方法来决定的。如果我们往集合中存放自定义的对象，那么保证其唯一，就必须复写hashCode和equals方法建立属于当前对象的比较方式。
HashMap: HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。
做的两个hash相关的Leetcode题都是与HashMap相关的，运用到了hashMap键值唯一的特性。都运用HashMap键值唯一的特性，根据题意唯一性选出来谁做key， 然后对应的value值一般要求解的结果相关。
1.2 HashMap常用的函数
clear()：清空HashMap。它是通过将所有的元素设为null来实现的；
containsKey()：判断HashMap是否包含key；
containsValue()：判断HashMap是否包含“值为value”的元素；
entrySet()、values()、keySet()：返回“HashMap中所有对应的集合”，它是一个集合；
get()：获取key对应的value；
put()：对外提供接口，让HashMap对象可以通过put()将“key-value”添加到HashMap中；
putAll()：将"m"的全部元素都添加到HashMap中；
remove()：删除“键为key”元素。
1.3 Leetcode上题目示例
q1 两数之和
package hashRelated;
import java.util.HashMap;
/**
* Given an array of integers,
* return indices of the two numbers such that they add up to a specific target.
*
* You may assume that each input would have exactly one solution,
* and you may not use the same element twice.
*/
public class TwoSum {
/**
* 使用hashmap的方式进行求解
* 使用hashmap存储所有数字以及它们的index, 遍历的时候看看互补的值是否已经在hashMap之中了
* @param nums
* @param target
* @return
*/
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
HashMap<Integer, Integer> allNums = new HashMap<>();
for (int i=0;i<nums.length;i++){
int complement = target - nums[i];
if (allNums.containsKey(complement)){
return new int[]{allNums.get(complement),i};
}
allNums.put(nums[i],i);
}
throw new IllegalArgumentException("No Two Sum Solution");
}
}
q387 字符串中第一个唯一字符
package hashRelated;
import java.util.*;
/**
* Given a string, find the first non-repeating character
* in it and return its index. If it doesn't exist, return -1.
*/
public class FirstUniqueCharInStr {
public static void main(String[] args) {
System.out.println(firstUniqChar("aadadaad"));
}
/**
* 使用LinkedHashMap, LinkedHashMap中存储所有的非重复的字母和它们的index,
* 于此同时还需要使用hashSet存储已经出现的重复的key值,
* 如果不为空返回第一个
* 如果为空返回-1
* @param s
* @return
*/
public static int firstUniqChar(String s) {
LinkedHashMap<Character, Integer> allUni = new LinkedHashMap<>();
HashSet<Character> allRepeatChar = new HashSet<>();
for (int i=0;i<s.length();i++){
char current = s.charAt(i);
if (allUni.containsKey(current) || allRepeatChar.contains(current)){
allUni.remove(s.charAt(i));
allRepeatChar.add(current);
} else {
allUni.put(s.charAt(i),i);
}
}
if (allUni.size() == 0){
return -1;
}else {
Iterator iterator = allUni.entrySet().iterator();
Map.Entry entry = (Map.Entry) iterator.next();
return (int) entry.getValue();
}
}
/**
* 使用简单的方式进行求解，统计所有字母出现的频率
*
* 然后再重新遍历一遍字符串, 返回第一个出现频率为1的结果
*/
public int firstUniqChar2(String s){
HashMap<Character, Integer> count = new HashMap<>();
int n = s.length();
for (int i=0;i<n;i++){
char c = s.charAt(i);
count.put(c, count.getOrDefault(c,0)+1);
}
for (int i=0;i<n;i++){
if (count.get(s.charAt(i))==1){
return i;
}
}
return -1;
}
}
2. 链表操作
2.1 链表的结构
多个节点之间，通过地址进行连接。节点：两个部分：数据域（存储的数值），指针域（存储地址）。
class ListNode{
int val;
ListNode next;
ListNode(){}
ListNode(int val){
this.val = val;
}
ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
2.2 Leetcode上题目示例以及做题的小方法
链表的题通常在比较了解了链表的数据结构就比较好做，总的来说就是在遍历链表，通过指针指向断开链表以及形成循环链表等等。
Leetcode之中几道题的思路
q2 两链表数字相加
顺序同时遍历两个链表（顺序遍历就是使用next指针进行遍历），将链表中的数字拿出来求和，于此同时更新下一步的进位标志。q19 删除链表的倒数第N个节点
solution1: 两次遍历，一次遍历得到链表的长度，然后就知道要删除的元素的位置，第二次遍历更新指针把指定位置的元素删除。
solution2: 使用两个指针，两个指针之间距离N个位置，那么第二个指针指向为空就知道要删除的元素是哪一个了。q61 按指定长度旋转链表
先计算出来链表长度，接着就可以计算得到需要旋转的绝对长度从而也就推导出来哪个节点是新的头节点。可以让链表首尾相连得到循环链表，然后在指定地方断开链表，返回新的头节点q138 复制带随机指针的链表
这个很简单，就是新建所有想复制的节点，然后把它们key是源节点，value是复制节点的键值对放到hashmap中，然后就是可以根据hashmap中源节点的指向更新复制的节点之间的指向。q206 反转链表
这个根本思想其实是把链表分成两部分，一部分是已经反转好的部分，另一部分是还未反转的部分。就是改变未反转部分的首节点指针的转向，把其添加到反转好的那部分，更新各个指针的位置。
以上几道题的具体思路和代码可以参考:我之前写的Leetcode刷题之链表操作https://www.jianshu.com/p/04b4b204bf50
补充的一道题
q25 k个一组翻转链表
package listOperation;
/**
* Given a linked list, reverse the nodes of a linked list k
* at a time and return its modified list.
*
* k is a positive integer and is less than or equal to the length of the linked list.
* If the number of nodes is not a multiple of k
* then left-out nodes in the end should remain as it is.
*/
public class ReverseNodesInKGroup {
/**
*
* @param head
* @param k 分组长度
* @param len 剩余需要计算的长度
* @return
*/
public ListNode reverseGroup(ListNode head, int k, int len){
if (head == null || k > len) return head;
//prev指的是已经反转链表的头节点
ListNode prev = null;
ListNode curr = head;
ListNode next = null;
int temp = k;
while (temp>0 && curr != null){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
temp--;
}
if (curr != null){
head.next = reverseGroup(curr, k, len-k);
}
return prev;
}
private int countLen(ListNode head)
{ ListNode cur=head;
int i=0;
while(cur!=null){
i++;
cur=cur.next;
}
return i;
}
/**
* 根据递归的方式进行求解
* 分组按长度一次次进行旋转，然后把翻转的部分和后面那部分连接起来，其实本质上还是在反转链表
* @param head
* @param k
* @return
*/
public ListNode reverseKGroup(ListNode head, int k) {
if(head==null)
return head;
int len=countLen(head);
return reverseGroup(head,k,len);
}
class ListNode{
int val;
ListNode next;
ListNode(){}
ListNode(int val){
this.val = val;
}
ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
}
