ARTS Algorihm iOS

ARTS #019

ARTS #019

Posted by Dan on December 21, 2018

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

ARTS 019

这是第19篇

Algorihm 算法题

804. Unique Morse Code Words

Difficulty Easy

International Morse Code defines a standard encoding where each letter is mapped to a series of dots and dashes, as follows: "a" maps to ".-", "b" maps to "-...", "c" maps to "-.-.", and so on.

For convenience, the full table for the 26 letters of the English alphabet is given below:

[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]

Now, given a list of words, each word can be written as a concatenation of the Morse code of each letter. For example, “cba” can be written as “-.-..–…”, (which is the concatenation “-.-.” + “-…” + “.-“). We’ll call such a concatenation, the transformation of a word.

Return the number of different transformations among all words we have.



Example:
Input: words = ["gin", "zen", "gig", "msg"]
Output: 2
Explanation: 
The transformation of each word is:
"gin" -> "--...-."
"zen" -> "--...-."
"gig" -> "--...--."
"msg" -> "--...--."

There are 2 different transformations, "--...-." and "--...--.".

Note:

  • The length of words will be at most 100.
  • Each words[i] will have length in range [1, 12].
  • words[i] will only consist of lowercase letters.

Solution

Language: C

方法1：就是最容易想到的方法， 直接把单词转换为摩尔玛，然后进行比较，去重

int uniqueMorseRepresentations(char** words, int wordsSize) {
    char *morse[26] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    
    
    //convert words to morse
    char **chatToMorse = (char **)malloc(sizeof(char*) * wordsSize);
    int index = 0;
    while (index < wordsSize) {
        char *word = words[index];
        char *charMorse = NULL;
        for (int j = 0; j <  strlen(word); j++) {
            char charter = word[j];
            char *newmorse = morse[charter - 'a'];
            
            if (charMorse == NULL) {
                char *result = malloc(strlen(newmorse)+1);
                memset(result, '\0', strlen(newmorse)+1);
                strcpy(result, newmorse);
                charMorse = result;
            }
            else{
                char *result = malloc(strlen(charMorse)+strlen(newmorse)+1);//+1 for the zero-terminator
                memset(result, '\0', strlen(charMorse)+strlen(newmorse)+1);
                strcpy(result, charMorse);
                strcat(result, newmorse);
                free(charMorse);
                charMorse = result;
            }
        }
        chatToMorse[index] = charMorse;
        ++index;
    }
    
    int falg = 0;
    for (int m =0; m < wordsSize; m++) {
        char *  ms = chatToMorse[m];
        if(ms == NULL){
            continue;
        }
        for(int n = m+1; n <wordsSize;n++ ){
            char *  ns = chatToMorse[n];
            if (ns != NULL)  {
                int res = strcmp(ms,ns);
                if (res ==0) {
                    chatToMorse[n] = NULL;
                    falg++;
                }
            }
        }
    }
    return wordsSize -falg;
}

方法2：这个方法的思路和我的是一样的但是比我的快，应该是因为他没有动态分配内存。还有一个就是在最后做去重计算的时候和我的不一样。但是这个代码比我的好，因为他对代码中不同的功能进行了方法封装，有面向对象的思想。


char *transMorse(const char alphabet){
    char *morseCode[] = { ".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.." };
    return morseCode[alphabet-'a'];
}

void transMorseString(char *word, char *morseString){
    char *morseTempt;
    while(*word){
        morseTempt = transMorse(*word);
        word++;
        while(*morseTempt){
            *morseString = *morseTempt;
            morseString++;
            morseTempt++;
        }
    }
    return;
}

int uniqueMorseRepresentations(char** words, int wordsSize) {
    char morseString[100][50] = {""};
    
    for(int i = 0 ; i<wordsSize ; ++i){
        transMorseString(words[i], morseString[i]);
    }
    
    //上面的方法h都好理解，就是把字符串转为Morse码
    //下面的这个去重计算 感觉不好理解
    for(int i = 0 ; i<wordsSize ; ++i){
        for(int j = i+1 ; j<wordsSize ; ++j){
            while(wordsSize>1 && j<wordsSize && !strcmp(morseString[i], morseString[j])){
                strcpy(morseString[j], morseString[wordsSize-1]);
                --wordsSize;
            }
        }
    }
    return wordsSize;
}

方法3： 这个方法的优点：

  1. 字符串转摩尔码的时候用了二维方法的时候 比较方便
  2. 去重的时候用到了集合(set)的概念

特别是第2点，集合的思路，这种情况不就是集合的用武之地吗，自己却没想到。


int addToSet(char** set, int setCount, char* buf);

int uniqueMorseRepresentations(char** words, int wordsSize) {
    char* morse[26] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
    char* set[100];
    int setCount = 0;
    //1. 字符串转摩尔码的时候用了二维方法的时候 比较方便
    //2. 去重的时候用到了集合(set)的概念
    int i = 0;
    for(i = 0; i < wordsSize; i++) {
        char* buf = malloc(sizeof(char) * 60);
        buf[0] = '\0';
        int j = 0;
        for(j = 0; j < strlen(words[i]); j++) {
            char* cat = strcat(buf, morse[words[i][j] - 97]);
            
            printf("add: %c %s, all is: %s", words[i][j], morse[words[i][j] - 97], cat);
        }
        setCount = addToSet(set, setCount, buf);
        printf("\n");
    }
    
    for(i = 0; i < setCount; i++) {
        free(set[i]);
    }
    
    return setCount;
}

int addToSet(char** set, int setCount, char* buf) {
    int i = 0;
    for(i = 0; i < setCount; i++) {
        printf("compare: %s %s", set[i], buf);
        if(strcmp(set[i], buf) == 0) {
            return setCount;
        }
    }
    
    set[i] = buf;
    return ++i;
}

方法4： 这个方法的思路也很好，把摩尔玛看做是二进制的0和1，.代表0，1代表- 。具体看代码注释


typedef struct {
    char len;
    char val;
} morseCode;

morseCode codeTable[] = {
    {2, 2}, /* a .-   10*/
    {4, 7}, /* b -... 0111*/
    {4, 5}, /* c -.-. 0101 */
    {3, 3},
    {1, 1},
    {4,13},
    {3, 1},
    {4,15},
    {2, 3},
    {4, 8},
    {3, 2},
    {4,11},
    {2, 0},
    {2, 1},
    {3, 0},
    {4, 9},
    {4, 2},
    {3, 5},
    {3, 7},
    {1, 0},
    {3, 6},
    {4,14},
    {3, 4},
    {4, 6},
    {4, 4},
    {4, 3}
};

typedef struct{
    int len;
    int val;
}morseString;

morseString getmorseString(char* s) {
    morseString str;
    str.len = 0;
    str.val = 0;

    char *p = s;
    while(*p != '\0')
    {
        char c = *p;
        if (c < 'a' || c > 'z'){
            printf("Invalid input *p = %c\n", c);
            p++;
            continue;
        }

        morseCode code = codeTable[c - 'a'];
        str.len += code.len;//记录单词转为摩尔码，也就是二进制之后的位数，当数据很长时有用，如果数据较短，比如没有超过64位或32位。但是超过之后这个就有用了
        str.val = (str.val << (code.len)) + code.val;//把str.val看成二进制数据 就容易理解了
        p++;
    }

    return str;
}

int uniqueMorseRepresentations(char** words, int wordsSize) {
    int result = -1;
    morseString stack[100];

    for(int i = 0; i < wordsSize; i++)
    {
        morseString str = getmorseString(words[i]);
        bool foundone = false;
        for (int j = 0; j <= result; j++)
        {
            // check one by one if str in stack
            // zstack[j].len == str.len 这个判断当摩尔码的二进制长度超过机器的最大字长时才有用。
            // 如果没有超过最大字长，二进制表示相等（stack[j].val == str.val），二进制的长度必然相等
            if (stack[j].len == str.len && stack[j].val == str.val) {
                foundone = true;
                break;
            }
        }

        if (!foundone)
        {
            stack[++result] = str;
        }
    }

    return result + 1;
}

方法5 ： 中规中矩的做法，用到了二维数组，比我的写法简单


int uniqueMorseRepresentations(char** words, int wordsSize) {
    char transBuffer[50] = {0};
    char transCode[100][50] = {0}; //Store the translation code
    char* morseCode[] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}; // 'a' ~ 'z' Morse Code Table
    
    int j, k;
    int existFlag = 0;
    int transCodeNum = 0;               //Different translation code numbers
    for(int i=0; i < wordsSize; i++)
    {
        j = 0;
        k = 0;
        existFlag = 0;                                      //Reset the flag
        memset(transBuffer, 0, sizeof(transBuffer));        //Reset the buffer
        while(words[i][j] != '\0')
        {
            k = words[i][j] - 'a';                          //get the number of letters
            strncat(transBuffer, morseCode[k], sizeof(morseCode[k]));   //translate the letter by morseCode
            j++;
        }
        
        
        for(int z = 0; z < transCodeNum && !existFlag; z++)     //Confirm transCode has already store same code
            if(strncmp(transCode[z], transBuffer, sizeof(transBuffer)) == 0)
                existFlag = 1;
        
        if(!existFlag)                                          //if the code isn't exist, store it
            strncpy(transCode[transCodeNum++], transBuffer, sizeof(transBuffer));
        
    }
    
    return transCodeNum;
}

Review

这篇文章讲的是：如何成为一名更好的软件开发人员 讲了除了开发技能之外的东西： 1 了解整个开发流程。建议开发者不仅仅只关注编码，要熟悉整个开发流程，从模糊的想法到精心设计的解决方案的转换过程，以及软件开发完成之后，进行的测试、部署、监视、分析和改进。这样可以让大家互相理解，减少由于互相不了解其他人的工作而导致的沟通障碍 2 了解客户的需求，要和客户交流，做到互相信任，及时的像客户反馈进度和结果 3 对于不同的工作选择不同的方案或工具，不能把已有的技能和经验用到所有的事情上。 4 站在巨人的肩膀上，要善于利用第三方工具，而不是每次都自己重头开发， 5 学习知识的基本原理，不能盲目追求新知识，要搞清知识背后的原理。

翻译参见： https://dandan2009.github.io/2018/12/18/how-to-become-a-better-software-developer/ 原文参见：https://medium.com/devtrailsio/how-to-become-a-better-software-developer-dd16072c974e

Tips

之前用Instruments来测试APP启动时间是，只能记录某一个方法的执行事件，现在可以使用Signposts 来打点记录APP每行代码的运行时间： 参见WWDC2018 Measuring Performance Using Logging: https://developer.apple.com/videos/play/wwdc2018/405/

这有一个译文你可以看下： https://blog.csdn.net/tugele/article/details/81252603

上面给出的例子是基于swift的，在Objective-C中可以使用C语言版本：

   os_log_t log = os_log_create("com.example.your-app",  "RefreshOperations");
   os_signpost_id_t log_t = os_signpost_id_generate(log);
   
    os_signpost_interval_begin(log, log_t, "Fetch Asset");
    你的代码
    os_signpost_interval_end(log, log_t, "Fetch Asset");
    
    os_signpost_interval_begin(log, log_t, "Fetch Asset1");
    你的代码
    os_signpost_interval_end(log, log_t, "Fetch Asset1");

Share

招聘行情：https://readhub.cn/jobs

谷歌学术、维基百科、谷歌翻译、Gmail网页版、Google 照片、Google 文档、Google Keep、Google 地球、Google 图书、Chrome同步、Pixiv、Steam社区、GitHub Releases、Pinterest、Vimeo、Yandex、Tumbl YouTube、Twitter、Facebook、Google+、Google Play、Google Drive、Blogger、部分新闻网站、Instagram

英文学习：https://learnamericanenglishonline.com/Red%20Level/R1%20Do.html

解密 Runloop: http://mrpeak.cn/blog/ios-runloop/

mac 开源播放器：1.5 万star, IINA is the modern video player for macOS. https://github.com/lhc70000/iina

通过开发的小程序赚钱的例子：https://www.v2ex.com/t/515777

可以访问Google：https://sss.cnsdhh.com/

搜索颜色的网站：https://picular.co/，搜索出来的颜色是一个色系的，不是单一的一种颜色

CATALOG
    FEATURED TAGS
    iOS Runtime Xcode ARTS Algorihm 翻译 方法论 算法 数据结构
    RECOMMEND