# Leetcode: 349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = `[1, 2, 2, 1]`nums2 = `[2, 2]`, return `[2]`.

Note:

• Each element in the result must be unique.
• The result can be in any order.
``````
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
int count = 0;
HashMap<Integer, Integer> twoSum1 = new HashMap<>();
HashMap<Integer, Integer> twoSum2 = new HashMap<>();

constructTwoPairMap(twoSum1, A, B);
constructTwoPairMap(twoSum2, C, D);
for (Integer pairSum : twoSum1.keySet()) {
count += twoSum1.get(pairSum) * twoSum2.getOrDefault(pairSum * (-1), 0);
}
return count;
}

public void constructTwoPairMap(HashMap<Integer, Integer> map, int[] A, int[] B) {
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B.length; j++) {
int sum = A[i] + B[j];
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
}
``````

# Bit Manipulation

1. Extract the last set bit

x & (-x)

eg.  x: 00110010

-x: 11001101 + 1 = 11001110

x & (-x) = 00000010

2. Remove the last set bit

x – x & (-x)

# Partition Array

1. with target outside the array

```    public int partitionArray(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
while (left <= right && nums[left] < k) {
left++;
}
while (left <= right && nums[right] >= k) {
right--;
}
if (left < right) {
swap(nums, left, right);
left++;
right--;
}
}
return left;
}

public void swap(int[] nums, int a, int b) {
int tmp = nums[a];
nums[a] = nums[b];
nums[b] = tmp;
}```

2. with target with in the array(Quick select)

# Implement rand7() using rand5()

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5 (i.e., implement rand7() using rand5()).

## 解答

rand5可以随机生成1,2,3,4,5；rand7可以随机生成1,2,3,4,5,6,7。 rand5并不能直接产生6，7，所以直接用rand5去实现函数rand7似乎不太好入手。 如果反过来呢？给你rand7，让你实现rand5，这个好实现吗？

```<code class="language-cpp" data-lang="cpp"><span class="kt">int</span> <span class="nf">Rand5</span><span class="p">(){</span>
<span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
<span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">5</span><span class="p">)</span>
<span class="n">x</span> <span class="o">=</span> <span class="n">Rand7</span><span class="p">();</span>
<span class="k">return</span> <span class="n">x</span><span class="p">;</span>
<span class="p">}</span></code>```

```<code>P(x=1)=1/7 + (2/7) * 1/7 + (2/7)^2 * 1/7 + (2/7)^3 * 1/7 + ...
=1/7 * (1 + 2/7 + (2/7)^2 + ...) // 等比数列
=1/7 * 1 / (1 - 2/7)
=1/7 * 7/5
=1/5
</code>```

```<code class="language-cpp" data-lang="cpp"><span class="c1">// a &gt; b</span>
<span class="kt">int</span> <span class="nf">Randb</span><span class="p">(){</span>
<span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
<span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">b</span><span class="p">)</span>
<span class="n">x</span> <span class="o">=</span> <span class="n">Randa</span><span class="p">();</span>
<span class="k">return</span> <span class="n">x</span><span class="p">;</span>
<span class="p">}</span></code>```

```<code>Rand5() + Rand5() - 1
</code>```

```<code>5 * (Rand5() - 1) + Rand5()
</code>```

Rand5产生1到5的数，减1就产生0到4的数，乘以5后可以产生的数是：0,5,10,15,20。 再加上第二个Rand5()产生的1,2,3,4,5。我们可以得到1到25， 而且每个数都只由一种组合得到，即上述代码可以等概率地生成1到25。OK， 到这基本上也就解决了。

```<code class="language-cpp" data-lang="cpp"><span class="kt">int</span> <span class="nf">Rand7</span><span class="p">(){</span>
<span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
<span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">7</span><span class="p">)</span>
<span class="n">x</span> <span class="o">=</span> <span class="mi">5</span> <span class="o">*</span> <span class="p">(</span><span class="n">Rand5</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">Rand5</span><span class="p">()</span> <span class="c1">// Rand25</span>
<span class="k">return</span> <span class="n">x</span><span class="p">;</span>
<span class="p">}</span></code>```

```<code class="language-cpp" data-lang="cpp"><span class="kt">int</span> <span class="nf">Rand7</span><span class="p">(){</span>
<span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
<span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="mi">21</span><span class="p">)</span>
<span class="n">x</span> <span class="o">=</span> <span class="mi">5</span> <span class="o">*</span> <span class="p">(</span><span class="n">Rand5</span><span class="p">()</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">+</span> <span class="n">Rand5</span><span class="p">()</span> <span class="c1">// Rand25</span>
<span class="k">return</span> <span class="n">x</span><span class="o">%</span><span class="mi">7</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span></code>```

1. 如果a > b，进入步骤2；否则构造Randa2 = a * (Randa – 1) + Randa， 表示生成1到a2 随机数的函数。如果a2 仍小于b，继教构造 Randa3 = a * (Randa2 – 1) + Randa…直到ak > b，这时我们得到Randak , 我们记为RandA。
2. 步骤1中我们得到了RandA(可能是Randa或Randak )，其中A > b， 我们用下述代码构造Randb：
```<code class="language-cpp" data-lang="cpp"><span class="c1">// A &gt; b</span>
<span class="kt">int</span> <span class="nf">Randb</span><span class="p">(){</span>
<span class="kt">int</span> <span class="n">x</span> <span class="o">=</span> <span class="o">~</span><span class="p">(</span><span class="mi">1</span><span class="o">&lt;&lt;</span><span class="mi">31</span><span class="p">);</span> <span class="c1">// max int</span>
<span class="k">while</span><span class="p">(</span><span class="n">x</span> <span class="o">&gt;</span> <span class="n">b</span><span class="o">*</span><span class="p">(</span><span class="n">A</span><span class="o">/</span><span class="n">b</span><span class="p">))</span> <span class="c1">// b*(A/b)表示最接近A且小于A的b的倍数</span>
<span class="n">x</span> <span class="o">=</span> <span class="n">RandA</span><span class="p">();</span>
<span class="k">return</span> <span class="n">x</span><span class="o">%</span><span class="n">b</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
<span class="p">}</span></code>```

```<code>Randab = b * (Randa - 1) + Randb
Randab = a * (Randb - 1) + Randa
</code>```

Cracking the coding interview–问题与解答

reference: http://www.hawstein.com/posts/19.10.html

# Longest Consecutive Sequence

#### Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Example

Given `[100, 4, 200, 1, 3, 2]`,
The longest consecutive elements sequence is `[1, 2, 3, 4]`. Return its length: `4`.

Clarification

Your algorithm should run in O(n) complexity.

Solution: 建一个hash表 对每一个num[i]上下浮动寻找num[i]+1, num[i]+2, …, 和num[i]-1, num[i]-2, …是不是在表里 如果找到的话就把该数从hash表里删除避免重复查找，所以建表时间是O(n) 每个数只会被访问一次，所以时间复杂度是O(n).

```public int longestConsecutive(int[] num) {
Set<Integer> numSet = new HashSet<>();
for (int i = 0; i < num.length; i++) {
}
int maxLength = 0;
for (int i = 0; i < num.length; i++) {
if (numSet.contains(num[i])) {
int length = 1;
int curr = num[i] - 1 ;
while (numSet.contains(curr)) {
numSet.remove(curr);
length++;
curr--;
}
curr = num[i] + 1;
while (numSet.contains(curr)) {
numSet.remove(curr);
length++;
curr++;
}
if (length > maxLength) {
maxLength = length;
}
}
}
return maxLength;
}```