当前位置: 首页> 健康> 美食 > 2024.6.12刷题记录

2024.6.12刷题记录

时间:2025/7/12 2:22:44来源:https://blog.csdn.net/lshx4658/article/details/139613038 浏览次数:0次

目录

一、801. 二进制中1的个数 - AcWing题库

二、802. 区间和 - AcWing题库

三、803. 区间合并 - AcWing题库

四、826. 单链表 - AcWing题库

五、827. 双链表 - AcWing题库


一、801. 二进制中1的个数 - AcWing题库

不会,来自题解(AcWing 801. 基础_位运算_二进制中1的个数java_python_c++ - AcWing)。

def func(x):# 获取最低位1,并删掉return x - (x & -x)if __name__ == '__main__':n = int(input())nums = list(map(int, input().split()))for i in range(n):cnt = 0x = nums[i]while x:x = func(x)cnt += 1print(cnt, end = ' ')

二、802. 区间和 - AcWing题库

不会,思路来自(AcWing 802. 画个图辅助理解~ - AcWing),代码参考(AcWing 802. 区间和 - AcWing),做了修改。

n, m = map(int, input().split())
addNum = [list(map(int, input().split())) for _ in range(n)]
querys = [list(map(int, input().split())) for _ in range(m)]
# 下标映射列表
idxList = [x for x, _ in addNum] + [x for i in querys for x in i]# 离散化操作
idxList = list(set(idxList))  # 去重
idxList.sort()  # 要排序# 构造下标映射查找
def find(x):# 二分查找l, r = 0, len(idxList) - 1while l <= r:mid = (l + r) // 2if idxList[mid] >= x:r = mid - 1else:l = mid + 1return l + 1    # 在此处+1,直接映射到1 ~ len(idxList) + 1# print(idxList)
# 差分数组,下标从1开始
nums = [0] * (len(idxList) + 5)
for x, c in addNum:nums[find(x)] += c
# print(nums)
# 求前缀和
# 从1开始,方便后面查询
s = [0] * (len(idxList) + 5)
for i in range(1, len(idxList) + 1):s[i] = s[i - 1] + nums[i]
# print(s)
# 查询操作
for i in querys:l, r = find(i[0]), find(i[1])print(s[r] - s[l - 1])

三、803. 区间合并 - AcWing题库

def main():n = int(input())lst = [list(map(int, input().split())) for _ in range(n)]ans = 1     # 至少为一个lst.sort(key = lambda x: x[0])  # 将相同开头的放一起start, end = lst[0][0], lst[0][1]for s, e in lst:if s > end:# 下一个区间不相接时更新ans += 1start = send = max(end, e)print(ans)main()

四、826. 单链表 - AcWing题库

不会,思路来自题解(AcWing 826. 单链表---图解 - AcWing),代码来自题解(AcWing 826. 单链表 - AcWing)。

# 用列表实现链表
N = 100010
e = [0] * N     # 表示节点值
ne = [0] * N    # next指针def init():# 初始化global head, idxhead = -1idx = 0def add_to_head(x):# 插入节点到head后global head, idxe[idx] = x  # 构造节点ne[idx] = head  # 更改指针head = idxidx += 1def add(k, x):# 将节点添加在节点k后global idxe[idx] = xne[idx] = ne[k]ne[k] = idxidx += 1def remove(k):# 移除节点k后的节点ne[k] = ne[ne[k]]m = int(input())init()  # 记得初始化链表for _ in range(m):oper = list(input().split())if oper[0] == 'H':x = int(oper[1])add_to_head(x)elif oper[0] == 'D':k = int(oper[1])if k == 0:head = ne[head]     # 去掉第一个节点else:remove(k - 1)   # 第k个插入的节点的下标为k - 1else:k, x = int(oper[1]), int(oper[2])add(k - 1, x)# 输出
cur = head
while cur != -1:print(e[cur], end = ' ')cur = ne[cur]   # 下一节点

五、827. 双链表 - AcWing题库

参考题解(AcWing 827. 双链表 - AcWing)。

# 双链表将头尾算作节点def init(n = 100010):# 初始化,n为长度global e, pe, ne, idxe = [0] * (m + 2)pe = [0] * (m + 2)    # 前节点ne = [0] * (m + 2)    # 后节点ne[0] = 1pe[1] = 0idx = 2     #0头1尾def remove(k):global e, pe, ne, idx# 将第k个节点删除pe[ne[k]] = pe[k]ne[pe[k]] = ne[k]def insert(k, x):global e, pe, ne, idx# 在第 k 个插入的数右侧插入一个数e[idx] = xpe[idx] = kne[idx] = ne[k]# 更改连接ne[pe[idx]] = idxpe[ne[idx]] = idxidx += 1m = int(input())init(m)     # 以命令长度初始化,链表长度不会超过# 注意下标和节点的映射关系,第k个节点的下标是k + 1
for _ in range(m):oper = input().split()if oper[0] == 'L':insert(0, int(oper[1]))elif oper[0] == 'R':# 尾节点的上一个节点的右侧插入insert(pe[1], int(oper[1]))elif oper[0] == 'D':# 下标映射remove(int(oper[1]) + 1)elif oper[0] == 'IL':# 第k个节点的左节点的右侧插入insert(pe[int(oper[1]) + 1], int(oper[2]))else:# 第k个节点的右侧插入insert(int(oper[1]) + 1, int(oper[2]))# 输出
cur = ne[0] # 头节点的右节点是第一个节点
res = []
while cur != 1:res.append(str(e[cur]))cur = ne[cur]
print(' '.join(res))

感谢你看到这里!一起加油吧! 

关键字:2024.6.12刷题记录

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: