الفنون رقم 008

ARTS هو نشاط بدأه 由左耳朵耗子--陈皓: قم بإجراء سؤال واحد على الأقل عن خوارزمية leetcode كل أسبوع، واقرأ مقالًا تقنيًا واحدًا على الأقل باللغة الإنجليزية وعلق عليه، وتعلم مهارة فنية واحدة على الأقل، وشارك المقالة مع الآراء والأفكار. (أي أن الخوارزمية والمراجعة والنصائح والمشاركة يشار إليها باسم ARTS) وتستمر لمدة عام واحد على الأقل.

فنون 008

هذه هي المادة 8

سؤال خوارزمية الخوارزمية

سؤال خوارزمية 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 هو 44 مللي ثانية. يوضح ما يلي أن وقت التشغيل على LeetCode هو 4 مللي ثانية. الكود أبسط مما كتبته، ووقت التشغيل أسرع 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;
}

مراجعة

هيئة الأوراق المالية والبورصات تقاضي إيلون ماسك بتهمة الاحتيال، وتطالب بإزالته من TeslaSEC

سعى منظمو الأوراق المالية في الولايات المتحدة يوم الخميس إلى إجبار الرئيس التنفيذي لشركة Tesla Inc Elon Musk على الخروج من الشركة التي ساعدها في تأسيسها قبل حوالي 15 عامًا، زاعمين أنه ضلل المساهمين عندما غرد بأنه حصل على تمويل لما كان يمكن أن يكون أكبر عملية استحواذ على الإطلاق للشركات.

سعى منظمو الأوراق المالية في الولايات المتحدة يوم الخميس إلى إجبار الرئيس التنفيذي لشركة Tesla Inc. TSLA، إيلون ماسك، على الخروج من الشركة التي شارك في تأسيسها قبل 15 عامًا تقريبًا، واتهموه بتضليل المساهمين عندما غرد قائلاً إنه حصل على تمويل لصفقة التحول إلى القطاع الخاص. وكان من المتوقع أن تكون الصفقة أكبر صفقة خاصة في التاريخ.

ويهدد التقديم الذي قدمته هيئة الأوراق المالية والبورصات إلى المحكمة الفيدرالية في مانهاتن بتوجيه ضربة قاسية لشركة صناعة السيارات الكهربائية في بالو ألتو، كاليفورنيا. إن علامتها التجارية والسيد ماسك مترابطان بشكل وثيق، ويقول المحللون إن القيمة السوقية للشركة البالغة 50 مليار دولار تقريبًا مدفوعة بتقدير وول ستريت لرؤية السيد ماسك ومهارته كمبتكر.

ورفعت هيئة الأوراق المالية والبورصة الأمريكية (SEC) الدعوى في محكمة مانهاتن الفيدرالية. ومن المرجح أن تمثل هذه القضية ضربة قوية لشركة صناعة السيارات الكهربائية ومقرها بالو ألتو بولاية كاليفورنيا. لا يمكن فصل علامة تسلا التجارية عن اسم ماسك. قال المحللون إن القيمة السوقية للشركة التي تبلغ حوالي 50 مليار دولار أمريكي تكمن وراء تقدير وول ستريت لرؤية ماسك وتقنياته كمبتكر.

لم يتم ذكر اسم تسلا في الدعوى كمدعى عليه، لكن هيئة الأوراق المالية والبورصة تسعى إلى منع السيد ماسك، أكبر مساهم في تسلا وكبير مسؤوليها التنفيذيين، من العمل كمسؤول أو مدير في أي شركة عامة أمريكية. وانخفضت أسهم تيسلا، التي تعرضت لضغوط شديدة وسط تساؤلات حول القوة المالية للشركة وسلوك السيد موسك، بنسبة 9.9٪ إلى 277 دولارًا في تعاملات ما بعد ساعات العمل يوم الخميس في بورصة ناسداك.

ولم يتم ذكر اسم تسلا كمدعى عليه في القضية، لكن هيئة الأوراق المالية والبورصات تسعى إلى منع موسك من العمل كمسؤول أو مدير في أي شركة عامة أمريكية. يعد Musk حاليًا أكبر مساهم ورئيس تنفيذي لشركة Tesla. وفي مواجهة الأسئلة حول القوة المالية لشركة تيسلا وسلوك ماسك الشخصي، تعرض سعر سهم الشركة لضغوط هائلة. انخفض السهم بنسبة 9.9٪ إلى 277 دولارًا بعد ساعات التداول في سوق ناسداك يوم الخميس.

وقال السيد ماسك في بيان: “هذا الإجراء غير المبرر من قبل هيئة الأوراق المالية والبورصات يتركني أشعر بحزن عميق وخيبة أمل”. “لقد اتخذت دائمًا إجراءات تصب في مصلحة الحقيقة والشفافية والمستثمرين. النزاهة هي القيمة الأكثر أهمية في حياتي وستظهر الحقائق أنني لم أتنازل عن هذا الأمر بأي شكل من الأشكال”.

وقال ماسك في بيان: “هذا الإجراء غير المعقول من قبل لجنة الأوراق المالية والبورصة يجعلني أشعر بالحزن وخيبة الأمل للغاية. أبذل قصارى جهدي دائمًا لدعم مبادئ الحقيقة والشفافية وحماية مصالح المساهمين. النزاهة هي القيمة التي أقدرها كثيرًا، وستثبت الحقائق أنني لم أفعل أبدًا أي شيء ينتهك النزاهة”.

وقال ماسك في بيان: “أشعر بحزن عميق وخيبة أمل بسبب هذا السلوك غير اللائق من قبل لجنة الأوراق المالية والبورصات”. “لقد تصرفت دائمًا بما يخدم مصلحة الحقيقة والشفافية والمستثمرين. النزاهة هي القيمة الأكثر أهمية في حياتي، وستثبت الحقائق أنني لم أتنازل عنها أبدًا بأي شكل من الأشكال.”

نصائح:

قدمت المقالة السابقة طريقة استخدام 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            المرجع CGGradient: يجب كتابة الكود التالي في 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

شارك:

هناك سؤال لم أفهمه قط. معظم الكهرباء التي نستخدمها الآن (70%) تأتي من توليد الطاقة الحرارية. الوقود المستخدم لتوليد الطاقة الحرارية يأتي من النفط والفحم. هناك الكثير من الخسائر في عملية توليد الطاقة الحرارية.

على سبيل المثال: 1 كجم من الزيت، إذا تم استخدامه مباشرة لغلي الماء، يمكن أن يغلي 20 كجم من الماء. إذا استخدمت أولًا كيلوجرامًا واحدًا من الزيت لتوليد الكهرباء ثم استخدمت الكهرباء لغلي الماء، فقد تتمكن من غلي 10 كيلوجرامات فقط من الماء.

وفي هذه الحالة لماذا نستخدم السيارات الكهربائية؟ ولنفس المسافة البالغة كيلومتر واحد، يكون استهلاك الوقود الفعلي للسيارات الكهربائية أعلى في الواقع. إن استخدام السيارات الكهربائية يزيد في الواقع من التلوث، ولكن التلوث يحدث في محطات توليد الطاقة ويتم نقله.

فلماذا نستخدم السيارات الكهربائية أو الأجهزة الأخرى التي تستخدم الكهرباء عندما يمكنها استخدام النفط؟