【程序人生】leetcode（三）_输入: head = 3->5->8->5->10->2->1, x = 5 输出: 3->1->2

说在前面

这篇博客中部分题目答案来自leetcode评论区，不是本人原创。感谢原作者的工作。这里记录在这篇博客中，方便日后回顾、学习

移除元素(原创)

给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用O(1)额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        while val in nums:
            nums.remove(val)
        
        return len(nums)
1
2
3
4
5
6

分割链表(原创)

编写程序以x为基准分割链表，使得所有小于x的节点排在大于或等于x的节点之前。如果链表中包含x，x只需出现在小于x的元素之后(如下所示)。分割元素x只需处于“右半部分”即可，其不需要被置于左右两部分之间。

示例：

输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        flag = True
        while flag:
            cur = head
            flag = False
            while cur and cur.next:
                if cur.val >=x and cur.next.val <x:
                    key = cur.val
                    cur.val = cur.next.val
                    cur.next.val = key
                    flag = True
                
                cur = cur.next
        
        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

奇偶链表(转载)

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为O(nodes)，nodes 为节点总数。

说明：

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        # 奇链表
        p = head
        
        if p is None:
            return p
        
        # 偶链表
        q =head.next

        if (q is None) or (q.next is None):
            # 只有一个节点或者只有两个节点的情况，不需要处理直接返回p
            return p

        i = p
        j = q
        while j != None and j.next:
            i.next = i.next.next
            j.next = j.next.next
            i = i.next
            j = j.next
        
        i.next = q

        return p
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

实现strStr()函数(原创)

给定一个haystack字符串和一个needle字符串，在haystack字符串中找出needle字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。

示例：

输入: haystack = “hello”, needle = “ll”
输出: 2

输入: haystack = “aaaaa”, needle = “bba”
输出: -1

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == "":
            return 0
        
        a = haystack.replace(needle, "")
        if len(a) == len(haystack):
            return -1
        
        else:
            for i in range(len(haystack) - len(needle) + 1):
                if haystack[i:i+len(needle)] == needle:
                    return i
1
2
3
4
5
6
7
8
9
10
11
12
13

完全平方数(转载)

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例：

输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.

输入: n = 13
输出: 2
解释: 13 = 4 + 9.

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            val = i
            j = 1
            while i - j * j >= 0:
                val = min(val, dp[i - j*j] + 1) 
                j += 1
            dp[i] = val
        return dp[n]
1
2
3
4
5
6
7
8
9
10
11

删除排序数组中的重复项(原创)

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        p = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[p]:
                key = nums[p+1]
                nums[p+1] = nums[i]
                nums[i] = key
                p = p + 1
        
        new_nums = nums[:p+1]

        return len(new_nums)
1
2
3
4
5
6
7
8
9
10
11
12
13

搜索插入位置(原创)

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。

示例：

输入: [1,3,5,6], 2
输出: 1

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        p = 0
        q = len(nums)
        while  p < q:
            mid = int((p + q) / 2)
            if nums[mid] > target:
                q = mid
            elif nums[mid] < target:
                p = mid +1
            else:
                return mid
        return p
1
2
3
4
5
6
7
8
9
10
11
12
13

二分法，如果最后不是从nums[mid]==target输出，那么最后一定是判断nums[p(等于q)]的值和target的大小。
如果值大于target，那么target插在p(等于q)的左边，也就是顶替了p(等于q)的位置，所以nums[mid]>target的分支是q=mid；如果值小于target，那么target插在p(等于q)的右边，也就是p(等于q)的后一个位置，所以nums[mid]<target的分支是p=mid+1。

删除链表的倒数第N个节点(原创)

给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

双指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        p = head
        for i in range(n):
            p = p.next
            if not p:
                return head.next
                
        q = head

        while p.next:
            p = p.next
            q = q.next

        q.next = q.next.next

        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

四数之和(原创)

给定一个包含 n个整数的数组nums和一个目标值target，判断nums中是否存在四个元素a，b，c和d ，使得a + b + c + d的值与target相等？找出所有满足条件且不重复的四元组。

注意：
答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]]

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        result = []
        nums.sort()

        def threeSum(nums, target):
            result = []
            for i in range(0, len(nums)-2):
                nums_ = nums[i+1:]
                target_ = target - nums[i]

                p = 0
                q = len(nums_) - 1

                while p < q:
                    if nums_[p] + nums_[q] == target_:
                        result.append([nums_[p], nums_[q], nums[i]])
                        p = p + 1
                        while (nums_[p - 1] == nums_[p]) and (p < q):
                            p = p + 1
                        q = q - 1
                        while (nums_[q + 1] == nums_[q]) and (p < q):
                            q = q - 1
                    elif nums_[p] + nums_[q] < target_:
                        p = p + 1
                        while (nums_[p - 1] == nums_[p]) and (p < q):
                            p = p + 1
                    else:
                        q = q - 1
                        while (nums_[q + 1] == nums_[q]) and (p < q):
                            q = q - 1
            return result

        for i in range(0, len(nums)-3):
            result_ = threeSum(nums[i+1:], target - nums[i])
            if result_ == []:
                continue
            else:
                for each in result_:
                    list0 = each
                    list0.append(nums[i])
                    list0.sort()
                    if list0 not in result:
                        result.append(list0)
        
        return result
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

外观数列(原创)

给定一个正整数$n（1\le n\le 30）$，输出外观数列的第$n$项。
注意：整数序列中的每一项将表示为一个字符串。
外观数列是一个整数序列，从数字$1$开始，序列中的每一项都是对前一项的描述。前五项如下：

1: 1
2: 11
3: 21
4: 1211
5: 111221

第一项是数字 1
描述前一项，这个数是 1 即 “一个 1 ”，记作 11
描述前一项，这个数是 11 即 “两个 1 ” ，记作 21
描述前一项，这个数是 21 即 “一个 2 一个 1 ” ，记作 1211
描述前一项，这个数是 1211 即 “一个 1 一个 2 两个 1 ” ，记作 111221

示例：

输入: 1
输出: “1”

输入: 4
输出: “1211”

class Solution:
    def countAndSay(self, n: int) -> str:
        the_list = []
        for i in range(1, n + 1):
            if i == 1:
                the_list.append(str(i))
            else:
                last = the_list[-1]
                result = ""
                
                while len(last):
                    key = last[0]
                    count = 1
                    last = last[1:]
                    
                    for each in list(last):
                        if each == key:
                            count = count + 1
                        else:
                            break
                    last = last[count-1:]
                    result = result + "{}".format(count) + "{}".format(key)
                    
                the_list.append(result)

        return the_list[n - 1]
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

结语

如果您有修改意见或问题，欢迎留言或者通过邮箱和我联系。
手打很辛苦，如果我的文章对您有帮助，转载请注明出处。