ARTS #027

ARTS 027

This is article 27

ARTS is an activity initiated by 由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.

Algorihm algorithm question

Reviewing the past and learning something new, I decided to do the questions I had done again in order. Although this question is simple, it is still difficult to optimize both time and memory.

The stupidest solution to this question is the brute force method. I guess everyone can think of this, and it can be passed on LeetCode.

A slightly better idea is to sort first and then use binary search, but note that there is a problem here, that is, if the original array is sorted directly, the position information of the elements will change, but the question requires that the position information be returned. In order to solve this problem, the first thing that can be thought of is to make a backup copy of the original array, and then find the value and then find the corresponding subscript, but this is almost the same as a brute force solution.

A better approach is to construct a data structure, such as a structure, record the values ​​and corresponding positions, and then sort them. This solves the problem of finding the corresponding subscript after finding the value.

1. Sum of two numbers

Difficulty: Easy

Given an integer array nums and a target value target, please find the two integers in the array whose sum is the target value, and return their array subscripts.

You can assume that each input will correspond to only one answer. However, you cannot reuse the same elements in this array.

Example:

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

The following is the solution for 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 solution:

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

Although the questions are simple, you can still learn new knowledge by studying other people’s solutions.

Review

This article talks about processes and threads, mainly about threads and thread safety. https://dandan2009.github.io/2019/03/18/a-gentle-introduction-to-multithreading/

Tips

With the fragmentation of iOS devices, iOS adaptation is becoming more and more troublesome. Our view size is enlarged according to the proportion of the device. For example, the height of the label on the 6s is 18, and on the 6p it is 18 * (540/375), which is 25.94. Note that there are decimals here. At this time, some views will have an extra thin line inexplicably. For example, the UIlabel I encountered on the iPhone xr will have an extra line at the top, and it is only iPhone When xr appears, the solution is very simple, which is to convert it to an integer; so the values related to the view position are best converted to integers during the conversion process.

Share

I feel very busy every day, but I don’t know what I am busy with. Looking back on the week, I feel that I have made too little progress. In the future, I decided to adopt a target value, which is to plan the work to be completed the next day one day in advance. This will improve work and study efficiency.