虾皮4.6算法岗笔试编程题目大意及AC代码

4.9更新：

依然没有收到面试邀请，可能是简历不匹配，也可能是没hc了。

---

之前看大家分享就很焦虑，各种全a也没有面试机会，求求了，给个面试机会吧虾皮。。。

1. 对数据（x，y）有两种操作：两边各加1和两边各乘2，问从（x，y）到（a，b）最少需要几次操作？

bfs

import collections
class Solution:
    def GetMinCalculateCount(self, sourceX, sourceY, targetX, targetY) :
        q = collections.deque([(targetX, targetY)])
        res = 0
        visited = set()
        while q:
            for _ in range(len(q)):
                a, b = q.popleft()
                if a == sourceX and b == sourceY:
                    return res
                elif a > sourceX and b > sourceY:
                    if (a - 1, b - 1) not in visited:
                        visited.add((a - 1, b - 1))
                        q.append((a - 1, b - 1))
                    if a % 2 == 0 and b % 2 == 0 and (a // 2, b // 2) not in visited:
                        visited.add((a // 2, b // 2))
                        q.append((a // 2, b // 2))
            res += 1
        return -1

a = Solution()
a.GetMinCalculateCount(10,100,22,203)

2. 把只含有A和B原字符串变成互逆字符串：

res1 = 0
res2 = 0
s1 = list(s)
s2 = list(s)
# begin with "A" 
pre = "B"
for i in range(len(s)):
    if s1[i] == pre:
        res1 += 1
    pre = "A" if pre == "B" else "B"

# begin with "B" 
pre = "A"
for i in range(len(s)):
    if s1[i] == pre:
        res2 += 1
    pre = "A" if pre == "B" else "B"

print(min(res1, res2))

3. 8皇后原题

n = 4
res = [0]
s1 = set() #row
s2 = set() #column
s3 = set() #diag
def backtracking(idx):
    if idx == n:
        res[0] += 1
        return 
    
    for i in range(n):
        if i not in s1 and i + idx not in s2 and i - idx not in s3:
            s1.add(i)
            s2.add(i + idx)
            s3.add(i - idx)
            backtracking(idx + 1)
            s1.remove(i)
            s2.remove(i + idx)
            s3.remove(i - idx)
backtracking(0)
print(res[0])

#笔试题目#