ARTES #007
ARTES #007
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 007
Este é o 7º artigo. Eu costumava ficar confuso ao olhar para algoritmos, mas agora estou lentamente entendendo e tenho ideias. Espero que fique cada vez melhor no futuro.
Pergunta sobre algoritmo de algoritmo
questão do algoritmo leetcode 15 3Sum: Dificuldade: Moderada
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
O primeiro método que vem à mente é o seguinte, que é obviamente o menos eficiente. No meu dispositivo, leva 15 segundos para testar 3.000 dados.
int** threeSum(int* nums, int numsSize, int* returnSize) {
int **a= NULL; //用二级指针动态申请二维数组
int count = 0;
for (int i =0; i < numsSize-2; i++) {
for (int j =i+1; j < numsSize-1; j++) {
for (int k =j+1; k<numsSize; k++) {
int first = nums[i];
int second = nums[j];
int third = nums[k];
if (first + second + third == 0) {
if (first < second ) {
int temp =first;
first = second;
second = temp;
}
if (first < third ) {
int temp =first;
first = third;
third = temp;
}
if (second<third) {
int temp =second;
second = third;
third = temp;
}
int b = 0;
if(a != NULL){
for (int loop = 0; loop < count; loop++) {
int *aa = a[loop];
if (aa[0] == first && aa[1] == second) {
//已经存在
b = 1;
break;
}
}
}
if (b == 0) {
int* result = (int*)malloc(sizeof(int) * (3));
result[0] = first;
result[1] = second;
result[2] = third;
if (count ==0) {
count++;
a=(int**)malloc(sizeof(result)*count);
}
else{
count++;
a=(int**)realloc(a,sizeof(int*)*count);
}
a[count-1] = result;
}
}
}
}
}
*returnSize = count;
return a;
}
Olhando para os prompts, todos eles são classificados primeiro. Após a classificação, pensei na pesquisa binária, então implementei da seguinte maneira
/插入排序
int* insertionSort(int nums[],int numsSize) {
for (int j = 1; j < numsSize; j++) {
int sortingNum = nums[j];
for (int i = j-1; i >=0; i--) {
if (sortingNum < nums[i] ) {
int temp = nums[i+1];
nums[i+1] = nums[i];
nums[i] = temp;
}
}
}
return nums;
}
// 二分查找
int binary_search(int arr[],int left,int right,int element){
while(left<=right) {
int mid = (left+right)/2;
if(arr[mid]>element){
right = mid - 1;
}
else if(arr[mid]<element){
left = mid + 1;
}
else{
return mid;
}
}
return -1;
}
int** threeSum3(int* nums1, int numsSize, int* returnSize) {
int *dddsd = insertionSort(nums1,numsSize);
if(dddsd[0] > 0)
return NULL;
if(dddsd[numsSize-1] < 0)
return NULL;
int **result= NULL; //用二级指针动态申请二维数组
int count = 0;
for (int i =0; i < numsSize-2 && dddsd[i] <=0; i++) {
for (int j =numsSize-1; j >i && dddsd[j] >= 0; j--) {
int first = dddsd[i];
int second = dddsd[j];
int third = 0 - first - second;
int dfsd =binary_search(dddsd, i+1, j-1, third);
if (dfsd == -1) {
continue;
}
third = dddsd[dfsd];
int b = 0;
if(result != NULL){
for (int loop = 0; loop < count; loop++) {
int *aa = result[loop];
if (aa[0] == first && aa[1] == second) {
//已经存在
b = 1;
break;
}
}
}
if (b == 0) {
int* sums = (int*)malloc(sizeof(int) * (3));
sums[0] = first;
sums[1] = second;
sums[2] = third;
if (count ==0) {
count++;
result=(int**)malloc(sizeof(sums)*count);
}
else{
count++;
result=(int**)realloc(result,sizeof(int*)*count);
}
result[count-1] = sums;
}
}
}
*returnSize = count;
return result;
}
O algoritmo acima, para evitar duplicação, irá compará-lo com o anterior sempre que o resultado for adicionado. Esta operação pode realmente ser otimizada e a implementação final é a seguinte:
//插入排序
int* insertionSort(int nums[],int numsSize) {
for (int j = 1; j < numsSize; j++) {
int sortingNum = nums[j];
for (int i = j-1; i >=0; i--) {
if (sortingNum < nums[i] ) {
int temp = nums[i+1];
nums[i+1] = nums[i];
nums[i] = temp;
}
}
}
return nums;
}
// 二分查找
int binary_search(int arr[],int left,int right,int element){
while(left<=right) {
int mid = (left+right)/2;
if(arr[mid]>element){
right = mid - 1;
}
else if(arr[mid]<element){
left = mid + 1;
}
else{
return mid;
}
}
return -1;
}
int** threeSum(int* nums, int numsSize, int* returnSize) {
int *sortedNums = insertionSort(nums,numsSize);
if(sortedNums[0] > 0)
return NULL;
if(sortedNums[numsSize-1] < 0)
return NULL;
int **result= NULL; //用二级指针动态申请二维数组
int count = 0;
for (int i =0; i < numsSize-2 && sortedNums[i] <=0; i++) {
if (i > 0 && sortedNums[i] == sortedNums[i-1]) {
continue;
}
for (int j =numsSize-1; j >i && sortedNums[j] >= 0; j--) {
if (j < numsSize-1 && sortedNums[j] == sortedNums[j+1]) {
continue;
}
int first = sortedNums[i];
int second = sortedNums[j];
int third = 0 - first - second;
int dfsd =binary_search(sortedNums, i+1, j-1, third);
if (dfsd == -1) {
continue;
}
third = sortedNums[dfsd];
int* sums = (int*)malloc(sizeof(int) * (3));
sums[0] = first;
sums[1] = second;
sums[2] = third;
if (count ==0) {
count++;
result=(int**)malloc(sizeof(sums)*count);
}
else{
count++;
result=(int**)realloc(result,sizeof(int*)*count);
}
result[count-1] = sums;
}
}
*returnSize = count;
return result;
}
Revisão
Entre com o programa QUER um emprego em uma multinacional de sucesso? Você enfrentará muita concorrência. Há dois anos, a Goldman Sachs recebeu um quarto de milhão de candidaturas de estudantes e licenciados. Essas não são apenas probabilidades assustadoras para quem procura emprego; eles são um problema prático para as empresas. Se uma equipe de cinco funcionários de recursos humanos do Goldman, trabalhando 12 horas todos os dias, incluindo fins de semana, gastasse cinco minutos em cada solicitação, levaria quase um ano para concluir a tarefa de examinar a pilha.
Procurando uma posição em uma empresa multinacional de sucesso? Então você tem que enfrentar muita concorrência. Há dois anos, a Goldman Sachs recebeu 250 mil pedidos de emprego de estudantes e graduados. Isso não apenas faz com que os candidatos a emprego tenham poucas chances de sucesso, mas também traz problemas reais para a empresa. Supondo que uma equipe de cinco funcionários do departamento de recursos humanos da Goldman Sachs trabalhasse 12 horas por dia, 24 horas por dia, e gastasse cinco minutos em cada aplicação, levaria quase um ano para examinar essa montanha de aplicações.
Não é de admirar que a maioria das grandes empresas utilize um programa de computador, ou algoritmo, quando se trata de selecionar candidatos que procuram empregos júnior. E isso significa que os candidatos se beneficiariam se soubessem exatamente o que os algoritmos procuram.
Não é de admirar que a maioria das grandes empresas utilize um programa de computador, conhecido como algoritmo, para selecionar candidatos para cargos de nível inferior. Isso significa que os candidatos a emprego podem se beneficiar sabendo exatamente o que o algoritmo está procurando.
Victoria McLean é uma ex-headhunter bancária e gerente de recrutamento que criou uma empresa chamada City CV, que ajuda candidatos a empregos com inscrições. Ela diz que os sistemas de rastreamento de candidatos (ATS) rejeitam até 75% dos currículos, ou currículos, antes que um ser humano os veja. Esses sistemas procuram palavras-chave que atendam aos critérios do empregador. Uma dica é estudar a linguagem utilizada no anúncio de emprego; se as iniciais PM forem usadas para gerenciamento de projetos, certifique-se de que PM apareça em seu currículo.
Victoria McLean, ex-headhunter bancária e gerente de recrutamento, fundou uma empresa chamada City CV para ajudar quem procura emprego a elaborar suas candidaturas. Ela disse que o Sistema de Rastreamento de Candidatos (ATS) rejeita até 75% das inscrições antes que um ser humano possa processar o currículo. Esses sistemas procuram palavras-chave que correspondam aos critérios do empregador. Uma dica rápida é pesquisar a linguagem usada no anúncio de emprego. Se as iniciais PM forem usadas para se referir ao gerenciamento de projetos, certifique-se de ter PM em seu currículo.
Isso significa que um currículo genérico pode falhar no primeiro obstáculo. A Sra. McLean tinha um cliente que era um membro sênior das forças armadas. Sua experiência apontou para empregos potenciais em treinamento e educação, compras ou vendas de defesa. A melhor estratégia foi criar três currículos diferentes usando diferentes conjuntos de palavras-chave. E os caçadores de emprego também precisam de se certificar de que o seu perfil no LinkedIn e o seu CV se reforçam mutuamente; a grande maioria dos recrutadores utilizará o site para verificar as qualificações dos candidatos, diz ela.
Isso significa que um currículo que não seja direcionado pode nem passar pela primeira barreira. McClain tinha um cliente que era um oficial militar de alta patente. A julgar pelo seu currículo, ele pode ter oportunidades de emprego em treinamento e educação, compras ou venda de armas. A melhor estratégia, diz ela, é criar três currículos diferentes usando três conjuntos diferentes de palavras-chave. Os candidatos também precisam ter certeza de que seu perfil no LinkedIn corresponde ao seu currículo – a grande maioria dos recrutadores usa o site para verificar as qualificações dos candidatos.
Passar na fase ATS pode não ser a única barreira tecnológica do caçador de empregos. Muitas empresas, incluindo Vodafone e Intel, usam um serviço de entrevista em vídeo chamado HireVue. Os candidatos são questionados enquanto um programa de inteligência artificial (IA) analisa suas expressões faciais (é aconselhável manter contato visual com a câmera) e padrões de linguagem (parecer confiante é o truque). Pessoas que agitam os braços ou se relaxam na cadeira provavelmente fracassarão. Somente se passarem nesse teste os candidatos conhecerão alguns humanos.
O ATS pode não ser o único obstáculo técnico que os candidatos a emprego enfrentam. Muitas empresas, incluindo Vodafone e Intel, adotaram um serviço de entrevistas em vídeo chamado HireVue. À medida que os candidatos respondem às perguntas do vídeo, os programas de IA analisam suas expressões faciais (recomenda-se manter contato visual com a câmera) e padrões de fala (parecer confiante é fundamental). Pessoas que agitam os braços ou ficam sentadas em uma postura desleixada provavelmente fracassarão. Somente depois de passar neste teste o candidato pode se reunir com alguns entrevistadores.
Seria de esperar que os programas de IA conseguissem evitar alguns dos preconceitos dos métodos convencionais de recrutamento – especialmente a tendência dos entrevistadores de favorecerem candidatos que se pareçam com o entrevistador. No entanto, a discriminação pode manifestar-se de formas inesperadas. Anja Lambrecht e Catherine Tucker, duas economistas, colocaram anúncios promovendo empregos em ciência, tecnologia, engenharia e matemática no Facebook. Eles descobriram que os anúncios tinham menos probabilidade de serem exibidos para mulheres do que para homens.
Talvez você tenha pensado que um programa de IA seria capaz de evitar alguns dos preconceitos presentes nos métodos tradicionais de recrutamento, especialmente a tendência dos entrevistadores de selecionar candidatos semelhantes a eles. No entanto, a discriminação pode manifestar-se de formas inesperadas. Duas economistas, Anja Lambrecht e Catherine Tucker, publicaram anúncios no Facebook promovendo oportunidades de emprego em ciência, tecnologia, engenharia e matemática. Eles descobriram que esses anúncios tinham maior probabilidade de serem veiculados para homens do que para mulheres.Isso não se deveu a um preconceito consciente por parte do algoritmo do Facebook. Em vez disso, as mulheres jovens são um grupo demográfico mais valioso no Facebook (porque controlam uma grande parte dos gastos das famílias) e, portanto, os anúncios direcionados a elas são mais caros. Os algoritmos direcionaram naturalmente as páginas onde o retorno do investimento é mais alto: para homens, não para mulheres.
Este não é o resultado de um preconceito consciente no algoritmo do Facebook. Em contraste, as mulheres jovens são um grupo mais valioso no Facebook (porque controlam uma grande parte das despesas domésticas), pelo que os anúncios direcionados a elas são mais caros. Esses algoritmos visam naturalmente as páginas com maior retorno sobre o investimento: homens, não mulheres.
No seu livro* sobre inteligência artificial, Ajay Agrawal, Joshua Gans e Avi Goldfarb, da Rotman School of Management de Toronto, afirmam que as empresas não podem simplesmente descartar tais resultados como um infeliz efeito secundário da natureza de “caixa negra” dos algoritmos. Se descobrirem que o resultado de um sistema de IA é discriminatório, terão de descobrir porquê e depois ajustar o algoritmo até que o efeito desapareça.
Ajay Agrawal, Joshua Gans e Avi Goldfarb, da Rotman School of Management da Universidade de Toronto, escrevem no seu coautor sobre inteligência artificial* que as empresas não podem simplesmente descartar tais resultados como um efeito secundário infeliz da natureza de “caixa negra” dos algoritmos. Se descobrirem que o resultado de um sistema de IA é discriminatório, terão de descobrir a razão e depois ajustar o algoritmo até que o impacto desapareça.
As preocupações sobre potenciais preconceitos nos sistemas de IA surgiram numa vasta gama de áreas, desde a justiça criminal até aos seguros. Também no recrutamento, as empresas enfrentarão um risco jurídico e de reputação se os seus métodos de contratação se revelarem injustos. Mas também precisam de considerar se os programas fazem mais do que apenas simplificar o processo. Por exemplo, os candidatos aprovados têm carreiras longas e produtivas? Afinal, a rotatividade de pessoal é um dos maiores custos de recrutamento que as empresas enfrentam.
O potencial de parcialidade dos sistemas de IA suscitou preocupações em muitas áreas, desde a justiça criminal até aos seguros. O mesmo se aplica ao recrutamento de pessoal. Se as empresas utilizarem métodos de recrutamento injustos, enfrentarão riscos legais e de reputação. Mas também precisam de considerar se estes programas podem fazer mais do que simplificar o processo de contratação. Por exemplo, um candidato selecionado permanecerá na empresa por um longo prazo e de forma produtiva? Afinal, a rotatividade de funcionários é um dos maiores custos de recrutamento que as empresas enfrentam.
Também pode haver uma corrida armamentista à medida que os candidatos aprendem como ajustar seus currículos para passar no teste inicial de IA e os algoritmos se adaptam para selecionar mais candidatos. Isto cria margem para outro potencial preconceito: os candidatos de agregados familiares em melhor situação (e de grupos específicos) podem ser mais rápidos a actualizar os seus CV. Por sua vez, isto pode exigir que as empresas ajustem novamente os seus algoritmos para evitar discriminação. O preço da inteligência artificial parece provavelmente ser a vigilância eterna.
À medida que os candidatos aprendem a ajustar seus currículos para passar no teste inicial de IA e os algoritmos melhoram para filtrar mais candidatos, isso pode desencadear uma corrida armamentista. Isto cria espaço para outro potencial preconceito: os candidatos de famílias mais ricas (e determinados grupos) poderão atualizar os seus currículos mais rapidamente. Por sua vez, as empresas poderão ter de ajustar novamente os seus algoritmos para evitar discriminação. O preço do uso da inteligência artificial parece ser a vigilância perpétua.
DICAS:
Como implementar diferentes tamanhos de arco em diferentes cantos da vista
Corte todos os quatro cantos direitos da vista em cantos arredondados:
//设置圆角半径值
self.view.layer.cornerRadius = 10.f;
//设置为遮罩，除非view有阴影，否则都要指定为YES的
self.view.layer.masksToBounds = YES;
- Corte um ângulo reto da vista em um canto arredondado:
//把 view2 的 左下角 和 右下角的直角切成圆角
UIView *view2 = [[UIView alloc] initWithFrame:CGRectMake(120,10,80,80)];
view2.backgroundColor = [UIColor redColor];
[self.view addSubview:view2];
//设置切哪个直角
// UIRectCornerTopLeft = 1 << 0, 左上角
// UIRectCornerTopRight = 1 << 1, 右上
// UIRectCornerBottomLeft = 1 << 2, 左下角
// UIRectCornerBottomRight = 1 << 3, 右下角
// UIRectCornerAllCorners = ~0UL 全部角
//得到view的遮罩路径
UIBezierPath *maskPath = [UIBezierPath bezierPathWithRoundedRect:view2.bounds byRoundingCorners:UIRectCornerBottomLeft | UIRectCornerBottomRight cornerRadii:CGSizeMake(10,10)];
//创建 layer
CAShapeLayer *maskLayer = [[CAShapeLayer alloc] init];
maskLayer.frame = view2.bounds;
//赋值
maskLayer.path = maskPath.CGPath;
Os cantos arredondados definidos pelo método acima possuem o mesmo arco para cada canto arredondado. Então, como conseguir quatro cantos com diferentes tamanhos de cantos arredondados? A chave para realizar os cantos arredondados acima é o caminho do CAShapeLayer, então só precisamos personalizar esse caminho. A implementação é a seguinte:
- (void)setViewRadius:(UIView *)view{
CGFloat topLeftRadius = 50;
CGFloat topRightRadius = 60;
CGFloat bottomRightRadius = 40;
CGFloat bottomLeftRadius = 30;
CGFloat minx = CGRectGetMinX(view.bounds);
CGFloat miny = CGRectGetMinY(view.bounds);
CGFloat maxx = CGRectGetMaxX(view.bounds);
CGFloat maxy = CGRectGetMaxY(view.bounds);
UIBezierPath *path = [[UIBezierPath alloc] init];
[path moveToPoint:CGPointMake(minx + topLeftRadius, miny)];
[path addLineToPoint:CGPointMake(maxx - topRightRadius, miny)];
[path addArcWithCenter:CGPointMake(maxx - topRightRadius, miny + topRightRadius) radius: topRightRadius startAngle: 3 * M_PI_2 endAngle: 0 clockwise: YES];
[path addLineToPoint:CGPointMake(maxx, maxy - bottomRightRadius)];
[path addArcWithCenter:CGPointMake(maxx - bottomRightRadius, maxy - bottomRightRadius) radius: bottomRightRadius startAngle: 0 endAngle: M_PI_2 clockwise: YES];
[path addLineToPoint:CGPointMake(minx + bottomLeftRadius, maxy)];
[path addArcWithCenter:CGPointMake(minx + bottomLeftRadius, maxy - bottomLeftRadius) radius: bottomLeftRadius startAngle: M_PI_2 endAngle:M_PI clockwise: YES];
[path addLineToPoint:CGPointMake(minx, miny + topLeftRadius)];
[path addArcWithCenter:CGPointMake(minx + topLeftRadius, miny + topLeftRadius) radius: topLeftRadius startAngle: M_PI endAngle:3 * M_PI_2 clockwise: YES];
[path closePath];
CAShapeLayer *maskLayer = [[CAShapeLayer alloc] init];
maskLayer.path = path.CGPath;
view.layer.mask = maskLayer;
Dê outra demonstração do UIView para implementar cores gradientes.
UIColor *frameColor = [UIColor colorWithHexString:@"#FFB300"];
UIColor *toColor = [UIColor colorWithHexString:@"#FF6100"];
CAGradientLayer *gradientLayer = [CAGradientLayer layer];
gradientLayer.locations = @[@0.0, @1.0];
gradientLayer.startPoint = CGPointMake(0, 0);
gradientLayer.endPoint = CGPointMake(1.0, 0);
gradientLayer.frame = _bgImageView.bounds;
gradientLayer.colors = @[(__bridge id)frameColor.CGColor, (__bridge id)toColor.CGColor];
[_bgImageView.layer insertSublayer:gradientLayer atIndex:0];
Compartilhar:
Há uma sessão de perguntas e respostas sobre Zhihu se tornando viral hoje, ~~ A construção de tecnologia da Tencent está atualmente (em 2018) atrasada em relação a empresas do mesmo tamanho? ~~,yUma resposta chamada durão se tornou popular, mas a resposta do autor foi excluída um dia depois de ser postada. No entanto, existe um backup online. Se você estiver interessado, pode pesquisá-lo.
Deixe-me compartilhar meus pensamentos sobre este assunto:
O artigo fala sobre tecnologia deficiente, reservas insuficientes de talentos, liquidação tecnológica e regras e regulamentos internos relativamente rígidos dentro da empresa. A empresa em que trabalho é realmente assim. Muitos dos sistemas da empresa não conduzem ao desenvolvimento da tecnologia da empresa. Muitos dos líderes juniores da empresa são idosos que estão na empresa há mais de 5 anos. Suas habilidades são medianas e eles sobreviveram. Alguns deles nem conhecem Git e ainda usam SVN. Ninguém se atreve a refatorar o código porque não há casos de teste. Se você corrigir o bug, terá que assumir a responsabilidade. A atitude do líder é que ela pode ser aproveitada.
Pode-se dizer que o nível técnico de uma equipe depende da liderança da equipe. Se o padrão de liderança for grande o suficiente e a habilidade for forte o suficiente, a criatividade de toda a equipe será forte.
Se um líder é complacente, busca a estabilidade e impede que outros utilizem novas tecnologias sem fazer progressos, então ele está ferrado e deve sair o mais rápido possível.
Numa grande empresa, é difícil para um programador de base mudar esta situação. Acho que a única maneira de mudar esta situação é através da liderança.
Há também a questão das horas extras. Na verdade, muitas horas extras em grandes empresas não são porque o trabalho não pode ser concluído, mas porque a empresa usa isso como padrão para medir a carga de trabalho. Desta forma, aconteça o que acontecer, deve haver horas extras suficientes. Comumente conhecido como projeto facial.
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