SENI #008

SENI adalah kegiatan yang diprakarsai oleh 由左耳朵耗子--陈皓: Kerjakan setidaknya satu pertanyaan algoritma leetcode setiap minggu, baca dan komentari setidaknya satu artikel teknis berbahasa Inggris, pelajari setidaknya satu keterampilan teknis, dan bagikan artikel yang berisi opini dan pemikiran. (Artinya, Algoritma, Review, Tip, dan Share disebut sebagai SENI) dan bertahan setidaknya selama satu tahun.

SENI 008

Ini adalah pasal 8

Pertanyaan algoritma algoritma

pertanyaan algoritma leetcode 18 4Sum: Kesulitan: Sedang

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

Karena saya baru saja menyelesaikan masalah 3Sum terakhir kali, solusi pertama yang saya pikirkan adalah mengubahnya menjadi masalah 3Sum. Implementasinya adalah sebagai berikut:

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

Waktu berjalan algoritma di atas pada LeetCode adalah 44ms. Berikut ini menunjukkan bahwa waktu berjalan pada LeetCode adalah 4ms. Kodenya lebih sederhana dari yang saya tulis, dan waktu prosesnya 10 kali lebih cepat dari milik saya. Perbedaannya tidak sedikit.

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

Ulasan

SEC Menuntut Elon Musk karena Penipuan, Mencari Penghapusan dari TeslaSEC

Regulator sekuritas AS pada hari Kamis berusaha memaksa Kepala Eksekutif Tesla Inc Elon Musk keluar dari perusahaan yang ia bantu berdirikan sekitar 15 tahun yang lalu, dengan tuduhan ia menyesatkan pemegang saham ketika ia men-tweet bahwa ia memiliki dana untuk pembelian perusahaan terbesar yang pernah ada.

Regulator sekuritas AS pada hari Kamis berusaha memaksa Kepala Eksekutif Tesla Inc. TSLA Elon Musk keluar dari perusahaan yang ia dirikan bersama hampir 15 tahun yang lalu, menuduhnya menyesatkan pemegang saham ketika ia men-tweet bahwa ia telah mendapatkan pembiayaan untuk kesepakatan go-private. Kesepakatan itu diharapkan menjadi kesepakatan swasta terbesar dalam sejarah.

Pengajuan SEC ke pengadilan federal di Manhattan mengancam akan memberikan pukulan telak bagi produsen mobil listrik Palo Alto, California. Mereknya dan Musk saling terkait erat, dan para analis mengatakan nilai pasar perusahaan yang bernilai sekitar $50 miliar didorong oleh apresiasi Wall Street atas visi dan keterampilan Musk sebagai seorang inovator.

Komisi Sekuritas dan Bursa AS (SEC) mengajukan gugatan di pengadilan federal Manhattan. Kasus ini kemungkinan besar akan menjadi pukulan berat bagi produsen mobil listrik yang berbasis di Palo Alto, California tersebut. Merek Tesla tidak lepas dari nama Musk. Analis mengatakan bahwa di balik nilai pasar perusahaan yang mencapai sekitar US$50 miliar adalah apresiasi Wall Street terhadap visi dan teknologi Musk sebagai inovator.

Tesla tidak disebutkan dalam gugatan tersebut sebagai tergugat, namun SEC berusaha untuk melarang Musk, pemegang saham terbesar Tesla dan eksekutif puncaknya, untuk menjabat sebagai pejabat atau direktur perusahaan publik AS mana pun. Saham Tesla, yang berada di bawah tekanan kuat di tengah pertanyaan tentang kekuatan finansial perusahaan dan perilaku Musk, anjlok 9,9% menjadi $277 dalam perdagangan after-hours Kamis di Nasdaq.

Tesla tidak disebutkan sebagai terdakwa dalam kasus ini, namun SEC berusaha untuk melarang Musk menjabat sebagai pejabat atau direktur perusahaan publik AS mana pun. Musk saat ini adalah pemegang saham dan CEO terbesar Tesla. Dihadapkan pada pertanyaan tentang kekuatan finansial Tesla dan perilaku pribadi Musk, harga saham perusahaan berada di bawah tekanan yang luar biasa. Sahamnya turun 9,9% menjadi $277 dalam perdagangan setelah jam kerja di pasar Nasdaq pada hari Kamis.

“Tindakan SEC yang tidak dapat dibenarkan ini membuat saya sangat sedih dan kecewa,” kata Musk dalam sebuah pernyataan. “Saya selalu mengambil tindakan demi kepentingan kebenaran, transparansi, dan investor. Integritas adalah nilai terpenting dalam hidup saya dan fakta menunjukkan bahwa saya tidak pernah mengkompromikan hal ini dengan cara apa pun.”

Musk mengatakan dalam sebuah pernyataan: “Tindakan SEC yang tidak masuk akal ini membuat saya sangat sedih dan kecewa. Saya selalu berusaha sebaik mungkin untuk menjunjung tinggi prinsip kebenaran dan transparansi serta menjaga kepentingan pemegang saham. Integritas adalah nilai yang paling saya hargai, dan fakta akan membuktikan bahwa saya tidak pernah melakukan apa pun yang melanggar integritas.”

“Saya sangat sedih dan kecewa dengan tindakan tidak pantas yang dilakukan SEC,” kata Musk dalam sebuah pernyataan. “Saya selalu bertindak demi kebenaran, transparansi, dan investor. Integritas adalah nilai terpenting dalam hidup saya, dan fakta akan membuktikan bahwa saya tidak pernah mengkompromikannya dengan cara apa pun.”

TIPS:

Artikel sebelumnya memperkenalkan metode penggunaan CAGradientLayer untuk mengimplementasikan warna gradien. Selain menggunakan CAGradientLayer untuk mengimplementasikan warna gradien, Anda juga dapat menggunakan CGGradientRef dan Core Image. Namun, saat menggunakan CGGradientRef dan Core Image untuk mengimplementasikan warna gradien, Anda perlu memanggilnya dalam metode drawRect:. Ada penjelasan yang sangat bagus tentang penggunaan Core Graphics dan Core Image: http://www.techotopia.com/index.php/An_iOS_7_Graphics_Tutorial_using_Core_Graphics_and_Core_Image            Referensi CGGradient: Kode berikut harus ditulis di 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];

Terlihat cara pelaksanaannya berbeda-beda, namun dampaknya tetap berbeda. Perlu juga disebutkan bahwa UIBezierPath dan CAShapeLayer dapat digabungkan untuk membuat beberapa animasi.

Artikel referensi: 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

Bagikan:

Ada pertanyaan yang tidak pernah saya mengerti. Sebagian besar listrik yang kita gunakan saat ini (70%) berasal dari pembangkit listrik termal. Bahan bakar pembangkit listrik tenaga panas berasal dari minyak bumi dan batu bara. Ada banyak kerugian dalam proses pembangkitan listrik termal.

Misal: 1kg minyak, jika dipakai langsung untuk merebus air, bisa merebus 20kg air. Jika Anda pertama kali menggunakan 1kg minyak untuk menghasilkan listrik dan kemudian menggunakan listrik untuk merebus air, Anda mungkin hanya bisa merebus 10kg air.

Dalam hal ini, mengapa kita menggunakan mobil listrik? Untuk jarak yang sama yakni 1 km, sebenarnya konsumsi bahan bakar kendaraan listrik justru lebih tinggi. Penggunaan kendaraan listrik sebenarnya meningkatkan polusi, namun polusi terjadi di pembangkit listrik dan berpindah.

Lalu mengapa kita menggunakan mobil listrik atau perangkat lain yang menggunakan listrik padahal bisa menggunakan minyak?