刷题记录合辑

标题不含题号，题号写在正文与 description 中。

274. H指数

思路
代码
题解排序
题解计数排序
二分

思路
给予数组a,找到最大的元素a[i],大于其的元素数量>= a[i]
寻找数组中至少有

尝试1 - 排序: 通过
将数组由大到小进行排序，然后看a[i]是否>=i即可
当前失败因为没有考虑不存在的情况，如果不存在，那么

题解1 - 排序: 最好想
题解注意到其实制约h-index的并不是citations[i]本身，而是i也就是数量这一限制，所以他就没有再去利用citations[i]来对res进行更新

题解2 - 计数排序: O(n)时间复杂度
题解注意到了h-index最大值其实也就是n

题解2 - 二分搜索: 常数空间复杂度

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort(reverse = True)
        size = len(citations)
        res = -1
        for i in range(0,size):
            if i+1 >=citations[i]:
                res = max(res, citations[i])
            else:
                res = max(res, i+1)
        return res if res!=-1 else 0
1
2
3
4
5
6
7
8
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations = sorted(citations, reverse = True)
        size = len(citations)
        i, h = 0,0
        while i < n and citations[i] > h:
            i, h = i+1, h+1
        return h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        cnt = [0] * (n+1)
        for i in range(0, n):
            if citations[i] > n:
                cnt[n] = cnt[n] + 1
            else:
                cnt[citations[i]] += 1
        tot = 0
        for i in range(n, -1, -1):
            tot += counter[i]
            if tot >= i:
                return i
        return 0


1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        left, right = 0, len(citations)
        while left < right:
            mid = (left + right +1) >>1
            cnt = 0
            for v in citations:
                if v >= mid:
                cnt+=1
            if cnt >= mid:
                left = mid
            else:
                right = mid-1
        return left

总结

我们要学会python的几种排序函数

845. 数组中的最长山脉

思路
代码

思路
解读题意: 这里要求的是连续单峰区间

尝试1 - 贪心+单调栈: 微调后通过

  • 我们首先对每一个点进行计算，看由他这个点结束的最长上升，然后对每一个点进行计算，看在他这个点结束的最长下降，那么最长山脉就是在一个点结束
  • 算一个点结束的最长上升其实就是单调栈
  • 算一个点开始的最长下降其实就是反过来的单调栈
  • 其实根本没有单调栈，就是纯贪心，但是要判断不存在下降或者上升的情况

题解1 - 动态规划：

  • 跟我的方法一摸一样，只不过他把状态转移方程写出来了而已

题解2 - 双指针一次遍历:

  • 先l找上升然后r找下降。更新完答案后l = r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        s = []
        n = len(arr)
        inc = [0] * n
        dec = [0] * n
        inc[0] = 1 
        for i in range(1, n):
            if arr[i] > arr[i-1]:
                inc[i] = inc[i-1]+1
            else:
                inc[i] = 1
        dec[n-1] = 1
        for i in range(n-2, -1, -1):
            if arr[i] > arr[i+1]:
                dec[i] = dec[i+1] +1
            else:
                dec[i] = 1
        res = 0
        for i in range(0,n):
            
            
            res = max(res, inc[i]+dec[i]-1 if inc[i]!=1 and dec[i]!=1 else 0)
        return res if res!=1 else 0

148. 排序链表

思路
排序
归并排序
题解
二分查找

思路

尝试1 - 排序: 通过
首先遍历数组然后将所有的数组放入一个heap中，然后取出一个一个连起来

题解进阶思路 - 归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    import heapq
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        q = []
        heapq.heapify(q)
        dummy = ListNode(0, head)
        p = head
        i = 0
        while p:
           heapq.heappush(q, (p.val, i, p))
           p = p.next
           i += 1
        
        p2 = dummy
        while len(q) != 0:
            p2.next = heapq.heappop(q)[2]
            p2 = p2.next
        p2.next = None
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        q = []
        
        def getLength(head):
            cnt = 0
            while head:
                cnt += 1
                head = head.next
            return cnt

        def merge(l1, l2):
            dummy = ListNode(0)
            p = dummy 
            while l1 and l2:
                if l1.val < l2.val:
                    p.next = l1
                    l1 = l1.next
                else:
                    p.next= l2
                    l2 = l2.next
            p.next = l1 if l1 else l2
            while p.next:
                p = p.next # 需要尾节点所以要走到最后
            return dummy.next, p
        
        total_len = getLength(head)
        dummy = ListNode(0)
        dummy.next = head
        size = 1
        
        while size < total_len:
            prev = dummy
            curr = dummy.next
            while curr:
                left = curr
                right = self.split(left, size)
                next_start = self.split(right, size)

                merged_head = merged_tail = merge(left, right)
                prev.next = merged_head
                prev = merged_tail
                curr = next_start
            size *= 2
        return dummy.next

        def split(self, head, size):
            if not head:
                return None
            for i in range(size - 1):
                if head.next:
                    head = head.next
                else:
                    break
            next_head = head.next
            head.next = None
            return next_head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
```

{% endtabs %}

**总结**

---
## 1054. 距离相等的条形码

{% tabs active:2 align:left %}
<!-- tab 思路 -->

**思路**
尝试1 - 排序: 错误
* 一定存在答案，那么直接排序然后两两配对
* 通过不了类似[1,2,2,3]的数据

题解 - 

<!-- tab 代码 -->

```python
class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        n = len(barcodes)
        if n == 0 or n == 1:
            return barcodes
        barcodes.sort()
        res = [0] * n
        if n%2==0:
            mid = n // 2
            for i in range(0,n,2):
                res[i], res[i+1] = barcodes[i//2], barcodes[i//2+mid]
        else:
            mid = n // 2 +1
            for i in range(0,n-1,2):
                res[i], res[i+1] = barcodes[i//2], barcodes[i//2+mid]
            res[n-1] = barcodes[mid-1]
        return res

总结

349. 两个数组的交集

思路
代码

思路
将s1里全部数存入set，然后s2进行判断是否加入结果集合，然后结果集合转换为list即可

1
2
3
4
5
6
7
8
9
10
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        s = set()
        res = []
        for num in nums1:
            s.add(num)
        for num in nums2:
            if num in s and num not in res:
                res.append(num)
        return res

总结

137. 只出现一次的数字2

思路
代码
灵神题解
题解

题解 位运算:
出现三次其对应二进制位上出现的1的次数也位3的倍数，可以通过对二进制各个位上的1的数量%3得到结果

思路 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        maxn = max(nums)
        size = math.log(nums,2)+2
        d = [0]* size
        n = len(nums)
        for num in nums:
            i = 0
            while num:
                if num%2 == 1:
                    d[i] += 1
                    i += 1
                    num = num//2
        res = 0
        p = 1
        for i in range(0,size):
            d[i] = d[i]%3
            res += d[i] * p 
            p = p*2
        return res
            

        
1
2
3
4
5
6
7
8
9
10
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(31):
            # cnt 表示的是1的数量？
            cnt1 = sum(x >> i & 1 for x in nums )
            ans |= cnt1%3 << i
        # 这个是对符号位进行处理
        cnt1 = sum (x >> 31 & 1 for x in nums)
        return ans - (cnt1 % 3 << 31)
1
2
3

总结

1
2
for i in range(31):
    cnt1 = sum(x >> i & 1 for x in nums )

这里的含义是对应第i位的1的个数，同时这里有一个比较细节的点

特点 sum( .. for .. in ..) sum( [.. for .. in ..] )
内存使用 按需生成元素，节省内存 先生成完整列表，内存开销较大
执行效率 较高，尤其是数据量大时更优 稍低，因为先生成整个列表

我们基本选择第一种，第二种一般是先生成还需其他操作的时候用

202. 快乐数

思路
集合判断，出现过了就是进入死循环了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isHappy(self, n: int) -> bool:
        s = set()
        s.add(n)
        while n!=1:
            next_n = 0
            while n:
                k = n%10
                next_n += k*k
                n = n/10
            if next_n in s:
                return False
            n = next_n
        return True

知识点小结

  • 只有在类定义时需要使用self

模板

xx. xxx

思路
代码
二分查找

思路 

1
        
1
2
3
4
```

<!-- tab 题解 -->
```python

总结

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。