ARTES #008

ARTS é uma atividade iniciada por 由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS) e persistem por pelo menos um ano.

ARTES 008

Este é o artigo 8

Pergunta sobre algoritmo de algoritmo

questão do algoritmo leetcode 18 4Sum: Dificuldade: 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 acabei de resolver o problema 3Sum da última vez, a primeira solução que pensei foi convertê-lo em um problema 3Sum. A implementação é a seguinte:

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

O tempo de execução do algoritmo acima no LeetCode é de 44ms. O seguinte mostra que o tempo de execução no LeetCode é de 4ms. O código é mais simples do que escrevi e o tempo de execução é 10 vezes mais rápido que o meu. A diferença não é nem um pouco.

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

Revisão

SEC processa Elon Musk por fraude e busca remoção da TeslaSEC

Os reguladores de valores mobiliários dos EUA tentaram na quinta-feira forçar o presidente-executivo da Tesla, Elon Musk, a deixar a empresa que ajudou a lançar há cerca de 15 anos, alegando que ele enganou os acionistas quando tuitou que tinha financiamento para o que teria sido a maior aquisição corporativa de todos os tempos.

Os reguladores de valores mobiliários dos EUA tentaram na quinta-feira forçar o presidente-executivo da Tesla Inc. TSLA, Elon Musk, a deixar a empresa que ele cofundou há quase 15 anos, acusando-o de enganar os acionistas quando tuitou que havia garantido financiamento para um acordo de fechamento de capital. Esperava-se que o negócio fosse o maior negócio privado da história.

O pedido da SEC no tribunal federal de Manhattan ameaça desferir um duro golpe para a fabricante de carros elétricos de Palo Alto, Califórnia. Sua marca e Musk estão intimamente interligados, e analistas dizem que o valor de mercado de cerca de US$ 50 bilhões da empresa é impulsionado pela apreciação de Wall Street pela visão e habilidade de Musk como inovador.

A Comissão de Valores Mobiliários dos EUA (SEC) entrou com a ação no tribunal federal de Manhattan. O caso provavelmente será um duro golpe para a fabricante de carros elétricos com sede em Palo Alto, Califórnia. A marca Tesla é inseparável do nome de Musk. Analistas disseram que por trás do valor de mercado da empresa de aproximadamente US$ 50 bilhões está a apreciação de Wall Street pela visão e tecnologia de Musk como inovador.

A Tesla não foi citada no processo como réu, mas a SEC está tentando impedir que Musk, o maior acionista e seu principal executivo da Tesla, atue como executivo ou diretor de qualquer empresa pública dos EUA. As ações da Tesla, que têm estado sob intensa pressão em meio a questões sobre a força financeira da empresa e o comportamento de Musk, caíram 9,9%, para US$ 277, no pregão de quinta-feira na Nasdaq.

Tesla não é citada como réu no caso, mas a SEC está tentando impedir Musk de atuar como executivo ou diretor de qualquer empresa pública dos EUA. Musk é atualmente o maior acionista e CEO da Tesla. Diante de questões sobre a solidez financeira da Tesla e o comportamento pessoal de Musk, o preço das ações da empresa tem estado sob tremenda pressão. As ações caíram 9,9%, para US$ 277, no pregão do mercado Nasdaq na quinta-feira.

“Esta ação injustificada da SEC me deixa profundamente triste e desapontado”, disse Musk em comunicado. “Sempre agi no melhor interesse da verdade, da transparência e dos investidores. A integridade é o valor mais importante da minha vida e os factos mostrarão que nunca comprometi isso de forma alguma.”

Musk disse em um comunicado: “Esta ação irracional da SEC me deixa muito triste e decepcionado. Sempre tento o meu melhor para defender os princípios da verdade e da transparência e salvaguardar os interesses dos acionistas. A integridade é o valor que mais valorizo, e os fatos provarão que nunca fiz nada que viole a integridade.”

“Estou profundamente triste e desapontado com esta conduta imprópria da SEC”, disse Musk em comunicado. “Sempre agi no melhor interesse da verdade, da transparência e dos investidores. A integridade é o valor mais importante da minha vida e os fatos provarão que nunca a comprometi de forma alguma.”

DICAS:

O artigo anterior introduziu o método de uso de CAGradientLayer para implementar cores gradientes. Além de usar CAGradientLayer para implementar cores gradientes, você também pode usar CGGradientRef e Core Image. No entanto, ao usar CGGradientRef e Core Image para implementar cores gradientes, você precisa chamá-lo no método drawRect:. Há uma explicação muito boa sobre o uso de Core Graphics e Core Image: http://www.techotopia.com/index.php/An_iOS_7_Graphics_Tutorial_using_Core_Graphics_and_Core_Image            CGGradientRef: O seguinte código deve ser escrito em 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];

Percebe-se que os métodos de implementação são diferentes, mas os efeitos ainda são diferentes. Vale ressaltar também que UIBezierPath e CAShapeLayer podem ser combinados para fazer algumas animações.

Artigo de referência: 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

Compartilhar:

Há uma pergunta que nunca entendi. A maior parte da eletricidade que utilizamos atualmente (70%) provém da geração de energia térmica. O combustível para geração de energia térmica vem do petróleo e do carvão. Existem muitas perdas no processo de geração de energia térmica.

Por exemplo: 1kg de óleo, se usado diretamente para ferver água, pode ferver 20kg de água. Se você usar primeiro 1 kg de óleo para gerar eletricidade e depois usar eletricidade para ferver água, poderá ferver apenas 10 kg de água.

Neste caso, por que usamos carros elétricos? Para a mesma distância de 1 km, o consumo real de combustível dos veículos elétricos é, na verdade, maior. A utilização de veículos eléctricos na verdade aumenta a poluição, mas a poluição ocorre nas centrais eléctricas e é transferida.

Então, por que usamos carros elétricos ou outros dispositivos que utilizam eletricidade quando poderiam usar petróleo?