ARTES #019
ARTES #019
ARTES es una actividad iniciada por
由左耳朵耗子--陈皓: Haga al menos una pregunta sobre el algoritmo leetcode cada semana, lea y comente al menos un artículo técnico en inglés, aprenda al menos una habilidad técnica y comparta un artículo con opiniones y pensamientos. (Es decir, Algoritmo, Revisión, Sugerencia y Compartir se denominan ARTS) y persisten durante al menos un año.
##ARTES 019 este es el articulo 19
Pregunta sobre el algoritmo del algoritmo
804. Palabras únicas en código Morse
Dificultad Fácil
El código Morse internacional define una codificación estándar en la que cada letra se asigna a una serie de puntos y guiones, de la siguiente manera: "a" se asigna a ".-", "b" se asigna a "-...", "c" se asigna a "-.-.", etc.
Para mayor comodidad, a continuación se muestra la tabla completa de las 26 letras del alfabeto inglés:
[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
Ahora, dada una lista de palabras, cada palabra se puede escribir como una concatenación del código Morse de cada letra. Por ejemplo, “cba” se puede escribir como “-.-…–…”, (que es la concatenación “-.-.” + “-…” + “.-”). A esta concatenación la llamaremos transformación de una palabra.
Devuelve el número de transformaciones diferentes entre todas las palabras que tenemos.
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 "--...--.".
Nota:
- La extensión de las palabras será como máximo 100.
- Cada palabra [i] tendrá una longitud en el rango [1, 12].
- las palabras [i] solo estarán compuestas por letras minúsculas.
Solución
Idioma: C
Método 1: este es el método más fácil de imaginar: convertir directamente las palabras a Morma, luego comparar y eliminar duplicaciones.
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;
}
Método 2: La idea de este método es la misma que la mía pero más rápida que la mía. Debería ser porque no asigna memoria dinámicamente. Otra cosa es que el cálculo final de deduplicación es diferente al mío. Pero este código es mejor que el mío porque encapsula diferentes funciones en el código y tiene un pensamiento orientado a objetos.
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;
}
Método 3: Ventajas de este método:
- Es más conveniente utilizar el método bidimensional al convertir una cadena a código moral.
- El concepto de conjunto se utiliza al eliminar duplicados.
Especialmente el punto 2, la idea de reunirse, no es esta situación en la que reunirse resulta útil, pero no lo esperaba.
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;
}
Método 4: La idea de este método también es muy buena. Piense en Morma como 0 y 1 binarios. representa 0 y 1 representa -. Ver comentarios de código para más detalles.
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;
}
Método 5: un método más satisfactorio, que utiliza una matriz bidimensional, que es más simple que mi método de escritura.
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;
}
Revisión
Este artículo trata sobre: Cómo convertirse en un mejor desarrollador de software Hablando de otras cosas además de las habilidades de desarrollo: 1 Comprender todo el proceso de desarrollo. Se recomienda que los desarrolladores no solo se concentren en la codificación, sino que también estén familiarizados con todo el proceso de desarrollo, el proceso de conversión de ideas vagas a soluciones cuidadosamente diseñadas y las pruebas, implementación, monitoreo, análisis y mejora una vez completado el desarrollo del software. Esto permite que todos se entiendan y reduzca las barreras de comunicación causadas por la comprensión mutua del trabajo de otras personas. 2 Comprender las necesidades de los clientes, comunicarse con los clientes, lograr confianza mutua y brindar retroalimentación oportuna sobre el progreso y los resultados a los clientes. 3 Elija diferentes soluciones o herramientas para diferentes trabajos y no pueda utilizar las habilidades y la experiencia existentes para todo. 4. Párese sobre los hombros de gigantes y sea bueno en el uso de herramientas de terceros en lugar de desarrollarlas desde cero cada vez. 5. Para aprender los principios básicos del conocimiento, no se puede buscar ciegamente nuevos conocimientos. Debe comprender los principios detrás del conocimiento.
Para traducción ver: https://dandan2009.github.io/2018/12/18/how-to-become-a-better-software-developer/ Ver el texto original: https://medium.com/devtrailsio/how-to-become-a-better-software-developer-dd16072c974e
Consejos
Anteriormente, se utilizaba Instruments para probar el tiempo de inicio de la aplicación. Solo podía registrar los eventos de ejecución de un determinado método. Ahora puedes usar Signposts para registrar el tiempo de ejecución de cada línea del código de la aplicación: Ver WWDC2018 Medición del rendimiento mediante el registro: https://developer.apple.com/videos/play/wwdc2018/405/
Aquí tenéis una traducción que podéis leer: https://blog.csdn.net/tugele/article/details/81252603
El ejemplo anterior se basa en Swift y la versión en lenguaje C se puede utilizar en 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");
Compartir
Cotización de reclutamiento: https://readhub.cn/jobs
Google Scholar, Wikipedia, Google Translate, Gmail web, Google Fotos, Google Docs, Google Keep, Google Earth, Google Books, Chrome Sync, Pixiv, Steam Community, Lanzamientos de GitHub, Pinterest, Vimeo, Yandex, Tumbl YouTube, Twitter, Facebook, Google+, Google Play, Google Drive, Blogger, algunos sitios web de noticias, Instagram
Aprendizaje de inglés: https://learnamericanenglishonline.com/Red Level/R1 Do.html
Descifrar bucle de ejecución: http://mrpeak.cn/blog/ios-runloop/
Reproductor de código abierto para Mac: 15.000 estrellas, IINA es el reproductor de vídeo moderno para macOS. https://github.com/lhc70000/iina
Ejemplo de ganar dinero a través de pequeños programas desarrollados: https://www.v2ex.com/t/515777
Puede acceder a Google: https://sss.cnsdhh.com/
Sitio web para buscar colores: https://picular.co/，搜索出来的颜色是一个色系的，不是单一的一种颜色
What to read next
Want more posts about ARTS?
Posts in the same category are usually the best next step for reading more on this topic.
View same categoryWant to keep following #iOS?
Tags are useful for related tools, specific problems, and similar troubleshooting notes.
View same tagWant to explore another direction?
If you are not sure what to read next, return to the homepage and start from categories, topics, or latest updates.
Back home