It's the Xinrui Ma

# Blog

## 387. First Unique Character in a String

Posted by in LeetCode on

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.

## 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:

## 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.

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

Posted by in LeetCode on

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.

Solution in Java:

## Majority Element: Answers in Java & JavaScript

Posted by in LeetCode on

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

Solution one using Hashtable in Java:

Since the element which appears for more than n/2 times in the array, it should always appear at the middle of a sorted one. After we sort it, simply return the number in the middle will solve the problem.

## Two Sum

Posted by in LeetCode on

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution in Java, version 1:
Time complexity in worst case: O(n^2).

Better Solution in Java, using HashTable.

Time complexity depends on the put and get operations of HashMap which is normally O(1).

Time complexity of this solution is O(n).