原文链接荣耀社招笔试题
十一放假回家参加了荣耀社招笔试，两道算法题，解析仅供参考
题目描述:
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请
你设计一种算法，将图像旋转 90 度。不占用额外内存空间能否做到？
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
作为数学系出生的学生，对矩阵的操作应该有所印象，本题的本质在于考察对于矩阵的基本运算能力，例如矩阵转置、内积、点积以及矩阵的迹、特征值和特征向量等等，这是解决本题以及类似题的关键，也是刷题过程中从仅仅刷题到总结经验的思考过程，发现自己目前欠缺的正是这个思考过程。
记得很清，在18年找实习的时候，人生中第一次求职面试公司是阿里，面试官在结束面试时给我说，“任何语言你应该看其本质，你是数学系的，你应该知道事物的本质，框架都是基于语言的本质搭建的”，这句话当时记得很清，很清楚其中的分量，很遗憾当时不能立即运用到实际开发学习之中，因为自己一直缺乏深入的思考，正如姜同学所说，“你在学校时候虽然也跟我们一起学，当你自己思考的太少了”，正因如此，走出学校去实习开始那一刻，和大部队渐行渐远，导致如此境地。思考，是突破瓶颈追求进步的必经之路，实操是检验思考的唯一标准，是及时反馈思考结果的不二法门。
回到本题，矩阵运算，就是通过转换操作把一个矩阵转为另一个矩阵，力扣原题是顺时针转换90度，荣耀笔试是顺时针转换m次，透过现象看本质，转换m次就是转换m个90度，循环即可。笔者当时在做这道题时观察转换后坐标和原坐标的关系，找出共同之处，这是思考欠缺的点，应该从更高的维度思考本题，基于做题的敏感性，联想矩阵的特征，n阶亦有诸多特征。
"""
@Auth ： Mario
@Date ： 2021/10/4 21:43
@Version ：
@Description ：旋转矩阵
"""
class Solution:
def rotate(self, matrix) -> None:
n = len(matrix)
# 水平翻转
i = 0
j = n -1
while i < j:
# 每一列上下翻转
for k in range(n):
matrix[i][k], matrix[j][k] = matrix[j][k], matrix[i][k]
i += 1
j -= 1
# 对角线翻转
for x in range(n):
for y in range(x):
matrix[x][y], matrix[y][x] = matrix[y][x], matrix[x][y]
def rotate2(self, matrix) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# 方法二
l = len(matrix)
# 先以对角线（左上-右下）为轴进行翻转
for i in range(l - 1):
for j in range(i+1,l):
temp = matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = temp
# 每一行中点两边交换元素交换
mid = l >> 1
for i in range(l):
for j in range(mid):
temp = matrix[i][j]
matrix[i][j] = matrix[i][l-1-j]
matrix[i][l-1-j] = temp
# 方法三： 多使用一个矩阵,内存较大
def rotate2(self, matrix) -> None:
n = len(matrix)
matrix_ = [i.copy() for i in matrix]
for i in range(n):
for j in range(n):
matrix_[j][n-1-i] = matrix[i][j]
# 注意这里是引用拷贝 不能写成 matrix = matrix_
matrix[:] = matrix_
# 翻转m次
def num(self, matrix, m):
while m > 0:
self.rotate(matrix)
m -= 1
print([x for x in matrix])
if __name__ == '__main__':
s = Solution()
m = [[1,2,3],[4,5,6],[7,8,9]]
s.num(m, 3)
题目描述:
给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：
操作 1 ：如果二进制串包含子字符串 “00” ，你可以用 “10” 将其替换。
比方说， “00010” -> “10010”
操作 2 ：如果二进制串包含子字符串 “10” ，你可以用 “01” 将其替换。
比方说， “00010” -> “00001”
请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。
示例 1：
输入：binary = "000110"
输出："111011"
解释：一个可行的转换为：
"000110" -> "000101"
"000101" -> "100101"
"100101" -> "110101"
"110101" -> "110011"
"110011" -> "111011"
示例 2：
输入：binary = "01"
输出："01"
解释："01" 没办法进行任何转换。
本题通过二进制变换找到最大的二进制数，第一个‘0’之前的1全部不动，之后的1全部移到末尾,'00’通过转换变为‘10’
class Solution:
def maximumBinaryString(self, binary: str) -> str:
pass
# 自己写的：完全没有深入琢磨题的意思
# l = len(binary)
# if l <= 1:
# return binary
# i = l - 2
# while binary[i] == '1' and i >= 0:
# for i in range(i,l):
# i -= 1
# j = 0
# while j < i and binary[j:j+2] == "00":
# binary[i:i+2] = "10"
# j += 1
# return binary
#
# num = 0
# start = 0
# for i in range(l):
# if binary[i] == '0':
# num += 1
# 方法二：失败
def maximumBinaryString2(self, binary: str) -> str:
l = len(binary)
left = 0 # 左边1 的个数
right = 0 # 右边1的个数
flag = True
for i in range(l):
flag = (flag and binary[i] == "1")
left += (flag and binary[i] == '1')
right += (not flag and binary[i] == '1')
if left + right < l -1:
for i in range(l):
k = l - 1 - right
if i == k:
binary[i] = '0'
else:
binary[i] = '1'
# binary[i] = (i == k ? '0' : '1' )
return binary
# 方法三：通过统计0 两边1的个数确定
def maximumBinaryString3(self, binary: str) -> str:
import collections
l = len(binary)
high1 = 0
start1 = 0
for i in range(l):
if binary[i] == '0':
break
# high1 统计第一个0 之前连续1 的个数
high1 += 1
# 此方法用于用于计数可哈希对象，返回一个dict 类型，统计每个数据的个数, 多学习呀
num = collections.Counter(binary)
if num['0'] == 0:
return binary
# 统计第一个0 之后1的个数
end1 = num['1'] - high1
# 由00 -> 10 转换后1的个数
start1 = l - 1 - end1
return '1' * start1 + '0' + '1' * end1
# 方法四： 统计第一个0前面1的个数，和0的个数
def maximumBinaryString3(self, binary: str) -> str:
l = len(binary)
start = -1
cnt = 0
for i in range(l):
if binary[i] == '0':
cnt += 1
if start == -1:
# 记录从第一位开始连续是1的个数
start = i
# 此时全部是1
if start == -1:
return binary
#第一个0 后面1的个数：
end = l - start - cnt
# 此时有cnt 个0，这经过000...0 -> 111...0转换后有(cnt - 1)个1，1个0
return '1' * start + '1' * (cnt - 1) + '0' + '1' * end
if __name__ == '__main__':
s = "hello"
# s[0:2] = "11" # 语法错误，string 是不可变类型
print(s)
print(s[0:2])
print(s[-1])
left = 0
flag = True
left += flag and s[0] == 'h'
print("flag and s[0] == 'h'： ", flag and s[0] == 'h') # flag and s[0] == 'h'： True
print(1 + True) # 2
print("left: ",left) # left: 1
print("True: ",True) # True: True
print(int(True)) # 1
祝好！
更多文章，请关注公众号：编程牧马人
