算法题练习——JS Node+python题解NC50 链表中的节点每k个一组翻转、NC19 连续子数组的最大和

Bertha 。 2024-04-07 11:28 61阅读 0赞

**目录**

NC50 链表中的节点每k个一组翻转

NC19 连续子数组的最大和

--------------------

### NC50 链表中的节点每k个一组翻转 ###

**描述**

> 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表  
> 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样  
> 你不能更改节点中的值，只能更改节点本身。

> 数据范围：0≤n≤2000 ，1≤k≤2000 ，链表中每个元素都满足0≤val≤1000  
> 要求空间复杂度 O(1)，时间复杂度 O(n)

> 例如：
> 
> 给定的链表是 1→2→3→4→5
> 
> 对于 k = 2 , 你应该返回 2→1→4→3→5
> 
> 对于 k = 3 , 你应该返回 3→2→1→4→5

**示例1**

> 输入：\{1,2,3,4,5\},2
> 
> 返回值：\{2,1,4,3,5\}

**示例2**

> 输入：\{\},1
> 
> 返回值：\{\}

**JavaScript题解：**

/*
     * function ListNode(x){
     *   this.val = x;
     *   this.next = null;
     * }
     */
    
    /**
      * 
      * @param head ListNode类 
      * @param k int整型 
      * @return ListNode类
      */
    function reverseKGroup( head ,  k ) {
        // write code here
        let preHead = new ListNode(-1);
        preHead.next = head
        let pre = preHead
        while(head){
            let tail = pre
            for(let i=0; i<k; i++){
                tail = tail.next
                if(!tail) return preHead.next
            }
            let next = tail.next;
            [head,tail]= reverse(head,tail)
            pre.next = head;
            tail.next = next;
            pre = tail;
            head = tail.next;
        }
        return preHead.next
    }
    
    function reverse(head,tail){
        let pre = null
        let current = head;
        while(pre!==tail){
            [current.next,pre,current] = [pre,current,current.next]
        }
        return [tail,head]
    }
    
    module.exports = {
        reverseKGroup : reverseKGroup
    };

**python代码解：**

# class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param head ListNode类 
    # @param k int整型 
    # @return ListNode类
    #
    class Solution:
        def reverse(self,head,tail):
            prev = tail.next
            p = head
            while prev != tail:
                next = p.next
                p.next = prev
                prev = p
                p = next
            return tail,head
        def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
            # write code here
            prehead = ListNode(0)
            prehead.next = head
            pre = prehead
            while head:
                tail = pre
                for i in range(k):
                    tail = tail.next
                    if not tail:
                        return prehead.next
                next = tail.next
                head, tail = self.reverse(head,tail)
                pre.next = head
                tail.next = next
                pre = tail
                head = tail.next
            return prehead.next

--------------------

### NC19 连续子数组的最大和 ###

**描述**

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

> 数据范围:1<=n<=2×10^5，-100<=a\[i\]<=100
> 
> 要求:时间复杂度为 O(n)，空间复杂度为 O(n)
> 
> 进阶:时间复杂度为 O(n)，空间复杂度为 O(1)

**示例1**

> 输入：\[1,-2,3,10,-4,7,2,-5\]
> 
> 返回值：18
> 
> 说明：经分析可知，输入数组的子数组\[3,10,-4,7,2\]可以求得最大和为18

**示例2**

> 输入：\[2\]
> 
> 返回值：2

**示例3**

> 输入：\[-10\]
> 
> 返回值：-10

**JavaScript题解：**

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param array int整型一维数组 
    # @return int整型
    #
    class Solution:
        def FindGreatestSumOfSubArray(self , array: List[int]) -> int:
            # write code here
            sum = array[0]
            temp = 0
            maxsum = sum
            for i in range(1,len(array)):
                temp = max(sum+array[i],array[i])
                maxsum = max(temp,maxsum)
                sum = temp
            return maxsum