# 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)`。

```go
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求解。

```go
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` 真香。

```cpp
#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;
}
```