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 所需要的步数更少。因此我们对字符串 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;
} #笔试题目##阿里巴巴#
