It's the Xinrui Ma

# Blog

## 3. Longest Substring Without Repeating Characters

Posted by in on

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.

Algorithm:

By using HashSet as a sliding window, checking if a character in the current can be done in O(1)O(1).

A sliding window is an abstract concept commonly used in array/string problems. A window is a range of elements in the array/string which usually defined by the start and end indices, i.e. [i, j)[i,j) (left-closed, right-open). A sliding window is a window “slides” its two boundaries to the certain direction. For example, if we slide [i, j)[i,j) to the right by 11 element, then it becomes [i+1, j+1)[i+1,j+1) (left-closed, right-open).

Back to our problem. We use HashSet to store the characters in current window [i, j)[i,j) (j = ij=i initially). Then we slide the index jj to the right. If it is not in the HashSet, we slide jj further. Doing so until s[j] is already in the HashSet. At this point, we found the maximum size of substrings without duplicate characters start with index ii. If we do this for all ii, we get our answer.

The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.

Key idea: If we find str.charAt(j) already exists in map at position k, we change our i to k + 1.

Solution:

## 461. Hamming Distance

Posted by in on

Total Accepted: 36432
Total Submissions: 51340
Difficulty: Easy
Contributors: Samuri
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

The above arrows point to positions where the corresponding bits are different.

## 260. Single Number III

Posted by in on

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Take a look at my previous post: http://maxinrui.com/index.php/2016/09/27/136-single-number-leetcode/

“Two same integers after XOR operation, the value is 0, and 0 XOR any integer is the integer itself”

Assume there are b and c that only appear once in the array, so, if we follow the same steps, perform XOR operation on each array elements, we could end up getting b ^ c;

What could b ^ c do for us?

It would be much simpler if the array can be split into two arrays that each only contain b or c, then we just do a XOR to all elements in each array, we could get the b and c.

That’s what b ^ c can do for us.

As we know, there must be a Kth bit of b and c that is different, otherwise they will be the same. Find the Kth bit that is different, we can use that to split the array into two arrays.

## 137. Single Number II LeetCode

Posted by in on

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

So when it comes with word like that “without using extra memory”, I will think of bit manipulation.

Since integer is 32 bits, and integers appears exactly three times except for one, so on the bit level, every bit of will be either 0 or 1, for all integers appears three times,the sum of them on the bit level will be a multiple of 3, after we do a mod 3, the result will be 0. so the only one that will not be 0 after mod 3, is the one that appear only once.

## 136. Single Number — LeetCode

Posted by in on

Given an array of integers, every element appears twice except for one. Find that single one.

Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Thought:

I can do this in Hash table, but that doesn’t meet the requirement ” implement it without using extra memory”

So, Hash table is not a best answer.

I read that operation about bit manipulation last night and that is a fact I found:

“Two same integers after XOR operation, the value is 0, and 0 XOR any integer is the integer itself”

So the condition is that “every element appears twice except for one”

So just do XOR for every element in the array, the final result is the integer we are looking for.

## Remove Element

Posted by in on

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Hint:

Try two pointers.

## How to implement Generic Binary Search Tree in Java

Posted by in Java on

First, you have to define the tree node with a Generic Type T

Then, we could define the BST methods and variable. Below code will be updated.