0%

• hashtable简洁即实现
• 3 Longest Substring Without Repeating Characters
• 160 Intersection of Two Linked Lists
• 202 Happy Number
• 242 Valid Anagram

## 一、hashtable简介

• 若关键字为k，则其值存放在f(k)的存储位置上。由此，要查找k的位置直接去f(k)查找即可。
• 对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突/碰撞（Collision）。可以说collision是不可避免的。但是有一些处理冲突的办法：

• 开散列：相同的key 存于链中
• 闭散列：相同key存于 不同的槽中
• 多个hashtable ： 如果一个冲突的概率是0.1.。那么我们用两个不同的散列函数，可以大大冲突概率。（暴雪好像就是这么做的，用了三个散列表，使得冲突概率为几亿分之一）

（C++可以把define改为const int N = 1<<7; ）

leetcode 202 Happy Number为例，来演示一下他们的用法：

## 二、题解

### 3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

1. 若该字符在hash表中，则说明s[j]在之前出现过，我们需要删除hash表中的字符s[i....vis[s[j]]]中的所有信息。并且将i 设置为 vis[s[j]] += 1（因为vis[s[j]]保存了上一个s[j]的下标，必须+1的位置才可能作为新的起点）
2. 将该字符的下表写进hash表。 就是vis[s[j]] = j
3. 看看能否更新最大长度。

Python

C++

Java

Python

dp[j]为以s[j]结尾不重复字符的长度， i = vis[s[j]]则为s[j]字符上一次出现的位置。

• j - i < dp[j - 1]： 说明上一次出现的位置在j - 1的子串里，只能重新开始，dp[j] = j - i
• j - i > dp[j - 1]： 说明上一次出现的位置不在j - 1的子串里面，因此dp[j] = dp[j - 1] + 1

### 160. leetcode Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

• 用哈希表O(n+m) 空间为O(m)或者O(n)
• 由于两个链表可能一长一短，故对其同时进行遍历时一定有一个先到达结尾。如果链表A先到结尾，则指向B的开头，如果B先到达结尾，则指向A的开头。然后继续进行遍历，这样两个链表一定同时到达结尾。当到达结尾时，如果之前最早出现过两个指针指向地址相同的，那么就是所求解。

c 的hash表

### 202 leetcode Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

1. 用hash表判断是否循环，若循环则不是happy number
2. 4为非happy number循环必经点。所以可以判断n是否为4即可。（这个是看discuss的）

C

C++

Python

### 242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false.

Note: You may assume the string contains only lowercase alphabets.

Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case?