ARTS #009

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.

ARTS 009

This is article 9

Algorihm algorithm question

leetcode algorithm question 338. Counting Bits: Difficulty: Moderate

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example 1:

Input: 2
Output: [0,1,1]
Example 2:

Input: 5
Output: [0,1,1,2,1,2]
Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Problem solving process:

0	1	2	3	4	5	6	7	8	9	10	11	12	13
1	1	1	2	1	2	2	3	1	2	2	3	2	3

If i happens to be 2 raised to the nth power, then the binary representation of i has only one 1. If i is not exactly 2 raised to the nth power, how should we calculate it? It can be split into 2^n + m, 2^n < i and 2^n+1 > i. For example, 13 can be split into 2^3 + 5. The number of 1s contained in the binary data of 13 is equal to the number of 1s contained in the binary data of 1 plus 5. It can be seen that we can use the known data to find the unknown data. The key to the implementation here is how to find n, which is the logarithmic operation with base 2. The implementation is as follows, the running time is 20ms:

int* countBits(int num, int* returnSize) {
    int* nums = (int*)malloc(sizeof(int) * (num + 1));
    nums[0]  = 0;
    if (num >0) {
        nums[1]  = 1;
        for (int i = 2; i <=num; i++) {
            double log2Dou = log2((double)i);
            int log2int = log2Dou;
            int  remainder = i - pow(2, log2int);
            nums[i] = nums[remainder] + 1;
        }
    }
    *returnSize = num+1;
    return nums;
}

I saw a short implementation, as follows, the running time is 16ms

int* countBits(int num, int* returnSize) 
{
    int* dp = (int*)malloc(sizeof(int) * (num + 1));
    for (dp[0] = 0, *returnSize = 1; *returnSize <= num; ++*returnSize)
        dp[*returnSize] = dp[*returnSize >> 1] + (*returnSize & 1);
    return dp;
}

Let’s analyze this implementation: The key to this algorithm is to understand dp[*returnSize] = dp[*returnSize >> 1] + (*returnSize & 1); It is easier to understand if *returnSize is written in binary. Assume *returnSiz is equal to 13, The binary representation of 13 is: 0000 1101, 0000 1101 >> 1, followed by 0000 0110, the last bit is removed, and the high bit is filled with 0; If the last digit is 0, such as 12, then the number of 1s contained in 0000 1100 is the same as the number of 1s contained in the right-shifted number 0000 0110. If the last digit is 1, such as 13, then the number of 1s contained in 0000 1101 is 1 more than the number of 1s contained in the number 0000 0110 after the right shift. The number of binary numbers containing 1 after right shift has been calculated previously.

Whether it is equal or 1 more than after right shift can be obtained by bitwise AND (*returnSize & 1), or *returnSize % 2 can also be used.

Let’s look at another algorithm:

int* countBits(int num, int* returnSize) {
    int *dp, i, nearest;

    dp = (int *)malloc(sizeof(int) * (num + 1));
    *returnSize = num + 1;
    if (dp == NULL)
        return NULL;

    dp[0] = 0;

    if (num >= 1)
        dp[1] = 1;

    i = nearest = 2;

    while (i <= num)
    {
        nearest = (i & (i - 1)) == 0 ? i : nearest;
        dp[i] = 1 + dp[i - nearest];
        i++;
    }

    return dp;
}

The key to this algorithm is

    while (i <= num)
    {
        nearest = (i & (i - 1)) == 0 ? i : nearest;
        dp[i] = 1 + dp[i - nearest];
        i++;
    }

After understanding nearest = (i & (i - 1)) == 0 ? i : nearest;, you also understand this algorithm. When i is worth something, (i & (i - 1)) == 0 will be true. It will only be true when i is exactly 2^n. Therefore, the idea of ​​this algorithm is the same as my implementation, but it is more clever in finding n and is worth learning.

There is also the following algorithm, which is also more clever when finding n. Sign is 2^n:

int* countBits(int num, int* returnSize) { 20
    int* nums=(int *)calloc(num+1,sizeof(int));

    for(int i=1,sign=1;i<=num;i++){
        if(i>1&&i%sign==0){
            sign*=2;
        }
        int n=i%sign;
        nums[i]=nums[n]+1;
    }

    *returnSize=num+1;
    return nums;
}

Let’s analyze another algorithm:

int* countBits(int num, int* returnSize) { //28
    int bit = 1;
    *returnSize = num+1;
    int *table = (int *) malloc((*returnSize)*sizeof(int));
    memset(table, 0, (*returnSize)*sizeof(int));
    


    for (int i = 1; i <= num; i++)
    {
        if ((1 << (bit-1)) == i)
        {
            table[i] = 1;
            bit++;
        }

        else
            table[i] = 1 + table[i & ~(1 << (bit-2))];
    }
    return table;
}

The implementation idea of this algorithm is also divided into 2^n + m. If is equivalent to looking for n, else looking for m. table[i] = 1 + table[i & ~(1 << (bit-2))];, the 1 on the left side of the plus sign is the highest 1, which is 2^n. i & ~(1 << (bit-2)) in table[i & ~(1 << (bit-2))]; is m, which is equivalent to i - 2^n.

Many other people’s implementations have been analyzed above, and you can see that they are basically techniques for operating binary data.

Review

This article comes from: https://blog.google/technology/developers/pushing-limits-streaming-technology/ Pushing the limits of streaming technology Challenging the limits of streaming technology

Streaming media has transformed the way we consume music and video, making it easy to instantly access your favorite content. It’s a technically complex process that has come a long way in a few short years, but the next technical frontier for streaming will be much more demanding than video. Streaming has changed the way we consume music and videos, making it easy to get your favorite content instantly. It’s a technically complex process that has come a long way in just a few years, but the next technological frontier in streaming will be even more demanding than video.

We’ve been working on Project Stream, a technical test to solve some of the biggest challenges of streaming. For this test, we’re going to push the limits with one of the most demanding applications for streaming—a blockbuster video game. We have been working on Project Stream, which is a technology test that solves the biggest challenges of streaming media. For this test, we’re going to push the envelope with one of the most demanding streaming apps out there - a blockbuster video game.

We’ve partnered with one of the most innovative and successful video game publishers, Ubisoft, to stream their soon-to-be released Assassin’s Creed Odyssey® to your Chrome browser on a laptop or desktop. Starting on October 5, a limited number of participants will get to play the latest in this best-selling franchise at no charge for the duration of the Project Stream test. We’re working with one of the most innovative and successful video game publishers, Ubisoft, to stream their upcoming release of Assassin’s Creed Odyssey® in Chrome for laptop or desktop. Starting on October 5, a limited number of participants will be able to play the latest game in the best-selling series for free during the project beta period. We’ve partnered with Ubisoft, one of the most innovative and successful video game publishers, to bring the upcoming Assassin’s Creed Odyssey® to the Chrome browser on your laptop or desktop. Starting October 5, a limited number of participants will play the best-selling franchise for free during the project stream beta.

The idea of streaming such graphically-rich content that requires near-instant interaction between the game controller and the graphics on the screen poses a number of challenges. When streaming TV or movies, consumers are comfortable with a few seconds of buffering at the start, but streaming high-quality games requires latency measured in milliseconds, with no graphic degradation. The idea of streaming such graphically rich content, requiring near-instant interaction between a game controller and on-screen graphics, presents a number of challenges. Consumers are fine with a few seconds of buffering when streaming TV or movies, but streaming high-quality games requires latency measured in milliseconds without a drop in image quality.

The technology and creativity behind these AAA video games is extraordinary—from incredible detail and life-like movement of the characters’ skin, clothing, and hair, to the massive scale of the world in which the game unfolds, down to every last blade of grass. Every pixel is powered by an array of real-time rendering technology, artistry, visual effects, animation, simulation, physics and dynamics. We’re inspired by the game creators who spend years crafting these amazing worlds, adventures and experiences, and we’re building technology that we hope will support and empower that creativity. The technology and creativity behind these AAA video games are phenomenal - from the incredible detail and lifelike movement of character skins, clothes and hair, to the sheer scale of the worlds in which the games unfold, down to every blade of grass. Every pixel is powered by an array of real-time rendering technologies, artistry, visual effects, animation, simulation, physics and dynamics. We’re inspired by the game developers who have spent years creating these amazing worlds, adventures, and experiences, and we’re developing technology that we hope will support and empower that creativity.There are limited spaces available for Project Stream, but if you’re interested in participating, you can apply on our website. Project Stream is geared toward home internet connections capable of 25 megabits per second, and you must be 17 years or older and live in the U.S. to participate (other requirements can be found on the help center).

Space available on Project Stream is limited, but if you are interested in participating you can apply on our website. Project Stream works on a 25 megabit per second home internet connection, and you must be 17 or older and reside in the United States to participate (additional requirements can be found in the Help Center).

We’re looking forward to what the future of streaming holds, and feedback from those participating in Project Stream. Thank you for helping us bring streaming to the next level. We look forward to the future of streaming and the feedback from those involved with Project Stream. Thank you for helping us take streaming to the next level.

<iframe width=“560” height=“315” src=“https://www.youtube.com/embed/sE53eSbzxoU” frameborder=“1” allow=“autoplay; encrypted-media” allowfullscreen></iframe>

Ubisoft and Assassin’s Creed Odyssey are trademarks of Ubisoft Entertainment in the U.S. and/or other countries.

POSTED IN: DEVELOPERS

TIPS:

How to implement linear animation like the following

It can be implemented with CAShapeLayer + UIBezierPath. The difficulty here is how to determine the CGPath. It is simple and can be adjusted slowly by yourself. For complex animations, the code can be automatically generated.

The general idea is as follows 1 Let the designer export the graphics drawn by Sketch in SVG format 2 Drag the SVG file to PaintCode, and the PaintCode software will automatically generate the OC path code. 3 With this path code, we can draw this graphic 4 Then use CABasicAnimation to add animation

Share:

Recently I was reading In-depth Understanding of Computer Systems, Third Edition, and I just read the first chapter. The first chapter talks a lot about the C language. It can be seen that the author of the book is really attentive. Each knowledge point will have corresponding exercises to help you understand the corresponding knowledge point. However, the density of knowledge is really high, so you can only take your time.

As an iOS developer, why do you need to read and understand the computer system in depth? In fact, a lot of iOS development work involves drawing UI and writing business. Commonly used methods are all packaged by Apple, but when you want to deeply optimize your APP, you will find that basic computer knowledge must be mastered, such as how to obtain crash information, how to speed up APP startup, and how to implement a logging system. All these require a solid computer foundation to do.