LeetCode题目：Maximal Rectangle

Maximal Rectangle
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

```struct Size{
int width;
int height;
void set(int w, int h){
width = w;
height = h;
}
int area(){
return width * height;
}
};
class Solution {
public:
int maximalRectangle(vector > &matrix) {
int rows = matrix.size();
if(rows == 0) return 0;
int cols = matrix[0].size();
if(cols == 0) return 0;
Size *map = new Size[rows * cols];
for(int ir = 0; ir < rows; ++ir) {
int left1s = 0;
for(int ic = 0; ic < cols; ++ic) {
if(matrix[ir][ic] == '1'){
++left1s;
} else {
left1s = 0;
}
(map + ir * cols + ic)->width = left1s;
}
}
for(int ic = 0; ic < cols; ++ic) {
int up1s = 0;
for(int ir = 0; ir < rows; ++ir) {
if(matrix[ir][ic] == '1'){
++up1s;
} else {
up1s = 0;
}
(map + ir * cols + ic)->height = up1s;
}
}
int maxArea = 0;
for(int ir = rows - 1; ir >= 0; --ir) {
for(int ic = cols - 1; ic >= 0; --ic) {
Size *cur = (map + ir * cols + ic);
if(cur->width > 0 && cur->height > 0) {
int minwidth = cols;
for(int h = 0; minwidth > 0 && h <= ir; ++h) {
Size *sup = (map + (ir - h) * cols + ic);
if(minwidth > sup->width) {
minwidth = sup->width;
}
int newarea = minwidth * (h + 1);
if(newarea > maxArea) maxArea = newarea;
}
}
}
}
return maxArea;
}
};
```

LeetCode题目：Longest Valid Parentheses

Longest Valid Parentheses
Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

```struct Info{
int index;
int bonus;
};
class Solution {
public:
int longestValidParentheses(string s) {
vector ls;//left parentheses that not matched
int maxlen = 0;
int curBonus = 0;
for(int i = 0 ; i < s.size(); ++i) {
if(s[i] == '(') {
Info info;info.index = i;info.bonus = curBonus;
curBonus = 0;
ls.push_back(info);
} else {
curBonus = 0;
if(ls.size() > 0) {
Info lastleft = ls[ls.size() - 1];
ls.pop_back();
int len = i - lastleft.index + 1 + lastleft.bonus;
curBonus = len;
if(maxlen < len)
maxlen = len;
}
}
}
return maxlen;
}
};
```

LeetCode题目：Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

```class Solution {
public:
int lengthOfLongestSubstring(string s) {
int map[256];
const int notFound = -1;
for(int i = 0 ; i < 256; ++i){
map[i] = notFound;
}
int maxlen = 0;
int len = 0;
for(int i = 0 ; i < s.size(); ++i) {
char si = s[i];
int lastSi = map[si];
if(lastSi == notFound) {
++len;
map[si] = i;
if(maxlen < len)
maxlen = len;
} else {
int curStart = i - len;
for(int j = curStart; j < lastSi; ++j) {
map[s[j]] = notFound;
}
curStart = lastSi + 1;
len = i - curStart + 1;
map[si] = i;
}
}
return maxlen;
}
};
```

New ruby solution at 2016-04-22

```# @param {String} s
# @return {Integer}
def length_of_longest_substring(s)
max = 0
c2imap = {}
si = -1
s.chars.each_with_index do |c, i|
if ci = c2imap[c] and ci > si
si = ci
end
c2imap[c] = i
new_length = i - si
max = new_length if max < new_length
end
max
end
```

LeetCode题目：Longest Palindromic Substring，二维动态规划

Updated at 2016-04-28

Question

Longest Palindromic Substring
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Analyze

The brute force method will take O(n3) time, and apparently, it will exceed the time limit.

To reduce the time, as we noticed there are a lot of duplicated comparisons in the brute force method, the first thought is dynamic programming. But I was too aggressive at the begging, want to solve this with 1-D dynamic programming in O(n) time.

After find out several exceptional cases with either focus on the start of substring or the end of substring, I realized that it can not fit into a 1-D dynamic programming. But 2-D, can easily beat this question.

2-D Dynamic Programming

Let’s focus on the start index `si` and end index `ei` of the substring. When we want answer the question: “Is the substring s[si..ei] palindromic?”, we just check if s[si + 1 .. ei – 1] is palindromic and if s[si] == s[ei]. If both conditions are true, then we can get the positive answer. Then if we solve the problem in this order:

```for(int ei = 0; ei < s.length(); ei ++)
for(int si = ei; si >= 0; si --)
{ // implement here }
```

Then we can make sure when we resolve sub problem on (si, ei), we know the answer of (si+1, ei-1). So, just build a 2-D matrix and we can beat this question in O(n2) time.

Expand from center

That’s the DP solution. And since it’s O(n2), then there is a more straight forward method with the same time level:
Just at each point in the string S, on the positions of it’s characters like 0,1,2,… or between characters like 0.5, 1.5, … . Then from this position, just expand the substring if it is still palindromic. Then there are O(n) centers and at each center, we need expand O(n) times. Thus, this is also a O(n2) time solution. And simpler.

Codes

Ruby version DP

```def longest_palindrome(s)
map = {}
max_si, max_ei, max_length = nil, nil, 0
s.length.times do |ei|
si = ei
while si >= 0 do
if si == ei
map[ei] = { si => true }
else
map[ei][si] = s[ei] == s[si] && (si + 1 >= ei || map[ei - 1][si + 1] == true)
end

len = (ei - si + 1)
if map[ei][si] && len > max_length
max_length = len
max_si = si
max_ei = ei
end

si -= 1
end
end

s[max_si..max_ei]
end
```

Ruby version expand from center

```def expand(s, center)
li, ri = center.floor, center.ceil
if li == ri
li -= 1
ri += 1
end
left_space = li
right_space = s.length - ri - 1
max_space = [left_space, right_space].min
most_left = li - max_space
while li >= most_left do
if s[li] == s[ri]
li -= 1
ri += 1
else
break
end
end
#p [ri - li - 1, li + 1, ri - 1]
[ri - li - 1, li + 1, ri - 1]
end

def longest_palindrome(s)
i = 0
max_si, max_ei, max_len = nil, nil, 0
while i <= s.length - 1 do
len, si, ei = expand(s, i)
if max_len < len
max_si, max_ei, max_len = si, ei, len
end
i += 0.5
end
s[max_si..max_ei]
end
```

C++ version DP

```class Solution {
public:
inline void setIsPalindrome(bool * dpmap, int si, int ei, int total_length, bool value) {
*(dpmap + total_length * ei + si) = value;
}
inline bool isPalindrome(bool * dpmap, int si, int ei, int total_length) {
return *(dpmap + total_length * ei + si);
}
string longestPalindrome(string s) {
int total_length = s.length();
int max_len = 0, max_si, max_ei;
bool *dpmap = new bool[total_length * total_length];
for(int ei = 0; ei < total_length; ei++) {
for(int si = ei; si >= 0; si--) {
bool positive =
(si == ei) ||
((s[si] == s[ei]) && ((si == ei - 1) || isPalindrome(dpmap, si + 1, ei - 1, total_length)));
setIsPalindrome(dpmap, si, ei, total_length, positive);
if(positive){
int len = ei - si + 1;
if(max_len < len){
max_len = len;
max_si = si;
max_ei = ei;
}
}
}
}
delete dpmap; dpmap = NULL;
return s.substr(max_si, max_len);
}
};
```

旧版，有误，奇怪的是当初竟然通过了测试…

1.在子函数longestCommonSub中，如果先new，在得到最长公共串之后delete申请的空间mat的话，运行到大概第5个test case的时候会报runtime error。
2.在代码段

`if(max <= len)`

```class Solution {
public:
string longestCommonSub(string &sa, string &sb) {
int rows = sa.size() + 1;
int cols = sb.size() + 1;
static int *mat = NULL;
if(NULL == mat) {
mat = new int[1001 * 1001];
}
for(int ir = 0 ; ir < rows; ++ ir) {
for(int ic = 0 ; ic < cols; ++ ic) {
*(mat + ir * cols + ic) = 0;
}
}
int max = 0;
int maxIr;
for(int ir = 1 ; ir < rows; ++ ir) {
char sai = sa[ir - 1];
for(int ic = 1 ; ic < cols; ++ ic) {
if(sai == sb[ic - 1]){
int len = 1 + *(mat + (ir-1) * cols + ic - 1);
*(mat + ir * cols + ic) = len;
if(max <= len) {
max = len;
maxIr = ir;
}
}
}
}
string result;
if(max > 0) {
result = sa.substr(maxIr - max, max);
}
return result;
}
string longestPalindrome(string s) {
string rs = s;
for( int i = 0 ; i < s.size(); ++ i) {
rs[i] = s[s.size() - 1 - i];
}
return longestCommonSub(s,rs);
}
};
```

LeetCode题目：Longest Common Prefix

Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.

```class Solution {
public:
string longestCommonPrefix(vector &strs) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
string result;
char common;
int curCharIndex = 0;
for(int istr = 0 ; istr < strs.size() ; ++istr) {
string &str = strs[istr];
if(curCharIndex >= str.size())
return result;
if(istr == 0 ) {
common = str[curCharIndex];
}else if(str[curCharIndex] != common) {
return result;
}
if(istr == strs.size() - 1) {
result.push_back(common);
++curCharIndex;
istr = -1;
}
}
return result;
}
};
```

<br>

用scp命令和远程服务器之间传送文件

scp aLocalFilePathName remoteUser@remoteServer:targetFilePathName

LeetCode题目：Letter Combinations of a Phone Number

Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

```class Solution {
public:
vector letterCombinations(string digits) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector >map(10);
map[0] = vector(1);

map[0][0] = ' ';
map[1] = vector(1);
map[1][0] = ' ';

map[2] = vector(3);
map[2][0] = 'a';
map[2][1] = 'b';
map[2][2] = 'c';

map[3] = vector(3);
map[3][0] = 'd';
map[3][1] = 'e';
map[3][2] = 'f';

map[4] = vector(3);
map[4][0] = 'g';
map[4][1] = 'h';
map[4][2] = 'i';

map[5] = vector(3);
map[5][0] = 'j';
map[5][1] = 'k';
map[5][2] = 'l';

map[6] = vector(3);
map[6][0] = 'm';
map[6][1] = 'n';
map[6][2] = 'o';

map[7] = vector(4);
map[7][0] = 'p';
map[7][1] = 'q';
map[7][2] = 'r';
map[7][3] = 's';

map[8] = vector(3);
map[8][0] = 't';
map[8][1] = 'u';
map[8][2] = 'v';

map[9] = vector(4);
map[9][0] = 'w';
map[9][1] = 'x';
map[9][2] = 'y';
map[9][3] = 'z';

vector result;
result.push_back("");
for(int idigit = 0; idigit < digits.size(); ++ idigit) {
char di = digits[idigit];
int index = di - '0';
if(index < 0 || index > 9)
continue;
vector &dmap = map[index];
int curSize = result.size();
int times = dmap.size();
for(int itime = 0; itime < times - 1; ++itime) {
for(int itemp = 0; itemp < curSize; ++itemp) {
result.push_back(result[itemp]);
}
}
for(int itime = 0; itime < times ; ++itime) {
char append = dmap[itime];
for(int itemp = 0; itemp < curSize; ++itemp) {
int itemIndex = itime * curSize + itemp;
if(itemIndex >= result.size()) {
cout<<"d";
continue;
}
result[itemIndex].push_back(append);
}
}
}
return result;
}
};
```

LeetCode题目：Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = “Hello World”,
return 5.

```class Solution {
public:
int lengthOfLastWord(const char *s) {
int beginAt = 0;
int lastLen = 0;
bool inword = false;
int i = 0;
for( ;s[i] != '\0'; ++i) {
if(s[i] == ' ') {
if (inword) {
lastLen = i - beginAt;
inword = false;
}
} else if (!inword) {
beginAt = i;
inword = true;
}
}
if (inword) {
lastLen = i - beginAt;
}
return lastLen;
}
};
```

LeetCode题目：Jump Game II，一维动态规划，贪心

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

```class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int minstep = 0;
int ldist = 0;
int hdist = 0;
if (n == 1) return 0;
while(ldist <= hdist) {
++minstep;
int lasthdist = hdist;
for(int i = ldist; i <= lasthdist; ++i) {
int possibledist = i + A[i];
if (possibledist >= n-1)
return minstep;
if (possibledist > hdist) {
hdist = possibledist;
}
}
ldist = lasthdist + 1;
}
return 0;
}
};
```

```class Solution {
public:
int jump(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n <= 1)
return 0;
const int noWay = n + 1;
int *jumps = new int[n];
jumps[n-1] = 0;
for(int i = n - 2; i >= 0; -- i) {
int lenJump = A[i];
int minJumps = noWay;
for(int j = i + 1; j <= i + lenJump && j < n; ++ j) {
if(jumps[j] + 1 < minJumps)
minJumps = jumps[j] + 1;
}
jumps[i] = minJumps;
}
return jumps[0];
}
};
```

LeetCode题目：Jump Game，一维动态规划

`vector`

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

```class Solution {
public:
bool canJump(int A[], int n) {
//if (n > 100) return false;
if (n <= 1)
return true;
//vector canJump(n, false);
bool *canJump = new bool[n];
canJump[n - 1] = true;
for( int i = n - 2; i >= 0; --i ) {
int maxJump = A[i];
for(int j = i + 1; j <= i + maxJump && j < n ; ++j) {
if (canJump[j]) {
canJump[i] = true;
break;
}
}
}
return canJump[0];
}
};
```

```class Solution {
public:
bool canJump(int A[], int n) {
if (n <= 1)
return true;
vector canJump(n, false);
canJump[n - 1] = true;
for( int i = n - 2; i >= 0; --i ) {
int maxJump = A[i];
if (i + maxJump >= n)
maxJump = n - i;
for(int j = i + maxJump; j > i; --j) {
if (canJump[j]) {
canJump[i] = true;
break;
}
}
}
return canJump[0];
}
};
```

LeetCode题目：Largest Rectangle in Histogram

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.

```struct Record{
int minHeight;
int start;
int areaToIndex(int index) {return (index - start + 1) * minHeight;}
};

class Solution {
public:
int largestRectangleArea(vector &height) {
//if(height.size() > 1000) return 0;
if(height.size() == 0)
return 0;
unsigned int count = height.size();
int *hs = new int[count];
for( int i = 0 ; i < count; ++i ) {
hs[i] = height[i];
}
int max = 0;
for(int i = 0 ; i < count; ++i) {
int hi = hs[i];
if(hi * count <= max) continue;
int mostLeft = i;
for(int pre = i - 1; pre >= 0 && hs[pre] >= hi; --pre) {
mostLeft = pre;
}
if(hi * (count - mostLeft) <= max) continue;
int mostRight = i;
for(int post = i + 1; post < count && hs[post] >= hi; ++post) {
mostRight = post;
}
int area = hi * (mostRight - mostLeft + 1);
if (max < area) max = area;
}
return max;
}
};
```

```class Solution {
public:
int largestRectangleArea(vector &height) {
int maxArea = 0;
for(int first = 0; first < height.size(); ++first) {
for(int last = first; last< height.size(); ++last) {
int minH = height[first];
for(int i = first + 1; i <= last; ++i) {
if(minH > height[i]) {
minH = height[i];
}
}
int area = minH * (last - first + 1);
if(maxArea < area)
maxArea = area;
}
}
return maxArea;
}
};
```

LeetCode题目：Interleaving String，二维动态规划

<br>

`bool isInterleaving(string &s1, int len1, string &s2, int len2, string &s3, int len3);`

```isInterleaving(s1,len1,s2,len2,s3,len3)
=   (s3.lastChar == s1.lastChar) && isInterleaving(s1,len1 - 1,s2,len2,s3,len3 - 1)
||(s3.lastChar == s2.lastChar) && isInterleaving(s1,len1,s2,len2 - 1,s3,len3 - 1)
```

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = “aabcc”,
s2 = “dbbca”,
When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.

```class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
//create indicator
vector > match(s1.size() + 1, vector(s2.size() + 1, false));
//initialization the first row and the first column
match[0][0] = true;
for( int l1 = 1; l1 <= s1.size(); ++ l1 ) {
char c1 = s1[l1 - 1];
char c3 = s3[l1 - 1];
if (c1 == c3) {
match[l1][0] = true;
} else
break;
}
for( int l2 = 1; l2 <= s2.size(); ++ l2 ) {
char c2 = s2[l2 - 1];
char c3 = s3[l2 - 1];
if (c2 == c3) {
match[0][l2] = true;
} else
break;
}
//work through the rest of matrix using the formula
for( int l1 = 1; l1 <= s1.size(); ++ l1 ) {
char c1 = s1[l1 - 1];
for( int l2 = 1 ; l2 <= s2.size() ; ++ l2 ) {
char c2 = s2[l2 - 1];
int l3 = l1 + l2;
char c3 = s3[l3 - 1];
if (c1 == c3) {
match[l1][l2] = match[l1 - 1][l2] || match[l1][l2];
}
if (c2 == c3) {
match[l1][l2] = match[l1][l2 - 1] || match[l1][l2];
}
}
}
//the last element is the result
return match[s1.size()][s2.size()];
}
};
```

```class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
int i1 = 0;
int i2 = 0;
for(int i3 = 0 ; i3 < s3.size(); ++i3) {
if(i1 < s1.size() && s1[i1] == s3[i3]) {
++i1;
} else if (i2 < s2.size() && s2[i2] == s3[i3]) {
++i2;
} else
return false;
}
return true;
}
};
```

```class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
vector visited(s3.size(),false);
int i3 = 0;
for( int i1 = 0; i1 < s1.size() ; ++i1 ) {
bool match = false;
while(i3 < s3.size()) {
if(s3[i3] == s1[i1]) {
visited[i3 ++] = true;
match = true;
break;
}
++i3;
}
if(!match)
return false;
}
i3 = 0;
for( int i2 = 0; i2 < s2.size() ; ++i2 ) {
bool match = false;
while(i3 < s3.size()) {
if (visited[i3]) {
++i3;
continue;
}
if(s3[i3 ++] == s2[i2]) {
match = true;
break;
}
}
if(!match)
return false;
}
return true;
}
};
```

```class Solution {
public:
bool isInterleave(string &s1,int i1, string &s2, int i2, string &s3, int i3) {
if(i1 == s1.size() && i2 == s2.size() && i3 == s3.size())
return true;
bool match = false;
if(i1 < s1.size() && s1[i1] == s3[i3]) {
match = isInterleave(s1, i1 + 1, s2, i2, s3, i3 + 1);
}
if (!match && i2 < s2.size() && s2[i2] == s3[i3]) {
match = isInterleave(s1, i1, s2, i2 + 1, s3, i3 + 1);
}
return match;
}
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size())
return false;
return isInterleave(s1,0,s2,0,s3,0);
}
};
```

LeetCode题目：Integer to Roman

I = 1;
V = 5;
X = 10;
L = 50;
C = 100;
D = 500;
M = 1000;

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

```class Solution {
public:
void appendNumToRoman(int num, string &roman, char symbols[]) {
if (num == 0)
return;
if (num <= 3) {
roman.append(num,symbols[0]);
} else if (num == 4) {
roman.append(1,symbols[0]);
roman.append(1,symbols[1]);
} else if (num <= 8) {
roman.append(1,symbols[1]);
roman.append(num - 5,symbols[0]);
} else {
//num == 9
roman.append(1,symbols[0]);
roman.append(1,symbols[2]);
}
}
string intToRoman(int num) {
char symbol[9] = { 'I','V','X', 'L','C', 'D','M', 'v', 'x' };//v和x应该是大写的上面有一横
string roman = "";
int scale = 1000;
for (int i = 6; i >= 0 ; i -= 2) {
int digit = num / scale;
appendNumToRoman(digit, roman, symbol + i);
num = num % scale;
scale /= 10;
}
return roman;
}
};
```

LeetCode题目：Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

```/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
inline int max(int a, int b) {
return a > b ? a : b;
}
void addInte2Vec(vector &vec, Interval &inte) {
if(vec.size() == 0)
vec.push_back(inte);
else {
Interval &last = vec[vec.size() - 1];
if (last.end < inte.start) {
vec.push_back(inte);
} else if (last.start <= inte.start) {
last.end = max(last.end,inte.end);
}
}
}
vector insert(vector &intervals, Interval newInterval) {
vector result;
if(intervals.size() == 0) {
result.push_back(newInterval);
return result;
}

bool merged = false;
if(intervals[0].start <= newInterval.start) {
result.push_back(intervals[0]);
} else {
result.push_back(newInterval);
merged = true;
}

for(int i = 0 ; i < intervals.size() ; ++i) {
Interval inte = intervals[i];
if (inte.start < newInterval.start) {
} else {
merged = true;
}
}
if(!merged)
return result;
}
};
```

Code rewrite at 2012-1-15, 72ms pass large test

```/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
static bool lessThan(const Interval &int0, const Interval &int1) {
return int0.start < int1.start;
}
public:
vector insert(vector &intervals, Interval newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector ret;
sort(intervals.begin(),intervals.end(),Solution::lessThan);
bool merged = false;
Interval openint;
openint.start = newInterval.start;
if(intervals.size() > 0 && openint.start > intervals[0].start) {
openint.start = intervals[0].start;
}
openint.end = openint.start;
int i = 0;
while(true) {
Interval *cur = NULL;
if(i < intervals.size() && (merged || intervals[i].start <= newInterval.start)) {
cur = &intervals[i++];
} else if (!merged) {
cur = &newInterval;
merged = true;
}
if(cur == NULL) break;
if(openint.end < cur->start) {
ret.push_back(openint);
openint = *cur;
} else {
if(openint.end < cur->end) openint.end = cur->end;
}
}
ret.push_back(openint);
return ret;
}
};
```

iOS中的文件存放法则

Apple对应用程序放在沙盒中的文件有严格要求，主要有：

存放位置要求

1. 用户创建的文件，（程序不能自动生成的），需要放在Documents\
2. 缓存文件，需要放在Library\Caches\
3. 临时文件，放在tmp\，而且要注意清空
文件备份
这个可以通过设置文件的一个属性来控制，具体见下面代码

1. 除了用户创建和编辑的文件，不允许保存到iTunes和iCloud
2. 用户升级程序之后，所有Documents\和Library\的文件会自动复制到新的bundle中去

```+(BOOL)addSkipBackupAttributeToItemAtURL:(NSURL *)URL
{
if (![[NSFileManager defaultManager] fileExistsAtPath: [URL path]]) {
return NO;
}
if ([[UIDevice currentDevice].systemVersion floatValue] >= 5.1) {
NSError *error = nil;
BOOL success = [URL setResourceValue: [NSNumber numberWithBool: YES]
forKey: NSURLIsExcludedFromBackupKey error: &error];
if(!success){
NSLog(@"Error excluding %@ from backup %@", [URL lastPathComponent], error);
}
return success;
} else {
const char* filePath = [[URL path] fileSystemRepresentation];
const char* attrName = "com.apple.MobileBackup";
u_int8_t attrValue = 1;
int result = setxattr(filePath, attrName, &attrValue, sizeof(attrValue), 0, 0);
return result == 0;
}
}
```

LeetCode题目：strstr，简单解法把，下一步再研究KMP算法

```class Solution {
public:
char *strStr(char *haystack, char *needle) {
if (haystack == NULL || needle == NULL)
return NULL;
int len = strlen(haystack);
int lenPat = strlen(needle);
if(lenPat == 0)
return haystack;
for(int i = 0 ;i < len - lenPat + 1; ++i) {
int j = 0;
for( ; j < lenPat; ++j) {
if(haystack[i + j] != needle[j]) {
break;
}
}
if (j == lenPat)
return haystack + i;
}
return NULL;
}
};
```

Code rewrite at 2012-12-21

```class Solution {
public:
char *strStr(char *haystack, char *needle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(haystack == NULL || NULL == needle)
return NULL;
while(*haystack != '\0') {
int i = 0;
while(true) {
char h = *(haystack + i);
char n = *(needle + i);
if (n == '\0')
return haystack;
if (h == n)
++i;
else
break;
}

++haystack;
}
return *needle == '\0' ? haystack : NULL;
}
};
```

LeetCode题目：Gray Code，用欧拉回路解，花了好长时间····最后还错了····

```class Solution {
public:
unsigned int binaryToGray(unsigned int num)
{
return (num >> 1) ^ num;
}
vector grayCode(int n) {
int count = pow(2,n);
vector result(count);
for( int i = 0 ; i < count; ++ i) {
result[i] = binaryToGray(i);
}
return result;
}
};
```

这个题发现了好多问题

1. 计算欧拉回路的两个方法有点模糊了：避桥法（Fleury算法）和逐步插入回路法
2. ```    inline int startOfEdge(int edge) {
return (edge & startMask) >> 1;
}```

忘了最后的移位，debug了不少时间

3. `int tempEdgeIndex = startEdgeIndex + (edgeIndex - startEdgeIndex + i) % lenCircle;`

忘了- startEdgeIndex，这是edgeIndex的定义到后面逻辑比较复杂就忘了不是从0开始的了。

4. 思路一旦错了，就惨了

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2

```class Solution {
public:
inline bool edgeShareStart(int e0, int e1) {
return startOfEdge(e0) == startOfEdge(e1);
}
inline bool edgeShareEnd(int e0, int e1) {
return endOfEdge(e0) == endOfEdge(e1);
}
inline bool edgeConnect(int e0, int e1) {
return endOfEdge(e0) == startOfEdge(e1);
}
inline int startOfEdge(int edge) {
return (edge & startMask) >> 1;
}
inline int endOfEdge(int edge) {
}
vector grayCode(int n) {
//0.prepare
int count = pow(2,n);
startMask = (count - 1) << 1;
endMask = (count - 1) >> 1;
vector code(count);
for(int i = 0 ; i < count; ++i) {
code[i] = i;
//cout<<"edge"< circleStartIndex;//recode the index of the start edge for circles
int startIndex = 0;
do {
int startEdge = code[startIndex];
int startPt = startOfEdge(startEdge);
circleStartIndex.push_back(startIndex);
if (circleStartIndex.size() >= count)
return circleStartIndex;
int i = startIndex + 1;
do {
int edgePrev = code[startIndex];
if (endOfEdge(edgePrev) == startPt) {
//a circle is found
++ startIndex;
break;
}
int edgeCur = code[i];
if (edgeConnect(edgePrev, edgeCur)) {
//swap edgeCur and position curStart + 1 if needed
//cout< currentCircle;
for( int i = 0; i < lenCircle; ++ i) {
int tempEdgeIndex = startEdgeIndex + (edgeIndex - startEdgeIndex + i) % lenCircle;
currentCircle.push_back(code[tempEdgeIndex]);
}
//2.2.2.move edges on CircleI - 1
for( int i = startEdgeIndex - 1; i > preEdgeIndex ; --i ) {
code[i + lenCircle] = code[i];
}
//2.2.3.insert circleI into circleI - 1
for( int i = 0 ; i < lenCircle; ++i ) {
code[preEdgeIndex + 1 + i] = currentCircle[i];
}
done = true;
break;
}
}
}
}
//3.return
return code;
}
};
```

Code rewrite at 2012-12-23,24ms pass large set

```class Solution {
public:
vector grayCode(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector ret;
ret.push_back(0);
if (n <= 0) return ret;
int mostbit = 1;
for(int i = 1; i <= n; ++i) {
for(int k = ret.size() - 1; k >= 0; --k) {
int v = ret[k];
ret.push_back(v | mostbit);
}
mostbit = mostbit << 1;
}
return ret;
}
};
```

LeetCode题目：Generate Parentheses

1.左右括号数相等
2.任一位置之前的右括号数不大于左括号数

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”

20ms过大测试集合

```class datum{
public:
int     leftParCount;
int     rightParCount;
string  result;
datum(){
leftParCount = 0;
rightParCount = 0;
result = "";
}
datum(const datum &another){
leftParCount = another.leftParCount;
rightParCount = another.rightParCount;
result = another.result;
}
};

class Solution {
public:
vector generateParenthesis(int n) {
if (n == 0)
return vector();
vector *preResult = new vector(1);
vector *curResult = new vector();

for(int i = 1 ; i <= 2 * n; ++i){
curResult->clear();
for(int preIndex = 0; preIndex < preResult->size(); ++preIndex) {
datum &preDatum = (*preResult)[preIndex];
//1.if we can add an left parenthesis
if (preDatum.leftParCount < n) {
datum newDatum(preDatum);
newDatum.leftParCount += 1;
newDatum.result = newDatum.result + "(";
curResult->push_back(newDatum);
}
//2. if we can add an right parenthesis
if(preDatum.rightParCount < preDatum.leftParCount) {
datum newDatum(preDatum);
newDatum.rightParCount += 1;
newDatum.result = newDatum.result + ")";
curResult->push_back(newDatum);
}
}
vector * temp = preResult;
preResult = curResult;
curResult = temp;
}

vector finalResult(preResult->size());
for(int i = 0 ; i < preResult->size(); ++ i) {
finalResult[i] = (*preResult)[i].result;
}
return finalResult;
}
};
```

UITableView的背景颜色以及层次研究

UITableView的背景颜色，并不是UITableView的backgroundColor。

1. 这个呈现backgroundColor的view
2. 放置其中的cell们
3. scroll indicators

UITableViewCell的背景颜色修改

UITableViewCell直接修改背景颜色是没有用的，因为加入UITableView的部分是cell.contentView。

```cell.contentView.backgroundColor = [UIColor grayColor];
```

LeetCode题目：First Missing Positive

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. 第一遍扫描排除所有非正的数，将它们设为一个无关紧要的正数(n+2)，因为n+2不可能是答案
2. 第二遍扫描，将数组作为hash表来使用，用数的正负来表示一个数是否存在在A[]中。
当遇到A[i]，而A[i]属于区间[1,n]，就把A中位于此位置A[i] – 1的数置翻转为负数。
所以我们取一个A[i]的时候，要取它的abs，因为如果它是负数的话，通过步骤一之后，只可能是我们主动设置成负数的
3. 第三遍扫描，如果遇到一个A[i]是正数，说明i+1这个数没有出现在A[]中，只需要返回即可。
4. 上一步没返回，说明1到n都在，那就返回n+1

8ms过大集合

```class Solution {
public:
int firstMissingPositive(int A[], int n) {
if(n <= 0)
return 1;
int intOutOfRange = n + 2;
//first run, turn every negetive value into an impossible positive value
//make every value in A is positive
for(int i = 0 ; i < n ; ++ i) {
if(A[i] <= 0)
A[i] = intOutOfRange;
}
//second run, make A[] as a hash table, A[i] indicate the presence of i + 1
//the way is that, if k in [1,n] is in A[], then turn A[k -1] to negetive
for(int i = 0 ; i < n ; ++i) {
int ai = A[i];
int absi = abs(ai);
if(absi <= n)
A[absi-1] = -abs(A[absi-1]);
}
//third run, if A[i] is positive, from step 2, we know that i + 1 is missing.
for(int i = 0 ; i < n ; ++i) {
if(A[i] > 0)
return i + 1;
}
//all int from 1 to n is present, then return n + 1
return n+1;
}
};
```

```class Solution {
public:
int firstMissingPositive(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n <= 0)
return 1;
sort(A,A+n);
int i = 0;
while(i= n)
return 1;
int target = 1;
int pre = 0;
for(; i < n ; ++i){
if(A[i] == pre)
continue;
if(A[i] != target)
return target;
++target;
pre = A[i];
}
return target;
}
};
```

Code rewrite at 2013-1-22

```class Solution {
public:
int firstMissingPositive(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n <= 0) return 1;
//first run, mark all the negetive or zero to an impossible positive
const int IMPOSSIBLE = n + 1;
for(int i = 0; i < n; ++i) {
if(A[i] <= 0) A[i] = IMPOSSIBLE;
}
//second run, using A[] as hash map, if k is in the array, flip A[k-1] to negative
for(int i=0; i < n; ++i) {
int val = abs(A[i]);
if(val <= n && A[val-1] > 0)
A[val-1] *= -1;
}
//third run, find out the first positive index p in A, then p+1 is missing
for(int i = 0; i 0) return i+1;
}
//no number is missing, in this case return n + 1
return n+1;
}
};
```

LeetCode题目：Edit Distance，字符串之间的编辑距离，动态规划

Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

一开始考虑的是，只要找到能重用的最大子串不就行了么，比如将字符：
abc变成xxxxxaxxxxxbxxxxxcxxxxx，只要abc都可以重用，就只需要20步。
但是写完了这个方法之后（见下面失败方法1），被一个简单的case击败了：
将ykyyyab变成abxxxxx，
这种情况下，如果利用了最长子串ab的话，编辑距离实际上是10，但是不用的话只需要7。也就是说，最长子串不一定能降低编辑距离。

然后就又想，上面这种失败case的原因在于为了利用最长子串，导致的头尾一删一添，两次操作，还不如只需一次的替换操作。
于是就限制了一下匹配的区间，比如abxxxxx中的b在匹配的时候，只在kyyya这个范围内才有实际作用，超过这个区间再匹配就会造成得不偿失的一删一添两次操作，得不偿失。
于是写完代码，悲剧的是，又发现问题：
sea变成eat，
按这个算法，编辑距离是3，但实际上是2（删s添t）。

最后花了太长时间忍不了了，百度之，发现正确的解出来方法是用二维的dp。
假如我们要将字符串str1变成str2
sstr1(i)是str1的子串，范围[0到i），sstr1(0)是空串
sstr2(j)是str2的子串，同上
d(i,j)表示将sstr1(i)变成sstr2(j)的编辑距离

首先d(0,t),0<=t<=str1.size()和d(k,0)是很显然的。 当我们要计算d(i,j)时，即计算sstr1(i)到sstr2(j)之间的编辑距离, 此时，设sstr1(i)形式是somestr1c；sstr2(i)形如somestr2d的话， 将somestr1变成somestr2的编辑距离已知是d(i-1,j-1) 将somestr1c变成somestr2的编辑距离已知是d(i,j-1) 将somestr1变成somestr2d的编辑距离已知是d(i-1,j) 那么利用这三个变量，就可以递推出d(i,j)了： 如果c==d，显然编辑距离和d(i-1,j-1)是一样的 如果c!=d，情况稍微复杂一点，

1. 如果将c替换成d，编辑距离是somestr1变成somestr2的编辑距离 + 1，也就是d(i-1,j-1) + 1
2. 如果在c后面添加一个字d，编辑距离就应该是somestr1c变成somestr2的编辑距离 + 1，也就是d(i,j-1) + 1
3. 如果将c删除了，那就是要将somestr1编辑成somestr2d，距离就是d(i-1,j) + 1
4. 那最后只需要看着三种谁最小，就采用对应的编辑方案了。

递推公式出来了，程序也就出来了。

```class Solution {
public:
int minDistance(string word1, string word2) {
int rows = word1.size() + 1;
int cols = word2.size() + 1;
int ** d = (int**)malloc(rows * sizeof(int*));
for(int i = 0; i < rows; ++i){
d[i] = (int*)malloc(cols * sizeof(int));
d[i][0] = i;//sub string in word1 range [0,i) edit to ""
}
for(int j = 0; j < cols; ++j)
d[0][j] = j;//sub string in word2 range [0,j) edit to ""
for(int i = 1; i < rows; ++i) {
char ci = word1[i-1];
for(int j = 1; j < cols; ++j) {
char cj = word2[j-1];
//we will edit str1:word1[0,i) to str2:word2[0,j)
if (ci == cj) {
//if ci equal to cj, then the edit ditance of word1[0,i) to word2[0,j)
// is the same as word1[0,i-1) to word2[0,j-1)
d[i][j] = d[i-1][j-1];
} else {
//if we modify letter ci to cj, there will be 1 operation
int dEdit = d[i-1][j-1] + 1;
//if we add cj to the end of word1[0,i), then from the edit distance of
// word1[0,i) to word2[0, j -1), we can conclude follow dist
int dAdd = d[i][j-1] + 1;
//if we delete ci from word1[0,i), and we know the dist
// from word1[0,i-1) to word2[0,j), the things done:
int dDel = d[i-1][j] + 1;
//the minimum one will be the final distance for str1 to str2
min = min < dDel ? min : dDel;
d[i][j] = min;
}
}
}
int result = d[rows - 1][cols - 1];
//delete dist;
return result;
}
};
```

1. 通过寻找最长公共子序列（可间断序列）来解决
```class Solution {
public:
class datum{
public:
int lastIndex;
int len;
datum(){
lastIndex = -1;
len = 0;
}
};
inline int locationOfCharInStr(char c, string &str, int startIndex) {
for( int i = startIndex; i < str.size() ; ++ i ) {
if (c == str[i])
return i;
}
return -1;
}
int longestCommonArray(string &str1, string &str2) {
if(str1.size() == 0 || 0 == str2.size())
return 0;
vector maxLen(str1.size());
for( int i = 0; i <  str1.size(); ++i ) {
char ci = str1[i];
datum &di = maxLen[i];
for (int pre = 0 ; pre < i; ++pre ) {
datum dpre = maxLen[pre];
if (dpre.len == 0 ) continue;
int cie = locationOfCharInStr(ci,str2,dpre.lastIndex + 1);
if( cie != -1 && di.len < dpre.len + 1 ) {
di.len = dpre.len + 1;
di.lastIndex = cie;
}
}
if(di.len == 0) {
int cie = locationOfCharInStr(ci,str2,0);
if( cie != -1 ) {
di.len = 1;
di.lastIndex = cie;
}
}
}
int maxlen = 0;
for(int i = 0 ; i < maxLen.size(); ++i) {
if (maxlen < maxLen[i].len)
maxlen = maxLen[i].len;
}
return maxlen;
}
int minDistance(string word1, string word2) {
int lcsl = longestCommonArray(word1,word2);
int maxlen = word1.size();
if(maxlen < word2.size())
maxlen = word2.size();
return maxlen - lcsl;
}
};
```
2. 通过限制查找范围来解决
```class Solution {
public:
class datum{
public:
int loc;
int len;
datum(){
loc = -1;
len = 0;
}
};
inline int locationOfCharInStr(char c, string &str, int startIndex, int endIndex) {
if(endIndex > str.size() - 1)
endIndex = str.size() - 1;
for( int i = startIndex; i <= endIndex ; ++ i ) {
if (c == str[i])
return i;
}
return -1;
}
int minDist(string &str1, string &str2) {
vector minLen(str2.size());
for( int i = 0; i <  str2.size(); ++i ) {
char ci = str2[i];
datum &di = minLen[i];
di.len = str1.size();
di.loc = i;
int endIndex = str1.size() - str2.size() + i;
for (int pre = 0 ; pre < i; ++pre ) {
datum dpre = minLen[pre];
int startIndex = dpre.loc + i - pre;
int cie = locationOfCharInStr(ci,str1,startIndex,endIndex);
if( cie != -1 && (di.len >= dpre.len ||
di.loc > cie)) {
di.len = dpre.len - 1;
di.loc = cie;
}
}
if(di.len == str1.size()) {
int cie = locationOfCharInStr(ci,str1,i,endIndex);
if( cie != -1 ) {
di.len = str1.size() - 1;
di.loc = cie;
}
}
}
int result = str1.size();
for(int i = 0 ; i < minLen.size(); ++i) {
if (result > minLen[i].len)
result = minLen[i].len;
}
return result;
}
int minDistance(string word1, string word2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
string *pSLen, *pSShort;
if(word1.size() >= word2.size()){
pSLen = &word1;
pSShort = &word2;
} else {
pSLen = &word2;
pSShort = &word1;
}
if (pSShort->size() <= 0)
return pSLen->size();
int result = minDist(*pSLen,*pSShort);
return result;
}
};
```

Code rewrite at 2012-12-29

```//
//  main.cpp
//  EditDistance
//
//  Created by Qiu Xiangyu on 12-12-29.
//

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int editDist(string &str0, string &str1) {
if (str0.size() == 0) {
return (int)str1.size();
} else if (str1.size() == 0) {
return (int)str0.size();
}
vector<vector<int> > dists(str0.size() + 1, vector<int>(str1.size() + 1,0));
for(int i0 = 0; i0 <= str0.size(); ++ i0) {
dists[i0][0] = i0;
}
for (int i1 = 0; i1 <= str1.size(); ++i1) {
dists[0][i1] = i1;
}
for (int l0 = 1; l0 <= str0.size(); ++l0) {
for (int l1 = 1; l1 <= str1.size(); ++l1) {
if (str0[l0 - 1] == str1[l1-1]) {
//the same ending of this length pair for strings
dists[l0][l1] = dists[l0-1][l1-1];
} else {
//for replace
int replaceDist = dists[l0-1][l1-1] + 1;
int mindist = replaceDist;
//insert the last char into substr1
int insertDist = dists[l0][l1-1] + 1;
if (mindist > insertDist) {
mindist = insertDist;
}
//delete the last char from substr1
int deleteDist = dists[l0-1][l1] + 1;
if (mindist > deleteDist) {
mindist = deleteDist;
}
dists[l0][l1] = mindist;
}
}
}
return dists[str0.size()][str1.size()];
}

int main(int argc, const char * argv[])
{
string str0 = "abc";
string str1 = "bcd";
int editdist = editDist(str0, str1);
cout<<"edit distance is : "<<editdist<<endl;
return 0;
}

```

Code rewrite 2012-12-30

```class Solution {
public:
int minDistance(string word1, string word2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > dists(word1.size() + 1, vector(word2.size() + 1, 0));
for(int l1 = 1; l1 <= word1.size(); ++l1) {
//by adding chars in sub-word1 to sub-word2 with zero length
dists[l1][0] = l1;
}
for(int l2 = 1; l2 <= word2.size(); ++l2) {
dists[0][l2] = l2;
}
for(int l1 = 1; l1 <= word1.size(); ++l1) {
for(int l2 = 1; l2 <= word2.size(); ++l2) {
if(word1[l1-1] == word2[l2-1]) {
dists[l1][l2] = dists[l1-1][l2-1];
} else {
//if we can form sub-word1 with length l1-1 to sub-word2 with length l2-1,
//with steps of dists[l1-1][l2-1]
//then we can replace the char sub-word2[l2] to sub-word1[l1],
//then we can edit sub-word2 with length l2 to sub-word1 with length l1
//with steps of dists[l1-1][l2-1] + 1
int replacedist = dists[l1-1][l2-1] + 1;
//if we can form sub-word1 with length l1-1 to sub-word2 with length l2,
//with steps of dists[l1-1][l2]
//then we can add the char sub-word1[l1] after sub-word2[l2],
//or se can delete the char sub-word1[l1]
//then we can edit sub-word2 with length l2 to sub-word1 with length l1
//with steps of dists[l1-1][l2] + 1
int adddist = dists[l1-1][l2] + 1;
//or if we can form sub-word1 with length l1 to sub-word2 with length l2-1,
//with steps of dists[l1][l2-1]
//then we can add the char sub-word2[l2] after sub-word1[l1],
//or we can delete the char sub-word2[l2]
//then we can edit sub-word2 with length l2 to sub-word1 with length l1
//with steps of dists[l1][l2-1] + 1
int deldist = dists[l1][l2-1] + 1;

int mindist = replacedist;
if(mindist>deldist) mindist = deldist;
dists[l1][l2] = mindist;
}
}
}
return dists[word1.size()][word2.size()];
}
};
```

iOS开发中使用平铺图像作为UIScrollView或者UITableView的可滚动背景

UIScroView和TableView都可以设置一张图片作为背景，或者设置一个颜色。

```self.tableView.backgroundColor = [UIColor colorWithPatternImage:[UIImage imageNamed:@"loginBkgWithoutLogo"]];
```

LeetCode题目：Divide Two Integers

Divide Two Integers
Divide two integers without using multiplication, division and mod operator.

```class Solution {
public:
int divide(int dividend, int divisor) {
if (divisor == 0 )
return -1;//error
int bits = sizeof(int) * 8;
int signMask = 0x01 << (bits - 1);

int count = 0;
bool minus = false;
unsigned int dend = dividend;
if(dividend < 0)
{
minus = true;
dend = ~(dend - 1);//补码还原，先-1，再取反。（-1的补码是，将1的原码0x01取反，在+1，也就是1...1）
}
unsigned int sor = divisor;
if( divisor < 0 )
{
minus = !minus;
sor = ~(sor - 1);
}
int offset = 0;
int mask = 0x01 << (bits-1);
while( (0 == (sor&mask)) && (sor<<1) <= dend)
{
++offset;
sor = sor << 1;
}

int result = 0;
while(offset >= 0)
{
if(dend >= sor)
{
result += (0x01 << offset);
dend -= sor;
}
--offset;
sor = sor >> 1;
}
if(minus)
return 0 - result;
return result;
}
};
```

LeetCode题目：Decode Ways，一维动态规划

Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).
The number of ways decoding “12” is 2.

```class Solution {
public:
int numDecodings(string s) {
if(s.size() == 0)
return 0;
if(s.size() == 1 && s[0] != '0')
return 1;
if(s[0] == '0')
return 0;
int fix = s.size() == 2 ? 1: 0;
if(s[0] == '1' || (s[0] == '2' && s[1] <= '6'))
return numDecodings(s.substr(1)) + numDecodings(s.substr(2)) + fix;
return numDecodings(s.substr(1));
}
};
```

```class Solution {
public:
int numDecodings(string s) {
if(s.size() == 0)
return 0;
vector ways(s.size() + 2,1);//多出来的两个作为占位符，避免程序内判断是否超过size
for(int i = s.size() - 1; i >= 0; --i)
{
//self
if(s[i] == '0')
ways[i] = 0;
else
ways[i] = ways[i+1];

//self and next
if( i + 1 < s.size() && ((s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')))) {
ways[i] += ways[i + 2];
}
}
return ways[0];
}
};
```

Code rewrite at 2013-1-4, not very nice

```class Solution {
public:
int numDecodings(string s) {
if (s.size() == 0) return 0;
if (s[0] == '0') return 0;
int *ways = new int[s.size()];
ways[0] = 1;
for(int ei = 1; ei < s.size(); ++ei) {
char last = s[ei - 1];
char cur = s[ei];
if(cur == '0') {
if(last == '1' || last == '2')
ways[ei] = ei > 1 ? ways[ei-2] : 1;
else {
delete ways;
return 0;
}
} else if(last == '1' || (last == '2' && cur <= '6')) {
ways[ei] = ways[ei-1];
ways[ei] += ei > 1 ? ways[ei-2] : 1;
} else {
ways[ei] = ways[ei-1];
}
}
int ret = ways[s.size() - 1];
delete ways;
return ret;
}
};
```

LeetCode题目：Container With Most Water

2013-1-4，更新

Container With Most Water
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

600ms过大集合

```class Solution {
public:
int maxArea(vector &height) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int max = 0;
for( int i = 0 ; i < height.size(); ++i)
{
int hi = height[i];
if(hi == 0)
continue;
int minPosibleIndex = max / hi + i;
for(int j = height.size() - 1; j > i && j >= minPosibleIndex; --j)
{
int hj = height[j];
int area = min(hi,hj) * (j - i);
if (area > max)
max = area;
}
}
return max;
}
};
```

Code rewrite at 2013-1-4,O(n)

```class Solution {
public:
int maxArea(vector &height) {
if (height.size() < 2) return 0;
int i = 0, j = height.size() - 1;
int maxarea = 0;
while(i < j) {
int area = 0;
if(height[i] < height[j]) {
area = height[i] * (j-i);
//Since i is lower than j,
//so there will be no jj < j that make the area from i,jj
//is greater than area from i,j
//so the maximum area that can benefit from i is already recorded.
//thus, we move i forward.
//因为i是短板，所以如果无论j往前移动到什么位置，都不可能产生比area更大的面积
//换句话所，i能形成的最大面积已经找到了，所以可以将i向前移。
++i;
} else {
area = height[j] * (j-i);
//the same reason as above
//同理
--j;
}
if(maxarea < area) maxarea = area;
}
return maxarea;
}
};
```

LeetCode题目：Combination，C(k,n)，从n中选出k个

Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

Code,52ms pass the large test set

```class Solution {
public:
vector > combine(int n, int k) {
vector > result;
if(k > n || n <= 0 || k <= 0)
return result;
vector index(k);
for(int i = 0 ; i < k ; ++ i)
{
index[i] = i + 1;
}
do
{
result.push_back(index);
bool carry = false;
int cur = k - 1;
do {
if(index[cur] < n - (k-1-cur))
{
carry = false;
++index[cur];
for(int i = 1; i + cur < k ; ++i)
index[i+cur] = index[cur] + i;
}
else
{
carry = true;
if(--cur < 0)
return result;
}
} while(carry && cur >=0);
} while(true);
return result;
}
};
```

Code rewrite at 2012-12-30, Another way to solve this problem, in my General Back-Tracing Frame

```class Solution {
public:
vector > combine(int n, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > ret;
if(n < k || k < 1) return ret;
vector numbers(k,1);
bool forward = true;
int icur = 0;
while(icur >= 0) {
if(forward) {
if(icur == k - 1) {
ret.push_back(numbers);
forward = false;
} else {
if(numbers[icur] < n) {
numbers[icur+1] = numbers[icur] + 1;
++icur;
} else {
forward = false;
}
}
} else {
if(numbers[icur] < n) {
++numbers[icur];
forward = true;
} else {
--icur;
}
}
}
return ret;
}
};
```

LeetCode题目：Combination Sum II

1. unique和erase的用法
`result.erase(unique(result.begin(),result.end()),result.end());`
2. 细心检查语法

Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

1432ms过大测试集合

```class Solution {
public:
vector > combinationSum2(vector &num, int target) {
if(num.size() == 0)
return vector >();
sort(num.begin(),num.end());
vector > > *pR = new vector > >(target + 1);
vector > > *pT = new vector > >(target + 1);
//initialize
{
int c0 = num[0];
if(c0 > 0 && c0 <= target)
{
vector titem = vector(1,c0);
(*pR)[c0].push_back(titem);
}
}

for(int k = 1; k < num.size(); ++k)
{
int ck = num[k];
for(int t = 1; t <= target; ++t)
{
(*pT)[t].clear();
vector > &excludePre = (*pR)[t];
for( int i = 0 ; i < excludePre.size(); ++i)
{
(*pT)[t].push_back(excludePre[i]);
}
if(t - ck > 0)
{
vector > &includePre = (*pR)[t - ck];
for( int i = 0 ; i < includePre.size(); ++i)
{
vector tResult = includePre[i];
tResult.push_back(ck);
(*pT)[t].push_back(tResult);
}
} else if (t == ck)
{
(*pT)[t].push_back(vector(1,ck));
}
}
vector > > *temp = pR;
pR = pT;
pT = temp;
}
vector > &result = (*pR)[target];
sort(result.begin(),result.end());
result.erase(unique(result.begin(),result.end()),result.end());
return result;
}
};
```

LeetCode题目：Combination Sum，动态规划

Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

```class Solution {
public:
vector > combinationSum(vector &candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (candidates.size() == 0)
return vector >();
sort(candidates.begin(),candidates.end());
vector > > *pR = new vector > >(target + 1);
vector > > *pT = new vector > >(target + 1);
for (int t = 1; t <= target; ++ t)
{
int c = candidates[0];
if (t % c == 0)
{
(*pR)[t].push_back(vector(t/c,c));
}
}
for (int k = 1; k < candidates.size(); ++k)
{
int ck = candidates[k];
for (int t = 1 ; t <= target; ++t)
{
(*pT)[t].clear();
for (int p = 0; p * ck <= t; ++p)
{
int remain = t - ck * p;
if (remain == 0)
{
(*pT)[t].push_back(vector(p,ck));
}
else
{
vector > &rRemain = (*pR)[remain];
for (int irr = 0; irr < rRemain.size() ;++ irr)
{
vector newSum(rRemain[irr]);
for(int ip = 0; ip < p; ++ip)
newSum.push_back(ck);
(*pT)[t].push_back(newSum);
}
}
}
}
vector > > *pTemp = pR;
pR = pT;
pT = pTemp;
}
return (*pR)[target];
}
};
```

LeetCode题目：Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.

代码

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
```
1. 递归解法
很简单，8ms过小集合，12ms过大集合

```class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector result;
if (NULL == root)
return result;
vector leftResult = inorderTraversal(root->left);
vector rightResult = inorderTraversal(root->right);
for( int i = 0 ; i < leftResult.size(); ++i)
result.push_back(leftResult[i]);
result.push_back(root->val);
for( int i = 0 ; i < rightResult.size(); ++i)
result.push_back(rightResult[i]);
return result;
}
};
```
2. 循环解法
稍复杂点，大小集合都是8ms过

```class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector result;

vector trace;
TreeNode *cur = root;
TreeNode *pre = NULL;
bool forward = true;
while(cur)
{
if (forward)
{
//have unvisited left
if (cur->left && pre != cur->left)
{
pre = cur;
trace.push_back(cur);
cur = cur->left;
continue;
}
forward = false;
}
else
{
//not return from right, add self
if(cur->right == NULL || cur->right != pre)
result.push_back(cur->val);
//go right if could
if(cur->right && pre != cur->right)
{
forward = true;
pre = cur;
trace.push_back(cur);
cur = cur->right;
continue;
}
//go up
pre = cur;
if (trace.size() > 0)
{
cur = trace[trace.size() - 1];
trace.pop_back();
} else
cur = NULL;

}
}

return result;
}
};
```
3. 循环解法，2012年12月6日重写，比上一个简洁
```class Solution {
public:
vector inorderTraversal(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector ret;
if(NULL == root) return ret;

bool forward = true;
stack trace;
TreeNode *preNode = NULL;
trace.push(root);

while(trace.size()) {
TreeNode *curNode = trace.top();
if(forward) {
if(curNode->left && preNode != curNode->left) {
trace.push(curNode->left);
} else {
//no left or left visited
forward = false;
}
} else {
//backward, find sibling(right child)
//if not back from right child, then visit it
if(curNode->right != preNode)
ret.push_back(curNode->val);
if(curNode->right && preNode != curNode->right) {
//if have an unvisited right child, traval it.
trace.push(curNode->right);
forward = true;
} else {
//all sub-tree of this node is visited
trace.pop();
}
}
preNode = curNode;
}

return ret;
}
};
```

windows7下有时候出现不能自动给移动设备分配盘符

```mountvol /e
```

UIImagePickerController返回的图片可能是旋转的需要用imageOrientation将其矫正

UIImagePickerController返回的照片带有方向信息，如果直接上传到服务器的话，可能造成旋转了90°（当手机竖直拍照）的情况。而且如果直接取其jpeg数据，或者将UIImage保存到本地的话，就会丢失这个方向信息，导致下一次读取出来图片就是颠倒的。

通过NSCalendar与NSDate的年月日时分秒等元素进行交互

```//首先创建NSCalendar的实例，可以简单的用当前实例，也可以创建其它的历法对应的实例。
NSCalendar *cal = [NSCalendar currentCalendar];

//下面通过NSCalendar来获取各个元素，保存在类NSDateComponents的实例中
//需要通过函数参数components指定希望获取的元素，详细的枚举后面会列出
NSDateComponents *dateComps = [cal components:NSYearCalendarUnit|NSMonthCalendarUnit|NSDayCalendarUnit|NSHourCalendarUnit|NSMinuteCalendarUnit fromDate:startDate];
int year = [dateComps year];
int month = [dateComps month];
int day = [dateComps day];
int hour = [dateComps hour];
int minute = [dateComps minute];
int second = [dateComps second];

//也可以通过NSCanlendar和NSDateComponents来创建NSDate
NSDate *newDate = [cal dateFromComponents:dateComps];
```
` <br \>`

```enum {
NSEraCalendarUnit = kCFCalendarUnitEra,
NSYearCalendarUnit = kCFCalendarUnitYear,
NSMonthCalendarUnit = kCFCalendarUnitMonth,
NSDayCalendarUnit = kCFCalendarUnitDay,
NSHourCalendarUnit = kCFCalendarUnitHour,
NSMinuteCalendarUnit = kCFCalendarUnitMinute,
NSSecondCalendarUnit = kCFCalendarUnitSecond,
NSWeekCalendarUnit = kCFCalendarUnitWeek /* NS_DEPRECATED(10_4, 10_7, 2_0, 5_0) */,
NSWeekdayCalendarUnit = kCFCalendarUnitWeekday,
NSWeekdayOrdinalCalendarUnit = kCFCalendarUnitWeekdayOrdinal,
#if MAC_OS_X_VERSION_10_6 <= MAC_OS_X_VERSION_MAX_ALLOWED || __IPHONE_4_0 <= __IPHONE_OS_VERSION_MAX_ALLOWED
NSQuarterCalendarUnit = kCFCalendarUnitQuarter,
#endif
#if MAC_OS_X_VERSION_10_7 <= MAC_OS_X_VERSION_MAX_ALLOWED || __IPHONE_5_0 <= __IPHONE_OS_VERSION_MAX_ALLOWED
NSWeekOfMonthCalendarUnit = kCFCalendarUnitWeekOfMonth,
NSWeekOfYearCalendarUnit = kCFCalendarUnitWeekOfYear,
NSYearForWeekOfYearCalendarUnit = kCFCalendarUnitYearForWeekOfYear,
#endif
#if MAC_OS_X_VERSION_10_7 <= MAC_OS_X_VERSION_MAX_ALLOWED || __IPHONE_4_0 <= __IPHONE_OS_VERSION_MAX_ALLOWED
NSCalendarCalendarUnit = (1 << 20),
NSTimeZoneCalendarUnit = (1 << 21),
#endif
};
typedef NSUInteger NSCalendarUnit;
```

在windows7下用diskpart命令行工具将大容量分区格式化为exfat并且指定分配单元大小

============ 以下是正文 =============

（就像下面截图的“文件系统”一项，大容量的分区就只能选择ntfs了；小u盘可以选fat，ntfs，exfat）

1. 在命令行下输入diskpart
2. 查看磁盘信息

这里可以看到我一共有4个磁盘，硬盘是第0个（这段文章是在pc上写的，截图和mbp上稍有不同，截图只做说明用）
3. 选择硬盘

diskpart的操作方式是先选择好要进行操作的目标（硬盘，分区），然后所有的命令都照着这个目标去，所以这里一定要谨慎，一旦选错，后果不堪设想啊
4. 查看所选硬盘的分区信息并且选择要格式化的分区

这两条命令第一条列出所选硬盘上的分区信息，第二条选择要格式化的分区，同上，一定要谨慎选择！！
5. 格式化

这就是格式化命令了，没有任何提示，没有让你选择yes或no，一旦回车直接执行。
命令中指定了格式化为exfat格式，单元大小1024，quick一定要加上，不然慢死。
6. 退出diskpart
直接输入exit就行了

iOS开发中混合使用ARC和非ARC项目

SDK5.0引入了ARC，到现在已经一年了，开始发现有很多项目会混合使用这两个方案。比如:

1.自己的旧项目没有使用ARC，但是引入的第三方库却是使用了ARC的。
2.自己的新项目使用了ARC，但是引入的第三方库或者以前写的代码却没有使用ARC。

1.对于第一个情况，给采用了ARC的源文件，添加-fobjc-arc选项
2.对于第二种情况，添加-fno-objc-arc

<br>

```-(void)dealloc{
//do something in common
#if !__has_feature(objc_arc)
[super dealloc];
#else
//nothing
#endif
}
```