题目441题
排列硬币
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
思路
数学法或者二分法
实现
class Solution:
def arrangeCoins(self, n: int) -> int:
return int(((8 * n + 1) ** 0.5 - 1) // 2)
题目442题
数组中重复的数据
给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？
示例：
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]
思路
利用条件1 ≤ a[i] ≤ n，因此可以将a[i] -1 作为索引号，每次将索引号所在的值乘以-1，当遍历到负数时，则遇到了重复数字
实现
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
result = []
for i in range(len(nums)):
index = abs(nums[i]) -1
if nums[index] < 0:
result.append(index+1)
nums[index] *= -1
return result
题目443题
压缩字符串
给定一组字符，使用原地算法将其压缩。
压缩后的长度必须始终小于或等于原数组长度。
数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
在完成原地修改输入数组后，返回数组的新长度。
思路
双指针法：一个指针read指向读取位置，一个指针write指向写入位置
实现
class Solution:
def compress(self, chars: List[str]) -> int:
start = write = 0
for read, curr in enumerate(chars):
if read + 1 == len(chars) or chars[read+1] != curr:
chars[write] = chars[read]
write +=1
if read > start:
for digit in str(read - start+1):
chars[write] = digit
write +=1
start = read + 1
return write
题目445题
两数相加II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
思路
栈
实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
stack1,stack2 = list(), list()
while l1:
stack1.append(l1.val)
l1 = l1.next
while l2:
stack2.append(l2.val)
l2 = l2.next
add = 0
result = None
while stack1 or stack2 or add:
a = 0 if not stack1 else stack1.pop()
b = 0 if not stack2 else stack2.pop()
num = a + b + add
add = num // 10
num = num % 10
newnode = ListNode(num)
newnode.next = result
result = newnode
return result