ARTES #008

ARTES es una actividad iniciada por 由左耳朵耗子--陈皓: Haga al menos una pregunta sobre el algoritmo leetcode cada semana, lea y comente al menos un artículo técnico en inglés, aprenda al menos una habilidad técnica y comparta un artículo con opiniones y pensamientos. (Es decir, Algoritmo, Revisión, Sugerencia y Compartir se denominan ARTS) y persisten durante al menos un año.

##ARTES 008

este es el articulo 8

Pregunta sobre el algoritmo del algoritmo

Algoritmo leetcode pregunta 18 4Sum: Dificultad: Moderada

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

Como resolví el problema de 3Sum la última vez, la primera solución que se me ocurrió fue convertirlo en un problema de 3Sum. La implementación es la siguiente:

//插入排序
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;
}

El tiempo de ejecución del algoritmo anterior en LeetCode es de 44 ms. A continuación se muestra que el tiempo de ejecución en LeetCode es de 4 ms. El código es más simple que el que escribí y el tiempo de ejecución es 10 veces más rápido que el mío. La diferencia no es pequeña.

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

Revisión

La SEC demanda a Elon Musk por fraude y busca la expulsión de TeslaSEC

Los reguladores de valores estadounidenses intentaron el jueves obligar al presidente ejecutivo de Tesla Inc, Elon Musk, a abandonar la compañía que ayudó a despegar hace unos 15 años, alegando que engañó a los accionistas cuando tuiteó que tenía fondos para lo que habría sido la mayor compra corporativa jamás realizada.

Los reguladores de valores estadounidenses intentaron el jueves obligar al presidente ejecutivo de Tesla Inc. TSLA, Elon Musk, a abandonar la compañía que cofundó hace casi 15 años, acusándolo de engañar a los accionistas cuando tuiteó que había obtenido financiamiento para un acuerdo de privatización. Se esperaba que el acuerdo fuera el mayor acuerdo privado de la historia.

La presentación de la SEC ante un tribunal federal de Manhattan amenaza con asestar un duro golpe al fabricante de automóviles eléctricos de Palo Alto, California. Su marca y Musk están estrechamente entrelazados, y los analistas han dicho que el valor de mercado de aproximadamente 50 mil millones de dólares de la compañía está impulsado por el aprecio de Wall Street por la visión y habilidad de Musk como innovador.

La Comisión de Bolsa y Valores de Estados Unidos (SEC) presentó la demanda en el tribunal federal de Manhattan. Es probable que el caso suponga un duro golpe para el fabricante de automóviles eléctricos con sede en Palo Alto, California. La marca Tesla es inseparable del nombre de Musk. Los analistas han dicho que detrás del valor de mercado de la compañía de aproximadamente 50 mil millones de dólares está la apreciación de Wall Street por la visión y la tecnología de Musk como innovador.

Tesla no fue nombrado en la demanda como acusado, pero la SEC busca prohibir a Musk, el mayor accionista de Tesla y su principal ejecutivo, desempeñarse como funcionario o director de cualquier empresa pública estadounidense. Las acciones de Tesla, que han estado bajo intensa presión en medio de dudas sobre la solidez financiera de la empresa y el comportamiento de Musk, cayeron un 9,9% a 277 dólares en las operaciones fuera de horario del jueves en Nasdaq.

Tesla no figura como acusado en el caso, pero la SEC busca impedir que Musk se desempeñe como funcionario o director de cualquier empresa pública estadounidense. Musk es actualmente el mayor accionista y director ejecutivo de Tesla. Ante las preguntas sobre la fortaleza financiera de Tesla y el comportamiento personal de Musk, el precio de las acciones de la compañía ha estado bajo una tremenda presión. La acción cayó un 9,9% a 277 dólares en las operaciones fuera de horario en el mercado Nasdaq el jueves.

“Esta acción injustificada de la SEC me deja profundamente entristecido y decepcionado”, dijo Musk en un comunicado. “Siempre he actuado en aras de la verdad, la transparencia y los inversores. La integridad es el valor más importante de mi vida y los hechos demostrarán que nunca comprometí esto de ninguna manera”.

Musk dijo en un comunicado: “Esta acción irrazonable de la SEC me entristece y decepciona mucho. Siempre hago todo lo posible para defender los principios de verdad y transparencia y salvaguardar los intereses de los accionistas. La integridad es el valor que más valoro, y los hechos demostrarán que nunca he hecho nada que viole la integridad”.

“Estoy profundamente entristecido y decepcionado por esta conducta inapropiada de la SEC”, dijo Musk en un comunicado. “Siempre he actuado en beneficio de la verdad, la transparencia y los inversores. La integridad es el valor más importante de mi vida y los hechos demostrarán que nunca lo he comprometido de ninguna manera”.

CONSEJOS:

El artículo anterior presentó el método de utilizar CAGradientLayer para implementar colores degradados. Además de usar CAGradientLayer para implementar colores degradados, también puede usar CGGradientRef y Core Image. Sin embargo, cuando usa CGGradientRef y Core Image para implementar colores degradados, debe llamarlo en el método drawRect:. Hay una muy buena explicación sobre el uso de Core Graphics y Core Image: http://www.techotopia.com/index.php/An_iOS_7_Graphics_Tutorial_using_Core_Graphics_and_Core_Image            CGGradientRef: El siguiente código debe escribirse en 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];

Se puede ver que los métodos de implementación son diferentes, pero los efectos siguen siendo diferentes. También vale la pena mencionar que UIBezierPath y CAShapeLayer se pueden combinar para realizar algunas animaciones.

Artículo de referencia: 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

Compartir:

Hay una pregunta que nunca he entendido. La mayor parte de la electricidad que utilizamos ahora (70%) proviene de la generación de energía térmica. El combustible para la generación de energía térmica proviene del petróleo y del carbón. Hay muchas pérdidas en el proceso de generación de energía térmica.

Por ejemplo: 1 kg de aceite, si se usa directamente para hervir agua, puede hervir 20 kg de agua. Si primero usa 1 kg de aceite para generar electricidad y luego usa electricidad para hervir agua, es posible que solo pueda hervir 10 kg de agua.

En este caso, ¿por qué utilizamos coches eléctricos? Para la misma distancia de 1 km, el consumo real de combustible de los vehículos eléctricos es en realidad mayor. El uso de vehículos eléctricos en realidad aumenta la contaminación, pero la contaminación se produce en las centrales eléctricas y se transfiere.

Entonces, ¿por qué utilizamos coches eléctricos u otros dispositivos que utilizan electricidad cuando podrían utilizar petróleo?