二刷整理

547，朋友圈，并查集,核心解根的父节点问题。

https://leetcode-cn.com/problems/friend-circles/submissions/

class Solution:def findCircleNum(self, M: List[List[int]]) -> int:#盲写class UnionFind:def __init__(self,n):self.count = nself.parent = [i for i in range(n)]self.deep = [1 for i in range(n)]def find_root(self, p):while self.parent[p] != self.parent[self.parent[p]]:self.parent[p] = self.parent[self.parent[p]]return self.parent[p]def union_find(self, p, q):p_root = self.find_root(p)q_root = self.find_root(q)if p_root == q_root: returnif self.deep[p_root] < self.deep[q_root]:#核心要解决根的父节点问题self.parent[p_root] = q_rootelif self.deep[p_root] > self.deep[q_root]:self.parent[q_root] = p_rootelif self.deep[p_root] == self.deep[q_root]:self.deep[q_root] += 1self.parent[p_root] = q_rootself.count -= 1n = len(M)uf = UnionFind(n)for i in range(n):for j in range(i):if M[i][j] == 1:uf.union_find(i,j)return uf.count

491. 递增子序列

class Solution(object):def findSubsequences(self, nums):self.ans = []self.s = set()""":type nums: List[int]:rtype: List[List[int]]"""def robot(idx, cur_list, nums):if len(cur_list)>=2:self.s.add(tuple(cur_list))for i in range(idx, len(nums)):if len(cur_list) > 0 and cur_list[-1]>nums[i]: continuecur_list.append(nums[i])#print('cur_list:',cur_list)robot(i+1, cur_list, nums)cur_list.pop()robot(0,[],nums)return [list(a) for a in self.s]

3、最长不重复子串

class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""cur_list = []cur_set = set()maxl = 0for i in range(len(s)):if s[i] not in cur_set:cur_set.add(s[i])cur_list.append(s[i])maxl = max(maxl, len(cur_set))else:midx = cur_list.index(s[i])cur_set =set(cur_list[midx+1:])cur_set.add(s[i])cur_list = cur_list[midx+1:] + [s[i]]return maxl

4，两个有序数组找中位数
import sys
class Solution(object):def findMedianSortedArrays(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: float"""#寻找第K大数def findKth(A,B,K):if len(A) == 0: return B[K-1]if len(B) == 0: return A[K-1]if K == 1:return min(A[0],B[0])a=sys.maxintb=sys.maxintif len(A) >= K/2: a = A[K/2-1]if len(B) >= K/2: b = B[K/2-1]if a < b:return findKth(A[K/2:],B,K-K/2)return findKth(A,B[K/2:],K-K/2)A,B = nums1,nums2K = len(A) + len(B)if K%2 == 1:return findKth(A,B,1+K/2)else:small = findKth(A,B,K/2)biger = findKth(A,B,1+K/2)return (small+biger)/2.0

5，最长回文子串
class Solution(object):def longestPalindrome(self, s):""":type s: str:rtype: str"""def robot(s1, i):k = 0maxl = 0#print 's1:',s1while k < i and k < len(s1)-i:if s1[i-k] == s1[i+k]:maxl +=1else:breakk += 1#最主要是k多走了一步，要减回来return s1[i-(k-1):i+(k-1)+1]#首尾都需要#号 写的时候容易错s1 = '#'s1 += '#'.join(list(s))s1 += '#'out = ''for i in range(len(s1)):out_list = robot(s1, i)if len(out_list) > len(out):out = out_listreturn out.replace('#','')

23. 合并k个排序链表
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
import heapq
class Solution:def mergeKLists(self, lists: List[ListNode]) -> ListNode:h = ListNode(0)hp = hhead = []#遍历数组的下标for i in range(len(lists)):if lists[i]:heapq.heappush(head, (lists[i].val,i))lists[i] = lists[i].nextwhile head:val, idx = heapq.heappop(head)hp.next =ListNode(val)hp = hp.nextif lists[idx]:heapq.heappush(head, (lists[idx].val,idx))lists[idx] = lists[idx].nextreturn h.next

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！