LeetCode题目:Triangle,动态规划

逐行扫描,计算在每一个位置能取得的最小sum,实际上是该元素上面两个能取得的最小sum中最小的那一个sum加上自己的值。
动态规划,只需要开一个数组重复利用就行了。



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.



代码:40ms过大集合

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

算法很简单,核心思想是:对某个值A[i]来说,能trapped的最多的water取决于在i之前最高的值leftMostHeight[i]和在i右边的最高的值rightMostHeight[i]。(均不包含自身)。如果min(left,right) > A[i],那么在i这个位置上能trapped的water就是min(left,right) – A[i]。

有了这个想法就好办了,第一遍从左到右计算数组leftMostHeight,第二遍从右到左计算rightMostHeight,在第二遍的同时就可以计算出i位置的结果了,而且并不需要开空间来存放rightMostHeight数组。

时间复杂度是O(n),只扫了两遍。



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!



代码,44ms过大集合

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.



代码:24ms过大集合

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.



迭代算法,44ms过大集合

/**
 * 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,然后移动两个位置继续,直到无法找到两个非空节点为止。



Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
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.



代码:16ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode **ppre = &head;
        
        while(true) {
            ListNode *n0 = *ppre;
            if(NULL == n0) return head;
            ListNode *n1 = n0->next;
            if(NULL == n1) return head;
            
            //swap n0 and n1
            *ppre = n1;
            n0->next = n1->next;
            n1->next = n0;
            ListNode *next = n1->next;
            ppre = &(n0->next);
        }
        
        return head;
    }
};

LeetCode题目:Sudoku Solver,回溯

回溯可解。不过最开始判断的时候不知道第三个条件:就是总共99的格子中,有9个33的格子,在这些小格子中,1,到9也只能出现一次



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.



代码:168ms过大集合

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

一开始就想复杂了。
设总共有单词N个的话,

一开始的想法是,维护一个有N个int的数组pos,每个值记录了对应word在S中的开头字符的index。
随着在S中向右扫描,每扫到一个在单词集合中的字符,就标记一下pos。如果pos中该字符还没有出现过,那么就标记上当前的S扫描的位置;如果已经出现过了,就将pos在此之前的所有单词记录都清空,然后将当前位置记入pos。每次操作都检测pos数组,看是否所有的字符都已经在S中找到对应了。那么扫描完一遍S,就得到了所有的组合。

但是,有一个问题没有解决,那就是如果S = “mississippi”, L = {“si”,”is”)的时候。当S扫描到index = 3的时候,能找到一个组合S[1,4] = “issi”;但是下一步就出现分支了,是从S[3] = s开始呢,还是从S[4] = i开始呢。

于是就悲剧了。。这个框架其实是不适合于这种有分支的扫描的。

然后又想dp,当L.size()==1的时候;当L.size()==2的时候容易解决;但是当L.size()==3的时候呢,那就是说可以从L.size()==2的结果中,尝试前后能否拼上L[2]来计算一部分结果,另一部分结果是将L[2]插在L[0]和L[1]中间形成的结果中,这其实还好,能想出来解决办法。但是当L.size() > 3的时候呢,那就爆炸了(包括存储空间的爆炸)。

一旦陷入死胡同,想转弯挺难····

然后百度之,发现一个思路其实挺直观的:
一个长度为M*N的子串在S上从左到右平移,每个位置上,直接去判断是不是每一个L中的单词都出现了一次。



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



代码,转自 http://blog.csdn.net/maqingli87/article/details/8009972

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

沿用上一个题的思路,但是如果一个元素重复次数是n次的话。比如:
[1,1,1],那么可以存在的bits位是:
0,0,0 = 0
1,0,0 = 1
1,1,0 = 3
1,1,1 = 7
也就是说,对于这个子集来说,2k – 1,0 <= k <= n,是可以出现的位序列。
那么在上一题算法的递增部分,只需要跳过那些不合理的部分就可以了。做法就是,如果一个元素是present的,那么就反向将和他相等的所有元素的present置位。



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],
[]
]



代码:8ms过大集合

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

用一串bool记录处于S中每一个位置的元素是否在输出集合中。然后这个bool串当做一个int来处理,每次输出之后,从末位+1,形成新的二进制串,就是新的输出集合。重复这个过程直到所有集合都输出。



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],
[]
]

代码:40ms过大集合

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.



代码,32ms过大集合

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)

牛顿法(最速下降法),如果初值合适的话,一次迭代足以。见前面有篇blog: 最快的sqrt函数,源自Quake



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



代码:44ms过大集合。代码中的20次迭代是经验值,是适合这个测试集合的最小值。如果输入是int,这个值够了。

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

没有用上一题的方式来做,这次把方向也程序化了,而且找到了规律。总的说来当前点得走向如下:
向右走n次,向下走n-1次,向左走n-1个数,向上走n-2个数,向右走n-2个数,……
即:每两次拐弯,下次拐弯的步数减1;



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



代码:20ms过大集合

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



代码:12ms过大集合

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

已经有点浆糊了,其实很简单,用i记录0应该放的位置,j记录2应该放的位置。
cur从0到j扫描,
遇到0,放在i位置,i后移;
遇到2,放在j位置,j前移;
遇到1,cur后移。
扫描一遍得到排好序的数组。
时间O(n)且一次扫描,空间O(1),满足要求。
这么做的前提是,拿到一个值,就知道它应该放在哪儿。(这点和快排的根据pivot交换元素有点像)



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.
Follow up:
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?



代码:16ms过大集合

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

用一个stack记录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”.



代码:36ms过大集合

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.先确定第一行和第一列是否需要清零
即,看看第一行中是否有0,记下来。也同时记下来第一列中有没有0。

2.扫描剩下的矩阵元素,如果遇到了0,就将对应的第一行和第一列上的元素赋值为0
这里不用担心会将本来第一行或第一列的1改成了0,因为这些值最后注定要成为0的。

3.根据第一行和第一列的信息,已经可以将剩下的矩阵元素赋值为结果所需的值了
即,拿第一行为例,如果扫描到一个0,就将这一列都清0.

4.根据1中确定的状态,处理第一行和第一列。
如果最开始得到的第一行中有0的话,就整行清零。同理对列进行处理。



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.
Follow up:
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?



代码:344ms过大集合

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

二分出来了的话,i就是target应该在的位置。



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



代码:36ms过大集合

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

四重判断,晕了~
这个代码是可以过大集合测试的。
不过后来百度之,发现有一个更好的思路,就是第一次二分先找到pivot,之后就简单了。



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.



代码:36ms过大集合

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.



代码:24ms过大集合

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

这题也是加深对二分的理解。特别是二分的最后阶段,肯定是有si == sj的。



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



代码:64ms过大集合,时间复杂度O(logn)

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;
        }
        if(ti == -1) return result;//target not found
        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

两次二分查找,第一次在第一列找到target应该在的行,第二次在该行中二分查找target。
这个题的第一次二分,对于二分查找失败的情况有了更深入的认识。
在循环出来之后,说明查找失败。
此时有两种可能:第一种,target在(ri,ri+1)之间;第二种target在(ri-1,ri)之间



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.



代码:56ms过大集合

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,三维动态规划

一开始拿到这个题的时候没什么想法,浆糊了之后立马百度之,才有了思路。
简单的说,就是s1和s2是scramble的话,那么必然存在一个在s1上的长度l1,将s1分成s11和s12两段,同样有s21和s22。
那么要么s11和s21是scramble的并且s12和s22是scramble的;
要么s11和s22是scramble的并且s12和s21是scramble的。
先用递归写了一个算法,但是大集合不过,然后用三维动态规划才搞定。



题目描述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.



代码:三维动态规划,48ms过大集合

    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];
    }



递归代码,小集合12ms过,大集合过不了,因为时间复杂度是O(3n)

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.



代码:递归解法,12ms过大集合

/**
 * 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

题目简单,就是先让一个ListNode **prob,从head开始跑,直到*prob是NULL。此时prob指向最后一个元素的next指针。并且在跑的过程中计算出总的元素个数count。
将整个圈连起来,prob接着往前跑count – k次(k先模一个count)。从这里断开,就是要求的结果了。



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.



代码:56ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        if(k <= 0) return head;
        ListNode **prob = &head;
        int count = 0;
        while(*prob){
            prob = &((*prob)->next);
            ++count;
        }
        if(count <= 1) return head;
        k = k % count;
        *prob = head;//form a circle
        
        for(int i = 0 ; i < count - k; ++i) {
            prob = &((*prob)->next);
        }
        head = *prob;
        *prob = NULL;
        
        return head;
    }
};

LeetCode题目:Rotate Image

旋转图像,方法就是从外到内一圈一圈的转。
在处理每一圈的旋转时,拿最上面一行的第一个元素到倒数第二个元素,逐个找到其在右边,下边和左边一行(或列)中对应的元素,交换这一组4个元素的值就可以了。
这个逻辑很清晰。



Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
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;
            }
        }
    }
};



代码:20ms过大集合

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

知道罗马数字的定义之后是很简单的,比int to roman简单。
从前往后扫描,用一个临时变量记录分段数字。

  • 如果当前处理的字符对应的值和上一个字符一样,那么临时变量加上这个字符。比如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,
    Given this linked list: 1->2->3->4->5
    For k = 2, you should return: 2->1->4->3->5
    For k = 3, you should return: 3->2->1->4->5



    代码:144ms过大集合

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *reverseKGroup(ListNode *head, int k) {
            if(k < 2) return head;
            ListNode **pps = &head;
            ListNode *pTail = head;
            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;
            }
            return head;
        }
    };
    



    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;
            //let ppStart point to head, and head points to the first node in the linked list.
            //  thus if we modify *ppStart, the point target of the head is modified as well.
            ListNode **ppStart = &head;
            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;
                }
            }
            return head;
        }
    };
    

    LeetCode题目:Reverse Linked List II

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



    Reverse Linked List II
    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过大集合

    /**
     * Definition for singly-linked list.
     * 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
            ListNode **firstBreak = &head;
            for(int i = 0 ; i < m - 1; ++i) {
                firstBreak = &( (*firstBreak) -> next );
            }
            //find the tail and point out the mid segment start/end point
            if(*firstBreak == NULL) return head;
    
            //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
    Have you thought about this?
    Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
    If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.
    Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
    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;
        }
    };
    

    LeetCode题目:Restore IP Addresses,回溯

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

    细节很重要:

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

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



    Restore IP Addresses
    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 restoreIpAddresses(string s) {
            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,设置好它的类型和值就可以了。
    这里例子中,keypath是“layer.cornerRadius”,类型是“Number”,值是“10”。
    不过要记得将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过大集合

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *removeNthFromEnd(ListNode *head, int n) {
            ListNode **prob = &head;
            ListNode **pre = &head;
            //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;
            return head;
        }
    };
    

    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过大集合

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            ListNode *root = NULL;
            ListNode **ppNext = &root;
            while(head) {
                if(head->next == NULL || head->next->val != head->val) {
                    *ppNext = head;
                    ppNext = &(head->next);
                    head = head->next;
                } else {
                    int val = head->val;
                    do {
                        head = head->next;
                    } while(head != NULL && head->val == val);
                }
            }
            *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过大集合

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            // Start typing your C/C++ solution below
            // DO NOT write int main() function
            if(!head) return NULL;
            ListNode *last = head;
            ListNode *cur = last->next;
            while(cur) {
                if(cur->val != last->val) {
                    last->next = cur;
                    last = cur;
                }
                cur = cur->next;
            }
            last->next = NULL;
            return head;
        }
    };
    

    LeetCode题目:Remove Duplicates from Sorted Array II

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



    Remove Duplicates from Sorted Array II
    Follow up for “Remove Duplicates”:
    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,
    S = “ADOBECODEBANC”
    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);
        }
    };