# Yu's Coding Garden

My blog for LeetCode Questions and Answers...

## Sunday, April 23, 2017

## Wednesday, December 7, 2016

### leetcode Question: Single Number III

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

# Analysis:

**.**

*x = a^b*- We have a serise of numbers.
- We have value
, but we don’t know which two numbers are*x = a ^ b*and*a*.*b* - But we know, there must be at least one bit in
and*a*are NOT the same. (because*b*is NOT 0, there must be at least one bit in*x*is*x*)*1* - In other words, in a certain bit, say
**kth bit**,must be*a*and*0*must be*b*, or vice versa.*1* - Look at the array, every number in the array
**may be**a, or b. - For every number in the array，look at the
**kth bit**, it has only two possible values: 0 or 1. - So if we divide the number in the arrary simplely by the
*kth bit,***the array is divided into two part, and a and b must be in different part.** - For each part, except the number a (or b), all the other numbers must appear twice in the same part.
- Now the problem becomes the simple version of single number we have seen before.
- Done.

## Code (C++):

## Code (Python):

### leetcode Question: House Robber II

## House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

### Analysis:

*We have never seen the first house, but search and rob houses from 2nd to the last.*

*searching and robbing from 1st to the last -1 house.*