## LeetCode题目：Triangle，动态规划

Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

```[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
```

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

```class Solution {
public:
int minimumTotal(vector > &triangle) {
int rows = triangle.size();
if(0 == rows) return 0;
int *minSums = new int[rows];
int *temp = new int[rows];

for(int r = 0; r < rows; ++r) {
vector trow = triangle[r];
if(trow.size() != r + 1) return 0;//input error occur
//first should be last 0 add trow[0]
temp[0] = trow[0] + (r > 0 ? minSums[0] : 0);
//from 1 to r - 1, the min from above to parants add self
for(int i = 1; i < r; ++ i) {
temp[i] = trow[i] + min(minSums[i-1],minSums[i]);
}
//last element, just like the first one. only can add self to the last element above.
if(r > 0)
temp[r] = trow[r] + minSums[r-1];
//swap temp with minSums
int *tswap = temp;
temp = minSums;
minSums = tswap;
}

//scan the minSums, find out the minimum one
int m = minSums[0];
for(int i = 1; i < rows; ++i) {
if(minSums[i] < m)
m = minSums[i];
}

delete temp;
delete minSums;
return m;
}
};
```

Code rewrite at 2012-12-30

```class Solution {
public:
int minimumTotal(vector > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int levels = triangle.size();
if(levels<=0) return 0;
vector *psum = new vector(levels,0);
vector *psumtemp = new vector(levels,0);
(*psum)[0] = triangle[0][0];
for(int ilevel = 1; ilevel < levels; ++ilevel) {
vector &level = triangle[ilevel];
const int levelsize = level.size();
//only one path could arrive to the first and last number in a level
(*psumtemp)[0] = (*psum)[0] + level[0];
//if (level.size() > 1)
(*psumtemp)[levelsize - 1] = (*psum)[levelsize - 2] + level[levelsize - 1];
//there are 2 pathes for the middle numbers.
for(int ipos = 1; ipos < levelsize - 1; ++ipos) {
int tsum = (*psum)[ipos] + level[ipos];
if(tsum > (*psum)[ipos-1] + level[ipos]) {
tsum = (*psum)[ipos-1] + level[ipos];
}
(*psumtemp)[ipos] = tsum;
}
//swap the psum and psumtemp
vector *ptemp = psum;
psum = psumtemp;
psumtemp = ptemp;
}
//scan the psum and output the minnimum sum
int minsum = (*psum)[0];
for(int i = 1; i < levels; ++i) {
if(minsum > (*psum)[i])
minsum = (*psum)[i];
}
//clearup
delete psum;
delete psumtemp;
return minsum;
}
};
```

Code rewrite at 2013-1-17

```class Solution {
public:
int minimumTotal(vector > &triangle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rows = triangle.size();
if(0 == rows) return 0;//error
int *sumrow = new int[rows];
int *sumrowtemp = new int [rows];
sumrow[0] = triangle[0][0];
for(int ir = 1; ir < rows; ++ir) {
vector &trirow = triangle[ir];
sumrowtemp[0] = sumrow[0] + trirow[0];
for(int ic = 1; ic < trirow.size(); ++ic) {
int minsum = sumrow[ic-1];
if(ic < trirow.size()-1 && sumrow[ic] < minsum) {
minsum = sumrow[ic];
}
sumrowtemp[ic] = minsum + trirow[ic];
}
int *temp = sumrow;
sumrow = sumrowtemp;
sumrowtemp = temp;
}
int ret = sumrow[0];
for(int ic = 1; ic < rows; ++ic) {
if(ret > sumrow[ic]) ret = sumrow[ic];
}
delete sumrow;
delete sumrowtemp;
return ret;
}
};
```

## LeetCode题目：Trapping Rain Water

Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

```class Solution {
public:
int trap(int A[], int n) {
//no way to contain any water
if(n <= 2) return 0;

//1. first run to calculate the heiest bar on the left of each bar
int *lmh = new int[n];//for the most height on the left
lmh[0] = 0;
int maxh = A[0];
for(int i = 1; i < n; ++i) {
lmh[i] = maxh;
if(maxh < A[i]) maxh = A[i];
}
int trapped = 0;

//2. second run from right to left,
// caculate the highest bar on the right of each bar
// and calculate the trapped water simutaniously
maxh = A[n-1];
for(int i = n - 2; i > 0; --i) {
int left = lmh[i];
int right = maxh;
int container = min(left,right);
if(container > A[i]) {
trapped += container - A[i];
}
if(maxh < A[i]) maxh = A[i];
}
delete lmh;
return trapped;
}
};
```

## LeetCode题目：Text Justification

Text Justification
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”]
L: 16.
Return the formatted lines as:
[
“This is an”,
“example of text”,
“justification. ”
]
Note: Each word is guaranteed not to exceed L in length.
Corner Cases:
A line other than the last line might contain only one word. What should you do in this case?
In this case, that line should be left-justified.

```class Solution {
public:
vector fullJustify(vector &words, int L) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector rslt;
if(0 == words.size()) return rslt;
int si = 0, ei = si;
int len = 0;
while(true) {
for(ei = si; ei < words.size(); ++ei) {
if(len + (ei - si) + words[ei].size() > L) {
break;
}
len += words[ei].size();
}
--ei;
if(ei < si) ei = si;
//form the string
if(si >= ei) {
//only one word on this line
string line = words[si];
line.append(L - line.size(), ' ');
rslt.push_back(line);
} else {
//multiple words on this line
bool lastline = (ei == (words.size() - 1));
int spaceBase = (L - len) / (ei - si);
int bonus = (L - len) - spaceBase * (ei - si);
if(lastline) {
//lastline
spaceBase = 1;
bonus = 0;
}
string line = words[si];
for(int i = si + 1; i <= ei; ++i) {
int space = spaceBase;
if(bonus > 0) {
++space;
--bonus;
}
line.append(space,' ');
line.append(words[i]);
}
if(lastline) {
line.append(L - len - ei + si,' ');
}
rslt.push_back(line);
}
//progress
si = ei + 1;
len = 0;
if(si >= words.size()) break;
}//end while
return rslt;
}
};
```

## LeetCode题目：Symmetric Tree

1. 两个节点值相等
2. 左节点的左子树和右节点的右子树对称
3. 左节点的右子树和右节点的左子树对称

Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:

```    1
/ \
2   2
/ \ / \
3  4 4  3
```

But the following is not:

```    1
/ \
2   2
\   \
3    3
```

Note:
Bonus points if you could solve it both recursively and iteratively.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode *left, TreeNode *right) {
if(left == NULL) {
return right == NULL;
} else {
if (right == NULL)
return false;
else {
if(left->val != right->val) {
return false;
}
if(!isSymmetric(left->right,right->left)) {
return false;
}
if(!isSymmetric(left->left, right->right)) {
return false;
}
return true;
}
}
}
bool isSymmetric(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(NULL == root) return true;
return isSymmetric(root->left,root->right);
}
};
```

## LeetCode题目：Swap Nodes in Pairs

Swap Nodes in Pairs
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// Start typing your C/C++ solution below
// DO NOT write int main() function

while(true) {
ListNode *n0 = *ppre;
ListNode *n1 = n0->next;

//swap n0 and n1
*ppre = n1;
n0->next = n1->next;
n1->next = n0;
ListNode *next = n1->next;
ppre = &(n0->next);
}

}
};
```

## LeetCode题目：Sudoku Solver，回溯

Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character ‘.’.
You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

```struct Position {
int row;
int col;
};
class Solution {
public:
inline bool isValid(vector > &board, Position &p) {
char val = board[p.row][p.col];
if(val < '1' || val > '9') return false;
//cout< &brow = board[p.row];
const int width = brow.size();
for(int ic = 0; ic < width; ++ ic) {
if(ic != p.col
&& brow[ic] != '.'
&& brow[ic] == val) {
//cout< > &board) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
static int times = 0;
//if(times ++ > 0) return;

vector pts;//empty positions
int rows = board.size();
if(0 == rows) return;
int cols = board[0].size();
if(0 == cols) return;

//1.found all the empties
for(int ir = 0 ; ir < rows; ++ir) {
for(int ic = 0; ic < cols; ++ ic) {
if(board[ir][ic] == '.') {
Position p;
p.row = ir;
p.col = ic;
pts.push_back(p);
}
}
}
if(pts.size() == 0) return;//no empty cells

//2.back tracing to fill the empties
int curi = 0;
bool forward = true;
board[pts[curi].row][pts[curi].col] = '1';
while(curi >= 0) {
if(curi >= pts.size()) return;
Position &curPt = pts[curi];
if(forward) {
bool valid = isValid(board,curPt);
if(valid) {
++curi;
} else {
forward = false;
}
} else {
char &c = board[curPt.row][curPt.col];
if(c == '9') {
//no siblings
c = '.';
--curi;
} else {
c += 1;
forward = true;
}
}
}
}//end function
};
```

## LeetCode题目：Substring with Concatenation of All Words

Substring with Concatenation of All Words
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: “barfoothefoobarman”
L: [“foo”, “bar”]
You should return the indices: [0,9].
(order does not matter).

```class Solution {
public:
vector findSubstring(string S, vector &L) {
map words;
map curStr;
for(int i = 0; i < L.size(); ++i)
++words[L.at(i)];
int N = L.size();
vector ret;
if(N <= 0)   return ret;
int M = L.at(0).size();
for(int i = 0; i <= (int)S.size()-N*M; ++i)
{
curStr.clear();
int j = 0;
for(j = 0; j < N; ++j)
{
string w = S.substr(i+j*M, M);
if(words.find(w) == words.end())
break;
++curStr[w];
if(curStr[w] > words[w])
break;
}
if(j == N)  ret.push_back(i);
}
return ret;
}
};
```

```class Solution {
public:
vector findSubstring(string S, vector &L) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector result;
if(L.size() == 0) return result;
const int wsize = L[0].size();
if(wsize == 0) return result;
//const int minSize = wsize * L.size();
const int notfound = -1;
vector pos(L.size(),notfound);
int si = 0;
while(S.size() - si >= wsize) {
vector mwis;
string possibleword = S.substr(si,wsize);
for(int wi = 0 ; wi < L.size(); ++wi) {
if(possibleword == L[wi]) {
mwis.push_back(wi);
}
}
int matchwordi = notfound;
if(mwis.size() > 0) {
matchwordi = mwis[0];
for(int i = 1 ;pos[matchwordi] != notfound &&  i < mwis.size(); ++i) {
if(pos[mwis[i]] < pos[matchwordi]) {
matchwordi = mwis[i];
}
}
}
if(matchwordi == notfound) {
//no match word found, clear all the pos
for(int i = 0 ; i < pos.size(); ++i) {
pos[i] = notfound;
}
++si;
} else {
//found one
if(pos[matchwordi] != notfound) {
//if this word is already matched,
// clear all the word found before it's old position
int prepos = pos[matchwordi];
for(int i = 0; i < pos.size(); ++i) {
if(pos[i] <= prepos) {
pos[i] = notfound;
}
}
}
pos[matchwordi] = si;

//check if all the word is found
{
int minindex = S.size();
for(int i = 0 ; minindex != notfound && i < pos.size(); ++i) {
if(pos[i] < minindex)
minindex = pos[i];
}
if(minindex != notfound) {
//found valid match for all words
result.push_back(minindex);
}
}

si += wsize;
}
}
return result;
}
};
```

## LeetCode题目：Subsets II

[1,1,1]，那么可以存在的bits位是：
0,0,0 = 0
1,0,0 = 1
1,1,0 = 3
1,1,1 = 7

Subsets II
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

```class Solution {
public:
vector > subsetsWithDup(vector &S) {
vector > result;
if(S.size() < 1)
return result;
sort(S.begin(),S.end());
vector pres(S.size(),false);
//pres[0] = true;//first
while(true) {
//1.output current
{
vector item;
for(int i = 0 ; i < pres.size(); ++i){
if(pres[i])
item.push_back(S[i]);
}
result.push_back(item);
}
//2.pregress
bool overflow = true;
for(int i = 0 ; overflow && i < pres.size(); ++ i) {
overflow = overflow && pres[i];
pres[i] = !pres[i];
//if i is present then propogate backward to the same ones.
if(pres[i] == true) {
for(int j = i - 1; j >= 0 && S[j] == S[i]; -- j)
pres[j] = true;
}
}
if(overflow) break;
}//end of while
return result;
}
};
```

## LeetCode题目：Subsets

Subsets
Given a set of distinct integers, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

```class Solution {
public:
vector > subsets(vector &S) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > result;
if(S.size() < 1)
return result;
sort(S.begin(),S.end());
vector pres(S.size(),false);
//pres[0] = true;//first
while(true) {
//1.output current
{
vector item;
for(int i = 0 ; i < pres.size(); ++i){
if(pres[i])
item.push_back(S[i]);
}
result.push_back(item);
}
//2.pregress
bool overflow = true;
for(int i = 0 ; overflow && i < pres.size(); ++ i) {
overflow = overflow && pres[i];
pres[i] = !pres[i];
}
if(overflow) break;
}//end of while
return result;
}
};
```

## LeetCode题目：String to Integer (atoi)

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

```class Solution {
public:
int atoi(const char *str) {
int i = 0;
int sign = 1;
bool innum = false;
int max =  2147483647;
int premax = 214748364;
int min = -2147483648;
while(*str != '\0') {
char c = *str;
if(c >= '0' && c <= '9') {
innum = true;
int digit = c - '0';
bool overflow = false;
if(i - premax >= 1) {
overflow = true;
} else if (i == premax) {
overflow = digit > 7;
}
if(overflow)
return (sign == 1 ? max : min);
i = 10 * i + (c - '0');
} else {
if(innum) break;
if (c == '-') {
sign = -1;
innum = true;
} else if(c == '+') {
innum = true;
} else if(c!= ' ') {
break;
}
}
++str;
}
return sign * i;
}
};
```

## LeetCode题目：Sqrt(x)

Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.

```class Solution {
public:
int sqrt(int x) {
if(x <= 1) return x;
double tpre = x;
double t = tpre;
for(int i = 0 ; i < 20; ++i) {
//newtown t1 = t0 - f(t0) / f'(t0);
t = (tpre * tpre + x) * 0.5 / tpre;
tpre = t;
}
return floor(t);
}
};
```

## LeetCode题目：Spiral Matrix II

Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

```class Solution {
public:
void nextDirection(int &steprow, int &stepcol){
if(steprow == 0) {//horizental
steprow = stepcol;
stepcol = 0;
} else if (stepcol == 0) {//vertical
stepcol = -steprow;
steprow = 0;
}
}
vector > generateMatrix(int n) {
// steps will like:
// n right, n-1 down, n-1 left, n-2 up, n-2 right, n-3 down, n-3 left,......
// each two phases ,steps count shink by 1;
// each 1 phases, direction turned
int steprow = 0,stepcol = 1;
bool reborned = true;
int ri = 0,ci = 0;
vector > mat(n, vector(n));
int val = 1;
int vallmt = n * n;
int stepslmt = n;
int steps = stepslmt;
while(val <= vallmt) {
mat[ri][ci] = val ++;
if(0 == --steps) {
nextDirection(steprow,stepcol);
if(reborned) {
steps = --stepslmt;
reborned = false;
} else {
steps = stepslmt;
reborned = true;
}
}
ri += steprow;
ci += stepcol;
}
return mat;
}
};
```

## LeetCode题目：Spiral Matrix

Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].

```class Solution {
public:
vector spiralOrder(vector > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector arr;
int rows = matrix.size();
if(0 == rows) return arr;
int cols = matrix[0].size();
if(0 == cols) return arr;
int bri = 0, bci = 0;//short for base row index, base column index
while(rows > 0 && cols > 0) {
//add a spiral circle based at bri and bci in matrix
if(rows == 1) {
for(int ci = bci; ci < bci + cols; ++ ci) {
arr.push_back(matrix[bri][ci]);
}
break;
} else if (cols == 1) {
for(int ri = bri; ri < bri + rows; ++ri) {
arr.push_back(matrix[ri][bci]);
}
break;
}
//rows >= 2 and cols >= 2, a circle well formed
//top
for(int ci = bci; ci < bci + cols; ++ci) {
arr.push_back(matrix[bri][ci]);
}
//right
for(int ri = bri + 1; ri < bri + rows; ++ri) {
arr.push_back(matrix[ri][bci + cols - 1]);
}
//bottom
for(int ci = bci + cols - 2; ci >= bci; --ci) {
arr.push_back(matrix[bri + rows - 1][ci]);
}
//left
for(int ri = bri + rows - 2; ri > bri; --ri) {
arr.push_back(matrix[ri][bci]);
}
rows -= 2;
cols -= 2;
bri += 1;
bci += 1;
}//end while
return arr;
}
};
```

Code rewrite at 2012-12-23, 4ms pass the large test set

```class Solution {
int _ir;//current positon of row index
int _ic;//current postion of col index
int _rows;//total rows at current point
int _cols;//total cols at current point
int _offsetr,_offsetc;//current direction
int _steps;//remaining steps in a line
void setup(int rows, int cols) {
_ir = 0;
_ic = 0;
_rows = rows;
_cols = cols;
_offsetr = 0;
_offsetc = 1;
_steps = cols;
}
void nextDirection() {
if(_offsetr == 0) {
//horizentoal moving
_offsetr = _offsetc > 0 ? 1 : -1;
_offsetc = 0;
_steps = --_rows;
} else {
//vertically
_offsetc = _offsetr > 0 ? -1 : 1;
_offsetr = 0;
_steps = --_cols;
}
}
bool nextPosition() {
if(--_steps == 0) {
//need turn direction
nextDirection();
if(_steps == 0) return false;
}
_ir += _offsetr;
_ic += _offsetc;
return true;
}
public:
vector spiralOrder(vector > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector ret;
int rows = matrix.size();
if(rows == 0) return ret;
int cols = matrix[0].size();
if(cols == 0) return ret;

setup(rows, cols);
do {
ret.push_back(matrix[_ir][_ic]);
} while (nextPosition());

return ret;
}
};
```

## LeetCode题目：Sort Colors

cur从0到j扫描，

Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library’s sort function for this problem.
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
Could you come up with an one-pass algorithm using only constant space?

```class Solution {
public:
inline void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void sortColors(int A[], int n) {
if(n <= 1) return;
int i = 0,j = n-1;
int cur = i;
while(cur <= j) {
if(A[cur] == 0) {
if(cur > i) {
swap(A[i++],A[cur]);
} else {
++cur;
++i;
}
} else if (A[cur] == 2) {
if(cur < j)
swap(A[j--],A[cur]);
else
return;
} else
++cur;
}
}
};
```

## LeetCode题目：Simplify Path

Simplify Path
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = “/home/”, => “/home”
path = “/a/./b/../../c/”, => “/c”
Corner Cases:
Did you consider the case where path = “/../”?
In this case, you should return “/”.
Another corner case is the path might contain multiple slashes ‘/’ together, such as “/home//foo/”.
In this case, you should ignore redundant slashes and return “/home/foo”.

```class Solution {
public:
string simplifyPath(string path) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
list pathes;
int i = 0;
while(i < path.size()) {
if(path[i] == '/') {
++i;
} else if (path[i] == '.') {
if(i + 1 < path.size() && path[i + 1] == '.') {
if(pathes.size()) pathes.pop_back();
i += 2;
} else {
++i;
}
} else {
int j = i + 1;
while(j < path.size() && path[j] != '/') ++j;
string subpath = path.substr(i,j - i);
pathes.push_back(subpath);
i = j;
}
}
string result;
while(pathes.size()) {
result.append("/");
result.append(pathes.front());
pathes.pop_front();
}
if(!result.size())
result.append("/");
return result;
}
};
```

Code rewrite at 2013-1-21

```class Solution {
public:
string simplifyPath(string path) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector pathes;
string seg = "";
for(int i = 0; i <= path.size(); ++i) {
if(i == path.size() || path[i] == '/') {
if(seg == "..") {
if(pathes.size() > 0) {
pathes.pop_back();
} else {
//return "/";//error, in the test set, this case just ignore
}
} else if(seg == ".") {
//do nothing
} else if(seg.size() > 0) {
pathes.push_back(seg);
}
seg = "";
} else {
seg += path[i];
}
}
string ret="/";
for(int i = 0; i < pathes.size(); ++i) {
if(i>0) ret += "/";
ret += pathes[i];
}
return ret;
}
};
```

## LeetCode题目：Set Matrix Zeroes

1.先确定第一行和第一列是否需要清零

2.扫描剩下的矩阵元素，如果遇到了0，就将对应的第一行和第一列上的元素赋值为0

3.根据第一行和第一列的信息，已经可以将剩下的矩阵元素赋值为结果所需的值了

4.根据1中确定的状态，处理第一行和第一列。

Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

```class Solution {
public:
void setZeroes(vector > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rows = matrix.size();
if(0 == rows) return;
int cols = matrix[0].size();
if(0 == cols) return;
//using first row and col as storage
//1.search zero in first row and col to determin it's own status
bool zerorow0 = false;
bool zerocol0 = false;
for(int ci = 0; ci < cols; ++ci) {
if(matrix[0][ci] == 0) {
zerorow0 = true;
break;
}
}
for(int ri = 0; ri < rows; ++ri) {
if(matrix[ri][0] == 0) {
zerocol0 = true;
break;
}
}
//2.search zeros in other position to sign the first row and col
for(int ri = 1; ri < rows; ++ri) {
for(int ci = 1; ci < cols; ++ci) {
if(matrix[ri][ci] == 0) {
matrix[0][ci] = 0;
matrix[ri][0] = 0;
}
}
}
//3.set zeroes in other positions according to first col and row
for(int ri = 1; ri < rows; ++ri) {
for(int ci = 1; ci < cols; ++ci) {
if(matrix[0][ci] == 0 || matrix[ri][0] == 0) {
matrix[ri][ci] = 0;
}
}
}
//4.set zeroes for first row and col
if(zerorow0){
for(int ci = 0; ci < cols; ++ci) {
matrix[0][ci] = 0;
}
}
if(zerocol0){
for(int ri = 0; ri < rows; ++ri) {
matrix[ri][0] = 0;
}
}
}
};
```

## LeetCode题目：Search Insert Position

Search Insert Position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

```class Solution {
public:
int searchInsert(int A[], int n, int target) {
if(n <= 0) return 0;
int i=0,j=n-1;
while(i <= j) {
int mid = (i + j)/2;
int mv = A[mid];
if(mv == target)
return mid;
if(mv < target)
i = mid+1;
else
j = mid-1;
}
return i;
}
};
```

## LeetCode题目：Search in Rotated Sorted Array II

Search in Rotated Sorted Array II
Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.

```class Solution {
public:
bool search(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n <= 0) return false;
int i = 0, j = n-1;
while(i <= j) {
int mid = (i + j) / 2;
int mval = A[mid];
if(target == mval) return true;
if(i == j) return false;
if(A[i] < A[j]) {
//we are in the normal sorted array range
if(target < mval)
j = mid - 1;
else
i = mid + 1;
} else if (A[i] > A[j]) {
//we are in the rotated range of array
if(mval > A[i]) {
//mid is in the ascending part of arr
if(target < mval) {
if(target < A[i]) {
//target should be in the rear of array
i = mid + 1;
} else if (target == A[i]) {
return true;
} else {
//target should be in the front
j = mid - 1;
}
}
else
i = mid + 1;
} else if (mval < A[i]) {
if(target < mval) {
j = mid - 1;
} else {
if(target == A[j])
return j;
else if(target < A[j])
i = mid + 1;
else
j = mid - 1;
}
} else {
i = mid + 1;
}
} else {
//A[i] == A[j]
if(mval == A[i]) {
bool onleft = search(A + i + 1, mid - i + 1 - 2, target);
if(onleft) return true;
return search(A + mid + 1, j - mid + 1 - 2, target);
} else if (mval > A[i]) {
if(target < mval) {
if(target == A[i]) return true;
else if(target < A[i]) {
i = mid + 1;
--j;
} else {
++i;
j = mid - 1;
}
} else {
i = mid + 1;
--j;
}
} else {
//mval < A[i]
if(target < mval) {
++i;
j = mid + 1;
} else {
if(target == A[j]) return true;
else if(target < A[j]) {
--j;
i = mid + 1;
} else {
++i;
j = mid - 1;
}
}
}
}
}
return false;
}
};
```

## LeetCode题目：Search in Rotated Sorted Array

Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

```class Solution {
public:
int search(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n <= 0) return -1;
int i = 0, j = n-1;
while(i <= j) {
int mid = (i + j) / 2;
int mval = A[mid];
if(target == mval) return mid;
if(i == j) return -1;
if(A[i] < A[j]) {
//we are in the normal sorted array range
if(target < mval)
j = mid - 1;
else
i = mid + 1;
} else if (A[i] > A[j]) {
//we are in the rotated range of array
if(mval > A[i]) {
//mid is in the ascending part of arr
if(target < mval) {
if(target < A[i]) {
//target should be in the rear of array
i = mid + 1;
} else if (target == A[i]) {
return i;
} else {
//target should be in the front
j = mid - 1;
}
}
else
i = mid + 1;
} else if (mval < A[i]) {
if(target < mval) {
j = mid - 1;
} else {
if(target == A[j])
return j;
else if(target < A[j])
i = mid + 1;
else
j = mid - 1;
}
} else {
i = mid + 1;
}
} else {
//unsure
return -3;
}
}
return -1;
}
};
```

Code rewrite at 2012-12-24, 28 ms pass large set
Draw an image and status situations(3 conditions) to solve this problem.

```class Solution {
public:
int search(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (n <= 0) return -1;
int ileft = 0, iright = n-1;
if(A[ileft] == target) return ileft;
bool searchFirst = target > A[ileft];
while(ileft <= iright) {
int imid = (ileft + iright) / 2;
if(A[imid] == target)
return imid;
bool inFirstSegment = A[ileft] < A[iright] || A[imid] > A[iright];
bool tlessm = target < A[imid];
if (searchFirst == inFirstSegment == tlessm) {
iright = imid - 1;
} else {
ileft = imid + 1;
if(A[ileft] == target) return ileft;
searchFirst = target > A[ileft];
}
}
return -1;
}
};
```

## LeetCode题目：Search for a Range

Search for a Range
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

```class Solution {
public:
vector searchRange(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector result(2,-1);
if(0 == n) return result;
if(A[0] > target) return result;
if(A[n-1] < target) return result;
int i = 0,j = n-1;
int ti = -1;
while(i <= j) {
int mid = (i+j) / 2;
int midval = A[mid];
if(target == midval) {
ti = mid;
break;
} else if (target < midval)
j = mid - 1;
else
i = mid + 1;
}
int si = 0, sj = ti - 1;
while(si <= sj) {
int mid = (si + sj) / 2;
int midval = A[mid];
if(target == midval) {
sj = mid - 1;
} else {
si = mid + 1;
}
}
//at last si will equal to sj, mid == si == sj, if midval == target, sj will be 1 position before target, else sj is some time before the final test to be 1 postion before target. so, over all, sj will be 1 position before target after the loop break.
result[0] = sj + 1;
int ei = ti + 1, ej = n - 1;
while(ei <= ej) {
int mid = (ei + ej) / 2;
int midval = A[mid];
if(target == midval)
ei = mid + 1;
else
ej = mid - 1;
}
result[1] = ei - 1;
return result;
}
};
```

## LeetCode题目：Search a 2D Matrix

Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.

```class Solution {
public:
bool searchMatrix(vector > &matrix, int target) {
int rows = matrix.size();
if(rows == 0) return false;
int cols = matrix[0].size();
if(cols == 0) return false;
if(matrix[0][0] > target) return false;
if(matrix[rows -1][cols -1] < target) return false;

//1.binary search to loate the row which target should be in.
int ri = 0 , rj = rows - 1;
while(ri <= rj) {
int mid = (ri + rj) / 2;
int midval = matrix[mid][0];
if(midval == target)
return true;
else if(target < midval)
rj = mid - 1;
else
ri = mid + 1;
}
if(ri == rows || matrix[ri][0] > target){
--ri;
}
//2.binary search in the specific row for target
int ci = 0, cj = cols - 1;
while(ci <= cj) {
int mid = (ci + cj) / 2;
int midval = matrix[ri][mid];
if(target == midval)
return true;
else if(target < midval)
cj = mid - 1;
else
ci = mid + 1;
}
return false;
}
};
```

## LeetCode题目：Scramble String，三维动态规划

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = “great”:

```    great
/    \
gr    eat
/ \    /  \
g   r  e   at
/ \
a   t
```

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

```    rgeat
/    \
rg    eat
/ \    /  \
r   g  e   at
/ \
a   t
```

We say that “rgeat” is a scrambled string of “great”.
Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

```    rgtae
/    \
rg    tae
/ \    /  \
r   g  ta  e
/ \
t   a
```

We say that “rgtae” is a scrambled string of “great”.
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

```    bool isScrambleDP(string s1, string s2) {
if(s1.size() != s2.size()) return false;
if(s1.size() == 0) return true;
if(s1 == s2) return true;
bool ***iss = NULL;//iss[len][startIndexAtS1][startIndexAtS2]
iss = new bool**[s1.size()];
for(int len = 1;len <= s1.size(); ++len) {
//size at this level
int levelSize = s1.size() - len + 1;
int levelIndex = len - 1;
iss[levelIndex] = new bool*[levelSize];
for(int indexS1 = 0;indexS1 < levelSize; ++ indexS1) {
iss[levelIndex][indexS1] = new bool[levelSize];
for(int is2 = 0; is2 < levelSize; ++is2) {
if(len == 1) {
iss[levelIndex][indexS1][is2] = (s1[indexS1] == s2[is2]);
} else {
iss[levelIndex][indexS1][is2] = false;
for(int seglen1 = 1; seglen1 < len; ++seglen1) {
int seglen2 = len - seglen1;
int sli1 = seglen1 - 1;
int sli2 = seglen2 - 1;
if(iss[sli1][indexS1][is2] && iss[sli2][indexS1 + seglen1][is2 + seglen1]) {
iss[levelIndex][indexS1][is2] = true;
break;
}
if(iss[sli1][indexS1][is2 + seglen2] && iss[sli2][indexS1 + seglen1][is2]) {
iss[levelIndex][indexS1][is2] = true;
break;
}
}
}
}
}
}
return iss[s1.size() - 1][0][0];
}
```

```class Solution {
public:
bool isScramble(string s1, string s2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s1.size() != s2.size()) return false;
if(s1 == s2) return true;
for(int isep = 1; isep < s1.size(); ++ isep) {
//seporate s1 as [0,isep - 1],[isep, s1.size() - 1]
string seg11 = s1.substr(0,isep);
string seg12 = s1.substr(isep);
{//see if forward order is ok
string seg21 = s2.substr(0,isep);
string seg22 = s2.substr(isep);
if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
}
{//see if reverse order is ok
string seg21 = s2.substr(s2.size() - isep);
string seg22 = s2.substr(0,s2.size() - isep);
if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
}
}
return false;
}
};
```

Recursive code rewrite at 2013-2-5, 48ms pass large set

```class Solution {
public:
bool isScramble(string s1, string s2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s1.size() != s2.size()) return false;
if(s1 == s2) return true;
string ts1 = s1,ts2 = s2;
sort(ts1.begin(), ts1.end());
sort(ts2.begin(), ts2.end());
if(ts1 != ts2) return false;
for(int isep = 1; isep < s1.size(); ++ isep) {
//seporate s1 as [0,isep - 1],[isep, s1.size() - 1]
string seg11 = s1.substr(0,isep);
string seg12 = s1.substr(isep);
{//see if forward order is ok
string seg21 = s2.substr(0,isep);
string seg22 = s2.substr(isep);
if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
}
{//see if reverse order is ok
string seg21 = s2.substr(s2.size() - isep);
string seg22 = s2.substr(0,s2.size() - isep);
if(isScramble(seg11,seg21) && isScramble(seg12,seg22)) return true;
}
}
return false;
}
};
```

## LeetCode题目：Same Tree

Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
if(p == NULL) {
return q == NULL;
} else {
if(q == NULL)
return false;
else {
if(q->val != p->val)
return false;
bool leftsame = isSameTree(p->left,q->left);
if (!leftsame) return false;
return isSameTree(p->right,q->right);
}
}
}
};
```

## LeetCode题目：Rotate List

Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
int count = 0;
while(*prob){
prob = &((*prob)->next);
++count;
}
k = k % count;

for(int i = 0 ; i < count - k; ++i) {
prob = &((*prob)->next);
}
*prob = NULL;

}
};
```

## LeetCode题目：Rotate Image

Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Could you do this in-place?

```class Solution {
public:
void rotate(vector > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rows = matrix.size();
if(rows == 0) return;
int cols = matrix[0].size();
if(cols == 0 || rows != cols) return;
for(int ilevel = 0; ilevel < rows / 2; ++ ilevel) {
int lCount = rows - 1 - 2 * ilevel;
for(int i = 0; i < lCount; ++i) {
//caculate the positions
int topr = ilevel;
int topc = ilevel + i;
int rightr = ilevel + i;
int rightc = cols - 1 - ilevel;
int downr = rows - 1 - ilevel;
int downc = cols - 1 - ilevel - i;
int leftr = rows - 1 - ilevel - i;
int leftc = ilevel;
//swap them
int temp = matrix[topr][topc];
matrix[topr][topc] = matrix[leftr][leftc];
matrix[leftr][leftc] = matrix[downr][downc];
matrix[downr][downc] = matrix[rightr][rightc];
matrix[rightr][rightc] = temp;
}
}
}
};
```

```class Solution {
public:
void rotate(vector > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int rows = matrix.size();
if(rows <= 1) return;
int cols = matrix[0].size();
if(cols != rows) return;
int baser = 0,basec = 0;
for(int level = rows; level >= 2;) {
for(int i = 0; i < level - 1; ++ i) {//skip last
//top
int temp = matrix[baser][basec + i];
//top == left
matrix[baser][basec + i] = matrix[baser + level - 1 - i][basec];
//left = bottom
matrix[baser + level - 1 - i][basec]
= matrix[basec + level - 1][basec + level - 1 - i];
//bottom = right
matrix[basec + level - 1][basec + level - 1 - i]
= matrix[baser + i][basec + level - 1];
//right = top
matrix[baser + i][basec + level - 1] = temp;
}
++baser;
++basec;
level -= 2;
}
}
};
```

## LeetCode题目：Roman to Integer

• 如果当前处理的字符对应的值和上一个字符一样，那么临时变量加上这个字符。比如III = 3
• 如果当前比前一个大，说明这一段的值应该是当前这个值减去前面记录下的临时变量中的值。比如IIV = 5 – 2
• 如果当前比前一个小，那么就可以先将临时变量的值加到结果中，然后开始下一段记录。比如VI = 5 + 1

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

代码：208ms过大集合

```class Solution {
public:
inline int c2n(char c) {
switch(c) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return 0;
}
}
int romanToInt(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s.size() < 1) return 0;
char sb[9] = { 'I','V','X', 'L','C', 'D','M', 'v', 'x' };//v和x应该是大写的上面有一横
int result = 0;
int sub = c2n(s[0]);
int lastv = sub;
for(int i = 1 ; i < s.size(); ++i) {
char curc = s[i];
int curv = c2n(curc);
if(curv == lastv)
sub += curv;
else if( curv < lastv) {
result += sub;
sub = curv;
} else {
sub = curv - sub;
}
lastv = curv;
}
result += sub;
return result;
}
};
```

## LeetCode题目：Reverse Nodes in k-Group

和上一题差不错，不过这次干脆换了简单的reverse方法，每次取末尾一个接到前面去。
在框架定了之后，确定循环次数就好了。

Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

代码：144ms过大集合

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
int subcount = 0;
while(pTail) {
++subcount;
if(k == subcount) {
//reverse node from *pps to pTail
ListNode *remainTail = pTail->next;
for(;subcount > 0; --subcount) {
ListNode *subTail = *pps;
for(int i = 0 ; i < subcount - 1; ++i) {
subTail = subTail->next;
}
subTail->next = *pps;
*pps = subTail;
pps = &(subTail->next);
}
//reset
pps = &((*pps)->next);
*pps = remainTail;
subcount = 0;
pTail = *pps;
} else
pTail = pTail->next;
}
}
};
```

Code rewrite at 2013-2-16, 136ms pass the large set

```class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
if (k < 2) return head;
//  thus if we modify *ppStart, the point target of the head is modified as well.
while(*ppStart) {
//1.first get the segment which need reverse
ListNode *pEnd = *ppStart;
for(int i = 1; pEnd && i < k; ++i) {
pEnd = pEnd->next;
}
//2.if there is k nodes need reverse,
//  then pEnd will point to the last node in the k-segment
//      and the *ppStart point to the first node of the k-segment
//  otherwise, pEnd is NULL.
if(pEnd) {
//2.1.Reverse the k-segment
//the tail of the reversed k-segment,
//  each time, move the next node to the front of this k-segment
//  moving k-1 times.
ListNode *pSubTail = *ppStart;
for(int i = 1; i < k; ++i) {
//move pNext to the front
ListNode *pNext = pSubTail->next;
//make the remain list linked to the tail
pSubTail->next = pNext->next;
//the node pointed by pNext become the new head of the k-segment
pNext->next = *ppStart;
//link the new k-segment to the list before.
*ppStart = pNext;
}
//update the ppStart to point to the next pointer of the new tail of k-segment.
ppStart = &(pSubTail->next);
} else {
//the remain nodes is less than k, so break.
break;
}
}
}
};
```

其实是一个简单题，只不过要考虑的临界情况还挺多。
如果用stack来做的话，超简单，不过貌似不满足题目上inplace的要求。
于是只好用笨一点的方法，就是先找到反转链开头，然后找到要反转的尾巴，调转两个node，然后让m+1，n-1，继续这个过程，直到m >= n为止。
有一个临界情况是当要反转的子链只有两个node的时候，由于缺了中间一段，导致出现死循环。

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

代码：16ms过大集合

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
//first find the first break point
for(int i = 0 ; i < m - 1; ++i) {
firstBreak = &( (*firstBreak) -> next );
}
//find the tail and point out the mid segment start/end point

//reverset the middle segment
{
int rStep = n - m;
while(rStep > 0) {
ListNode ** pprTail = firstBreak;
for(int i = 0 ; i < rStep; ++i)
pprTail = &((*pprTail)->next);

ListNode *firstNode = *firstBreak;
ListNode *lastNode = *pprTail;
ListNode *pOut = lastNode->next;
ListNode *ps = firstNode->next;

if(ps == lastNode) {
ps = firstNode;
}

//cout<val<<","<val<<","<next = ps;
*pprTail = firstNode;
firstNode->next = pOut;

firstBreak = &(lastNode->next);
rStep -= 2;

//cout<val<<",";
t = t->next;
}
return NULL;
}
}
};
```

## LeetCode题目：Reverse Integer

题目让反转一个int，主要问题在于如何考虑越界问题。

Reverse Integer
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
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?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

代码：40ms过大集合

```class Solution {
public:
int reverse(int x) {
int sup = 1;
{//find the most significant bit
int temp = x;
while(temp /= 10) {
sup *= 10;
}
}
int sub = 10;
int y = 0;//result
while(sup >= sub) {
int dsup = x / sup;
int dsub = (x % sub) / (sub / 10);
//cout<<dsup<<","<<dsub<<",";
x -= sup * dsup;
x -= (sub / 10) * dsub;
//cout<<x<<"|";
y += sup * dsub;
y += (sub / 10) * dsup;

sup /= 10;
sub *= 10;
}
if (sup * 10 == sub) {
y += x;
}
return y;
}
};
```

用回溯算法解，还是得益于前面总结的方案，只在forward的时候进行强有效判断，在反向的时候只做简单判断就可以了。
用一个数组（5个元素）记录每一小段ip地址的起始index，最后一个元素是s.size()，用作哨兵。
用一个变量curi记录当前操作的小段index，另一个变量forward表示状态。
如果forward==true，那么首先判断当前小段是否合法，如果有效那么进入下一小段进行处理；否则forward反转。
如果forward==false，那么判断当前小数点是否可以右移，可以的话右移，forward置位；否则curi回退，处理上一小段。

细节很重要：

`valid = valid && remain <= remainmax && remain >= (4 - curi);`

一开始最后一个条件没写，结果总报运行时错误。

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given “25525511135”,
return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

代码：8ms过大集合

```class Solution {
public:
vector result;
if(s.size() < 4) return result;
int start[5];//each section start index, last for end
start[0] = 0;
start[4] = s.size();
start[1] = 1;
int curi = 1;//current dot index, 4 for the one exceed whole ip address
bool forward = true;
while(curi > 0) {
if(forward) {
//check validation of self
bool valid = true;
if(valid) {//check len of section before dot is no more than 3
int count = start[curi] - start[curi - 1];
valid = valid && count <= 3;
if(valid && count > 1) {
//if the len of section > 1, then the leading digit could not be 0
valid = s[start[curi - 1]] != '0';
}
}
if(valid) {//check remain digits count validation
int remain = s.size() - start[curi];
int remainmax = (4 - curi) * 3;
valid = valid && remain <= remainmax && remain >= (4 - curi);
}
if(valid) {//check section value not exceed 255
int secvalue = 0;
for(int i = start[curi - 1]; i < start[curi]; ++i) {
secvalue *= 10;
secvalue += (s[i] - '0');
}
valid = valid && secvalue <= 255;
}
if(valid) {
if(curi == 4) {
//this is a valid solution
string ip = s.substr(start[0],start[1] - start[0]);
for(int isec = 1; isec < 4; ++isec) {
ip = ip + '.' + s.substr(start[isec],start[isec + 1] - start[isec]);
}
result.push_back(ip);
--curi;
forward = false;
} else {
//check if there is a child to go
if(curi == 3) {
start[curi + 1] = s.size();
} else {
start[curi + 1] = start[curi] + 1;
}
++curi;
}
} else {
if(curi == 4) {
curi = 3;
}
forward = false;
}
} else {
//backward
int count = start[curi] - start[curi - 1];
if (count < 3) {
++start[curi];
forward = true;
} else {
--curi;
}
}
}//end while
return result;
}
};
```

## 利用XCode中Interface Builder的Runtime Attribute来设置运行时参数，比如圆角

要设置一个view的圆角，可以通过在代码里面写上：

`aView.layer.cornerRadius = 10`

这样的内容来将其圆角设为10px。

其实在interface builder中，完全可以设置圆角，不用写一行代码：

选择要设置圆角的view之后，在这个页面下可以设置其runtime attribute,只需要添加一个keypath，设置好它的类型和值就可以了。
不过要记得将view的clipSubviews设为true哦。

## LeetCode题目：Remove Nth Node From End of List

Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

代码：32ms过大集合

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
//let prob go first by n step
for(int i = 0 ; i < n; ++i) {
if(NULL == *prob) return head;//input error occur
prob = &((*prob)->next);
}
//let prob and pre go synchronized
while(NULL != *prob) {
prob = &((*prob)->next);
pre = &((*pre)->next);
}
//remove the next node of pre in the list
*pre = (*pre)->next;
}
};
```

## LeetCode题目：Remove Element

Remove Element
Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

代码：24ms过大集合

```class Solution {
public:
int removeElement(int A[], int n, int elem) {
int len = 0;
for(int i = 0 ; i < n; ++i) {
if(A[i] != elem) A[len++] = A[i];
}
return len;
}
};
```

## LeetCode题目：Remove Duplicates from Sorted List II

Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

代码：44ms过大集合

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *root = NULL;
ListNode **ppNext = &root;
} else {
do {
}
}
*ppNext = NULL;
return root;
}
};
```

## LeetCode题目：Remove Duplicates from Sorted List

简单，链表的问题注意收尾。

Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

代码：84ms过大集合

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode *cur = last->next;
while(cur) {
if(cur->val != last->val) {
last->next = cur;
last = cur;
}
cur = cur->next;
}
last->next = NULL;
}
};
```

## LeetCode题目：Remove Duplicates from Sorted Array II

在上一题的基础上跟踪最后一个元素的重复度就行了。

Remove Duplicates from Sorted Array II
What if duplicates are allowed at most twice?
For example,
Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3].

代码：72ms过大集合

```class Solution {
public:
int removeDuplicates(int A[], int n) {
if (n < 2) return n;
int len = 1;
bool duplicated = false;
for(int i = 1; i < n; ++i) {
if(A[i] != A[len - 1]) {
A[len++] = A[i];
duplicated = false;
} else if (!duplicated) {
A[len++] = A[i];
duplicated = true;
}
}
return len;
}
};
```

## LeetCode题目：Remove Duplicates from Sorted Array

很直观的问题，每次和已经记录的最后一个数组元素比较，如果重复就跳过，否则将其加入数组末尾。

Remove Duplicates from Sorted Array
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].

代码，64ms过大集合

```class Solution {
public:
int removeDuplicates(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (n < 2) return n;
int len = 1;
for(int i = 1; i < n; ++i) {
if(A[i] != A[len - 1]) {
A[len++] = A[i];
}
}
return len;
}
};
```

## 最快的sqrt函数，源自Quake

昨晚看到题目如何实现sqrt方法后睡觉，边睡边想，从开方的意义想到了二分，再想到牛顿法。
早上起来，想看看系统究竟是如何实现的，于是百度之，发现了一篇文章介绍了目前最快的方法，还是牛顿迭代，只不过初值选得匪夷所思：

```//计算 1 / sqrt(x)
float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating VALUE
i = 0x5f375a86- (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits BACK to float
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return x;
}
```

据文章所述，此方法源自Quake源代码。
文章链接：http://www.2cto.com/kf/201206/137256.html

## LeetCode题目：Multiply Strings

Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

模拟手动乘法做一遍就ok

```class Solution {
public:
string multiply(string num1, string num2) {
vector prods(num2.size(),string(num1.size() + 1,'0'));
for(int i = 0 ; i < num2.size() ; ++ i) {
char n2i = num2[num2.size() - 1 - i];
int dig2 = n2i - '0';
string &prod = prods[i];
int overflow = 0;
for(int i1 = 0; i1 < num1.size(); ++i1) {
char n1i = num1[num1.size() - 1 - i1];
int dig1 = n1i - '0';
int multi = dig1 * dig2 + overflow;
int mdig = multi % 10;
overflow = multi / 10;
prod[i1] = mdig + '0';
}
prod[num1.size()] = overflow + '0';
}
string result(num1.size() + num2.size() + 1,'0');
int overflow = 0;
for(int i = 0; i < result.size(); ++i){
int dsum = overflow;
for(int ip = 0; ip < num2.size(); ++ip) {
string &prod = prods[ip];
int digitI = i - ip;
if(digitI >= 0 && digitI < prod.size()) {
char pi = prod[digitI];
int pdi = pi - '0';
dsum += pdi;
}
}
overflow = dsum / 10;
int digit = dsum % 10;
result[result.size() - 1 - i] = digit + '0';
}
//trim zeroes
for(int i = 0 ; i < result.size(); ++i) {
if (result[i] != '0') {
result = result.substr(i);
break;
}
if(i == result.size() - 1) {
return "0";
}
}
return result;
}
};
```

Code rewrite at 2012-12-26, 8ms pass large set

```class Solution {
public:
string multiply(string num1, string num2) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
const int dcx = num1.size() - 1;//digital count of x, or of num1
const int dcy = num2.size() - 1;
if (dcx < 0 || dcy < 0) return "";
string ret = "";
int overflow = 0;
for(int di = 0; di <= dcx + dcy; ++di) {
int rd = overflow;
int dxis = di - dcy; dxis = dxis < 0 ? 0 : dxis;
for(int dxi = dxis; dxi <= dcx && dxi <= di; ++ dxi) {
int dx = num1[num1.size() - 1 - dxi] - '0';
int dy = num2[num2.size() - 1 - di + dxi] - '0';
rd += dx * dy;
}
overflow = rd / 10;
rd %= 10;
char digital = rd + '0';
ret = digital + ret;
}
if(overflow > 0) {
char digital = overflow + '0';
ret = digital + ret;
}
{
int zeros = 0;
for(int i = 0; i < ret.size() && ret[i] == '0'; ++ i) {
++zeros;
}
if(zeros == ret.size()) return "0";
}
return ret;
}
};
```

## LeetCode题目：Minimum Window Substring

Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
T = “ABC”
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string “”.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

分析
由于要求时间复杂度在O(n)，经测试，实际上是O(S.size())，只好用空间换时间来做。
算法实际上是维持着一个window，这个window应当覆盖了所有T中出现的字符。
随着游标在S上扫描，window逐渐向右移动。
当扫描到一个出现在T中的字符，而在window中整体出现次数还没有达到T中出现的次数时，将次数递增；
当已经达到了T中出现次数时，将window中最开始出现的此字符挤掉。
当window有效时（window中包含了所有T中出现的字符并且出现的次数是不小于T中该字符出现的次数的），就扫描一下，看这个window的长度是多少。
这样S扫描完之后，就得到了最短window。
算法除了扫描S的时间复杂度是O(S.size())之外，循环内部的所有操作都是常数次。

代码：0ms过小测试集合，113ms过大集合

```class Solution {
public:
string minWindow(string S, string T) {
if(S.size() == 0 || T.size() == 0)  return "";

int tc[256];//target count in T
for(int i = 0; i < 256; ++i) tc[i] = 0;
for(int i = 0 ; i< T.size(); ++i) ++tc[T[i]];
int totalCount = T.size();//this count down to 0, then the match is possible

int firstI[256];//first loc on specific char in T
for(int i = 0 ; i< 256; ++i) firstI[i] = -1;

int count[256];//current count for each char in T
for(int i = 0 ; i < 256; ++i) count[i] = 0;

int *nextSI = new int[S.size()];
{
int last[256];
for(int i = 0 ; i < 256; ++i) last[i] = -1;
for(int i = S.size() - 1; i >= 0; --i) {
char si = S[i];
nextSI[i] = last[si];
last[si] = i;
}
}

int minI = -1;
int minL = S.size() + 1;
for(int i = 0 ; i < S.size(); ++i) {
char si = S[i];
if(tc[si] == 0)//this char is irrelavent
continue;
if(count[si] < tc[si]) {//the count of this char is not match target yet
++count[si];
--totalCount;
if(count[si] == 1) {//record the first appearance of this char
firstI[si] = i;
}
} else {//there is more si in T, remove the first record one
firstI[si] = nextSI[firstI[si]];
}
//there will be a match
if(totalCount == 0) {
int minFirstI = S.size();
for(int ti = 0; ti < 256; ++ ti) {
if(tc[ti] == 0) continue;
int firstIndex = firstI[ti];
if (firstIndex == -1) {
minFirstI = S.size();
break;
}
if(firstIndex < minFirstI) minFirstI = firstIndex;
}
if(minFirstI < S.size()){
int len = i - minFirstI + 1;
if(len < minL) {
minL = len;
minI = minFirstI;
}
}
}
}
if(minI == -1) return "";
return S.substr(minI,minL);
}
};
```