ARTS #019
ARTS #019
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 019
This is article 19
Algorihm algorithm question
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
Method 1: This is the easiest method to think of, directly convert the words into Morma, then compare and remove duplications
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;
}
Method 2: The idea of this method is the same as mine but faster than mine. It should be because it does not allocate memory dynamically. Another thing is that the final deduplication calculation is different from mine. But this code is better than mine because it encapsulates different functions in the code and has object-oriented thinking.
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;
}
Method 3: Advantages of this method:
- It is more convenient to use the two-dimensional method when converting a string to Morale code.
- The concept of set is used when removing duplicates
Especially point 2, the idea of gathering, isn’t this situation where gathering comes in handy, but I didn’t expect it.
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;
}
Method 4: The idea of this method is also very good. Think of Morma as binary 0 and 1, . represents 0, and 1 represents -. See code comments for details
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;
}
Method 5: A more satisfactory method, using a two-dimensional array, which is simpler than my writing method.
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
This article is about: How to become a better software developer Talking about things other than development skills: 1 Understand the entire development process. It is recommended that developers not only focus on coding, but also be familiar with the entire development process, the conversion process from vague ideas to carefully designed solutions, and the testing, deployment, monitoring, analysis, and improvement after software development is completed. This allows everyone to understand each other and reduce communication barriers caused by mutual understanding of other people’s work. 2 Understand the needs of customers, communicate with customers, achieve mutual trust, and provide timely feedback on progress and results to customers. 3 Choose different solutions or tools for different jobs, and cannot use existing skills and experience for everything. 4. Stand on the shoulders of giants and be good at using third-party tools instead of developing it from scratch every time. 5. To learn the basic principles of knowledge, you cannot blindly pursue new knowledge. You must understand the principles behind the knowledge.
For translation see: https://dandan2009.github.io/2018/12/18/how-to-become-a-better-software-developer/ See the original text: https://medium.com/devtrailsio/how-to-become-a-better-software-developer-dd16072c974e
Tips
Previously, Instruments was used to test the APP startup time. It could only record the execution events of a certain method. Now you can use Signposts to record the running time of each line of APP code: See WWDC2018 Measuring Performance Using Logging: https://developer.apple.com/videos/play/wwdc2018/405/
Here is a translation you can read: https://blog.csdn.net/tugele/article/details/81252603
The example given above is based on swift, and the C language version can be used in Objective-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
Recruitment Quotation: https://readhub.cn/jobs
Google Scholar, Wikipedia, Google Translate, Gmail web, Google Photos, Google Docs, Google Keep, Google Earth, Google Books, Chrome Sync, Pixiv, Steam Community, GitHub Releases, Pinterest, Vimeo, Yandex, Tumbl YouTube, Twitter, Facebook, Google+, Google Play, Google Drive, Blogger, some news websites, Instagram
English learning: https://learnamericanenglishonline.com/Red Level/R1 Do.html
Decrypt Runloop: http://mrpeak.cn/blog/ios-runloop/
mac open source player: 15,000 stars, IINA is the modern video player for macOS. https://github.com/lhc70000/iina
Example of making money through small programs developed: https://www.v2ex.com/t/515777
Can access Google: https://sss.cnsdhh.com/
Website to search for colors: https://picular.co/，搜索出来的颜色是一个色系的，不是单一的一种颜色
读完之后，下一步看什么
如果还想继续了解，可以从下面几个方向接着读。