文章目录
一、两两交换链表中的节点
1、程序简介
- 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
- 输入：head = [1,2,3,4]
- 输出：[2,1,4,3]
示例 2：
- 输入：head = []
- 输出：[]
示例 3：
- 输入：head = [1]
- 输出：[1]
提示：
- 链表中节点的数目在范围 [0, 100] 内
- 0 <= Node.val <= 100
进阶：
- 你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）
2、程序代码
# -*- coding: utf-8 -*-
"""
Created on Fri Dec 3 15:31:48 2021
Function:
@author: 小梁aixj
"""
class ListNode(object):
def __init__(self, x):
self.val=x
self.next=None
class LinkList:
def __init__(self):
self.head=None
def initList(self, data):
self.head=ListNode(data[0])
r=self.head
p=self.head
for i in data[1:]:
node=ListNode(i)
p.next=node
p=p.next
return r
def convert_list(self,head):
ret=[]
if head==None:
return
node=head
while node != None:
ret.append(node.val)
node=node.next
return ret
class Solution(object):
def swapPairs(self, head):
dummyHead=ListNode(-1)
dummyHead.next=head
prev, p = dummyHead, head
while p != None and p.next != None:
q, r=p.next, p.next.next
prev.next=q
q.next=p
p.next=r
prev=p
p=r
return dummyHead.next
#%%
l=LinkList()
head=[1,2,3,4]
l1=l.initList(head)
s=Solution()
print(l.convert_list(s.swapPairs(l1)))
3、运行结果
二、K个一组翻转列表
1、程序简介
- 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
- k 是一个正整数，它的值小于或等于链表的长度。
- 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进阶：
- 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
- 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
- 输入：head = [1,2,3,4,5], k = 2
- 输出：[2,1,4,3,5]
示例 2：
- 输入：head = [1,2,3,4,5], k = 3
- 输出：[3,2,1,4,5]
示例 3：
- 输入：head = [1,2,3,4,5], k = 1
- 输出：[1,2,3,4,5]
示例 4：
- 输入：head = [1], k = 1
- 输出：[1]
提示：
- 列表中节点的数量在范围 sz 内
- 1 <= sz <= 5000
- 0 <= Node.val <= 1000
- 1 <= k <= sz
2、程序代码
# -*- coding: utf-8 -*-
"""
Created on Fri Dec 3 15:32:44 2021
Function:
@author: 小梁aixj
"""
class ListNode(object):
def __init__(self, x):
self.val=x
self.next=None
class LinkList:
def __init__(self):
self.head=None
def initList(self, data):
self.head=ListNode(data[0])
r=self.head
p=self.head
for i in data[1:]:
node=ListNode(i)
p.next=node
p=p.next
return r
def convert_list(self,head):
ret=[]
if head == None:
return
node=head
while node != None:
ret.append(node.val)
node=node.next
return ret
class Solution(object):
def reverseKGroup(self, head, k):
if head is None:
return None
index = 0
lead, last=0,0
pos=head
temp=ListNode(-1)
temp.next=head
head=temp
start=head
while pos is not None:
if index%k == k-1:
last=pos.next
start=self.reverseList(start, last)
pos=start
pos=pos.next
index ^= 1
return head.next
def reverseList(self, head, end):
pos=head.next
last=end
next_start=pos
while pos != end:
head.next=pos
last_pos=pos
pos=pos.next
last_pos.next=last
last=last_pos
return next_start
#%%
l = LinkList()
head = [1,2,3,4,5]
l1 = l.initList(head)
s = Solution()
print(l.convert_list(s.reverseKGroup(l1, k = 2)))
3、运行结果
三、解数独
1、程序简介
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注：数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
示例：
输入：
board =
[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
输出：
[["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]
解释：
输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
- board.length == 9
- board[i].length == 9
- board[i][j] 是一位数字或者 ‘.’
- 题目数据 保证 输入数独仅有一个解
2、程序代码
# -*- coding: utf-8 -*-
"""
Created on Fri Dec 3 15:33:29 2021
Function:
@author: 小梁aixj
"""
class Solution(object):
def solveSudoku(self, board):
def isvaild(i,j):
for m in range(9):
if m!=i and board[m][j]==board[i][j]:
return False
for n in range(9):
if n!=j and board[i][n]==board[i][j]:
return False
for m in range(i//3*3,i//3*3+3):
for n in range(j//3*3,j//3*3+3):
if m!=i and n!=j and board[m][n]==board[i][j]:
return False
return True
def f(a,b,board):
for i in range(a,9):
for j in range(b,9):
if board[i][j]=='.':
for c in '123456789':
board[i][j]=c
if isvaild(i,j):
if f(a,b,board):return True
else: board[i][j]='.'
else: board[i][j]='.'
return False
return True
f(0,0,board)
return board
#%%
s=Solution()
board=[['5','3','.','.','7','.','.','.','.'],
['6','.','.','1','9','5','.','.','.'],
['.','9','8','.','.','.','.','.','.'],
['8','.','.','.','6','.','.','.','3'],
['4','.','.','8','.','3','.','.','1'],
['7','.','.','.','2','.','.','.','6'],
['.','6','.','.','.','.','2','8','.'],
['.','.','.','4','1','9','.','.','5'],
['.','.','.','.','8','.','.','7','9']]
print('按原样输出：')
print(s.solveSudoku(board))
print('格式化输出：')
#格式化输出
a=s.solveSudoku(board)
for x in range(9):
for y in range(9):
print(a[x][y], end=" ")
print()