ARTS #022

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 022

This is article 22

Algorihm algorithm question

648. Replace Words

Difficulty Medium

In English, we have a concept called root, which can be followed by some other words to form another longer word - let’s call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Note:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Solution

Language: C

/**判断str1是否以str2开头
 * 如果是返回1
 * 不是返回0
 * 出错返回-1
 * */
int is_begin_with(const char * str1,char *str2){
    if(str1 == NULL || str2 == NULL)
        return -1;
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    if((len1 < len2) ||  (len1 == 0 || len2 == 0))
        return -1;
    char *p = str2;
    int i = 0;
    while(*p != '\0')
    {
        if(*p != str1[i])
            return 0;
        p++;
        i++;
    }
    return 1;
}

/*方法，调用C库函数,*/
char* join(char *s1, char *s2){
    char *result = malloc(strlen(s1)+strlen(s2)+1);//+1 for the zero-terminator
    if (result == NULL)
        return NULL;
    
    strcpy(result, s1);
    strcat(result, s2);
    
    return result;
}

char* replaceWords(char** dict, int dictSize, char* sentence) {
    int i = 0;
    //先处理dict，把dict中词根 处理为最短词根
    while (i < dictSize) {
        char* str2 = dict[i];
        if (str2 == NULL) {
            i++;
            continue;
        }
        
        int j = i+1;
        while (j < dictSize) {
            char* str1 = dict[j];
            if (str1 == NULL) {
                j++;
                continue;
            }
            
            if (strcmp(str1, str2) == 0) {
                dict[j] = NULL;
                j++;
                continue;
            }
            
            if (is_begin_with(str1,str2)==1) {
                dict[j] = NULL;
                j++;

            }
            j++;
        }
        i++;
    }
    

    //分割字符串进行替换
    char * re = "";
    char * pch = strtok(sentence, " ");
    while (pch != NULL){
        if (strlen(re) > 0){
             re = join(re," ");
        };
        
        
        int j=0;
        while (j < dictSize) {
            char* str1 = dict[j];
            if (str1 == NULL) {
                j++;
                continue;
            }

            if ((strcmp(pch, str1) != 0) && (is_begin_with(pch,str1)==1)) {
                pch = str1;
                break;
            }
            j++;
        }
        re = join(re,pch);
        pch = strtok(NULL, " ");
        
    }
    return re;
}

Review

https://dandan2009.github.io/2018/12/28/exposing-NSDictionary/

TIPS

Two controls were open sourced this week: Highly customized circular scrolling Banner: https://github.com/dandan2009/DDCircleScrollViewBanner Pop-up window control, supports text, pictures, graphics, and custom view pop-ups: https://github.com/dandan2009/DDPopUpView

Share

Today I asked an interviewer a question: Why does AF2.x need resident threads?

That is what this code does:

+ (void)networkRequestThreadEntryPoint:(id)__unused object {
     @autoreleasepool {
          [[NSThread currentThread] setName:@"AFNetworking"];

          NSRunLoop *runLoop = [NSRunLoop currentRunLoop];
          [runLoop addPort:[NSMachPort port] forMode:NSDefaultRunLoopMode];
          [runLoop run];
     }
}

+ (NSThread *)networkRequestThread {
     static NSThread *_networkRequestThread = nil;
     static dispatch_once_t oncePredicate;
     dispatch_once(&oncePredicate, ^{
          _networkRequestThread =
          [[NSThread alloc] initWithTarget:self
               selector:@selector(networkRequestThreadEntryPoint:)
               object:nil];
          [_networkRequestThread start];
     });

     return _networkRequestThread;
}

As a result, several interviewees gave incorrect answers, and many answers on the Internet were also incorrect. Here is a summary:

AF2.x uses NSURLConnection to initiate network requests. NSURLConnection is designed to be sent asynchronously. After calling the start method, NSURLConnection will create some new threads and use the underlying CFSocket to send and receive requests. After some events are sent and received, the Runloop of the original thread is notified to call back the event. But the original thread may have been released.

In order to ensure that the original thread is not released and to ensure normal reception of the NSURLConnectionDelegate callback method, it is necessary to open a thread for each request and keep the thread alive. There are too many threads to keep alive, and the overhead is too high. So you only need to keep a fixed thread alive, initiate requests and receive callbacks in this thread.