## leetcode-137. Single Number II[很有意思的一道题目]

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?

```class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
one, two, three = 0, 0, 0
for v in nums:
two |= one & v
one ^= v
three = ~(one & two)
one &= three
two &= three
return one

one&two的结果的某个比特位＝＝1，说明one中的该比特位与two中的

## leetcode－287. Find the Duplicate Number［Floyd算法－龟兔算法］

http://keithschwarz.com/interesting/code/find-duplicate/FindDuplicate.python.html

```这道题（据说）花费了计算机科学界的传奇人物Don Knuth 24小时才解出来。并且我只见过一个人（Keith Amling）用更短时间解出此题。

x_0     = k       (for some k)
x_1     = f(x_0)
x_2     = f(f(x_0))
...
x_{n+1} = f(x_n)

x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
^                       |
|                       |
+-----------------------+

x_{l'} = x_{2l'}

Floyd算法的一个关键点就是即使我们不明确知道c的值，依然可以在O(l')时间内找到值l'。思路如下。我们追踪两个值"slow"和"fast"，均从x_0开始。然后迭代计算

slow = f(slow)
fast = f(f(fast))

finder = f(finder)
slow   = f(slow)

(1) 两者一定会相遇
(2) 它们会在环的入口相遇。

Python程序如下：```
```class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
fast = 0
slow = 0

while True:
fast = nums[nums[fast]]
slow = nums[slow]
if slow == fast:
break

fast = 0
while fast != slow:
fast = nums[fast]
slow = nums[slow]

return fast```

## leetcode-287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than
O(n<sup>2</sup>)

.

4. There is only one duplicate number in the array, but it could be repeated more than once.

1.不能修改数组（假设数组只读）

2.空间复杂度为O(1)

3.时间复杂度小于O(n^2)

4.数组中只有一个重复数字，但是它可能重复不止一次。

```class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
right = len(nums)-1
left = 1

while left < right:
mid = left + (right-left)/2
counter = 0
for num in nums:
if num <= mid:
counter += 1
if counter > mid:
right = mid－1
else:
left = mid+1
return left```

## leetcode-41.First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given

[1,2,0]

return

3

,
and

[3,4,-1,1]

return

2

.

Your algorithm should run in O(n) time and uses constant space.

［1，2，0］ 返回 3

［3，4，－1，1］返回2

Python代码示例：

```class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i = 0
while i < len(nums):
if nums[i] != i+1 and nums[i] < len(nums) and nums[i] >= 1 and nums[i] != nums[nums[i]-1]:
tmp = nums[i]
nums[i] = nums[tmp-1]
nums[tmp-1] = tmp
else:
i += 1
print nums
for i in xrange(len(nums)):
if i+1 != nums[i]:
return i+1
return len(nums)+1```

## leetCode-319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

```Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.

```

## 题目来源：

https://leetcode.com/problems/palindrome-number/

## 题目描述：

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

## 我的AC：

<1>正逆序按位比较法     100ms

bool isPalindrome(int x) {
if (x < 0) return false;
if (x == 0) return true;
unsigned pdlen = 0, half=0;
while (jlen){//首先求出int长度
++pdlen;
jlen /= 10;
}
half = pdlen / 2;//分割数据
prefix = pow(10, half);
header = pdlen & 0x1 ? x / pow(10, half + 1) : x / pow(10, half);
tailer = x – x / prefix*prefix;

while (half){//按位判断
int div = pow(10, half – 1);
int htop = header / div;

int tbot = tailer % 10;
tailer /= 10;
if (htop != tbot) return false;
–half;
}
return true;
}

<2>单一逆序比较法   76ms

bool isPalindrome(int x) {
if (x < 0) return false;
if (x == 0) return true;
unsigned pdlen = 0, half=0;
while (jlen){
++pdlen;
jlen /= 10;
}
half = pdlen / 2;
prefix = pow(10, half);
header = pdlen & 0x1 ? x / pow(10, half + 1) : x / pow(10, half);
tailer = x – x / prefix*prefix;

//上面先求出数据长度

int mod = header % 10;
}
if (reverse_header != tailer) return false;
return true;
}

## 题目来源：

https://leetcode.com/problems/string-to-integer-atoi/

## 题目描述：

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the

C++

function had been updated. If you still see your function signature accepts a

const char *

spoilers alert… click to show requirements for atoi.

Requirements for atoi:The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

## 解题思路：

<1>int上下界的处理方法，比如要用long long类型的变量接收总和。并在总和计算循环中对上下界进行比较，防止最后的总和越过long long范围的情况发生。

<2>对于首个非空格字符为+ -两个字符的特殊考虑。

<3>对于字符开始的连续空格与计数开始之后出现的空格的处理

## 我的AC：

int myAtoi(string str) {
long long sum = 0;//用long long类型的变量接收总和，以防止可能的溢出。
const int max = 0x7fffffff, min = 0x80000000;//设置int的上下界
int flag = 1,sflag=0;
string::iterator is = str.begin();
while (is != str.end()){
char curChar = *is;
if (isdigit(curChar)){
if (curChar==’0’&&sum==0) ++is;//如果是字符是0，并且sum=0，那么这个0前面没有别的数字，跳过该0往后计算
else {
sum = sum * 10 + curChar – ‘0’;//否则计算sum
if (sum*flag > max) return max;//及时判断是否越界
if (sum*flag < min) return min;
++is;
}
sflag = 1;
}
else if (isspace(curChar)){//对空格的处理
if (sflag) break;//如果空格出现在计数数字之后，停止循环
++is;//如果空格出现在字符串最前面，继续循环
}
else if (curChar == ‘-‘ || curChar == ‘+’){//对+-号的处理
string::iterator is_tail = is + 1;
if (is_tail != str.end()){
if (isdigit(*is_tail)) {
if (curChar==’-‘) flag = -1;
}
else break;
}
++is;
}
else break;
}

return sum*flag;
}

## leetcode7 [Reverse Integer] [Easy，C++]

### 题目来源:

https://leetcode.com/problems/reverse-integer/

### 题目描述：

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Have you thought about this?Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.Update (2014-11-10):

### 自己的解题思路：

<1>int的范围边界

<2>c++中求余运算时的结果符号问题

==================================================================

#include “stdafx.h”
#include <string>
#include <vector>
#include <iostream>
using namespace::std;
#pragma warning(disable:4146)
class Solution {
public:
int reverse(int x) {
long long v = 0;
int max = 0x7fffffff, min = 0x80000000;//注意int最小负数的表示 1000 0000 0000 0000 0000 0000 0000 0000B===>80000000H
while (x){
int tmp = x % 10;//求余，其符号跟随x
v = v * 10 + tmp;//当前结果*10,然后累加余数
cout << v << endl;
if (v > max || v < min) return 0;//如果溢出，返回0
x = x / 10;
}

return v;
}
};

==================================================================

## leetcode-6 [ZigZag Conversion] [Easy,C++]

The string

"PAYPALISHIRING"

is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

```P   A   H   N
A P L S I I G
Y   I   R
```

And then read line by line:

"PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

`string convert(string text, int nRows);`
convert("PAYPALISHIRING", 3)

should return

"PAHNAPLSIIGYIR"

.

```P   A   H   N
A P L S I I G
Y   I   R

=============================================================================
1           7             d
2       6   8        c    e
3   5       9    b        f
4           a             g

==============================================================================

&lt;1&gt;上图每两条竖线之间的区域相当于一个n*n的n维矩阵。
&lt;2&gt;可以观察到如果矩阵同一行的元素是在竖线上的，那么他们之间的差值对于每一行来说都是等量的。那么这个差值是多少呢？
观察第一行的1 7，第二行的2 8。可以发现差值点之间会经过一条对角线,两条竖线的部分。而两条竖线的部分恰好是矩阵的一条边长。
那么去除重复点可以归纳出这个差值就是2*n-2=2*(n-1)。
&lt;3&gt;同时还会发现，同一行的两条竖线间最多会出现一个元素。该元素在数串中的位置也是有规律的。观察3与5之间经过的路径，2与6经过的路径会发现,他们之间的差值与左侧竖线元素的行数有很大的联系。2出现在第二行，当由2至6时，先向下经过了2个位置，又向右经过了2个位置到达6.再看3到5，3在第三行，3到5是向下一个向右1个位置。此时会得出结论，这个差值就是总行数与当前行的差值的1倍，即(numRows-currentRow)*2.

&lt;code&gt;
string convert(string s,int numRows){
int sz = s.size();
string ret;
int row = 1, pivot = 0;
while (row &lt;= numRows){
vector&lt;char&gt; v;
int next_pivot;
int b_pivot = pivot;
while (b_pivot &lt; sz){
v.push_back(s[b_pivot]);//存储当前元素
//此处有个例外，如果只有一行，那么下一个竖线的节点应该是当前节点直接+1
//否则要按照差值计算
if (numRows==1) next_pivot = 1 + b_pivot;//计算下一个竖线中在该行的节点
else next_pivot = 2 * (numRows - 1) + b_pivot;

int inside = next_pivot - 2 * (row-1);//计算两条竖线间属于该行的节点
if (inside != next_pivot&amp;&amp;inside != b_pivot&amp;&amp;inside&lt;sz){//如果竖线间存在节点,加入vector
v.push_back(s[inside]);
}
b_pivot = next_pivot;
}
//输出该行节点
for (vector&lt;char&gt;::iterator vi = v.begin(); vi != v.end(); ++vi){
ret.push_back(*vi);
}
cout &lt;&lt; endl;
++pivot;
++row;
}
return ret;
}
&lt;/code&gt;

```

## LeetCode 算法@001 -Two Sum

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

1.爆破法

2.哈希表

Java代码：

import java.util.HashMap;
public class twosum {
public static void main(String[] args){
int[] a={3,2,4};
int target=6;
int[] x=twoSum(a,target);
for(int y:x){System.out.println(y);}
}
public static int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map =new HashMap<Integer,Integer>();
int numLen = nums.length;
int[] res=new int;
for(int j=0;j<numLen;j++){
map.put(nums[j],j+1);
}
for(int i=0;i<numLen;i++){
int findIndex = target-nums[i];
if(map.containsKey(findIndex)&&map.get(findIndex)!=i+1) {
int foundIndex = map.get(findIndex);
if(foundIndex<(i+1)){res=foundIndex;res=i+1;}
else{res=foundIndex;res=i+1;}
break;
}
}
return res;
}
}