ARTES #003

ARTS16 de agosto de 2018 às 04:555 min read

ARTES #003

简体中文 العربية English Español Bahasa Indonesia Português

ARTS é uma atividade iniciada por 由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS) e persistem por pelo menos um ano.

ARTES 003

Este é o terceiro artigo e está relativamente mal escrito. Espero que fique cada vez melhor no futuro.

Pergunta sobre algoritmo de algoritmo

Pergunta do algoritmo leetcode 151 Palavras reversas em uma string (palavras invertidas em uma string) Poderia ser: Moderado

Given an input string, reverse the string word by word.

Example:  

Input: "the sky is blue",
Output: "blue is sky the".
Note:

A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.
Follow up: For C programmers, try to solve it in-place in O(1) space.

给定一个字符串，逐个翻转字符串中的每个单词。

示例:  

输入: "the sky is blue",
输出: "blue is sky the".
说明:

无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
进阶: 请选用C语言的用户尝试使用 O(1) 时间复杂度的原地解法。

Se você não considerar o problema do espaço, esse algoritmo é relativamente simples. Inverta a string inteira e depois inverta cada palavra. A dificuldade desta questão é como remover espaços em excesso, incluindo espaços no início, espaços no final e espaços em excesso entre palavras. A implementação é a seguinte:

void ReverseString(char* str,int min,int max) {
    int i = min;
    int j = max;
    while (i < j) {
        char temp = * (str + i);
        * (str + i) = * (str + j);
        * (str + j)  = temp;
        i++;
        j--;
    }
}

//翻转字符串
void reverseWords(char *fdg) {
    RemoveEmptyChar(fdg);
    ReverseString(fdg,0,strlen(fdg) -1);
    int i = 0;
    int j = 0;
    while (*(fdg + j)) {
        if (*(fdg + j) == ' ') {
            ReverseString(fdg,i,j-1);
            i=j+1;
        }
        j++;
        
    }
    ReverseString(fdg,i,j-1);
}

//去掉空格
void RemoveEmptyChar(char* str) {
     //先去掉尾部的空格
    int j  = strlen(str) -1;
    while (*(str + j) == ' ') {
        *(str + j) = '\0';
        j--;
    }
    
    //去掉头部的空格
    int i = 0;
    while (*(str + i) == ' ') {
        i++;
    }
    if(i > 0){
        int count = 0;
        while ((count < strlen(str) - i) && *(str +i + count)) {
            *(str + count) = *(str +i + count);
            count++;
        }
        *(str + count) = '\0';
    }
    
    //去掉中间的空格
    int m  = 0;
    int flag = 0;
    while (m < strlen(str)) {
        if (*(str + m) == ' '){
            flag++;
            m++;
            continue;
        }
        if (flag > 1) {
            int count = 0;
            while ((count < strlen(str) -m)) {
                *(str + m - flag + 1 + count) = *(str + m + count);
                count++;
            }
            *(str + m - flag + 1 + count) = '\0';
            m = m - flag ;
        }
        flag = 0;
        m++;
    }
}

Este algoritmo tem um problema no leetcode, que é o tempo limite. Como você pode ver acima, não há espaço para otimização no método de inversão de strings. O tempo limite deve ser causado pelo método de remoção de espaços. A implementação do método de remoção de espaços é que, se forem encontrados espaços extras, a string após os espaços será movida para frente. Na pior das hipóteses, o número de movimentos de caracteres deve ser aproximadamente: o segundo caractere é movido uma vez, o terceiro caractere é movido duas vezes e o enésimo caractere é movido n-1 vezes, a complexidade do tempo é O(n<sup>2</sup>). Na verdade, não há necessidade de se mover tantas vezes. Um personagem só precisa ser movido uma vez. O método aprimorado de remoção de espaços é o seguinte:

void RemoveEmptyChar1(char* str) {
    char * i = str;
    char * j = str;
    while (*i  && (*i == ' ')) {
        if (i == str) {
            j = i;
            while (*j && (*j == ' ')) {
                j++;
            }
            
            if (!*j) {//说明全是空格
                i = j;
            }
            
            while (*j && (*j != ' ')) {
                *i = *j;
                *j = ' ';
                i++;
                j++;
            }

        }
        else{
            if (*(i+1) == ' ') {
                j = i+ 1;
                while (*j && (*j == ' ')) {
                    j++;
                }
                i++;
                
                while (*j && (*j != ' ')) {
                    *i = *j;
                    *j = ' ';
                    i++;
                    j++;
                }
            }
            else{
                i++;
            }
        }
    }
    
    //先去掉尾部的空格
    int m  = strlen(str) -1;
    while (*(str + m) == ' ') {
        *(str + m) = '\0';
        m--;
    }
}

Após a melhoria, o tempo de execução do leetcode é de 4ms, e a melhor resposta enviada no leetcode é de 0ms. Dei uma olhada e descobri que o método de virar a corda é igual ao meu. A diferença é o método de remoção de espaços. O método de remoção de espaços em 0ms é o seguinte:

void updateString(char *s) {
    int i = 0;
    int end = 0;
    int index = 0;
    bool flag = false;
    while (s[i] == ' ') {
        i++;
    }
    while (s[i] != '\0') {
        if (s[i] == ' ') {
            flag = true;
        } else {
            if (flag) {
                index = end + 1;
                end = index + 1;
                flag = false;
            } else {
                index = end;
                end++;
            }
            if (i > index) {
                s[index] = s[i];
                s[i] = ' ';
            }
        }
        i++;
    }
    s[end] = '\0';
}

Pode-se observar que não há aninhamento de loop em sua implementação, o que significa que ele usou apenas um loop para fazer isso. Quando ele implementou, ele moveu no máximo um personagem por vez. Quanto à minha implementação acima, em um loop, se precisar ser movido, pelo menos uma palavra será movida, todas com loops aninhados.

Revisão

O seguinte artigo vem de: https://littlebitesofcocoa.com/251-face-aware-image-views-with-aspectfillfaceaware;. Ele fala sobre o uso de AspectFillfaceaware para perceber que ao definir uma imagem para imageView, se a imagem contiver um rosto, o rosto poderá ser exibido automaticamente no centro.

Visualizações de imagens com reconhecimento de rosto com AspectFillFaceAware (use AspectFillFaceAware para permitir que o imageView reconheça rostos)

Ao usar UIImageViews, às vezes os modos de conteúdo integrados podem prejudicar nosso estilo.

Ao usar UIImageViews, às vezes o modo de conteúdo integrado destrói nosso estilo e não consegue atender às nossas necessidades.

Muitas vezes, exibimos fotos de pessoas. Nesses casos, seria ótimo se a visualização da imagem pudesse, de alguma forma, ser informada para cortar de forma inteligente a foto ao redor do rosto da pessoa.

Muitas vezes mostramos fotos de pessoas. Nesses casos, seria ótimo se a visualização da imagem pudesse, de alguma forma, cortar de forma inteligente a foto ao redor do rosto da pessoa.

Hoje veremos uma biblioteca do Beau Nouvelle chamada AspectFillFaceAware. É super simples, vamos dar uma olhada.

Hoje vamos dar uma olhada em uma biblioteca de classes da Beau Nouvelle chamada AspectFillFaceAware. É muito simples, vamos dar uma olhada.

AspectFillFaceAware é essencialmente apenas uma extensão do UIImageView. Ele fornece duas maneiras de configurar uma visualização de imagem para “reconhecer o rosto”.

AspectFillFaceAware é essencialmente apenas uma extensão do UIImageView. Ele fornece dois métodos de configuração da visualização da imagem para “reconhecimento facial”.

A primeira está no Interface Builder, podemos habilitar o recurso ativando-o no Inspetor. (Não está vendo a opção? Execute seu projeto uma vez, então ele deverá aparecer).

A primeira maneira é no Interface Builder, podemos habilitar o recurso percorrendo Recursos no Inspetor. (Não vê a opção? Execute seu projeto uma vez e ele deverá aparecer).

<img src=“/img/15334638167496.jpg” largura=“50%” altura=“50%” /> Veja como fica:

Também podemos ativar a funcionalidade no código definindo a imagem da visualização da imagem usando esta nova função:

Também podemos usar esse novo recurso por meio de código:

imageView.set (imagem: avatar, focusOnFaces: verdadeiro) Podemos até mesmo lançar um raio de canto rápido na camada de visualização da imagem para testar a funcionalidade “reconhecer o rosto” em uma visualização circular. (ou seja, avatares de usuários):

Podemos até lançar um raio de canto rápido na camada de visualização da imagem para testar o recurso de “reconhecimento facial” na visualização circular. (ou seja, avatar do usuário):

deixe raio = imageView.bounds.size.width / 2.0 imageView.layer.cornerRadius = raio

Nos bastidores, a biblioteca está usando um CIDetector de baixa precisão com um tipo de CIDetectorTypeFace para lidar com a detecção de rosto real. Quer mergulhar mais fundo aqui? Abordamos os CIDetectors em [Bite # 87.] (https://littlebitesofcocoa.com/87)

Nos bastidores, a biblioteca está usando um CIDetector de baixa precisão com o tipo CIDetectorTypeFace para lidar com a detecção de rosto real. Quer se aprofundar? Introduzimos a abordagem CIDetectors em Bite #87.

Dica

####1 Como definir pontos de interrupção para métodos do sistema ao usar o Xcode para depuração? A resposta é ponto de interrupção. Por exemplo, para o método setContentInset, ponto de interrupção, você pode usar o seguinte comando:

breakpoint set -S  setContentInset:

Para obter detalhes, consulte: https://www.jianshu.com/p/8e9fc9a8ab78?from=jiantop.com

####2 Otimização UITableView Pode-se dizer que a otimização do UITableView é um tópico que nunca sairá de moda no desenvolvimento do iOS. Aqui está um resumo das ideias de otimização. Você mesmo pode pesquisar os métodos específicos no Google. A ideia geral é a seguinte:

Reduza a quantidade de cálculos de CPU/GPU 1.1 Mecanismo de reutilização celular 1.2 Armazene em cache a altura da célula e o quadro dos controles na célula do modelo 1.3 Reduza o nível de controles dentro da célula 1.4 Obtenha o efeito de canto arredondado do avatar cobrindo o canto arredondado da imagem
Carregar células sob demanda 2.1 Carregar apenas células visíveis no método cellForRow: 2.2 Monitore a rolagem rápida da tableview e salve os índices das três linhas antes e depois do intervalo de rolagem de destino
Processamento assíncrono de células 3.1 Carregamento assíncrono de imagens de rede 3.2 Desenhe imagens locais de forma assíncrona 3.3 Desenho assíncrono do UIView 3.4 Desenho assíncrono de NSString 3.5 Desenho assíncrono do UILabel

Compartilhando uma pergunta hoje, vi essa pergunta em um grupo hoje

Qual você escolherá? Escolha D?

Pelo conhecimento anterior, eu deveria escolher D, mas quando vi alguém dizendo para escolher B, tentei. O código de teste é o seguinte:

- (void)viewDidLoad {
    [super viewDidLoad];
    for (int i =0; i < MAXFLOAT; i++) {
         @autoreleasepool{
             UIImage *img = [[UIView alloc] init];// A
             
             UILabel *lab = [[UILabel alloc] init];// B
             
             NSString *str = @"abc";
             str = [str stringByAppendingString:@"xyz"];// C
        }
    }
}

O resultado é realmente B. B fará com que a memória continue aumentando. Após o teste, descobriu-se que, independentemente do autoreleasepool, B fará com que a memória continue aumentando. Os outros dois não farão com que a memória continue aumentando. É estranho. É lógico que após adicionar @autoreleasepool, a memória será liberada automaticamente quando atingir um determinado valor. A explicação no grupo é:

Relacionado a tópicos
A Apple otimizou o loop for. Se não for UIView e suas subclasses, será processado em um subthread.
O objeto UIView será criado automaticamente no thread principal
Se você colocar UIImage no thread principal para processamento, a memória ainda aumentará.
O método de liberação do pool de liberação automática do thread principal é diferente daquele do thread filho.

Mas ainda não entendo o porquê: 1 lab é uma variável local, exceto que o colchete direito do loop for deve ser liberado. 2 Adicionado @autoreleasepool, que deve ser liberado quando a memória atingir seu pico. ? ? ?

FAQ