Leetcode總結(jié)之Hash相關(guān) & 鏈表操作

  1. hash相關(guān)
  2. 鏈表操作

1. hash相關(guān)

1.1 hash在java中的使用

主要有兩種一個(gè)是HashMap，一個(gè)是HashSet。

HashSet: HashSet集合元素具有唯一性。這其實(shí)就是根據(jù)對(duì)象的hashCode和equals方法來決定的。如果我們往集合中存放自定義的對(duì)象，那么保證其唯一，就必須復(fù)寫hashCode和equals方法建立屬于當(dāng)前對(duì)象的比較方式。

HashMap: HashMap 是一個(gè)散列表，它存儲(chǔ)的內(nèi)容是鍵值對(duì)(key-value)映射。
HashMap 繼承于AbstractMap，實(shí)現(xiàn)了Map、Cloneable、java.io.Serializable接口。
HashMap 的實(shí)現(xiàn)不是同步的，這意味著它不是線程安全的。它的key、value都可以為null。

做的兩個(gè)hash相關(guān)的Leetcode題都是與HashMap相關(guān)的，運(yùn)用到了hashMap鍵值唯一的特性。都運(yùn)用HashMap鍵值唯一的特性，根據(jù)題意唯一性選出來誰(shuí)做key， 然后對(duì)應(yīng)的value值一般要求解的結(jié)果相關(guān)。

1.2 HashMap常用的函數(shù)

clear()：清空HashMap。它是通過將所有的元素設(shè)為null來實(shí)現(xiàn)的；
containsKey()：判斷HashMap是否包含key；
containsValue()：判斷HashMap是否包含“值為value”的元素；
entrySet()、values()、keySet()：返回“HashMap中所有對(duì)應(yīng)的集合”，它是一個(gè)集合；
get()：獲取key對(duì)應(yīng)的value；
put()：對(duì)外提供接口，讓HashMap對(duì)象可以通過put()將“key-value”添加到HashMap中；
putAll()：將"m"的全部元素都添加到HashMap中；
remove()：刪除“鍵為key”元素。

1.3 Leetcode上題目示例

q1 兩數(shù)之和

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的方式進(jìn)行求解
     * 使用hashmap存儲(chǔ)所有數(shù)字以及它們的index, 遍歷的時(shí)候看看互補(bǔ)的值是否已經(jīng)在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 字符串中第一個(gè)唯一字符

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中存儲(chǔ)所有的非重復(fù)的字母和它們的index,
     * 于此同時(shí)還需要使用hashSet存儲(chǔ)已經(jīng)出現(xiàn)的重復(fù)的key值,
     * 如果不為空返回第一個(gè)
     * 如果為空返回-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();
        }

    }


    /**
     * 使用簡(jiǎn)單的方式進(jìn)行求解，統(tǒng)計(jì)所有字母出現(xiàn)的頻率
     *
     * 然后再重新遍歷一遍字符串, 返回第一個(gè)出現(xiàn)頻率為1的結(jié)果
     */
    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 鏈表的結(jié)構(gòu)

多個(gè)節(jié)點(diǎn)之間，通過地址進(jìn)行連接。節(jié)點(diǎn)：兩個(gè)部分：數(shù)據(jù)域（存儲(chǔ)的數(shù)值），指針域（存儲(chǔ)地址）。

    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上題目示例以及做題的小方法

鏈表的題通常在比較了解了鏈表的數(shù)據(jù)結(jié)構(gòu)就比較好做，總的來說就是在遍歷鏈表，通過指針指向斷開鏈表以及形成循環(huán)鏈表等等。

Leetcode之中幾道題的思路

  1. q2 兩鏈表數(shù)字相加
    順序同時(shí)遍歷兩個(gè)鏈表（順序遍歷就是使用next指針進(jìn)行遍歷），將鏈表中的數(shù)字拿出來求和，于此同時(shí)更新下一步的進(jìn)位標(biāo)志。

  2. q19 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
    solution1: 兩次遍歷，一次遍歷得到鏈表的長(zhǎng)度，然后就知道要?jiǎng)h除的元素的位置，第二次遍歷更新指針把指定位置的元素刪除。
    solution2: 使用兩個(gè)指針，兩個(gè)指針之間距離N個(gè)位置，那么第二個(gè)指針指向?yàn)榭站椭酪獎(jiǎng)h除的元素是哪一個(gè)了。

  3. q61 按指定長(zhǎng)度旋轉(zhuǎn)鏈表
    先計(jì)算出來鏈表長(zhǎng)度，接著就可以計(jì)算得到需要旋轉(zhuǎn)的絕對(duì)長(zhǎng)度從而也就推導(dǎo)出來哪個(gè)節(jié)點(diǎn)是新的頭節(jié)點(diǎn)?？梢宰屾湵硎孜蚕噙B得到循環(huán)鏈表，然后在指定地方斷開鏈表，返回新的頭節(jié)點(diǎn)

  4. q138 復(fù)制帶隨機(jī)指針的鏈表
    這個(gè)很簡(jiǎn)單，就是新建所有想復(fù)制的節(jié)點(diǎn)，然后把它們key是源節(jié)點(diǎn)，value是復(fù)制節(jié)點(diǎn)的鍵值對(duì)放到hashmap中，然后就是可以根據(jù)hashmap中源節(jié)點(diǎn)的指向更新復(fù)制的節(jié)點(diǎn)之間的指向。

  5. q206 反轉(zhuǎn)鏈表
    這個(gè)根本思想其實(shí)是把鏈表分成兩部分，一部分是已經(jīng)反轉(zhuǎn)好的部分，另一部分是還未反轉(zhuǎn)的部分。就是改變未反轉(zhuǎn)部分的首節(jié)點(diǎn)指針的轉(zhuǎn)向，把其添加到反轉(zhuǎn)好的那部分，更新各個(gè)指針的位置。

以上幾道題的具體思路和代碼可以參考:我之前寫的Leetcode刷題之鏈表操作http://www.itdecent.cn/p/04b4b204bf50

補(bǔ)充的一道題

q25 k個(gè)一組翻轉(zhuǎn)鏈表

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 分組長(zhǎng)度
     * @param len 剩余需要計(jì)算的長(zhǎng)度
     * @return
     */
    public ListNode reverseGroup(ListNode head, int k, int len){

        if (head == null || k > len) return head;

        //prev指的是已經(jīng)反轉(zhuǎn)鏈表的頭節(jié)點(diǎn)
        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;
    }

    /**
     * 根據(jù)遞歸的方式進(jìn)行求解
     * 分組按長(zhǎng)度一次次進(jìn)行旋轉(zhuǎn)，然后把翻轉(zhuǎn)的部分和后面那部分連接起來，其實(shí)本質(zhì)上還是在反轉(zhuǎn)鏈表
     * @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;
        }
    }

}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容