LeetCode题目:Maximal Rectangle

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



代码:64ms过大集合,还可以优化时间

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

LeetCode题目:Longest Valid Parentheses

关键问题在于括号对能匹配的条件是左右括号数目相等。
然后已经匹配的长度有可能扩散到下一次匹配,比如()(),在第二次右括号匹配的时候,当时的长度要计算上被匹配的左括号左边的成功匹配长度。



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



代码:O(n)

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

LeetCode题目:Longest Substring Without Repeating Characters

贪心法,从头扫描到尾,O(n)搞定。
用一个map[256]来记录出现过的字符位置。
遇到没有出现过的字符,将map对应位置标记,并且子串长度+1;
遇到出现过的字符,将子串自上一次出现该字符位置前面的截断,对这部分截断的字符,标记map为notFound,重新计算子串长度。



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



代码:44ms过大集合

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

New ruby solution at 2016-04-22

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

LeetCode题目:Longest Palindromic Substring,二维动态规划

Updated at 2016-04-28

Question

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

Analyze

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

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

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

2-D Dynamic Programming

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

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

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

Expand from center

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

Codes

Ruby version DP

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

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

            si -= 1
        end
    end

    s[max_si..max_ei]
end

Ruby version expand from center

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

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

C++ version DP

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

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

问题要求是寻找一个字符串中的最长可逆子串,可以转化为求它和自身的逆序串的最长公共子串问题。
关键的思路是:
用一个matrix记录最长公共子串的长度,mat[i][j]表示以a串的i-1字符结束且以b串的j-1字符结束的最长子串长度。
当stringa[i-1] == stringb[j-1]时,mat[i][j] == mat[i-1][j-1] + 1

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

if(max <= len)

中,如果把小于等于改成小于,在大测试集合中会有一个莫名其妙的test case结果错误。
这两个问题都不知道原因。



代码:1488ms过大集合

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

LeetCode题目:Longest Common Prefix

注意细节



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


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

viewWillAppear不执行的问题

今天遇到了viewWillAppear函数不执行的问题,最后找到了症结所在。
<br>
那就是使用了UINavigationControllerDelegate,但是没有在相应的函数中显示调用即将显示的viewController的viewWillAppear方法。
系统的UINavigationControllerDelegate会自动调用这4个方法,但是如果是自己重载了delegate的话,就需要手动去调用。

LeetCode题目:Letter Combinations of a Phone Number

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

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


class Solution {
public:
    vector letterCombinations(string digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector >map(10);
        map[0] = vector(1);
        
        map[0][0] = ' ';
        map[1] = vector(1);
        map[1][0] = ' ';
        
        map[2] = vector(3);
        map[2][0] = 'a';
        map[2][1] = 'b';
        map[2][2] = 'c';
        
        map[3] = vector(3);
        map[3][0] = 'd';
        map[3][1] = 'e';
        map[3][2] = 'f';
        
        map[4] = vector(3);
        map[4][0] = 'g';
        map[4][1] = 'h';
        map[4][2] = 'i';
        
        map[5] = vector(3);
        map[5][0] = 'j';
        map[5][1] = 'k';
        map[5][2] = 'l';
        
        map[6] = vector(3);
        map[6][0] = 'm';
        map[6][1] = 'n';
        map[6][2] = 'o';
        
        map[7] = vector(4);
        map[7][0] = 'p';
        map[7][1] = 'q';
        map[7][2] = 'r';
        map[7][3] = 's';
        
        map[8] = vector(3);
        map[8][0] = 't';
        map[8][1] = 'u';
        map[8][2] = 'v';
        
        map[9] = vector(4);
        map[9][0] = 'w';
        map[9][1] = 'x';
        map[9][2] = 'y';
        map[9][3] = 'z';
        
        vector result;
        result.push_back("");
        for(int idigit = 0; idigit < digits.size(); ++ idigit) {
            char di = digits[idigit];
            int index = di - '0';
            if(index < 0 || index > 9)
                continue;
            vector &dmap = map[index];
            int curSize = result.size();
            int times = dmap.size();
            for(int itime = 0; itime < times - 1; ++itime) {
                for(int itemp = 0; itemp < curSize; ++itemp) {
                    result.push_back(result[itemp]);
                }
            }
            for(int itime = 0; itime < times ; ++itime) {
                char append = dmap[itime];
                for(int itemp = 0; itemp < curSize; ++itemp) {
                    int itemIndex = itime * curSize + itemp;
                    if(itemIndex >= result.size()) {
                        cout<<"d";
                        continue;
                    }
                    result[itemIndex].push_back(append);
                }
            }
        }
        return result;
    }
};

LeetCode题目:Length of Last Word

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



简单,注意收尾就行

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

LeetCode题目:Jump Game II,一维动态规划,贪心

这个简单,只需要在Jump Game的基础上用一个int来记录最小跳跃次数就行了。

不过,贪心法可以解,O(n)扫一次就可以了,比DP好得多。因为这道题是最远跳到那么远,而不是只能跳到那么远。如果是后者,引入dp值得。



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



贪心法,48ms过大集合

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



一维动态规划,1936ms过大集合

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

LeetCode题目:Jump Game,一维动态规划

最开始用

vector

超时,想了想没法改进算法的阶,就把这个换成bool[],居然就过了。。。哎,该用数组还是用数组啊。



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



大集合不超时了,不过貌似有一个testcase有问题,错误一个:[2,0,1,1,1,1],这应该返回true啊,不过系统给的答案是false

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



大集合超时

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

LeetCode题目:Largest Rectangle in Histogram

题目描述:Largest Rectangle in Histogram
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

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

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



同样是暴力破解,只不过先把vector转成int[],就800ms过了大集合。
要注意用unsigned int来接受height.size()

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

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



暴力破解,大集合超时

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

LeetCode题目:Interleaving String,二维动态规划

分析
题目给定3个字符串(s1,s2,s3),看s3是否是有s1和s2通过交织可以得到。


可以这么来看这个问题,每次从s3开头拿出来一个字符,如果s1的开头或者s2的开头有这个字符的话,就消掉相应的字符,把这个操作记为del。
这样看待这个问题的话,好像挺简单的,很直观。
但是当遇到case:s1=aa,s2=ab,s3=abaa,的时候可以看出当s1和s2同时可以进行del操作的时候,选择就成了一个必须考虑的问题。
假如最开始那个a,消掉了s1中的第一个a,那么就进行不下去了。
<br>
所以最后这个问题其实并不那么简单,假如函数

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

表示子问题:si取前leni个字符的话,那么实际上可以得到这样的一个公式:

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

由于len3 === len1 + len2,所以这个问题里面实际上存在着两个变量,是一个二维动态规划题目。
从矩阵的角度来看的话,每一个元素的值,依赖于它的上边和左边两个值。
最后写出程序,用24ms过大测试集合。



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



正解就是二维动态规划

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



几个失败的想法

一开始的想法,错在当s1,s2同时匹配的时候,这里存在一个策略问题,比如测试用例:aa,ab,abaa,就过不了。

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



第二个错误想法,先从s3中标记掉s1中出现的内容,然后在看剩下的部分是不是s2,也不对,一样的存在“标记掉s1"的策略问题

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



所以,绕不开策略问题,就得在做出决策的时候让程序分支。下面是一个正确但大集合会超时的递归算法:

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

LeetCode题目:Integer to Roman

罗马数字是由字符I,V,X,L,C,D,M等等表示的,其中
I = 1;
V = 5;
X = 10;
L = 50;
C = 100;
D = 500;
M = 1000;
接下来应该是V开始的重复,但是上面要加一个横线,表示对应数字的1000倍。
而且对于某位上(以个位为例),1 – 9,应该是:I,II,III,IV,V,VI,VII,VIII,IX
而,对于百位上,100 – 900,应该是:C,CC,CCC,CD,D,DC,DCC,DCCC,CM
依此类推。
有一点比较有意思,那就是IV,正统的写法是IIII(写程序倒是容易些)。后来简写为IV,但是由于IV也是朱皮特神的名字,为了不让神的名字看起来像普通数字,这种简写遭到了很多人的抵制。



题目描述:Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.


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

LeetCode题目:Insert Interval

这个题目简单,简单的题目注意细节就行了。



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



直观的算法,就是细节比较多。68ms过大集合

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



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

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

iOS中的文件存放法则

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

    存放位置要求

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

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



下面的代码是如何设置属性,让apple在备份的时候,不会包含这个文件。
对于iOS版本5.1之前和之后的处理方式是不一样的。

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

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

简单解法,O(m * n)

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



Code rewrite at 2012-12-21

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

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

这题太bug了,啥也不说了,链接:http://en.wikipedia.org/wiki/Gray_code

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


总结

    这个题发现了好多问题

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

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

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

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

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



分析
题目是给定一个n之后,要返回一个1到2^n的整数序列。要求满足每相邻两个数之间(包括最后一个数和最开始一个数)只能相差一bit。
比如n=2,就要返回[0,1,3,2],因为写成二进制是:[00,01,11,10]。

看到这个问题就想到了欧拉回路。欧拉回路的一个应用就是计算机的一种译码问题:将m个字母,每个字母出现n次排列在一个圆盘上,圆盘上连续的n个字母(比如顺时针方向)就组成了一个单词。找到一种字母在圆盘上的排列方式,让所有的单词出现一次而且相邻单词之间除了首尾bit都相等。

放到题目中,就是图上有n个点,点之间的有向边连接的条件就是点相差一个bit。然后在这个图中寻找欧拉回路即可。方法就是Fluery或者逐步插入回路法。



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



代码没有通过测试,是因为结果是对的,只不过对于这个欧拉图而言,我的程序走的欧拉回路和题目用来判断正确与否的测试回路不是同一条路而已。

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



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

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

LeetCode题目:Generate Parentheses

生成合法的括号对。
这里只需要搞清楚“合法(well-formed)”的概念就行了,那就是
1.左右括号数相等
2.任一位置之前的右括号数不大于左括号数

有了这样两点,那么要生成括号对总数为n的所有可能性的串。就从空字符串开始,按照上面的第二点限制,逐步添加左右括号即可。
当拿到合法的串,长度为k,时,要继续添加一个括号,那么就看这个串如果左括号的数目没有达到n,那就可以在此基础上添加一个左括号;
同时,如果串内右括号数目小于左括号数目的话,还可以在k串上添加一个右括号。
这样遍历了所有长度为k的合法串之后,我们就得到了所有合法的长度为k+1的串。
当我们生成了所有长度为2n的合法串,就得到了答案。


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


代码如下
20ms过大测试集合

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

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

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

UITableView的背景颜色,并不是UITableView的backgroundColor。
其内部实际上创建了一个UIView来专门呈现设定的背景颜色。
感觉它的subview层次从下往上是这样的:

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

而且每次添加一个cell,tableView会自动将这个cell放置在backgroundView的上面一层,而且UITableView的sendViewToBack和bringToFront函数应该是重新定义过的,并不会按照普通UIView的方式去执行。

LeetCode题目:First Missing Positive

First Missing Positive
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.


题目的最后一行,要求O(n)实际上暗示了用hash,但是又说要contant space,就没法再开新空间来建hash。
正好这个题目中处理的是1到n的数据,提供了一个将输入的数组同时用作hash表的可能性。
于是算法就是:

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



8ms过大集合

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


排序版本,24ms过大集合

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



Code rewrite at 2013-1-22

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

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

这个题目花了我太长的时间,方向是对的,不过一直没有找到关键的递推。

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

简单的说,就是将一个字符串变成另外一个字符串所用的最少操作数,每次只能增加、删除或者替换一个字符。


做这个题过程挺曲折

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


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


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

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

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

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



终于过了,72ms过大集合

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



这是两次错误的尝试

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



Code rewrite at 2012-12-29


// // main.cpp // EditDistance // // Created by Qiu Xiangyu on 12-12-29. // Copyright (c) 2012年 Qiu Xiangyu. All rights reserved. // #include <iostream> #include <string> #include <vector> using namespace std; int editDist(string &str0, string &str1) { if (str0.size() == 0) { return (int)str1.size(); } else if (str1.size() == 0) { return (int)str0.size(); } vector<vector<int> > dists(str0.size() + 1, vector<int>(str1.size() + 1,0)); for(int i0 = 0; i0 <= str0.size(); ++ i0) { dists[i0][0] = i0; } for (int i1 = 0; i1 <= str1.size(); ++i1) { dists[0][i1] = i1; } for (int l0 = 1; l0 <= str0.size(); ++l0) { for (int l1 = 1; l1 <= str1.size(); ++l1) { if (str0[l0 - 1] == str1[l1-1]) { //the same ending of this length pair for strings dists[l0][l1] = dists[l0-1][l1-1]; } else { //for replace int replaceDist = dists[l0-1][l1-1] + 1; int mindist = replaceDist; //insert the last char into substr1 int insertDist = dists[l0][l1-1] + 1; if (mindist > insertDist) { mindist = insertDist; } //delete the last char from substr1 int deleteDist = dists[l0-1][l1] + 1; if (mindist > deleteDist) { mindist = deleteDist; } dists[l0][l1] = mindist; } } } return dists[str0.size()][str1.size()]; } int main(int argc, const char * argv[]) { string str0 = "abc"; string str1 = "bcd"; int editdist = editDist(str0, str1); cout<<"edit distance is : "<<editdist<<endl; return 0; }



Code rewrite 2012-12-30

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

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

UIScroView和TableView都可以设置一张图片作为背景,或者设置一个颜色。
但是这两种方法设定的颜色都是固定的,不会随着表格或者Scroll的滚动而滚动。
不过,要使用一张图片以平铺的形式贴在可滚动区域上也是可以的,只需要一个语句即可:

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

LeetCode题目:Divide Two Integers

实际上是在二进制基础上进行运算,要考虑到有无符号,补码问题,还是挺复杂的。
类似问题还有用位运算做加法;不用if求两个数中最大的一个。


补码
补码是方便计算机运算搞出来的一个奇怪码。
以单字节的整数来说,为了表示正负,用最前面那个bit作为符号位,1是负数,0是正数。

这样就有原码,1的原码就是00000001,-1的原码就是10000001。
但是这样很不方便,比如1+(-1) = 00000001 + 10000001 = 10000010 = -2,显然不对嘛。

于是就有了反码,那就是负数的原码除了符号位都取反,也就是说-1的反码就是11111110。
这样1 + (-2) = 00000001 + 11111101 = 11111110 = -1,ok的
但同时有1 + (-1) = 00000001 + 11111110 = 11111111 = -0,出了一个-0,还有+0

于是再来,将反码+1叫做补码,也就是说-1的补码是11111111
这样的话:1+(-1) = 00000001 + 11111111 = 00000000 = 0,就对了。



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


代码
写的算法用了两个unsigned的int变量,如果重新写一个比较的话(把int当做无符号二进制数来处理的话),可以省去这两个变量

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (divisor == 0 )
            return -1;//error
        int bits = sizeof(int) * 8;
        int signMask = 0x01 << (bits - 1);
        int valMask = ~signMask;
        
        int count = 0;
        bool minus = false;
        unsigned int dend = dividend;
        if(dividend < 0)
        {
            minus = true;
            dend = ~(dend - 1);//补码还原,先-1,再取反。(-1的补码是,将1的原码0x01取反,在+1,也就是1...1)
        }
        unsigned int sor = divisor;
        if( divisor < 0 )
        {
            minus = !minus;
            sor = ~(sor - 1);
        }
        int offset = 0;
        int mask = 0x01 << (bits-1);
        while( (0 == (sor&mask)) && (sor<<1) <= dend)
        {
            ++offset;
            sor = sor << 1;
        }
        
        int result = 0;
        while(offset >= 0)
        {
            if(dend >= sor)
            {
                result += (0x01 << offset);
                dend -= sor;
            }
            --offset;
            sor = sor >> 1;
        }
        if(minus)
            return 0 - result;
        return result;
    }
};

LeetCode题目:Decode Ways,一维动态规划

从后往前动态规划,要注意临界状态,可以用占位符来避免程序内的越界判断。


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

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


暴力递归,大集合超时

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



动态规划,16ms过大集合

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



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

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

LeetCode题目:Container With Most Water

没有找到太好的办法,只能暴力破解,加上一点预判。时间是O(n^2)

2013-1-4,更新
看了nandawys的评论,找到了O(n)方法,思路是从两头到中间扫描,设i,j分别指向height数组的首尾。
那么当前的area是min(height[i],height[j]) * (j-i)。
当height[i] < height[j]的时候,我们把i往后移,否则把j往前移,直到两者相遇。

这个正确性如何证明呢?
代码里面的注释说得比较清楚了,即每一步操作都能保证当前位置能取得的最大面积已经记录过了,而最开始初始化的时候最大面积记录过,所以有点类似于数学归纳法,证明这个算法是正确的。



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



代码
600ms过大集合

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



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

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

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

枚举所有的在n个中选择k个的可能性


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



Code,52ms pass the large test set
代码如下,52ms过大集合

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



Code rewrite at 2012-12-30, Another way to solve this problem, in my General Back-Tracing Frame
在2012-12-30重写的代码,用了我的回溯通用框架

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

LeetCode题目:Combination Sum II

题目和Combination Sum差不多,加了限制,候选参数中的数字只能使用一次。
还是动态规划,利用两个数组来回倒腾。
其中还是发现了不少问题:

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



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


代码
1432ms过大测试集合

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

LeetCode题目:Combination Sum,动态规划

这道题是动态规划,先写一个伪代码是挺好的方法。可以先笼统的写出来算法,算法ok了再注意语法之类的细节。


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



小集合12ms,大集合1416ms过

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

LeetCode题目:Binary Tree Inorder Traversal

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

    代码

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

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

    class Solution {
    public:
        vector inorderTraversal(TreeNode *root) {
            vector result;
            
            vector trace;
            TreeNode *cur = root;
            TreeNode *pre = NULL;
            bool forward = true;
            while(cur)
            {
                if (forward) 
                {
                    //have unvisited left
                    if (cur->left && pre != cur->left)
                    {
                        pre = cur;
                        trace.push_back(cur);
                        cur = cur->left;
                        continue;
                    }
                    forward = false;
                }
                else
                {
                    //not return from right, add self
                    if(cur->right == NULL || cur->right != pre)
                        result.push_back(cur->val);
                    //go right if could
                    if(cur->right && pre != cur->right)
                    {
                        forward = true;
                        pre = cur;
                        trace.push_back(cur);
                        cur = cur->right;
                        continue;
                    }
                    //go up
                    pre = cur;
                    if (trace.size() > 0)
                    {
                        cur = trace[trace.size() - 1];
                        trace.pop_back();
                    } else
                        cur = NULL;
                    
                }
            }
            
            return result;
        }
    };
    
  3. 循环解法,2012年12月6日重写,比上一个简洁
    class Solution {
    public:
        vector inorderTraversal(TreeNode *root) {
            // Start typing your C/C++ solution below
            // DO NOT write int main() function
            vector ret;
            if(NULL == root) return ret;
            
            bool forward = true;
            stack trace;
            TreeNode *preNode = NULL;
            trace.push(root);
            
            while(trace.size()) {
                TreeNode *curNode = trace.top();
                if(forward) {
                    if(curNode->left && preNode != curNode->left) {
                        trace.push(curNode->left);
                    } else {
                        //no left or left visited
                        forward = false;
                    }
                } else {
                    //backward, find sibling(right child)
                    //if not back from right child, then visit it
                    if(curNode->right != preNode)
                        ret.push_back(curNode->val);
                    if(curNode->right && preNode != curNode->right) {
                        //if have an unvisited right child, traval it.
                        trace.push(curNode->right);
                        forward = true;
                    } else {
                        //all sub-tree of this node is visited
                        trace.pop();
                    }
                }
                preNode = curNode;
            }
            
            return ret;
        }
    };
    

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

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


为了让上传到服务器或者保存的本地的图片和照相时候一样,需要利用UIImage的imageOrientation将其矫正。


已经有一个开源的Category来处理这个问题,原理就是根据UIImage的imageOrientation属性反过来绘制到新的CGImage里面,然后保存为正常的UIImage。
链接是:https://gist.github.com/1531596

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

在iOS中,表示时间的类是NSDate,但是NSDate仅仅保存了一个时刻(据1970年1月1日凌辰开始的秒数)。
想获取这个时刻的年,月,日,时,分,秒等等信息,光从NSDate是不行的。
而获取这些元素的途径是通过NSCalendar类来进行的。


下面的代码展示了如何从一个NSDate获取这些元素,并通过指定的元素来创建NSDate对象

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

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

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

可用的元素枚举定义如下

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

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

警告!!!
最好别用exfat格式为硬盘分区,会丢分区的····(我已经丢了3次了,还好备份做得充分,现在用NTFS,mac/win互相只读)



============ 以下是正文 =============
本文介绍如何在win7下用diskpart命令行工具将大容量分区格式化为exfat文件系统并且指定分配单元大小(簇大小)。
提示:在进行格式化操作之前,请备份硬盘上的所有数据,安全第一~~
新的MacbookPro是固态硬盘,为了装Mac和Win7双系统,需要一个在双系统下通用的文件格式。

这个格式就是exFat,为闪存优化的文件系统格式,而且macOS和windows都是原生支持。

但是,做好双系统之后,将原来的数据拷入这个交换分区,却发现,原本200G的内容,占用了210+G的空间。
汗,原本就紧张的空间还浪费这么多···一定要解决之。
仔细一查,发现苹果系统下的“磁盘工具”在格式化的时候无法指定分区大小,于是,苹果自动使用了128kb的单元大小,又有叫簇大小的。
单元大小就是磁盘分配空间的最小单位。这里是128kb,就是说,你新建一个文本文档,里面随便敲一个字符,然后保存。你会发现,这个文件的大小是1字节(占用128kb)空间。
单元大小越大,读取大文件越快。因为读完一个文件需要读取的磁盘块的个数越少;
但同时,意味着浪费的空间越大。

固态硬盘的存取速度本来就比传统硬盘快,没有必要为了速度更快(在固态硬盘上也快不了多少了),而牺牲那么多无辜的空间。所以我决定把单元大小改到1kb。

这个时候问题来了,mac系统下的工具无法指定簇大小。windows下的资源管理器本来是可以指定大小的,但是超过一定大小的分区,就没有了exFat这个格式的选项。
(就像下面截图的“文件系统”一项,大容量的分区就只能选择ntfs了;小u盘可以选fat,ntfs,exfat)

然后就是漫长的搜索,diskgenius,partition magic,等等都试过。但是在这个问题上统统不给力。

后来辗转想起来windows命令行里面可以分区格式化,于是让我找到了diskpart这个命令行工具(win7自带),终于成功解决了这个问题。

使用步骤如下

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

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

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

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

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

这个时候,如果在新的分区上建一个文本文档,然后敲一个字符保存,查看新文档的属性可以看到:

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

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

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

这两种情况下,直接肯定是通不过编译的。可以通过升级旧项目,让其使用ARC来解决,但这个办法有时候会很麻烦。
有一个简单的办法就是,可以指定单个文件是否采用ARC来进行编译。
方法就是在Build Phase里面的Compile Source里面找到需要特殊处理的文件,加上编译选项(Compiler Flags),具体针对上面两种情况有所区别。

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

此外,xcode貌似有点问题,在点击某个源文件的Compiler Flags条目的时候,应该显示光标的地方却什么也没有提示,输入字符也没有echo,只有敲完之后,选择其它文件才能看到添加的编译选项···这真无语。。

<br>
对于新写的各种插件,可以这么干:

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

让它在arc和非arc都可用。