【LeetCode算法题库】Day2：Median of Two Sorted Arrays & Longest Palindromic Substring & ZigZag Conversion

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

[Q4] There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution: 按从小到大的顺序依次遍历两个数组，直至中间位置停止，此时：

（1）当两个数组长度N1+N2为偶数时，取（中间数+前一数）/2
（2）当N1+N2为奇数时，取当前位置的数

class Solution:

    def findMedianSortedArrays(self, nums1, nums2):

        """

        :type nums1: List[int]

        :type nums2: List[int]

        :rtype: float

        """

        i,j,idx = 0,0,0

        m,n = len(nums1),len(nums2)

        N = m+n

        prv, cur = None, None

        while idx<N:

            if i<m and j<n and nums1[i]<nums2[j]:

                cur = nums1[i]

                i = i+1

            elif i<m and j<n and nums1[i]>=nums2[j]:

                cur = nums2[j]

                j = j+1

            elif i>=m:

                cur = nums2[j]

                j = j+1

            elif j>=n:

                cur = nums1[i]

                i = i+1

            if N%2 == 0 and idx == N/2: #  if m+n is even

                return (cur+prv)/2

            elif N%2 == 1 and idx == N//2: #   floor division

                return cur

            prv = cur

            idx = idx+1

[Q5] 找最长回文序列

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"

Output: "bb"

Solution：遍历中心，从中心依次向两端迭代

class Solution:

    def longestPalindrome(self, s):

        """

        :type s: str

        :rtype: str

        """

        maxl = 0

        i=0

        left, right = 0,0

        maxs = ""

        while i<len(s): #  center location

            left = right = i

            while left>=0 and right<len(s) and s[left]==s[right]:

                left = left-1

                right = right+1

            tem = s[left+1:right]

            if len(tem)>len(maxs):

                maxs = tem

            left, right = i,i+1

            while left>=0 and right<len(s) and s[left]==s[right]:

                left = left-1

                right = right+1

            tem = s[left+1:right]

            if len(tem)>len(maxs):

                maxs = tem

            i = i+1

        return maxs

[Q6] 解法很棒

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N

A P L S I I G

Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = "PAYPALISHIRING", numRows = 3

Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4

Output: "PINALSIGYAHRPI"

Explanation:

P     I    N

A   L S  I G

Y A   H R

P     I

Solution: https://leetcode.com/problems/zigzag-conversion/discuss/3404/Python-O(n)-Solution-in-96ms-(99.43)

class Solution:

    def convert(self, s, numRows):

        """

        :type s: str

        :type numRows: int

        :rtype: str

        """

        if len(s)<numRows or numRows==1:

            return s

        idx = 0

        step = 1

        L = ['']*numRows

        for x in s:

            if idx==0:

                step = 1

            elif idx==numRows - 1:

                step = -1

            L[idx] += x

            idx = idx+step

        return ''.join(L)

重点：

（1）L的初始化，L为一个3行字符串数组

（2）引入Step，相当于把每一行的数直接压缩到同一行的唯一字符串内

（3）join函数：‘sep’.join（seq）即将seq字符串去sep后连接

【LeetCode算法题库】Day2：Median of Two Sorted Arrays & Longest Palindromic Substring & ZigZag Conversion的更多相关文章

(python)leetcode刷题笔记04 Median of Two Sorted Arrays
4. Median of Two Sorted Arrays There are two sorted arrays nums1 and nums2 of size m and n respectiv ...

LeetCode解题报告—— 2 Keys Keyboard & Longest Palindromic Substring & ZigZag Conversion
1. Longest Palindromic Substring Given a string s, find the longest palindromic substring in s. You ...

【leetcode刷题笔记】Median of Two Sorted Arrays
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted ...

【LeetCode算法题库】Day5：Roman to Integer & Longest Common Prefix & 3Sum
[Q13] Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Valu ...

LeetCode第[4]题(Java)：Median of Two Sorted Arrays 标签：Array
题目难度:hard There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median ...

LeetCode第[4]题(Java)：Median of Two Sorted Arrays （俩已排序数组求中位数）——HARD
题目难度:hard There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median ...

【LeetCode算法题库】Day4：Regular Expression Matching & Container With Most Water & Integer to Roman
[Q10] Given an input string (s) and a pattern (p), implement regular expression matching with suppor ...

【LeetCode算法题库】Day7：Remove Nth Node From End of List & Valid Parentheses & Merge Two Lists
[Q19] Given a linked list, remove the n-th node from the end of list and return its head. Example: G ...

【LeetCode算法题库】Day3：Reverse Integer & String to Integer (atoi) & Palindrome Number
[Q7] 把数倒过来 Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Outpu ...

随机推荐

Git Hooks、GitLab CI持续集成以及使用Jenkins实现自动化任务
Git Hooks.GitLab CI持续集成以及使用Jenkins实现自动化任务前言在一个共享项目(或者说多人协同开发的项目)的开发过程中,为有效确保团队成员编码风格的统一,确保部署方式的统一, ...

ajax执行失败原因
ajax 跳入error的一些原因先放一个标准的jquery的ajax代码: $.ajax({ type: 'POST', url: 'getSecondClassification', data: ...

php官网下载的chm手册，源码字号太小的问题解决
首先,到官方网站上下载chm格式的文档,地址如下: http://php.net/downloads.php 如图,点击荧光笔标出链接然后就可以看到各种语言版本的文档手册,可以选择中文版,并带有笔记 ...

Python学习笔记系列——九九乘法表&猜大小
再重新捡起Python,数据库短时间之内已经没啥看的了,不知道今年结束之前能不能Python入门,一直认为自己是没有编程思想的... 1.九九乘法表 #九九乘法表实现的一种方式之一 def Multi ...

P1120 小木棍［数据加强版］
题目描述乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50. 现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度. 给出每段小木棍的长度,编 ...

怎么用CIFilter给图片加上各种各样的滤镜_2
上一篇讲了怎么找到能用的的滤镜和大概怎么去寻找... 这里接着说如何详细地给图片加滤镜效果..前的准备工作... . 1. 在找到想用的滤镜名字之后.须要知道这个滤镜究竟须要什么參数. . 例如以下图 ...

Mybatis联合查询记录，左连接参数操作
公司业务需求要做个列表的排序而实际排序的字段不再本库中,需要跨库去拿到字段,因为是微服务体系架构,不可能Left join跨库的表,所以决定调用一次跨服务的API拿到排序相关的对象,里面包含需要排序 ...

centos下安装myrocksdb
承接上一篇,https://www.cnblogs.com/lunyu/p/10190364.html .编译安装myrocks的整个过程,特别是第2步和第7步,让人冗长难耐.因此编译安装成功后省去这 ...

如何使用cubemx 配置freertos，实时查看FreeRTOS任务列表和运行状态
---------------------------------------------------------------------------------------------------- ...

【转】比较详细的Asp伪静态化方法及Asp静态化探讨
目前,各大搜索引擎如google.百度.雅虎已经对动态页面诸如asp,php有着不错的支持了,只要动态页面后面的参数不要太长,如控制在3个参数内,页面内容做点优化,各大搜索对该类页面收录甚至不比静态h ...

正文

相关阅读

java中kmp算法代码，kmp算法 leetcode

玩转算法面试 leetcode题库分门别类详细解析视频教程

面试算法LeetCode刷题班—BAT面试官带你刷真题、过笔试

【机器学习】【No294】面试算法LeetCode刷题班—BAT面试官带你刷真题、过笔试

ios在哪里下载节奏大师，苹果节奏大师怎么下载不了

html5音频样式更改，html设置音频

寄生格斗游戏，寄生模式怎么玩

python万能库，python库大全一览

目录[+]

相关阅读

java中kmp算法代码，kmp算法 leetcode

玩转算法面试 leetcode题库分门别类详细解析视频教程

面试算法LeetCode刷题班—BAT面试官带你刷真题、过笔试

【机器学习】【No294】 面试算法LeetCode刷题班—BAT面试官带你刷真题、过笔试

ios在哪里下载节奏大师，苹果节奏大师怎么下载不了

html5音频样式更改，html设置音频

寄生格斗游戏，寄生模式怎么玩

python万能库，python库大全一览

目录[+]

【机器学习】【No294】面试算法LeetCode刷题班—BAT面试官带你刷真题、过笔试