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 所需要的步数更少。因此我们对字符串 origin 和 reversed 都进行受限的转换（交换 或 改变）得到 target，并比较总步数取较小值。

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

origin 和 target不匹配有两种情况：

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

如果两类不匹配分别有 dismatch0，dismatch1 个。
那么我们可以用交换消除 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题

给定两个数 n 和 m 小强可以通过对 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;
}