ARTS Algorihm iOS

ARTS #008

ARTS #008

Posted by Dan on September 30, 2018

ARTS是由左耳朵耗子--陈皓发起的一个活动: 每周至少做一个leetcode的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的文章。（也就是Algorithm、Review、Tip、Share简称ARTS），至少坚持一年。

ARTS 008

这是第8篇

Algorihm 算法题

leetcode算法第18题4Sum: 难度：中等

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

由于上一次刚做过3Sum的问题，那么这道题我最先想到的解决办法就是，把他转为3Sum问题，实现如下:

//插入排序
int* insertionSort(int nums[],int numsSize) {
    for (int j = 1; j < numsSize; j++) {
        int  sortingNum = nums[j];
        for (int i = j-1; i >=0; i--) {
            if (sortingNum < nums[i] ) {
                int temp = nums[i+1];
                nums[i+1] = nums[i];
                nums[i] = temp;
            }
        }
    }
    return nums;
}


// 二分查找
int binary_search(int arr[],int left,int right,int element){
    while(left<=right) {
        int mid = (left+right)/2;
        if(arr[mid]>element){
            right = mid - 1;
        }
        else if(arr[mid]<element){
            left = mid + 1;
        }
        else{
            return mid;
        }
    }
    return -1;
}

int** threeSumtarget(int* nums, int numsSize, int* returnSize,int target) {
    int *sortedNums = insertionSort(nums,numsSize);
    int min = sortedNums[0] ;
    int max = sortedNums[numsSize-1];

    
    
    
    int count = 0;
    int **result= NULL;
    
    int mixLimit = 0;
    int maxLimit = 0;
    if (target > 0) {
        mixLimit = target;
        maxLimit = 0;
    }
    else if (target < 0){
        mixLimit = 0;
        maxLimit = target;
    }
    else{
        mixLimit = 0;
        maxLimit = 0;
    }
    
    if(min > mixLimit)//最小数
        return NULL;
    if(max < maxLimit)//最大数
        return NULL;
    
    
    for (int i = 0; i < numsSize-2 && sortedNums[i] <=mixLimit; i++) {
        if (i > 0 && sortedNums[i] == sortedNums[i-1]) {
            continue;
        }
        for (int j =numsSize-1; j >i && sortedNums[j] >= maxLimit; j--) {
            if (j < numsSize-1 && sortedNums[j] == sortedNums[j+1]) {
                continue;
            }
            
            int first = sortedNums[i];
            int second = sortedNums[j];
            int third = target - first - second;
            int dfsd =binary_search(sortedNums, i+1, j-1, third);
            if (dfsd == -1) {
                continue;
            }
            third = sortedNums[dfsd];
            
            
            int* sums = (int*)malloc(sizeof(int) * (3));
            sums[0] = first;
            sums[1] = second;
            sums[2] = third;
            
            if (count ==0) {
                count++;
                result=(int**)malloc(sizeof(sums)*count);
            }
            else{
                count++;
                result=(int**)realloc(result,sizeof(int*)*count);
            }
            result[count-1] = sums;
        }
    }

    
    *returnSize = count;
    return result;
}

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 
 Given array nums = [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]
 ]
 */
int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
    int *sortedNums = insertionSort(nums,numsSize);
    int **result= NULL;
    int count =0;
    for (int i=0; i < numsSize- 3; i++) {
        if (target >0 ) {
            if (sortedNums[i] >= target) {
                break;
            }
        }
        else if ( target < 0){
            if (sortedNums[i] >= 0) {
                break;
            }
        }else{
            if (sortedNums[i] > 0) {
                break;
            }
        }
        if (i > 0 && sortedNums[i] == sortedNums[i-1]) {
            continue;
        }
        
        int left = target - sortedNums[i];
        int returnSize1 = 0;
        int **aa = threeSumtarget(nums + i +1,  numsSize - i-1, &returnSize1,left);
        for (int j =0; j< returnSize1; j++) {
            int *t = aa[j];
             t=(int*)realloc(t,sizeof(int)*4);
            t[3] = sortedNums[i];
            
            if (count ==0) {
                count++;
                result=(int**)malloc(sizeof(t)*count);
            }
            else{
                count++;
                result=(int**)realloc(result,sizeof(int*)*count);
            }
            result[count-1] = t;
        }
        
    }
     *returnSize = count;
    return result;
}

上面的算法在LeetCode的运行时间是44ms，下面给出的是LeetCode上运行时间是4ms，代码比我写的简单，运行时间是我的10快，差距不是一点点啊。

void Qsort(int*s,int left,int right){
    
    if(left >= right) return ;   //这一句必不可少，后面递归的终止条件
    int tem = s[left];
    int i = left;
    int j = right;
    while(i < j){
        while((s[j] >= tem) && (i < j))   //从后往前比较
            j--;
        if(i < j) s[i] = s[j];
        while((s[i] <= tem) && (i < j)) //从前往后比较
            i++;
        if(i < j) s[j] = s[i];
    }
    s[i] = tem;    //把基准放到位置上
    Qsort(s,left,i-1);
    Qsort(s,j+1,right);
}



int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
    Qsort(nums,0,numsSize-1);
    int **res = NULL;
    *returnSize = 0;
    if ((nums == NULL) || (numsSize < 4))
        return NULL;
    
    res =  malloc(sizeof(int *) * numsSize * (numsSize - 1) * (numsSize - 2) * (numsSize - 3) / 24);
    int i,j,m = 0;
    
    
    for(i = 0;i < numsSize - 3;i++){
        if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target)
            break;
        // check [a,x,x,x] maxinum
        if(nums[i]+nums[numsSize-3]+nums[numsSize-2]+nums[numsSize-1] < target)
            continue;
        for(j = i + 1;j < numsSize - 2;j++){
            // check [a,b,x,x] mininu
            if(nums[i]+nums[j]+nums[j+1]+nums[j+2] > target)
                break;
            // check [a,b,x,x] maxinum
            if(nums[i]+nums[j]+nums[numsSize-2]+nums[numsSize-1] < target)
                continue;
            
            int left = j + 1;
            int right = numsSize - 1;
            while(left < right){
                if((nums[i] + nums[j] + nums[left] + nums[right]) == target){
                    res[*returnSize] = (int*)malloc(sizeof(int)*4);
                    res[*returnSize][0] = nums[i];
                    res[*returnSize][1] = nums[j];
                    res[*returnSize][2] = nums[left];
                    res[*returnSize][3] = nums[right];
                    (*returnSize)++;
                    while(left<right && nums[left] == nums[left+1])
                        left++;
                    while(left<right && nums[right] == nums[right-1])
                        right--;
                    left++;
                    right--;
                }
                else if((nums[i] + nums[j] + nums[left] + nums[right]) > target)      //右指针左移
                    right--;
                else
                    left++;                                       //左指针右移
            }
            while(j < numsSize-2 && nums[j+1] == nums[j])
                j++;
        }
        while(i < numsSize - 3 && nums[i+1] == nums[i])
            i++;
    }
    //*returnSize = m;
    return res;
}

Review

SEC Sues Elon Musk for Fraud, Seeks Removal From TeslaSEC

U.S. securities regulators on Thursday sought to force Tesla Inc Chief Executive Elon Musk out of the company he helped get off the ground about 15 years ago, alleging he misled shareholders when he tweeted he had funding for what would have been the largest-ever corporate buyout.

美国证券监管机构周四寻求迫使特斯拉(Tesla Inc., TSLA)首席执行长马斯克(Elon Musk)离开这家他大约15年前联合创办的公司，指控他在发表推文称已为私有化交易锁定融资时误导了股东。这宗交易原本有望成为史上规模最大的私有化交易。

The filing by the SEC in federal court in Manhattan threatens to deal a severe blow to the Palo Alto, Calif., electric car maker. Its brand and Mr. Musk are closely intertwined, and analysts have said the company’s roughly $50 billion market value is driven by Wall Street’s appreciation for Mr. Musk’s vision and skill as an innovator.

美国证券交易委员会(Securities and Exchange Commission, 简称SEC)向曼哈顿联邦法院提起该诉讼。该案恐怕会给这家总部位于加州帕洛阿尔托的电动汽车制造商带来沉重一击。特斯拉品牌与马斯克之名密不可分，分析师曾表示，这家公司获得约500亿美元市值的背后，是华尔街对马斯克这位创新者的眼光和技术的赏识。

Tesla wasn’t named in the suit as a defendant, but the SEC is seeking to bar Mr. Musk, Tesla’s largest shareholder and its top executive, from serving as an officer or director of any U.S. public company. Tesla shares, which have been under intense pressure amid questions about the firm’s financial strength and Mr. Musk’s behavior, tumbled 9.9% to $277 in after-hours trading Thursday on Nasdaq.

特斯拉并未在该案中被列为被告，但SEC正试图禁止马斯克担任任何美国上市公司的高管或董事。目前马斯克是特斯拉最大股东兼首席执行长。面对围绕特斯拉财务实力以及马斯克个人行为的质疑之声，该公司股价一直承受巨大压力，该股周四在纳斯达克市场盘后交易中重挫9.9%，至277美元。

“This unjustified action by the SEC leaves me deeply saddened and disappointed,” Mr. Musk said in a statement. “I have always taken action in the best interests of truth, transparency and investors. Integrity is the most important value in my life and the facts will show I never compromised this in any way.”

马斯克在一份声明中称：“SEC这一不合理行动让我非常难过和失望。我总是尽最大可能维护真实透明的原则，维护股东的利益。诚信是我最看重的价值观，事实将会证明我从未做有违诚信的事。”

马斯克在一份声明中说，“SEC的这一不正当行为让我深感悲哀和失望。”“我总是为了真理、透明度和投资者的最大利益而采取行动。诚信是我生命中最重要的价值，事实将证明我从未以任何方式妥协。

TIPS:

上篇文章介绍了用CAGradientLayer实现渐变色的方法，除了使用CAGradientLayer可以实现渐变色之外还可以使用CGGradientRef和 Core Image，但是使用CGGradientRef和 Core Image实现渐变色的时候需要在drawRect：方法里面调用 关于 Core Graphics 和 Core Image,的使用这有一篇非常好的讲解： http://www.techotopia.com/index.php/An_iOS_7_Graphics_Tutorial_using_Core_Graphics_and_Core_Image            CGGradientRef： 下面的代码要写在drawRect：    

    UIColor *_inputColor0 = [UIColor yellowColor];
    UIColor *_inputColor1 = [UIColor blueColor];
    CGPoint _inputPoint0 = CGPointMake(0, 0);
    CGPoint _inputPoint1 = CGPointMake(0, 1);
  //方法1
    CGContextRef context = UIGraphicsGetCurrentContext();
    UIGraphicsPushContext(context);
    CGColorSpaceRef colorSpace = CGColorSpaceCreateDeviceRGB();
    CGFloat locations[] = {0,1};
    NSArray *colors = @[(__bridge id)_inputColor0.CGColor, (__bridge id)_inputColor1.CGColor];
    CGGradientRef gradient = CGGradientCreateWithColors(colorSpace, (CFArrayRef) colors, locations);
    CGColorSpaceRelease(colorSpace);
    CGPoint startPoint = (CGPoint){rect.size.width * _inputPoint0.x, rect.size.height * _inputPoint0.y};
    CGPoint endPoint = (CGPoint){rect.size.width * _inputPoint1.x, rect.size.height * _inputPoint1.y};
    CGContextDrawLinearGradient(context, gradient, startPoint, endPoint, 0);
    CGGradientRelease(gradient);
    UIGraphicsPopContext();

    

   UIColor *_inputColor0 = [UIColor yellowColor];
    UIColor *_inputColor1 = [UIColor blueColor];
    CGPoint _inputPoint0 = CGPointMake(0, 0);
    CGPoint _inputPoint1 = CGPointMake(0, 1);
    
    CIFilter *ciFilter = [CIFilter filterWithName:@"CILinearGradient"];
    CIVector *vector0 = [CIVector vectorWithX:rect.size.width * _inputPoint0.x Y:rect.size.height * (1 - _inputPoint0.y)];
    CIVector *vector1 = [CIVector vectorWithX:rect.size.width * _inputPoint1.x Y:rect.size.height * (1 - _inputPoint1.y)];
    [ciFilter setValue:vector0 forKey:@"inputPoint0"];
    [ciFilter setValue:vector1 forKey:@"inputPoint1"];
    [ciFilter setValue:[CIColor colorWithCGColor:_inputColor0.CGColor] forKey:@"inputColor0"];
    [ciFilter setValue:[CIColor colorWithCGColor:_inputColor1.CGColor] forKey:@"inputColor1"];
    CIImage *ciImage = ciFilter.outputImage;
    CIContext *con = [CIContext contextWithOptions:nil];
    CGImageRef resultCGImage = [con createCGImage:ciImage                                             fromRect:rect];
    UIImage *resultUIImage = [UIImage imageWithCGImage:resultCGImage];
    CGImageRelease(resultCGImage);
    [resultUIImage drawInRect:rect];
   效果如下图


    UIColor *_inputColor0 = [UIColor yellowColor];
    UIColor *_inputColor1 = [UIColor blueColor];
    CGPoint _inputPoint0 = CGPointMake(0, 0);
    CGPoint _inputPoint1 = CGPointMake(0, 1);
    
    CAGradientLayer *layer = [CAGradientLayer new];
    layer.colors = @[(__bridge id)_inputColor0.CGColor, (__bridge id)_inputColor1.CGColor];
    layer.startPoint = _inputPoint0;
    layer.endPoint = _inputPoint1;
    layer.frame = view.bounds;
    [view.layer addSublayer:layer];

可以看到实现方法不一样，效果还是不一样的。另外值得一提的是UIBezierPath和CAShapeLayer可以组合起来做一些动画。

参考文章： http://www.cnblogs.com/YouXianMing/p/3793913.html https://www.techotopia.com/index.php/An_iOS_7_Graphics_Tutorial_using_Core_Graphics_and_Core_Image

Share:

一直有一个问题没想明白，我们现在用的电大部分（70%）来自火力发电，火力发电的燃料来自石油和煤炭，在火力发电过程中是有很多损耗的。

比如：1kg的石油，如果直接用来烧水，可以烧开20kg的水。如果先用1kg的石油发电，然后再用电烧水，可能就只能烧开10kg的水。

既然这样的话，我们为什么要用电动汽车呢？同样1km的距离，电动汽车实际耗油量其实更高了。 使用电动汽车实际上是加剧了污染，只不过污染发生在发电厂，污染转移了而已。

那么我们为什么使用电动汽车或者其他可以使用石油却使用电的设备呢？

CATALOG
    FEATURED TAGS
    iOS Runtime Xcode ARTS Algorihm 翻译 方法论 算法 数据结构
    RECOMMEND