35.復雜鏈表的復制 難度：中等
本題核心：哈希表，用哈希表來存原鏈表的每個節點和新鏈表的每個節點，兩者是一一對應的關系，我們先存盤只帶有val的每一個新節點，那么哈希表中存盤的每一個舊節點和每一個新節點都是key-value的關系，接下來就是通過這種關系讓新節點的next和random指向正確的節點，最后回傳新節點的頭結點即可，
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head == null) return null;
ListNode newHead = new ListNode(-1);
newHead.next = head;
ListNode cur = head;
ListNode pre = newHead;
while(cur != null){
if(cur.val == val){
pre.next = cur.next;
}
pre = cur;
cur = cur.next;
}
return newHead.next;
}
}
50.第一個只出現一次字符 難度：簡單
本題用哈希表可以很簡便地解決，關鍵點在于key-value鍵值對型別是Character-Boolean，Character：對應每一個字符，Boolean：對應該字符是否只出現一次，若只出現一次為true，否則為flase，將每個字符存盤到哈希表中后，再從原先字串的順序遍歷，判斷每個字符對應的value值，得到第一個只出現一次的字符，
class Solution {
public char firstUniqChar(String s) {
Map<Character,Boolean> map = new HashMap<>();
char[] ch = s.toCharArray();
for(char c : ch){
map.put(c,!map.containsKey(c));
}
for(char c : ch){
if(map.get(c)) return c;
}
return ' ';
}
}
48. 最長不含重復字符的子字串 難度：中等
本題的主要思想是動態規劃，但是需要用到哈希表來存盤資料，tmp是以當前字符為尾字符的最長不含重復字符字串的最大長度，res為當前遍歷到的最長不包含重復字符的字串的最大長度，
哈希表中存盤的key：字串中的字符，value：該字符在字串中的下標，
因為字符有可能是重復的，所以當遍歷到重復字符時，會重繪哈希表中該字符的value值，而 i 為字符在這次重繪前該字符的下標，那么當前的i和j對應的就是該字串中相同的兩個字符下標，j - i就是 以 j 對應的字符為尾字符的字串長度，
但是j-i這個字串里面可能有其他重復字符，所以我們將tmp與j-i來比較，重繪tmp的值，讓tmp存盤的是不含重復字符的子字串長度，
如果tmp >= j - i,說明j-i對應字串在tmp對應字串中，那么將tmp重繪為j-i，
如果tmp < j - i,說明 j - i 對應的字串中包含tmp對應的字串，那么j-i中必然有重復字符，所以將不能將tmp重繪為j-i，只需要將tmp+1即可，
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap<>();
int tmp = 0;
int res = 0;
for(int j = 0; j < s.length(); ++j){
int i = map.getOrDefault(s.charAt(j),-1);
map.put(s.charAt(j),j);
tmp = (tmp < j-i) ? tmp+1 : j-i;
res = Math.max(res,tmp);
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353394.html
標籤：其他
下一篇：鏈表經典面試題（含圖解）