8月28日 阿里笔试

8月28日 阿里笔试

第1题

如果对于一个 01 字符串,每次可以进行如下操作中的一种。

  • 只能交换任意两个元素
  • 把一个0变成1或把一个1变成0
  • 翻转整个字符串

请问从A串变成B串最少需要多少步?

我们先分析一波。

在这里插入图片描述
我们要用三种操作将字符串 origin 变成 target
尽管不一定最优,假设我们得到了一种可行方案。
假设这个方案里的翻转次数 r>1,那么我们一定可以消除其中的两次翻转操作达到一样的效果。
现在我们的方案里只有0次或1次翻转操作。假设现在我们的方案里仍然有1次翻转操作,那么翻转操作一定可以挪到最开始首先进行。那么我们得到翻转字符串 reversed
那么就得到两种可能的方案。
第一种:将字符串 origin 进行 交换改变 得到 target
第二种:将字符串 origin 翻转 得到 reversed, 再对 reversed 进行 交换改变 得到 target

我无法判断在这两种情况中哪一种转化为 target 所需要的步数更少。因此我们对字符串 originreversed 都进行受限的转换(交换改变)得到 target,并比较总步数取较小值。

接下来我们继续考虑用受限的转换将字符串 origin 变成 target
交换一次消一对,改变一次消一个。
交换的时候我们无脑交换就行了。

origintarget不匹配有两种情况:

  • dismatch0: origin[i]=='1' && target[i]=='0'
  • dismatch1: origin[i]=='0' && target[i]=='1'

如果两类不匹配分别有 dismatch0dismatch1 个。
那么我们可以用交换消除 min(dismatch0,dismatch1),剩余的不匹配用改变逐一处理。
交换改变的次数之和为 max(dismatch0,dismatch1)

package main

import "fmt"

func convert(origin,target string) (n int) {
    k:=0
    for i:=0;i< len(origin);i++{
        if origin[i]!=target[i]{
            k++
        }
    }
    reversed:=""
    for _,v:=range origin{
        reversed=string(v)+reversed
    }
    return min(1+convertBanRev(reversed,target),convertBanRev(origin,target))
}

func convertBanRev(origin,target string) (n int){
    dismatch0,dismatch1:=0,0
    for i:=0;i< len(origin);i++{
        if origin[i]=='1'&&target[i]=='0'{
            dismatch1++
        }else if origin[i]=='0'&&target[i]=='1'{
            dismatch0++
        }
    }
    return max(dismatch1,dismatch0)
}

func max(a,b int) int {
    if a<b{
        return b
    }else{
        return a
    }
}

func min(a,b int) int {
    if a<b{
        return a
    }else{
        return b
    }
}

func main()  {
    n:=0
    var origin,target string
    fmt.Scan(&n,&origin,&target)
    fmt.Println(convert(origin,target))
}
// cases:
//    case1:
//        in:        "1111000","0010011"
//        out:    3
//    case2:
//        in:        "11111000","001111110"
//        out:    2

第2题

给定两个数 nm 小强可以通过对 n 里面的数位进行重新排列。例如对 520 中的数位重新排列后能得到 520, 502, 250, 205, 052, 025 六种不同的数。求经过重新排列后所得到的数中满足不含有前导零并且能够整除m的数字有多少个?相同的数只算一次。

全排列问题可以用dfs求解。

package main

import (
    "fmt"
    "sort"
)

var numbers=[]int{}

func interestingNumberCnt(n,m int) (cnt int) {
    b:=1
    var digits=[]int{}
    for ;n>0;n/=10{
        digits = append(digits, n%10)
        b*=10
    }
    b/=10
    sort.Ints(digits)
    dfs(digits,0)
    for _,v:=range numbers{
        if v>=b&&v%m==0{
            cnt++
        }
    }
    return
}

func dfs(digits []int, number int) {
    if len(digits)==0{
        numbers = append(numbers, number)
    }else{
        pre:=digits[0]-1
        for i,n:=range digits{
            if n!=pre{
                dfs(append(digits[:i:i],digits[i+1:]...),number*10+n)
            }
            pre=n
        }
    }
}

func main() {
    var n,m int
    fmt.Scan(&n,&m)
    fmt.Println(interestingNumberCnt(n,m))
}

// cases:    in        out
//            322        2
//            97284    4

学习 go 的同学请注意看一下第 35 行,我们使用了 digits 的第 i 个元素,因此函数 dfs 要传入的第一个参数是删除第 i 个元素之后的新切片。

那为什么是 append(digits[:i:i],digits[i+1:]...) 而不是 append(digits[:i],digits[i+1:]...) 呢?

因为当切片的容量足够进行 append 的时候会在原切片上进行 append 操作,而当切片的容量不足以在原切片上进行 append 时则会将原切片拷贝到一个容量更大的切片上并 append

这里之所以用 digits[:i:i] 就是使这个切片的容量与长度对齐,使得 append 之后得到一个新切片不会影响原切片。如果你需要写这样一个函数,在函数对一个切片进行append操作而不影响原切片,就可以采用这种方式。

接下来我要讲的事情你们千万不要害怕。

我们刷题碰到这种全排列的大多得花点功夫写 dfs, 其实 C++ 的 STL 里有现成的函数可以快速输出无重复的全排列,next_permutation() 会生成一个序列的重排列,它是所有可能的字典序中的下一个排列。

利用 STL 就可以光速解题。这个时候我只想感叹一句, STL 真香。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int getValue(vector<int> digits){
    int sum=0;
    for (auto d:digits){
        sum=sum*10+d;
    }
    return sum;
}

int main(){
    int n,m,v,b=1,cnt=0;
    cin>>n>>m;
    vector<int> digits;
    for (;n;n/=10){
        digits.push_back(n%10);
        b*=10;
    }
    b/=10;
    sort(digits.begin(),digits.end());
    do{
        v=getValue(digits);
        //cout<<v<<endl;
        if (v>=b&&(v%m==0)){
            cnt++;
        }
    }while (next_permutation(digits.begin(),digits.end()));
    cout<<cnt;
    return 0;
}
#笔试题目##阿里巴巴#
全部评论
点赞 回复 分享
发布于 2020-08-31 19:28
**牛逼啊,思路杠杠了。😂
点赞 回复 分享
发布于 2020-09-01 11:41
老哥,第一题第一个方法里面的k是干嘛的
点赞 回复 分享
发布于 2020-09-10 15:06

相关推荐

12-02 17:22
已编辑
西安交通大学 Java
华为 昇腾 ai软件开发 薪资20k x (14-16),职级13A,5%公积金,c/cpp
BLOOMING7:闭眼滴滴,华子给的又少又累
点赞 评论 收藏
分享
Bug压路:老哥看得出来你是想多展示一些项目,但好像一般最多两个就够了😂页数一般一页,多的也就2页;这些项目应该是比较同质化的,和评论区其他大佬一样,我也觉得应该展示一些最拿手的(质量>数量)😁😁😁专业技能部分也可以稍微精简一些
点赞 评论 收藏
分享
评论
6
9
分享
牛客网
牛客企业服务