如何解决iOS瀑布流(UIScrollView或UITableView)运行不流畅

写的一个程序中用到了瀑布流的展现方式,但是发现当图片数量太大的时候,在iPhone4上会不流畅,这点很不爽。

写代码之初是做了一些优化的,比如cell重用,异步加载,但是还是很卡。

终于后来发现了症结所在,那就是,如果滑动太快,可能同时就发出了比如10个图片请求。这些请求虽然都在后台运行,但是它们可能在同一个时间点返回UI线程。这个时候如果加载图片到UIImageView太频繁,就会造成UI卡得严重。(虽然在new iPad和iPhone4s上看不出来)

在找到这个问题的同时,也发现performSelectorAfterDelay这个方法,会堆积到UI线程空闲的时候执行。而dispatch_after或者dispatch_async都会直接插入UI线程当场执行。所以这个问题其实可以用performSelectorAfterDelay来解决,测试也是非常流畅,感觉不出一点点的卡。但会出现新的问题,那就是在滑动过程中,不会加载任何图片。知道scrollView停止的时候,图片才会出来。当然这不是理想的解决方法了。这个方法也没有解决异步过程集中到达UI线程的问题。然后采用了NSOperationQueue来解决这个问题。

问题本身和UITableView加载不流畅是一样的。

解决办法

    主要要做到一下几个方面:

  1. 除了UI部分,所有的加载操作都在后台完成。
    这一点可以通过dispatch或者performSelectorInBackground或者NSOperationQueue来实现。见:
    在iOS开发中利用GCD进行多线程编程
    iOS开发中使用NSOperationQueue进行多线程操作
  2. 避免后台加载完成多个资源之后集中到达占用UI线程的处理时间太长。
    这一点可以通过NSOperationQueue来实现,将资源到UI的展现过程放在队列中逐个执行,且在每个操作完成之后进行强制等待,可以用usleep(int microSeconds)来解决。
  3. 重用cell。
    创建cell一般是很慢的,一定要重用,甚至为了performance,可以在view创建之初就创建足够多的cell在重用队列中。

LeetCode题目:Anagrams

这道题目花的时间比较长,一来是因为有点麻烦,二来是因为有好几次敲完代码没保存,结果一不小心让浏览器后退了一个页面~~~不得不重新敲一遍代码。

  1. 题目描述:
    Anagrams
    Given an array of strings, return all groups of strings that are anagrams.
    Note: All inputs will be in lower-case.
  2. 思路:
      题目是让找出在一个string数组中的所有类似(含有相同字符集,且其中每个字符出现的频率一样)的字符串组。

    1. 第一个问题就是如何判断两个字符串anagram。
      由于题目中限定了全部是小写,也就是说字符范围是’a’ ~ ‘z’,26个字符,所以可以直接开26个int的数组来统计每个字符串各个字符出现的频率,这样只要两个字符串得到的这种数组相等,就可以认为这两个字符串是类似的。
      这个算法的时间复杂度是O(m)。m为字符串长度。
    2. 第二个问题就是如何在字符串数组中挑出来类似的字符串。
      这个没有想到太好的方法,直接暴力破解吧,不过可以采用一些tricks跳过不必要的计算。
      比如先将字符串数组按字符串长度排序,那么长度相等的字符串就落到了一段段连续的地址上,这样就可以很方便地跳过字符串长度不相符的部分。
      还可以给第一步得到的int数组进行一个预计算,比如按照fp->abstract += fp->fingerPrint[i] * (i+1);的形式计算一个整数作为预判条件,可以先一步滤掉不可能类似的字符串,从而用单个int相等的判断来避免一部分的数组相等判断。这一步优化使得程序从large测试超时变成了960ms
  3. 收获:
    1. sort的第三个参数要传递一个静态的函数。
      在这个问题上纠结了不少的时间。
      另外函数的形式可以是:bool comp(const string &a, const string &b) 或者 bool comp(string a,string b)
    2. 容器的resize(n),resize(n,val)函数。

下面是代码
1.
这个代码直接进行int数组的相等判断
small 8ms, large 超时

class Solution {
public:
    vector getFingerPrint(string &str) {
        vector fp(26,0);
        for(int i = 0 ; i < str.size(); ++i) {
            fp[str[i]-'a'] ++;
        }
        return fp;
    }
    static bool AcsByLen(const string &stra, const string &strb) {
        return stra.size() < strb.size();
    }
    vector anagrams(vector &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vectorresult;
        if(strs.size() < 2) {
            return result;
        }
        vector >fps;//finger prints
        vector selected(strs.size(),false);
        // sort by length
        sort(strs.begin(),strs.end(),Solution::AcsByLen);
        // calculate the finger prints of strings
        for(int i = 0; i < strs.size(); ++i) {
            string &str = strs[i];
            vector fp = getFingerPrint(str);
            fps.push_back(fp);
        }
        for (int ia = 0 ; ia < strs.size(); ++ia) {
            if(selected[ia]) continue;
            string &stra = strs[ia];
            vector fpa = fps[ia];
            for(int ib = ia + 1 ; ib < strs.size(); ++ib) {
                if(selected[ib]) continue;
                string &strb = strs[ib];
                if(strb.size() > stra.size()) {
                    break;
                }
                vector fpb = fps[ib];
                if (fpb == fpa) {
                    if(!selected[ia]) {
                        selected[ia] = true;
                        result.push_back(stra);
                    }
                    selected[ib] = true;
                    result.push_back(strb);
                }
            }
        }
        return result;
    }
};

2.改进的代码先算了一个整数来作为字符串的抽象指纹,这个整数保证了如果是类似的字符串,这个抽象指纹一定相等;但是抽象指纹相等的字符串不一定是类似的。这个优化使得程序不超时了。
small 4ms, large 960ms

class Solution {
public:
    class FingerPrint {
        public:
            vector fingerPrint;
            int abstract;
    };
    FingerPrint * getFingerPrint(string &str) {
        FingerPrint *fp = new FingerPrint();
        fp->fingerPrint.resize(26,0);
        for(int i = 0 ; i < str.size(); ++i) {
            fp->fingerPrint[str[i]-'a'] ++;
        }
        fp->abstract = 0;
        for(int i = 0 ; i < 26; i ++) {
            fp->abstract += fp->fingerPrint[i] * (i+1);
        }
        return fp;
    }
    static bool AcsByLen(const string &stra, const string &strb) {
        return stra.size() < strb.size();
    }
    vector anagrams(vector &strs) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vectorresult;
        if(strs.size() < 2) {
            return result;
        }
        vectorfps;//finger prints
        vector selected(strs.size(),false);
        // sort by length
        sort(strs.begin(),strs.end(),Solution::AcsByLen);
        // calculate the finger prints of strings
        for(int i = 0; i < strs.size(); ++i) {
            string &str = strs[i];
            FingerPrint &fp = *getFingerPrint(str);
            fps.push_back(fp);
        }
        for (int ia = 0 ; ia < strs.size(); ++ia) {
            if(selected[ia]) continue;
            string &stra = strs[ia];
            FingerPrint &fpa = fps[ia];
            for(int ib = ia + 1 ; ib < strs.size(); ++ib) {
                if(selected[ib]) continue;
                string &strb = strs[ib];
                if(strb.size() != stra.size()) {
                    break;
                }
                FingerPrint &fpb = fps[ib];
                if (fpb.abstract == fpa.abstract 
                && fpb.fingerPrint == fpa.fingerPrint) {
                    if(!selected[ia]) {
                        selected[ia] = true;
                        result.push_back(stra);
                    }
                    selected[ib] = true;
                    result.push_back(strb);
                }
            }
        }
        return result;
    }
};



Code rewrite at 2012-12-24, 1048ms pass large set.
Be aware of the usage of static data member in class, notice the last line in this code.
For a ascending sorting, the compare function is just like 'is the first object less than the second one?'.

class Solution {
public:
    static map > g_dict;
    static bool compareSign(const string & str0, const string & str1) {
        vector & v0 = Solution::g_dict[str0];
        vector & v1 = Solution::g_dict[str1];
        return v0 < v1;
    }
    static bool equalSign(const string & str0, const string & str1) {
        vector & v0 = Solution::g_dict[str0];
        vector & v1 = Solution::g_dict[str1];
        return v0 == v1;
    }
    static bool compare(const string & str0, const string & str1) {
        if(str0.size() < str1.size()) {
            return true;
        } else if(str0.size() > str1.size()) {
            return false;
        } else {
            return Solution::compareSign(str0,str1);
        }
    }
    vector anagrams(vector &strs) {
        Solution::g_dict.erase(Solution::g_dict.begin(),Solution::g_dict.end());
        for(int i = 0; i < strs.size(); ++i) {
            string &str = strs[i];
            vector sign(26,0);
            for(int j = 0; j < str.size(); ++j) {
                ++sign[str[j] - 'a'];
            }
            Solution::g_dict[str] = sign;
        }
        sort(strs.begin(),strs.end(),Solution::compare);
        vector ret;
        for (int i = 0; i < strs.size(); ++i) {
            string &str = strs[i];
            int c = 0;
            for (int j = i + 1; j < strs.size(); ++j) {
                if (strs[j].size() != str.size()) {
                    break;
                }
                if (!Solution::equalSign(strs[j], str)) {
                    break;
                }
                if (c == 0) {
                    ret.push_back(str);
                }
                ret.push_back(strs[j]);
                ++c;
            }
            i += c;
        }
        return ret;
    }
};
map > Solution::g_dict;

LeetCode题目:Binary Add

Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = “11”
b = “1”
Return “100”.

20ms过大集合测试。

class Solution {
public:
    string addBinary(string a, string b) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int la = a.size();
        int lb = b.size();
        string sum = la > lb ? a : b;
        int overflow = 0;
        for( int i = 0; i < sum.size(); i ++ )
        {
            char ca = i < la ? a[la - i - 1] : '0';
            char cb = i < lb ? b[lb - i - 1] : '0';
            int bit = ca - '0' + cb - '0' + overflow;
            overflow = bit / 2;
            sum[sum.size() - i - 1] = bit % 2 + '0';
        }
        if(overflow)
        {
            sum = "1" + sum;
        }
        return sum;
    }
};

LeetCode题目:Count and Say

Count and Say
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …
1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.



small 4ms ; large output limit exceeded
这个提示不知道什么意思,等搞定了更新。

class Solution {
public:
    string countAndSay(int n) {
        string str = "1";
        for (int iTime = 2; iTime <= n ; ++iTime)
        {
            string strori = str;
            str = "";
            for (int j = 0; j < strori.size(); ++j)
            {
                char first = strori[j];
                if (first == '2')
                    str += "12";
                else
                {
                    char second = 0;
                    if (j + 1 < strori.size())
                        second = strori[j+1];
                    if (second == '1')
                    {
                        str += "21";
                        j++;
                    }
                    else
                        str += "11";
                }
            }
        }
        return str;
    }
};



Code rewrite at 2012-12-22, 4ms accept by large test set

class Solution {
public:
    string countAndSay(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (n <= 0) return "";
        string s = "1";
        for(int ir = 2; ir <= n; ++ir) {
            string t;
            for(int i = 0; i < s.size(); ++i) {
                char curc = s[i];
                int countc = 1;
                for(int j = i + 1; j < s.size() && s[j] == curc; ++j) {
                    ++countc;
                    ++i;
                }
                if(countc > 3) cout<<"!!!";
                t += ('0' + countc);
                t += curc;
            }
            s = t;
        }
        return s;
    }
};

The previous version of code is mistake by understanding the question. That at each point in the sequence, we have to count the repeat count of same character in the pre sequence.

For example: when n == 5, the sequence is 111221.
Then , when n == 6, we have to say Three-1s,Two-2s and One-1, that is: 312211.
With this understanding, we can achieve the right code above.



But, there is a interesting things, that the repeat character cannot exceeds 3 times. Why?
Why could not see the sequence like "41", that means the previous sequence must be like "x1111y". There are only two ways to translating the meaning of this sequence:
1. x-1s, one-1, one-y, obviously, this is not valid, because, in this case, we could leading to "(x+1)11y"
2. some-xs, one-1, one-1, y-someelses, like above, this leading to "x21y"
Thus, the character '4', can never be a part of the sequence no matter how large the n is.

iOS中UILabel滚动字幕动画的实现

有时候会遇到UILabel中的内容超出长度,显示不完全的问题。有一种解决方法是通过动画字幕来实现,比如:

  1. 字幕向左或者右滚动
  2. 字幕来回滚动

本文以后者为例来说明吧。这里先介绍UIView的通过Block实现的Animation以及其参数控制,最后是实现滚动字幕的代码。

  1. UIView有方便的动画实现方式,SDK4.0以上,提供了三个Block的动画方式:

    + (void)animateWithDuration:(NSTimeInterval)duration delay:(NSTimeInterval)delay options:(UIViewAnimationOptions)options animations:(void (^)(void))animations completion:(void (^)(BOOL finished))completion __OSX_AVAILABLE_STARTING(__MAC_NA,__IPHONE_4_0);
    
    + (void)animateWithDuration:(NSTimeInterval)duration animations:(void (^)(void))animations completion:(void (^)(BOOL finished))completion __OSX_AVAILABLE_STARTING(__MAC_NA,__IPHONE_4_0); // delay = 0.0, options = 0
    
    + (void)animateWithDuration:(NSTimeInterval)duration animations:(void (^)(void))animations __OSX_AVAILABLE_STARTING(__MAC_NA,__IPHONE_4_0); // delay = 0.0, options = 0, completion = NULL
    

    其中第一个最全面,可以设置UIViewAnimationOptions来控制动画的参数,比如重复,自动reverse之类的。

  2. UIViewAnimationOptions具体定义如下:

    enum {
        UIViewAnimationOptionLayoutSubviews            = 1 <<  0,
        UIViewAnimationOptionAllowUserInteraction      = 1 <<  1, // turn on user interaction while animating
        UIViewAnimationOptionBeginFromCurrentState     = 1 <<  2, // start all views from current value, not initial value
        UIViewAnimationOptionRepeat                    = 1 <<  3, // repeat animation indefinitely
        UIViewAnimationOptionAutoreverse               = 1 <<  4, // if repeat, run animation back and forth
        UIViewAnimationOptionOverrideInheritedDuration = 1 <<  5, // ignore nested duration
        UIViewAnimationOptionOverrideInheritedCurve    = 1 <<  6, // ignore nested curve
        UIViewAnimationOptionAllowAnimatedContent      = 1 <<  7, // animate contents (applies to transitions only)
        UIViewAnimationOptionShowHideTransitionViews   = 1 <<  8, // flip to/from hidden state instead of adding/removing
        
        UIViewAnimationOptionCurveEaseInOut            = 0 << 16, // default
        UIViewAnimationOptionCurveEaseIn               = 1 << 16,
        UIViewAnimationOptionCurveEaseOut              = 2 << 16,
        UIViewAnimationOptionCurveLinear               = 3 << 16,
        
        UIViewAnimationOptionTransitionNone            = 0 << 20, // default
        UIViewAnimationOptionTransitionFlipFromLeft    = 1 << 20,
        UIViewAnimationOptionTransitionFlipFromRight   = 2 << 20,
        UIViewAnimationOptionTransitionCurlUp          = 3 << 20,
        UIViewAnimationOptionTransitionCurlDown        = 4 << 20,
        UIViewAnimationOptionTransitionCrossDissolve   = 5 << 20,
        UIViewAnimationOptionTransitionFlipFromTop     = 6 << 20,
        UIViewAnimationOptionTransitionFlipFromBottom  = 7 << 20,
    };
    typedef NSUInteger UIViewAnimationOptions;
    
  3. 本文实现方法就是使用Animation with Block的方式来实现UILabel来回滚动。代码如下:

    -(void)startAnimationIfNeeded{
        //取消、停止所有的动画
        [self.aUILabel.layer removeAllAnimations];
        CGSize textSize = [self.aUILabel.text sizeWithFont:self.aUILabel.font];
        CGRect lframe = self.aUILabel.frame;
        lframe.size.width = textSize.width;
        self.aUILabel.frame = lframe;
        const float oriWidth = 180;
        if (textSize.width > oriWidth) {
            float offset = textSize.width - oriWidth;
            [UIView animateWithDuration:3.0
                                  delay:0
                                options:UIViewAnimationOptionRepeat //动画重复的主开关
             |UIViewAnimationOptionAutoreverse //动画重复自动反向,需要和上面这个一起用
             |UIViewAnimationOptionCurveLinear //动画的时间曲线,滚动字幕线性比较合理
                             animations:^{
                                 self.aUILabel.transform = CGAffineTransformMakeTranslation(-offset, 0);
                             }
                             completion:^(BOOL finished) {
                                 
                             }
             ];
        }
    }
    

LeetCode题目:4Sum

4Sum 题目描述
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

采用外三层过滤枚举,最内层二分查找的方式可以达到大集合 1112 ms.

class Solution {
public:
    vector > fourSum(vector &num, int target) {
        vector > result;
        if(num.size() < 4)
            return result;
        
        sort(num.begin(),num.end());
        int lastVi = num[0] - 1;
        for(int i = 0 ; i < num.size() - 3; ++i)
        {
            int vi = num[i];
            if(vi == lastVi)
                continue;
            lastVi = vi;
            
            int lastVj = num[i+1] - 1;
            for( int j = i + 1; j < num.size() - 2 ; ++j)
            {
                int vj = num[j];
                if(vj == lastVj)
                    continue;
                lastVj = vj;
                
                int lastVk = num[j + 1] - 1;
                for(int k = j + 1; k < num.size() - 1; ++k)
                {
                    int vk = num[k];
                    if(vk == lastVk)
                        continue;
                    lastVk = vk;
                    
                    int sum3 = vi + vj + vk;
                    int tarVl = target - sum3;//find this for last num
                    int si = k + 1, ei = num.size() - 1;
                    //没有这个判断的话会超时
                    if(num[si] > tarVl || num[ei] < tarVl)
                        continue;
                    while(si <= ei)
                    {
                        int mi = (si + ei) / 2;
                        int vl = num[mi];
                        if(vl == tarVl)
                        {
                            vector quad;
                            quad.push_back(vi);
                            quad.push_back(vj);
                            quad.push_back(vk);
                            quad.push_back(vl);
                            result.push_back(quad);
                            break;
                        }
                        else if(vl > tarVl)
                        {
                            ei = mi - 1;
                        }
                        else
                        {
                            si = mi + 1;
                        }
                    }
                    
                }//end k
            }//end j
        }//end i
        return result;
        
    }//end function
};

LeetCode题目:3Sum Closest

没什么好办法,就硬来吧。时间复杂度是O(n3)
2012-12-31,更新了一个O(n2)的算法,思路就是第一个数按照原来的从前往后走,后面两个数一前一后相向而行,最差的情况只是走完剩下的那一段一遍,所以整体来说时间复杂度是O(n2)



3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).



代码:large 1180ms

class Solution {
public:
    int threeSumClosest(vector &num, int target) {
        if(num.size() < 3)
            return 0;
        sort(num.begin(),num.end());
        int minSum = 10000;
        int minDiff = 100000;
        int lastVi = num[0] - 1;
        for( int i = 0; i < num.size() - 2; ++ i)
        {
            int vi = num[i];
            if (vi == lastVi)
                continue;
            lastVi = vi;

            int lastVj = num[i+1] - 1;
            for (int j = i + 1; j < num.size() - 1; ++j)
            {
                int vj = num[j];
                if(vj == lastVj)
                    continue;
                lastVj = vj;

                int lastVk = num[j+1] - 1;
                for (int k = j + 1; k < num.size(); ++k)
                {
                    int vk = num[k];
                    if(vk == lastVk)
                        continue;
                    lastVk = vk;

                    int sum = vi + vj + vk;
                    int diff = abs(sum - target);
                    if (diff < minDiff)
                    {
                        minSum = sum;
                        minDiff = diff;
                    }
                    else if (sum - target > 0)
                        continue;
                }
            }
        }
        return minSum;
    }
};



Code rewrite at 2012-12-31,32ms pass large set.
Time complexity is O(n2)

class Solution {
public:
    int threeSumClosest(vector &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(num.size() < 3) return 0;//error occur
        sort(num.begin(),num.end());
        int minsumret = num[0] + num[1] + num[2];
        int mindiff = abs(target - minsumret);
        for(int i0 = 0; i0 < num.size() - 2; ++i0) {
            int ileft = i0 + 1, iright = num.size() - 1;
            int targetsum = target - num[i0];
            while(ileft < iright) {
                int subsum = num[ileft] + num[iright];
                if(abs(subsum-targetsum) < mindiff) {
                    minsumret = subsum + num[i0];
                    mindiff = abs(subsum-targetsum);
                }
                if (subsum == targetsum) {
                    return minsumret;
                } else if (subsum > targetsum) {
                    --iright;
                } else {
                    ++ileft;
                }
            }
        }
        return minsumret;
    }
};

LeetCode题目:最长前缀

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

small 4ms, large 36ms

class Solution {
public:
    string longestCommonPrefix(vector &strs) {
        if (strs.size() == 0)
            return "";
        string prefix = "";
        int minlen = strs[0].size();
        for (int istr = 1; istr < strs.size(); ++istr)
        {
            string str = strs[istr];
            if (str.size() < minlen)
                minlen = str.size();
        }
        for (int i = 0 ; i < minlen; ++i)
        {
            string firststr = strs[0];
            char firstchar = firststr[i];
            for (int istr = 1; istr < strs.size(); ++istr)
            {
                string str = strs[istr];
                if(str[i] != firstchar)
                    return prefix;
            }
            prefix = prefix + firstchar;
        }
        return prefix;
    }
};

LeetCode题目:Climbing Stairs

Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

一开始是用简单的方法递归求解,程序很快完成,通过了小集合测试,但是大集合超时;
然后发现了其中的规律,实际上就是一个x(n) = x(n-1) + x(n-2)的数列,又叫斐波纳契数列(Fibonacci Sequence)。

  1. small 8ms, large 超时
    class Solution {
    public:
        int climbStairs(int n) {
            // Start typing your C/C++ solution below
            // DO NOT write int main() function
            if (n == 1)
                return 1;
            if (n == 2)
                return 2;
            //first take 1 step
            int first1 = climbStairs(n- 1);
            //first take 2 step
            int first2 = climbStairs(n-2);
            return first1 + first2;
        }
    };
    
  2. small 0ms, large 4ms
    class Solution {
    public:
        int climbStairs(int n) {
            // Start typing your C/C++ solution below
            // DO NOT write int main() function
            int last = 0;
            int cur = 1;
            for(int i = 1; i <= n ; ++ i){
                int temp = cur;
                cur = last + cur;
                last = temp;
            }
            return cur;
        }
    };
    

在iOS项目中使用SDWebImage进行网络图片加载

SDWebImage是以Category的形式对UIImageView进行扩展。
是git上的一个开源项目:https://github.com/rs/SDWebImage

使用了它之后,让UIImageView可以直接设置图片的Url地址,剩下的下载,缓存就交给SDWebImage处理吧。

使用如下:

  1. 将下载的zip中的所有文件拷贝到项目文件夹中
  2. 将项目文件SDWebImage.xproj添加到自身的项目文件中
  3. 选中自身项目,在Target Dependencies中添加SDWebImage(一共有三个版本,根据需要选取一个)
  4. 在Link Binary With Library中,添加SDWebImage的.a静态库
  5. 在Link Binary With Library中,添加ImageIO.framework
  6. 在”Build Settings”–“Other Linker Flags”中添加”-ObjC”
  7. 在需要使用它的文件中包含h文件:
    #import 
  8. 然后使用很简单:
    [imageView setImageWithURL:aUrl];

Leetcode题目:Add Two Numbers, 两个链表数相加

临睡前A一道题,题目简单,没什么可说的。就是需要小心对NULL指针的调用。



Add Two Numbers
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode rootNode(0);
        ListNode *pCurNode = &rootNode;
        int forward = 0;
        while(l1||l2)
        {
            int v1 = (l1 ? l1->val : 0);
            int v2 = (l2 ? l2->val : 0);
            int sum = v1 + v2 + forward;
            forward = sum / 10;
            sum = sum % 10;
            ListNode *pNode = new ListNode(sum);
            pCurNode->next = pNode;
            pCurNode = pNode;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2 ->next;
        }
        if(forward > 0)
        {
            ListNode *pNode = new ListNode(forward);
            pCurNode->next = pNode;
        }
        return rootNode.next;
    }
};

Code rewrite at 2012-12-26, Simpler

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        int overflow = 0;
        ListNode *ret = NULL;
        ListNode **pnode = &ret;
        while(l1 && l2) {
            int val = l1->val + l2->val + overflow;
            overflow = val / 10;
            *pnode = new ListNode(val % 10);
            pnode = &((*pnode)->next);
            l1 = l1->next;
            l2 = l2->next;
        }
        ListNode *lremain = l1 ? l1 : l2;
        while(lremain) {
            int val = lremain->val + overflow;
            overflow = val / 10;
            *pnode = new ListNode(val % 10);
            pnode = &((*pnode)->next);
            lremain = lremain->next;
        }
        if(overflow > 0) {
            *pnode = new ListNode(overflow);
        }
        return ret;
    }
};

New C solution at 2016-04-22

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    if(l1 == NULL) return l2;
    if(l2 == NULL) return l1;
    struct ListNode* root = NULL;
    struct ListNode** next = NULL;
    int overflow = 0;
    while(l1 || l2 || overflow > 0){
        // calculation
        int v = overflow;
        if(l1){ v += l1->val; l1 = l1->next;}
        if(l2){ v += l2->val; l2 = l2->next;}
        overflow = v / 10;
        v = v % 10;
        // new node
        struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        newNode->val = v;
        newNode->next = NULL;
        if(next) *next = newNode;
        next = &(newNode->next);
        if(root == NULL) root = newNode;
    }
    return root;
}

New Ruby solution at 2016-04-22

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val)
#         @val = val
#         @next = nil
#     end
# end

# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def add_two_numbers(l1, l2)
    return l1 if l2.nil?
    return l2 if l1.nil?
    root = nil
    tail = nil
    overflow = 0
    while l1 || l2 || overflow > 0 do
        v = overflow
        unless l1.nil?
            v += l1.val
            l1 = l1.next
        end
        unless l2.nil?
            v += l2.val
            l2 = l2.next
        end
        overflow = v / 10
        v = v % 10
        new_node = ListNode.new(v)
        root = new_node if root.nil?
        tail.next = new_node unless tail.nil?
        tail = new_node
    end
    root
end

Leetcode题目:pow(x,n)

题目看似简单,其实考虑到时间复杂度之后,还有有得做的。

  1. 最简单的方法,循环n-1遍,每次乘以x。
    时间复杂度:O(N)
    很显然,最后超时了。并且如果用递归的话,函数好写简洁,但是会导致运行时错误(stack overflow)
  2. 还是用二分靠谱:
    xn = xn/2 * xn/2 * xn%2
    时间复杂度:O(logN)
    这样,用时24ms过大测试集合
  3. 2012-12-31重写,常数时间搞定(这个算法推敲一下还是logN的,只不过如果n限于32bit以内的话,乘法次数在64次以内,后面有解释)

代码如下:

class Solution {
public:
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (x==0){
            if(n==0)
             return 1;
            else
             return 0;
        } else if (x == 1) {
            return 1;
        }
        if (n == 0)
            return 1;
        double result = x;
        int absn = abs(n);
        int remain = 0;
        int powindex = 1;
        while (absn / 2)
        {
            result = result * result;
            remain = remain  + absn % 2 * powindex;
            powindex *= 2;
            absn /= 2;
        }
        result = result * pow(x,remain);
        if (n < 0)
            result = 1.0 / result;
        return result;
    }
};



Code rewrite at 2012-12-31, Better than before.
The more practice the better quality.
看到有人在mitbbs上讨论这个算法(http://www.mitbbs.com/article_t/JobHunting/32300887.html),然后仔细想了想,因为这个循环最多32次,所以我就没细想以为就是常数时间了。这是因为n超不过32bit,但是如果n不限于32bit的话,算法本身实际上还是logN的。

<

pre>

//
// main.cpp
// Pow
//
// Created by Qiu Xiangyu on 12-12-31.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

using namespace std;

double pow(double x, unsigned int n) {
if(n == 0) return 1;
unsigned int bitmask = 0x01 << (sizeof(unsigned int) * 8 - 1);
//find the most significant bit of n
while ((bitmask & n) == 0) {
bitmask = bitmask >> 1;
}
//doing calculation from the most significant bit
bitmask = bitmask >> 1;
double ret = x;
while (bitmask != 0) {
ret *= ret;
if (bitmask & n) {
ret *= x;
}
bitmask = bitmask >> 1;
}
return ret;
}

int main(int argc, const char * argv[])
{
cout<<pow(2.0, 18);
return 0;
}

Leetcode题目:3Sum

http://www.leetcode.com/onlinejudge
心得:

  1. vector的使用上
      成员函数:

    • size();
    • erase(beginIterator,endIterator);
    • push_back(anItem);
    • begin();
    • end();
      泛型函数:

    • sort(vec.begin(),vec.end())//将顺序容器vec排序
    • vector::iterator unique(vec.begin(),vec.end())//将顺序容器vec中重复出现的元素放在vec的末尾,返回操作完成时第一个重复元素的迭代器
  2. 二分查找还是很给力的
  3. 从简单的方法做起,逐步优化

题目描述:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)

解决方法:
方法一:最原始的方法
时间复杂度为n^3
小测试集合能过,但是大测试集合超时。

方法二:先排序,最外两层遍历,确定前两个数之后,最后一个数用二分查找
时间复杂度为logN * n^2
大测试集合花时间1220ms左右

方法三:在方法二的基础上,让前两个数跳过已经考察过的数
时间复杂度同上,没有质的改变,但是有点优化作用。
先优化第二圈,得到的时间在500ms左右
再优化第一圈,得到的时间为260ms左右
虽然时间复杂度在阶上没有提升,但是效果还是挺明显的。

代码如下:
方法一

class Solution {
public:
    vector > threeSum(vector &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector > *pResult = new vector >();
        for(int i = 0 ; i < num.size(); i ++) {
            for(int j = i + 1; j < num.size(); j ++) {
                for(int k = j + 1; k < num.size(); k ++){
                    int vi = num[i];
                    int vj = num[j];
                    int vk = num[k];
                    if(vi + vj + vk == 0){
                        vector *pTriple = new vector(3);
                        vector &triple = *pTriple;
                        triple[0] = vi;
                        triple[1] = vj;
                        triple[2] = vk;
                        sort(triple.begin(),triple.end());
                        (*pResult).push_back(triple);
                    }
                }
            }
        }
        sort(pResult->begin(),pResult->end());
        pResult->erase(unique(pResult->begin(),pResult->end()),pResult->end());
        return *pResult;
    }
};

方法二

class Solution {
public:
    vector > threeSum(vector &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sort(num.begin(),num.end());
        vector > *pResult = new vector >();
        if (num.size() < 3)
            return *pResult;
        for(int i = 0 ; i < num.size(); i ++) {
            int vi = num[i];
            for(int j = i + 1; j < num.size(); j ++) {
                int vj = num[j];
                int targetVk = -vi - vj;
                {//binary search targetVk in range j + 1 to num.size() - 1
                    int bI = j + 1;
                    int eI = num.size() - 1;
                    while( bI <= eI )
                    {
                        int mI = (bI + eI) / 2;
                        if (num[mI] == targetVk)
                        {
                            //bingo
                            vector *pTriple = new vector(3);
                            vector &triple = *pTriple;
                            triple[0] = vi;
                            triple[1] = vj; 
                            triple[2] = targetVk;
                            sort(triple.begin(),triple.end());
                            (*pResult).push_back(triple);
                            break;
                        } else if (num[mI] > targetVk) 
                        {
                            eI = mI - 1;
                        } else
                        {
                            bI = mI + 1;
                        }
                    }
                }
            }
        }
        sort(pResult->begin(),pResult->end());
        pResult->erase(unique(pResult->begin(),pResult->end()),pResult->end());
        return *pResult;
    }
};

方法三

class Solution {
public:
    vector > threeSum(vector &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sort(num.begin(),num.end());
        vector > *pResult = new vector >();
        if (num.size() < 3)
            return *pResult;
        int lastVi = num[0] - 1;
        for(int i = 0 ; i < num.size(); i ++) {
            int vi = num[i];
            if (vi == lastVi)
                continue;
            lastVi = vi;
            int lastVj = vi -1;
            for(int j = i + 1; j < num.size(); j ++) {
                int vj = num[j];
                if (vj == lastVj)
                    continue;
                lastVj = vj;
                int targetVk = -vi - vj;
                {//binary search targetVk in range j + 1 to num.size() - 1
                    int bI = j + 1;
                    int eI = num.size() - 1;
                    while( bI <= eI )
                    {
                        int mI = (bI + eI) / 2;
                        if (num[mI] == targetVk)
                        {
                            //bingo
                            vector *pTriple = new vector(3);
                            vector &triple = *pTriple;
                            triple[0] = vi;
                            triple[1] = vj; 
                            triple[2] = targetVk;
                            sort(triple.begin(),triple.end());
                            (*pResult).push_back(triple);
                            break;
                        } else if (num[mI] > targetVk) 
                        {
                            eI = mI - 1;
                        } else
                        {
                            bI = mI + 1;
                        }
                    }
                }
            }
        }
        sort(pResult->begin(),pResult->end());
        pResult->erase(unique(pResult->begin(),pResult->end()),pResult->end());
        return *pResult;
    }
};



Code rewrite at 2012-12-22, 256ms pass the large test set

class Solution {
public:
    vector > threeSum(vector &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector > ret;
        if(num.size() < 3) return ret;
        
        sort(num.begin(),num.end());
        
        for(int i = 0; i < num.size() - 2; ++i) {
            if(i > 0 && num[i] == num[i-1]) continue;
            for(int j = i + 1; j < num.size() - 1; ++j) {
                if(j > i + 1 && num[j] == num[j - 1]) continue;
                int target = -(num[i] + num[j]);
                int ks = j + 1;
                int ke = num.size() - 1;
                if(target < num[ks] || target > num[ke]) continue;
                while(ks <= ke) {
                    int km = (ks + ke) / 2;
                    if(num[km] == target) {
                        //found an triplet
                        vector tri(3,target);
                        tri[0] = num[i];
                        tri[1] = num[j];
                        ret.push_back(tri);
                        break;
                    } else if (num[km] > target) {
                        ke = km - 1;
                    } else {
                        ks = km + 1;
                    }
                }
            }
        }
        
        return ret;
    }
};

NSString和NSDate相互转换

使用方法如下所示:

NSString *dateStr = @"20120821161441";
NSDateFormatter *formater = [[NSDateFormatter alloc] init];
[formater setDateFormat:@"yyyyMMddhhmmss"];
NSDate *date = [formater dateFromString:dateStr];
[formater setDateFormat:@"yyyy-MM-dd hh:mm:ss"];
dateStr = [formater stringFromDate:date];
//dateStr is :2012-08-21 16:14:41

格式化参数如下:

G: 公元时代,例如AD公元
yy: 年的后2位
yyyy: 完整年
MM: 月,显示为1-12
MMM: 月,显示为英文月份简写,如 Jan
MMMM: 月,显示为英文月份全称,如 Janualy
dd: 日,2位数表示,如02
d: 日,1-2位显示,如 2
EEE: 简写星期几,如Sun
EEEE: 全写星期几,如Sunday
aa: 上下午,AM/PM
H: 时,24小时制,0-23
K:时,12小时制,0-11
m: 分,1-2位
mm: 分,2位
s: 秒,1-2位
ss: 秒,2位
S: 毫秒
Z: GMT时间

Examples

//like 2016-01-18T20:35:11.011Z
"yyyy-MM-dd'T'HH:mm:ss.SSSZ"

让iOS键盘在用户点击其它区域的时候隐藏

实现这个功能很简单,只需要在整个view上创建一个UITapGestureRecognizer

    {//tap gr
        UITapGestureRecognizer *tapGr = [[UITapGestureRecognizer alloc] initWithTarget:self action:@selector(viewTapped:)];
        tapGr.cancelsTouchesInView = NO;
        [self.view addGestureRecognizer:tapGr];
        [tapGr release];
    }
-(void)viewTapped:(UITapGestureRecognizer*)tapGr{
    [self.theTextField resignFirstResponder];
}

在这样操作之后,当用户点击键盘以外空白区域的时候,就能自动隐藏键盘了。
下面这句代码挺重要,因为如果没有这一句,在view中的button等可能会无法触发TouchUpInside事件。

        tapGr.cancelsTouchesInView = NO;

POJ1004 12个数求平均

今天晚上用手机刷了一道POJ 1004。题虽简单却有两点收获:
1.scanf/printf比cin/cout快,而且内存消耗少。
2.对于那些0k,0ms过的题目,不用纠结了。应该是poj系统的问题,现在写一个3个变量的程序都136K内存。

题目:求12个数的平均数
代码:
============== cin,cout 208K,16ms ================

#include<iostream>
using namespace std;
int main()
{
  float sum = 0;
  float cur = 0;
  while(cin>>cur)
  {
    sum+=cur;
  }
  sum/=12;
  cout<<'$'<<sum<<endl;
  return 0;
}

============== printf,scanf 136K,0ms ================

#include<stdio.h>
int main()
{
  float sum = 0;
  float cur = 0;
  for(int i=0;i<12;i++)
  {
    scanf("%f",&cur);
    sum+=cur;
  }
  sum/=12;
  printf("$%.2f",sum);
  return 0;
}

UIImagePickerController的自定义,状态栏空白问题

UIImagePickerController提供了很方便的界面和逻辑让我们可以直接拍照或者从相机胶卷选取照片。

使用的方法如下所示:

但是使用过程中也遇到一些问题,比如:
1.如何自定义拍照界面:

2.当[ctrl dismiss]之后,有时会出现20像素的下移空白,其实这个很容易解决。
比如,假设imagepicker是从parantController弹出来的,那么只需要在parentController的viewWillAppear函数中加入调整view.frame的代码即可。

3.设置界面语言,如设置为中文
默认是是英文的,如果需要中文的话,需要设置多语言环境,其实只需要创建一个.strings文件即可。

iOS截屏

在iOS开发中,遇到了一个需要截取当前窗口并保存在相册中的问题。代码如下:

    CGSize imageSize = CGSizeMake(320, 480 - 88);
    //支持retina就靠这句话,不带参数的begin保存的图片分辨率很低的。
    if (UIGraphicsBeginImageContextWithOptions != NULL) {
        UIGraphicsBeginImageContextWithOptions(imageSize, NO, 0.0);
    } else {
        UIGraphicsBeginImageContext(imageSize);
    }
    [self.view.layer renderInContext:UIGraphicsGetCurrentContext()];
    UIImage *image = UIGraphicsGetImageFromCurrentImageContext();
    UIGraphicsEndImageContext();
    
    UIImageWriteToSavedPhotosAlbum(image, nil, nil, nil);