算法题练习——JS Node+python题解NC41 最长无重复子数组、NC4 判断链表中是否有环

客官°小女子只卖身不卖艺 2024-04-07 11:55 61阅读 0赞

**目录**

NC41 最长无重复子数组

NC4 判断链表中是否有环

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

### NC41 最长无重复子数组 ###

**描述**

> 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
> 
> 子数组是连续的，比如\[1,3,5,7,9\]的子数组有\[1,3\]，\[3,5,7\]等等，但是\[1,3,7\]不是子数组

> 数据范围：0≤arr.length≤10^5，0 <arr\[i\]≤10^5

**示例1**

> 输入：\[2,3,4,5\]
> 
> 返回值：4
> 
> 说明：\[2,3,4,5\]是最长子数组

**示例2**

> 输入：\[2,2,3,4,3\]
> 
> 返回值：3
> 
> 说明：\[2,3,4\]是最长子数组

**示例3**

> 输入：\[9\]
> 
> 返回值：1

**示例4**

> 输入：\[1,2,3,1,2,3,2,2\]
> 
> 返回值：3
> 
> 说明：最长子数组为\[1,2,3\]

**示例5**

> 输入：\[2,2,3,4,8,99,3\]
> 
> 返回值：5
> 
> 说明：最长子数组为\[2,3,4,8,99\]

**JavaScript题解：**

/**
     * 
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    function maxLength( arr ) {
        // write code here
       var ret = 0
       var k = 0
       var map = new Map()
       for(var i=0; i<arr.length; i++){
           if(map.has(arr[i])){
               k = Math.max(k,map.get(arr[i])+1)
           }
           ret = Math.max(ret,i-k+1)
           map.set(arr[i],i)
       }
        return ret 
    }
    module.exports = {
        maxLength : maxLength
    };

**python代码解：**

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

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

### NC4 判断链表中是否有环 ###

**描述**

> 判断给定的链表中是否有环。如果有环则返回true，否则返回false。

> 数据范围：链表长度 0≤n≤10000，链表中任意节点的值满足 |val| <=100000
> 
> 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

> 输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

> 例如输入\{3,2,0,-4\},1时，对应的链表结构如下图所示：

![4e7fce7e6b6949bf9866eea851ba966d.png][]

> 可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。

**示例1**

> 输入：\{3,2,0,-4\},1
> 
> 返回值：true
> 
> 说明：第一部分\{3,2,0,-4\}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true

**示例2**

> 输入：\{1\},-1
> 
> 返回值：false
> 
> 说明：第一部分\{1\}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false

**示例3**

> 输入：\{-1,-7,7,-4,19,6,-9,-5,-2,-5\},6
> 
> 返回值：true

**JavaScript题解：**

/*
     * function ListNode(x){
     *   this.val = x;
     *   this.next = null;
     * }
     */
    
    /**
     * 
     * @param head ListNode类 
     * @return bool布尔型
     */
    function hasCycle( head ) {
        // write code here
        let fast = head
        let slow = head
        while(fast){
            if(fast.next){
                fast = fast.next.next
            }else{
                return false
            }
            slow = slow.next
            if(fast == slow) return true
        }
    }
    module.exports = {
        hasCycle : hasCycle
    };

**python代码：**

# class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    #
    # 
    # @param head ListNode类 
    # @return bool布尔型
    #
    class Solution:
        def hasCycle(self , head: ListNode) -> bool:
            if not head:
                return False
            fast = head
            slow = head
            while slow and fast:
                slow = slow.next
                if fast.next:
                    fast = fast.next.next
                else:
                    return False
                if slow == fast:
                    return True
            return False

[4e7fce7e6b6949bf9866eea851ba966d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4d840c4c75a44948ba9457ae054cd0bf.png