ARTS #027

ARTS 027

这是第27篇

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

Algorihm 算法题

温故而知新，决定把做过的题按顺序再做一遍。这道题虽然简单，但是要想把时间和内存都做到最优还是比较难的。

这道题的最笨的解法就暴力法，估计这个大家都能想到，LeetCode上竟然也能通过。

稍微好一点的能想到先排序，然后用二分查找，但是注意这里有个问题，就是如果直接对原数组进行排序，那么元素的位置信息就会发生变化，但是题目要求返回位置信息。为了解决这个问题，首先能想到的就是把原数组备份一份，然后找到值后再找对应的下标，但是这样的话和暴力解法几乎差不多。

再优一点的做法是构造数据结构，比如结构体，记录值和对应的位置，然后进行排序，这样就解决了找到值后再找对应的下标的问题。

1. 两数之和

Difficulty: 简单

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Solution

Language: C

#include <stdio.h>
#include <stdlib.h>

struct object {
    int val;
    int index;
};

static int compare(const void *a, const void *b)
{
    return ((struct object *) a)->val - ((struct object *) b)->val;
}

static int * twoSum(int *nums, int numsSize, int target)
{
    int i, j;
    struct object *objs = malloc(numsSize * sizeof(*objs));
    for (i = 0; i < numsSize; i++) {
        objs[i].val = nums[i];
        objs[i].index = i;
    }
    qsort(objs, numsSize, sizeof(*objs), compare);
    
    int count = 0;
    int *results = malloc(2 * sizeof(int));
    i = 0;
    j = numsSize - 1;
    while (i < j) {
        int diff = target - objs[i].val;
        if (diff > objs[j].val) {
            while (++i < j && objs[i].val == objs[i - 1].val) {}
        } else if (diff < objs[j].val) {
            while (--j > i && objs[j].val == objs[j + 1].val) {}
        } else {
            results[0] = objs[i].index;
            results[1] = objs[j].index;
            return results;
        }
    }
    return NULL;
}

下面这个是4ms的解法

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int *res = calloc(2, sizeof(int));
    struct hash {
        int id;
        int pair;
        UT_hash_handle hh;
    } *hashTable = NULL;
    
    for (int i = 0; i < numsSize; i++) {
        struct hash *h;
        HASH_FIND_INT(hashTable, nums + i, h);
        if (h == NULL) {
            h = calloc(1, sizeof(struct hash));
            h->id = target - nums[i];
            h->pair = i;
            HASH_ADD_INT(hashTable, id, h);
        } else {
            res[0] = h->pair;
            res[1] = i;
            return res;
        }
    }
    
    return res;
​
}

8ms的解法：

void swap(int *a, int *b)
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

void heapify(int *arr, int n, int i)
{
    int largest = i; // Initialize largest as root
    int l = (i << 1) + 1; // left = 2*i + 1
    int r = (i << 1) + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // If largest is not root
    if (largest != i) {
        swap(&arr[i], &arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

void heap_sort(int *arr, int len)
{
    int i;
    for (i = len >> 1; i >= 0; --i)
        heapify(arr, len, i);
    for(i = len - 1; i > 0; --i) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

int* twoSum(int* nums, int numsSize, int target) {
    if (!nums || numsSize < 2)
        return NULL;

    if (numsSize > 50) {
        int i, j, sum;
        int *sort = malloc(sizeof(int) * numsSize);
        memcpy(sort, nums, sizeof(int) * numsSize);
        heap_sort(sort, numsSize);
        for (i = 0, j = numsSize - 1; i < j;) {
            sum = sort[i] + sort[j];
            if (sum == target) {
                int k;
                int *res = malloc(sizeof(int) << 1);
                for (k = 0; k < numsSize; k++) {
                    if (nums[k] == sort[i])
                        res[0] = k;
                }
                for (k = 0; k < numsSize; k++) {
                    if (nums[k] == sort[j])
                        res[1] = k;
                }
                free(sort);
                return res;
            } else if (sum < target)
                i++;
            else
                j--;
        }
    } else if (numsSize > 10) {
        int i, j, k, c, l;
        bool back;

        for (i = 0, j = numsSize - 1, back = false; i < j; back = !back) {
            if (back)
                l = j--;
            else
                l = i++;
            c = target - nums[l];
            for (k = i; k <= j; k++) {
                if (nums[k] == c) {
                    int *res = malloc(sizeof(int) << 1);
                    res[0] = l;
                    res[1] = k;
                    return res;
                }
            }
        }
    } else {
        int i, j, c;

        for (i = 0; i < numsSize - 1; i++) {
            c = target - nums[i];
            for (j = i + 1; j < numsSize; j++) {
                if (nums[j] == c) {
                    int *res = malloc(sizeof(int) << 1);
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
    }

    return NULL;
}

虽然题目简单，但是通过学习别人的解法还是能学到新的知识。

Review

这篇文章讲了进程和线程，主要是讲了线程，线程安全的知识。 https://dandan2009.github.io/2019/03/18/a-gentle-introduction-to-multithreading/

Tips

随着iOS设备的碎片化，iOS的适配也越来越麻烦了。我们的视图大小是根据设备等比放大的，比如label在6s上是18的高度，在6p上就是18 * (540/375)，就是25.94，注意这里出现了小数，这时有的视图就会莫名的多出一条细线，比如笔者遇到的UIlabel在iPhone xr上，顶部会多出一条线，而且只有iPhone xr出现，解决办法也很简单，就是转为整数；所以和视图位置相关的值在转换的过程中最好都转为整数。

每天都感觉自己好忙，但是也不知道在忙什么，回顾一周，感觉自己进步太少，以后决定采用目标值，就是提前一天规划第二天要完成的工作。以此来提高工作、学习效率。