LeetCode简单题目(#160 #167 #168 #169 #171)-5道（序列、数字）

港控/mmm° 2023-06-15 15:25 20阅读 0赞

> leetcode题库中共有350道简单题目。  
> 本文记录已解决的题目和代码。  
> 本文中的序号是leetcode题目中的真实序号。

### 文章目录 ###

*  160 相交链表
 *   *  描述
     *  代码
     *  大神代码-双指针法
     *  大神代码-哈希表法
     *  3种方法总结
 *  167 两数之和 II - 输入有序数组
 *   *  描述
     *  代码
     *  大神代码-哈希方法
 *  168 Excel表列名称
 *   *  描述
     *  代码
     *  大神代码
 *  169 求众数
 *   *  描述
     *  代码
     *  大神代码
 *  171 Excel表列序号
 *   *  描述
     *  代码
     *  大神代码
     *  另一个大佬解法

# 160 相交链表 #

## 描述 ##

编写一个程序，找到两个单链表相交的起始节点。  
如下面的两个链表：  
A: a1 -> a2 ->  
\-> c1 -> c2 -> c3  
B: b1 -> b2 -> b3 ->  
在节点 c1 开始相交。

示例 1：  
输入：intersectVal = 8, listA = \[4,1,8,4,5\], listB = \[5,0,1,8,4,5\], skipA = 2, skipB = 3  
输出：Reference of the node with value = 8  
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 \[4,1,8,4,5\]，链表 B 为 \[5,0,1,8,4,5\]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：  
输入：intersectVal = 2, listA = \[0,9,1,2,4\], listB = \[3,2,4\], skipA = 3, skipB = 1  
输出：Reference of the node with value = 2  
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 \[0,9,1,2,4\]，链表 B 为 \[3,2,4\]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

注意：  
如果两个链表没有交点，返回 null.  
在返回结果后，两个链表仍须保持原有的结构。  
可假定整个链表结构中没有循环。  
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

## 代码 ##

# Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def getIntersectionNode(self, headA, headB):
            """
            :type head1, head1: ListNode
            :rtype: ListNode
            """
            tempA,tempB = headA,headB
            countA,countB = 0,0
            while tempA:
                countA += 1
                tempA = tempA.next
            while tempB:
                countB += 1
                tempB = tempB.next
            sub = abs(countA - countB)
            if countA > countB:
                for i in range(sub):
                    headA = headA.next
            elif countA < countB:
                for i in range(sub):
                    headB = headB.next
            while headA and headB:
                if headA == headB:
                    return headA
                headA = headA.next
                headB = headB.next
            return None

## 大神代码-双指针法 ##

> 作者：jyd  
> 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/

class Solution(object):
        def getIntersectionNode(self, headA, headB):
            ha, hb = headA, headB
            while ha != hb:
                ha = ha.next if ha else headB
                hb = hb.next if hb else headA
            return ha

## 大神代码-哈希表法 ##

> https://leetcode-cn.com/u/irvlin/

class Solution(object):
        def getIntersectionNode(self, headA, headB):
            """
            :type head1, head1: ListNode
            :rtype: ListNode
            """
            hashIDs = {
        }
            while headA:
                hashIDs[id(headA)] = 1
                headA = headA.next
            while headB:
                if id(headB) in hashIDs:
                    return headB
                headB = headB.next

## 3种方法总结 ##

> https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode/

# 167 两数之和 II - 输入有序数组 #

## 描述 ##

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。  
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:  
返回的下标值（index1 和 index2）不是从零开始的。  
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。  
示例:  
输入: numbers = \[2, 7, 11, 15\], target = 9  
输出: \[1,2\]  
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

## 代码 ##

> 参考网址  
> https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/solution/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-shuang-zh/

class Solution:
        def twoSum(self, numbers: List[int], target: int) -> List[int]:
            i,j = 0,len(numbers)-1
            temp_sum = numbers[i]+numbers[j]
            while temp_sum != target:
                if temp_sum < target:
                    i += 1
                elif temp_sum > target:
                    j -= 1
                temp_sum = numbers[i]+numbers[j]
            return [i+1,j+1]

## 大神代码-哈希方法 ##

> https://leetcode-cn.com/u/cengshenlan/

class Solution(object):
        def twoSum(self, numbers, target):
            d = {
        }
            for i, n in enumerate(numbers):
                another_num = target-n
                if another_num in d:
                    return [d[another_num]+1, i+1]
                d[n]=i

# 168 Excel表列名称 #

## 描述 ##

给定一个正整数，返回它在 Excel 表中相对应的列名称。  
例如，

1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 
    ...

示例 1:  
输入: 1  
输出: “A”  
示例 2:  
输入: 28  
输出: “AB”  
示例 3:  
输入: 701  
输出: “ZY”

## 代码 ##

class Solution:
        def convertToTitle(self, n: int) -> str:
            letter_dic =           {
        0:'Z',1:'A',2:'B',3:'C',4:'D',5:'E',6:'F',7:'G',8:'H',9:'I',10:'J',11:'K',12:'L',13:'M',14:'N',15:'O',16:'P',17:'Q',18:'R',19:'S',20:'T',21:'U',22:'V',23:'W',24:'X',25:'Y',26:'Z'}
            if n in letter_dic:
                return letter_dic[n]
            col_str = ''
            while n//26 > 1:
                col_str = letter_dic[n%26] + col_str
                if n%26:
                    n = n//26
                else:
                    n = n//27
            while n > 26:
                col_str = letter_dic[n%26] + col_str
                n = n//26
            col_str = letter_dic[n] + col_str
            return col_str

## 大神代码 ##

> 作者：powcai  
> 链接：https://leetcode-cn.com/problems/excel-sheet-column-title/solution/shi-jin-zhi-zhuan-26jin-zhi-by-powcai/

class Solution:
        def convertToTitle(self, n: int) -> str:
            res = ""
            while n:
                n, y = divmod(n, 26) 
                if y == 0:
                    n -= 1
                    y = 26
                res = chr(y + 64) + res
            return res

class Solution:
        def convertToTitle(self, n: int) -> str:
            res = ""
            while n:
                n -= 1
                n, y = divmod(n, 26) 
                res = chr(y + 65) + res
            return res

# 递归解法
    class Solution:
        def convertToTitle(self, n: int) -> str:
            return "" if n == 0 else self.convertToTitle((n - 1) // 26) + chr((n - 1) % 26 + 65)

# 169 求众数 #

## 描述 ##

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。  
你可以假设数组是非空的，并且给定的数组总是存在众数。  
示例 1:

输入: \[3,2,3\]  
输出: 3  
示例 2:

输入: \[2,2,1,1,1,2,2\]  
输出: 2

## 代码 ##

class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            num_dic = {
        }
            for i in nums:
                if i not in num_dic:
                    num_dic[i] = 1
                else:
                    num_dic[i] += 1
            for k in num_dic:
                if num_dic[k] >= len(nums)/2:
                    return k

## 大神代码 ##

> python 方法总结  
> https://leetcode-cn.com/problems/majority-element/solution/mo-er-tou-piao-fa-di-yi-shi-jian-xiang-dao-ha-xi-p/

# 摩尔投票法
    class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            n=len(nums)
            res=0
            count=0
            for i in range(n):
                if(count==0):
                    res=nums[i]
                    count=1
                else:
                    if(nums[i]==res):
                        count+=1
                    else:
                        count-=1
            if(count>0):
                return res

# 171 Excel表列序号 #

## 描述 ##

给定一个Excel表格中的列名称，返回其相应的列序号。  
例如，

A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 
    ...

示例 1:  
输入: “A”  
输出: 1  
示例 2:  
输入: “AB”  
输出: 28  
示例 3:  
输入: “ZY”  
输出: 701

## 代码 ##

class Solution:
        def titleToNumber(self, s: str) -> int:
            col_number = 0
            s_len = len(s)
            for i,a in enumerate(s):
                col_number += (ord(a)-64)*(26**(s_len-i-1))
            return col_number

## 大神代码 ##

> 作者：powcai  
> 链接：https://leetcode-cn.com/problems/excel-sheet-column-number/solution/26jin-zhi-zhuan-shi-jin-zhi-by-powcai/

class Solution:
        def titleToNumber(self, s: str) -> int:
            return sum( (ord(a) - 64) * (26 ** i)  for i, a in enumerate(s[::-1]))

## 另一个大佬解法 ##

> https://leetcode-cn.com/u/chenhengtai123/

class Solution(object):
        def titleToNumber(self, s):
            #26进制转10进制
            ans = 0
            for x in s:
                ans *= 26
                ans += ord(x)-ord('A')+1
            return ans