算法题练习——JS Node+python题解NC61 两数之和、NC33 合并两个排序的链表

桃扇骨 2024-04-07 11:13 78阅读 0赞

**目录**

NC61 两数之和

NC33 合并两个排序的链表

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

### NC61 两数之和 ###

**描述**

> 给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
> 
> （注：**返回**的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

> 数据范围：2≤len(numbers)≤10^5，-10≤numbersi≤10^9，0≤target≤10^9
> 
> 要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

**示例1**

> 输入：\[3,2,4\],6
> 
> 返回值：\[2,3\]
> 
> 说明：因为 2+4=6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回\[2,3\]

**示例2**

> 输入：\[20,70,110,150\],90
> 
> 返回值：\[1,2\]
> 
> 说明：20+70=90

**JavaScript题解：**

/**
      * 
      * @param numbers int整型一维数组 
      * @param target int整型 
      * @return int整型一维数组
      */
    function twoSum( numbers ,  target ) {
        // write code here
        if(numbers.length===0) return null
        const map = new Map()
        for(let i=0; i<numbers.length; i++){
            if(map.has(target-numbers[i])){
                return [map.get(target-numbers[i])+1,i+1]
            }
            map.set(numbers[i],i)
        }
    }
    module.exports = {
        twoSum : twoSum
    };

**python代码解：**

#
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param numbers int整型一维数组 
    # @param target int整型 
    # @return int整型一维数组
    #
    class Solution:
        def twoSum(self , numbers: List[int], target: int) -> List[int]:
            # write code here
            hash = {}
            for i, num in enumerate(numbers):
                if target-num in hash:
                    return [hash[target-num]+1,i+1]
                hash[num] = i

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

### NC33 合并两个排序的链表 ###

**描述**

> 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

> 数据范围： 0≤n≤1000，-1000≤节点值≤1000  
> 要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入\{1,3,5\},\{2,4,6\}时，合并后的链表为\{1,2,3,4,5,6\}，所以对应的输出为\{1,2,3,4,5,6\}，转换过程如下图所示：

![fbc3e270cb2641be95f4325dbc97f592.png][]

或输入\{-1,2,4\},\{1,3,4\}时，合并后的链表为\{-1,1,2,3,4,4\}，所以对应的输出为\{-1,1,2,3,4,4\}，转换过程如下图所示：

![0d7d0f57e04b423e9a8c9ada9e555fdc.png][]

**示例1**

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

**示例2**

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

**示例3**

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

**JavaScript题解：**

/*function ListNode(x){
        this.val = x;
        this.next = null;
    }*/
    function Merge(pHead1, pHead2)
    {
        // write code here
        if(!pHead1) return pHead2
        if(!pHead2) return pHead1
        if(pHead1.val<=pHead2.val){
            pHead1.next = Merge(pHead1.next,pHead2)
            return pHead1
        }else{
            pHead2.next = Merge(pHead1,pHead2.next)
            return pHead2
        }
    }
    module.exports = {
        Merge : Merge
    };

**python代码解：**

# class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param pHead1 ListNode类 
    # @param pHead2 ListNode类 
    # @return ListNode类
    #
    class Solution:
        def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
            # write code here
            if not pHead1 or not pHead2:
                return pHead1 or pHead2
            if pHead1.val < pHead2.val:
                pHead1.next = self.Merge(pHead1.next,pHead2)
                return pHead1
            else:
                pHead2.next = self.Merge(pHead1,pHead2.next)
                return pHead2

[fbc3e270cb2641be95f4325dbc97f592.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/f9f65cd83b4f496e85aa9ca90aa3f5f8.png
[0d7d0f57e04b423e9a8c9ada9e555fdc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/91176484dc2d44b29de71f56d9138d63.png