It's the Xinrui Ma

Blog

Tag: Java

260. Single Number III

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?

Answer:

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

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?

Answer:

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

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 Java LeetCode 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).

LeeCode: Summary Ranges answer in JavaScript and Java

Posted by in LeetCode on

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return [“0->2″,”4->5″,”7”].

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

Reverse a singly linked list.

Posted by in LeetCode on

Reverse a singly linked list.

click to show more hints.

Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution in Java: