精华内容
下载资源
问答
  • 连续签到

    2019-04-24 15:56:55
    因此,需要提供个查询计算连续签到的算法。 由于需要补签,故需做成日历的形式,可一目了然知道哪些日期未签到,因此需要记录每日签到情况。 表设计关键字段如下: -- 签到表 CREATE TABL...

    说明:刚开始需求只是做一个登陆签到,就奖励积分的一个操作;达到设定的连续签到xx天后,就额外增加xx积分奖励;如果中断签到,则连续签到次数将重新计算;

    后来需求变化,需要增加一个提供补签到的功能。因此,需要提供一个查询计算连续签到的算法。

    由于需要补签,故需做成日历的形式,可一目了然知道哪些日期未签到,因此需要记录每日签到情况。

    表设计关键字段如下:

    -- 签到表
    CREATE TABLE `t_sign` (
      `sign_id` varchar(64) NOT NULL COMMENT '主键ID',
      `user_id` varchar(64) NOT NULL COMMENT '用户ID',
      `continue_times` int(4) unsigned NOT NULL DEFAULT '0' COMMENT '连续签到次数',
      `sign_count` int(4) unsigned NOT NULL DEFAULT '0' COMMENT '签到累计总次数',
      `award_count` int(4) unsigned NOT NULL DEFAULT '0' COMMENT '总累计奖励',
      `expend_count` int(4) unsigned NOT NULL DEFAULT '0' COMMENT '总累计耗费(因补签造成)'
      PRIMARY KEY (`sign_id`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='签到表';
    
    -- 每日签到表
    CREATE TABLE `t_sign_daily` (
      `sign_daily_id` varchar(64) NOT NULL COMMENT '主键ID',
      `sign_id` varchar(64) NOT NULL COMMENT '签到ID',
      `user_id` varchar(64) NOT NULL COMMENT '用户ID',
      `award` int(4) NOT NULL DEFAULT '0' COMMENT '本次签到奖励wb(补签扣除wb)',
      `sign_time` datetime NOT NULL COMMENT '签到/补签时间',
      `sign_type` int(2) unsigned NOT NULL COMMENT '签到类型:1-签到,2-补签'
      PRIMARY KEY (`sign_daily_id`) USING BTREE
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8 COMMENT='每日签到表';

    由于计算连续签到次数都是对同一张表的重复循环比较,这种场景比较适用 存储过程进行计算:

    CREATE DEFINER=`mysql`@`%` PROCEDURE `proc_sign_continue_times`(IN in_user_id VARCHAR(64), OUT isSinginToday Integer, OUT continueTimes INTEGER)
    BEGIN
    	
        SET @now = CURRENT_DATE(); 
    	SET @count = 0;
    	SET @isSinginToday = false;
    	set @row_number = 0;
    		
    	select count(*) into @count from (
    		select  ABS(datediff(signin_time, @now))  aa ,  -- 签到时间对比今天的差值
    				(@row_number:=@row_number + 1) bb    -- 排序字段 
    		from  t_sign_daily
    		where user_id  = in_user_id   and  ABS(datediff(sign_time, @now))  > 0  -- 条件排除今天的签到记录
    		and status = true	
    		ORDER BY aa asc
    	) T where aa = bb ;
    		
    	select COUNT(*) into @isSinginToday from  t_sign_daily  where user_id  = in_user_id and status = true and DATEDIFF(signin_time , @now ) = 0 ;-- 今天是否登录
    		
        -- 更新连续签到次数
    	update t_sign set continue_times = (select @count + @isSinginToday) where user_id  = in_user_id and status = true;
    		
    	select  @isSinginToday , -- 当天是否签到
    		    @count + @isSinginToday;  -- 连续签到n天	
    				
    END

      

    展开全文
  • 统计连续登陆5以上的用户

    千次阅读 2020-11-19 20:04:43
    前两面试的时候,被问到个sql的问题,有一张用户登录表,里面有用户名和登陆日期,现在要统计连续登陆5以上的用户,问如何实现。 面试的时候,下子就被难住了,后来百度了一下,后来百度了一下发现这个问题...

    统计连续登陆5天以上的用户

    前两天面试的时候,被问到一个sql的问题,有一张用户登录表,里面有用户名和登陆日期,现在要统计连续登陆5天以上的用户,问如何实现。
    面试的时候,一下子就被难住了,后来百度了一下,后来百度了一下发现这个问题问的还挺多,看来还是我接触的场景比较少。。。。
    我百度到了一个实现的思路感觉还是比较容易理解的,自己验证了一遍,在此就记录一下~

    先说一下思路:假设每个用户每天只登陆一次,当然其实每天的登陆多次也是一样的方法。
    1、先按用户名和登陆日期分组,按登陆日期升序排序,并写出序号
    2、用日期减去序号,因为如果是连续登陆的日期减去其对应的序号,得出的日期应该是一样的,比如20201118-1 和 20201119 -2 ,得出的都是20201117
    3、最后统计每个用户,减去后的日期相同的的次数,大于等于5的就是

    代码如下

    1、先建表,插入数据:

    create table user_login (user_id varchar(10),login_date date);
    
    insert into user_login  values('A',date_add(now(), interval -10 day))
    ,('A',date_add(now(), interval -9 day))
    ,('A',date_add(now(), interval -8 day))
    ,('A',date_add(now(), interval -7 day))
    ,('A',date_add(now(), interval -6 day))
    ,('A',date_add(now(), interval -4 day))
    ,('A',date_add(now(), interval -3 day))
    ,('B',date_add(now(), interval -11 day))
    ,('B',date_add(now(), interval -9 day))
    ,('B',date_add(now(), interval -8 day))
    ,('B',date_add(now(), interval -7 day))
    ,('C',date_add(now(), interval -10 day))
    ,('C',date_add(now(), interval -9 day))
    ,('C',date_add(now(), interval -8 day))
    ,('C',date_add(now(), interval -7 day))
    ,('C',date_add(now(), interval -6 day))
    ,('C',date_add(now(), interval -1 day));
    
    select * from user_login  ;
    +---------+------------+
    | user_id | login_date |
    +---------+------------+
    | A       | 2020-11-08 |
    | A       | 2020-11-09 |
    | A       | 2020-11-10 |
    | A       | 2020-11-11 |
    | A       | 2020-11-12 |
    | A       | 2020-11-14 |
    | A       | 2020-11-15 |
    | B       | 2020-11-07 |
    | B       | 2020-11-09 |
    | B       | 2020-11-10 |
    | B       | 2020-11-11 |
    | C       | 2020-11-08 |
    | C       | 2020-11-09 |
    | C       | 2020-11-10 |
    | C       | 2020-11-11 |
    | C       | 2020-11-12 |
    | C       | 2020-11-17 |
    +---------+------------+
    

    2、查出每个用户,以及每天的登陆时间减去序号后的日期

    select user_id,date_add(login_date, interval -rnn day) login_date
    from (
    select user_id,login_date, 
    case when user_id =@last_user then @rn:=@rn+1 
         else @rn:=1 
     end  as rnn
     ,@last_user:=user_id  
    from user_login a,
    (select @last_user:='' , @rn:=0 ) b
    order by user_id,login_date) T ;
    

    结果如下:

    +---------+------------+
    | user_id | login_date |
    +---------+------------+
    | A       | 2020-11-07 |
    | A       | 2020-11-07 |
    | A       | 2020-11-07 |
    | A       | 2020-11-07 |
    | A       | 2020-11-07 |
    | A       | 2020-11-08 |
    | A       | 2020-11-08 |
    | B       | 2020-11-06 |
    | B       | 2020-11-07 |
    | B       | 2020-11-07 |
    | B       | 2020-11-07 |
    | C       | 2020-11-07 |
    | C       | 2020-11-07 |
    | C       | 2020-11-07 |
    | C       | 2020-11-07 |
    | C       | 2020-11-07 |
    | C       | 2020-11-11 |
    +---------+------------+
    

    3、再统计日期出现的次数5次以上的(在上面的查询外面再套一层查询)

    select user_id ,count(*) from (
    select user_id,date_add(login_date, interval -rnn day) login_date
    from (
    select user_id,login_date, 
    case when user_id =@last_user then @rn:=@rn+1 
         else @rn:=1 
     end  as rnn
     ,@last_user:=user_id  
    from user_login a,
    (select @last_user:='' , @rn:=0 ) b
    order by user_id,login_date) T 
    ) T1
    group by user_id,login_date
    having count(*)>=5;
    

    结果如下:

    +---------+----------+
    | user_id | count(*) |
    +---------+----------+
    | A       |        5 |
    | C       |        5 |
    +---------+----------+
    

    下面也顺便写一下oracle的写法(顺便考虑了一下每天登陆多次的情况):

    with temp_aa as (
    select  user_id,login_date ,row_number() over(partition by user_id order by login_date ) rn
    from ( select user_id,trunc(login_date) login_date 
                from user_login
              group by user_id,trunc(login_date)
               order by user_id,trunc(login_date)
              ) T
    )
    select user_id,count(*) 
     from (select  user_id,login_date - rn as login_date  from temp_aa )
    group by user_id,login_date  
    having count(*) >=5;
    

    因为考虑了一下每天登陆多次的情况,所以多套了一层子查询,但是因为没有装oracle。所以也没办法验证。

    展开全文
  • 之前遇到的一个面试题,跟...(2)员工每次请假一天连续请10次,一共休假10天。(这里包括连续请假N次的情形) (3)员工从周一请假到周五,然后又从下周一请到下周五,两次请假一共10天。 针对这3中情况,我们可以

    之前遇到的一个面试题,跟大家分享一下。
    对接公司人力资源部门,需要统计连续休假超过10天的员工。
    表名:xiujia
    字段名: user_id , start_dt , end_dt
    员工id 休假开始日期 休假结束期

    这里连续休假可能有以下几种情形:
    (1) 从周一休息到下周五,去掉中间的周六日,一共休假10天。
    (2)员工每次请假一天,连续请10次,一共休假10天。(这里包括连续请假N次的情形)
    (3)员工从周一请假到周五,然后又从下周一请到下周五,两次请假一共10天。

    针对这3种情况,我们可以发现,计算请假天数的时候,要排除周六日,并且,如果两次请假中间只隔了一个周六日,也算连续请假。

    首先我们考虑连续的判断,假如我们把员工请假的日期都罗列出来,按照时间排序再加个行号,用休假日期减去行号,得到的那个日期,如果是相同的,那么就是连续的。如果遇到节假日,在算行号的时候要考虑节假日,然后计算连续休假天数的时候再把这个周六起给去掉。
    这个面试题,有的人看了思路也可能会很蒙,不知道怎么实现,下面直接看代码:

    select user_id,date_sub(dt_id,rn) as date_diff
    from (
    	select 
    		aa.user_id,aa.dt_id,aa.is_weekend,aa.is_holiday,row_number() over(partition by aa.user_id order by aa.dt_id) as rn 
    	from (
    		select a.user_id,b.dt_id,b.is_weekend,b.is_holiday
    		-- 找到所有的日期
    		(
    		select user_id ,min(start_dt) as min_start_dt ,max(end_dt) as max_end_dt 
    		from xiujia 
    		group by user_id 
    		) a 
    		left join (
    		select dt_id ,is_weekend,is_holiday 
    		from dim_dt 
    		) b 
    		on 1 = 1 
    		where b.dt_id >= a.min_start_dt
    		and b.dt_id <= a.max_end_dt
    	) aa  
    	left join (
    		select user_id ,start_dt ,end_dt ,lead(start_dt,1) over(partition by user_id order by start_dt) next_start_dt
    		from xiujia
    	) bb 
    	on aa.user_id = bb.user_id  
    	where aa.dt_id >= bb.start_dt and aa.dt_id <= bb.end_dt -- 在请假起止时间内
    	or ( aa.dt_id > bb.end_dt and aa.dt_id < next_start_dt and (aa.is_weekend = 1 or aa.is_holiday = 1) ) -- 不在请假起止时间内且为节假日
    ) t 
    where is_weekend = 0 and is_holiday = 0 -- 先排序编号,再把节假日去掉
    group by user_id,date_sub(dt_id,rn)
    having count(1) >=  10
    

    结论:这个题比较考验思维,首先面试官可能要你想到休假的几种情形,然后再思考怎么实现能够兼容上面这三种情形。代码没经过测试,如有问题欢迎指正~

    展开全文
  • 一天一道LeetCode

    2020-05-30 16:58:08
    一天一道LeetCode(1-30题) 文章目录一天一道LeetCode(1-30题)1.两数之和2.两数相加3.无重复字符的最长子串4.寻找两个正序数组的中位数(未解决)5.最长回文子串6.Z字形变换7.整数反转8.字符串转换整数(atoi)9....

    一天一道LeetCode(1-30题)

    1.两数之和

    题目:

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍

    示例

    给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
    

    思路

    enumerate函数可以将列表变为以下标为键,列表元素为值的字典,通过循环可以分别拿出列表中对应的元素和下标,同时构建一个哈希表,判断目标值减去当前值是否存在于表中,如果存在,则返回对应元素下标,若不存在,则将当前元素存入表中

    class Solution:
        def twoSum(self,nums,target):
            dic={}
            for i,num in enumerate(nums):
                if (target - num) in dic:
                    return [i,dic[target - num]]
                dic[num] = i
    

    2.两数相加

    题目

    给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

    如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

    您可以假设除了数字 0 之外,这两个数都不会以 0 开头

    示例

    输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出:7 -> 0 -> 8
    原因:342 + 465 = 807
    

    思路:直接从两个链表中分别取出对应数字,相加,如果这两个数字相加的结果大于10,则需要进位

    ​ 重复上述操作,直至链表尾,如果此时进位标记仍不为0(比方说5+5),则结果链表的下一个节点值设置为1

    class Solution:
        def addTwoNumbers(self,l1,l2):
            head = ListNode(0)
            node = head
            carry = 0
            while l1 or l2:
                x = l1.val if l1 else 0
                y = l2.val if l2 else 0
                sum = x + y + carry
                carry = sum // 10
                node.next = ListNode(sum % 10)
                if l1:
                    l1 = l1.next
                if l2:
                    l2 = l2.next
                node=node.next
            if carry != 0:
                node.next = ListNode(1)
            return head.next
    

    3.无重复字符的最长子串

    题目

    给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度

    示例

    输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3
    
    输入: "bbbbb"
    输出: 1
    解释: 因为无重复字符的最长子串是 "b",所以其长度为 1
    
    输入: "pwwkew"
    输出: 3
    解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
         请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串
    

    思路

    • 1.使用数组作为滑动窗口,遍历字符串,如果当前字符不在滑动窗口中,则直接使用当前字符扩展窗口,如果当前字符在滑动窗口中,则从窗口中移除重复字符及之前的字符串部分,再扩展窗口
    class Solution:
        def lengthOfLongestSubstring(self,s):
            if not s:
                return 0
            window = []
            max_length = 0
            for c in s:
                if c not in window: # 当前字符不在滑动窗口中,直接扩展
                    window.append(c)
                else:  # 当前字符在滑动窗口中,移除字符之前的部分,再扩展
                    window[:] = window[window.index(x) + 1:]
                    window.append(c)
            max_length = max(len(window),max_length)
        return max_length if max_length != 0 else len(s)
    
    • 2.使用双指针,记录滑动窗口其实和结束的索引值,可以减少数组的增删操作,思想和上面的方法一致,但是用指针位移及从原数组中截取,代替原来的窗口元素增删操作
    class Solution:
        def lengthOfLongestSubstring(self,s):
            if not s:
                return 0
            max_length = 0
            left, right = 0, 0
            for i, c in enumerate(s):
                if c not in s[left:right]:
                    right += 1
                else:
                    left += s[left:right].index(c) + 1
                    right += 1
                max_length = max(right - left, max_length)
            return max_length if max_length != 0 else len(s)
    
    • 3.使用字典记录任意字符最近的索引值,如果字典中已经存在当前字符,则当前字符是重复字符,如果当前字符索引值大于“可抛弃字符串的索引尾值”,则当前字符在需要处理的范围内
    class Solution:
        def lengthOfLongestSubstring(self,s):
            # 可抛弃字符串的索引尾值 - 字符串索引值,该索引值以及之前的字符串都属于重复字符串中的一部分,不再计算中涉及
            ignore_str_index_end = -1
            dic = {}
            max_length = 0
            for i, c in enumerate(s):
                if c in dic and dic[c] > ignore_str_index_end:
                    ignore_str_index_end = dic[c]
                    dic[c] = i
                else:
                    dic[c] = i
                    max_length = max(i - ignore_str_index_end, max_length)
            return max_length
    

    4.寻找两个正序数组的中位数(未解决)

    题目

    给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。

    请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

    你可以假设 nums1 和 nums2 不会同时为空

    示例

    nums1 = [1, 3]
    nums2 = [2]
    
    则中位数是 2.0
    
    nums1 = [1, 2]
    nums2 = [3, 4]
    
    则中位数是 (2 + 3)/2 = 2.5
    

    思路

    题目要求时间复杂度为 O ( log ⁡ ( m + n ) ) O(\log(m+n)) O(log(m+n)),想到应该用二分法

    利用中位数的性质和左右中位数之间的关系来把所有的数先分成两堆,然后在两堆的边界返回答案

    class Solution:
        def findMedianSortedArrays(self,nums1,nums2):
            m = len(nums1)
            n = len(nums2)
            # 让nums2是更长的那个数组
            if m > n:
                nums1, nums2, m, n = nums2, nums1, n, m
            if n == 0:
                raise ValueError
            # nums1中index在imid左边的都被分配到左堆,nums2中jmid左边的都被分到左堆
            imin, imax = 0, m
            while(imin <= imax):
                imid = imin + (imax - imin) // 2
                jmid = (m + n - 2 * imid) // 2
                if(imid > 0 and nums1[imid - 1] > nums2[jmid]):
                    imax = imid - 1
                elif(imid < m and nums2[jmid - 1] > nums1[imid]):
                    imin = imid + 1
                else:
                    if(imid == m): minright = nums2[jmid]
                    elif(jmid == n): minright = nums1[imid]
                    else:
                        minright = min(nums1[imid], nums2[jmid])
                    if(imid == 0): maxleft = nums2[jmid - 1]
                    elif(jmid == 0): maxleft = nums1[imid - 1]
                    else:
                        maxleft = max(nums1[imid - 1], nums2[jmid - 1])
                    if((m + n) % 2 == 1):
                        return minright
                    return (maxleft + minright) / 2
    

    5.最长回文子串

    题目

    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000

    示例

    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案
    
    输入: "cbbd"
    输出: "bb"
    

    思路

    • 1.动态规划

      1)特判,当s的长度为1或0时,返回s

      2)初始化最长会问子串的开始索引start和最长长度max_len = 1

      3)初始化dp数组,为n x n,全部初始化为False,dp[i][j]表示s[i - j]是否为回文串

      4)将dp中,所有单个字符处都是回文串,置为True,s中若相邻的字符串相同,则同样将这两个字符对应的位置置为True,即遍历s:

      • dp[i][i] = True,表示单个字符一定是回文串
      • 若i < n - 1 and s[i] == s[i + 1],表示相邻的字符相同,则dp[i][i + 1] = True,并更新最长回文子串的开始索引start = i 和长度max_len = 2

      5)此时,从长度3开始遍历,遍历区间[3, n + 1),表示所有最长子串可能的长度,因为场地为1和2的已经在上一步找完了,对于可能的长度L:

      • 从索引0开始遍历,遍历区间[0, n - l + 1],对于开始索引i
        • 令子串右侧索引r = i + l - 1
        • 若满足s[i] == s[r] and dp[i + 1][r - 1] == True,表示子串s[s + 1,…,r - 1]为回文且s[i] == s[r],说明s[i,…,r]也是回文,则此时,更新dp[i][r] = True,并更新最长子串开始索引start = i 和长度max_len = l

      6)返回s[start, …, start + max_len - 1]

    class Solution:
        def longestPalindrome(self,s):
            if(not s or len(s) == 1):
                return s
            n = len(s)
            dp = [[False]*n for _ in range(n)]
            max_len = 1
            start = 0
            for i in range(n):
                dp[i][i] = True
                if(i < n - 1 and s[i] == s[i + 1]):
                    dp[i][i + 1] = True
                    start = i
                    max_len = 2
            for l in range(3,n + 1):
                for i in range(n + 1 - l):
                    r = i + l - 1
                    if(s[i] == s[r] and dp[i + 1][r - 1]):
                        dp[i][r] = True
                        start = i
                        max_len = l
            return s[start:start + max_len]
    
    • 2.中心扩展法

      回文串的中心可能是一个字符串或者两个字符串,因此,我们遍历每一个字符和每一对相邻的字符

      1)特判

      2)初始化最长回文子串的开始索引和结束索引start = 0,end = 0

      3)扩展函数expand( l , r l,r l,r), l l l表示传入中心字符的左界,r表示传入字符中心的右界

      • 若满足条件0 <= l l l and r < n and s[ l l l] == s[r],执行循环:向两侧扩展 l l l -=1,r += 1
      • 返回回文串的长度r - l l l - 1

      4)遍历s,遍历区间[0, n)

      • 中心为一个字符的扩展后长度len_1 = expand(i,i)
      • 中心为两个字符的扩展后长度len_2 = expand(i, i + 1)
      • 较长的子串长度len_long = max(len_1, len_2)
      • 若满足len_long > end - start + 1,表示当前长度大于之前的最长长度,更新start和end
        • start = i - (len_long - 1) // 2
        • end = i + len_long // 2

      5)返回s[start,…, end]

    class Solution:
        def longestPalindrome(self,s):
            def expand(l,r):
                while(0 <= l and r < n and s[l] == s[r]):
                    l -= 1
                    r += 1
                return r - l - 1
            if(not s or len(s) == 1):
                return s
            n = len(s)
            start = 0
            end = 0
            for i in range(n):
                len1 = expand(i,i)
                len2 = expand(i,i + 1)
                len_long = max(len1,len2)
                if(len_long > end - start):
                    start = i- (len_long - 1) // 2
                    end = i + (len_long) // 2
            return s[start:end + 1]
    
    • 3.双指针 + 滑动窗口

      初始化两个指针left,right,遍历字符串

      最开始的情况是第一个字符的索引和右索引相等(都为0),需要判断[0: 2]这段字符串是否是回文字符串(因为1个字符的情况不用讨论),如果这2个字符是回文字符,则更新左指针为当前字符索引和右指针之差(其实这个值为0,目的是为了下次判断还是从头开始,接着判断[0: 3]的情况),同时更新右指针(向右移动一位),如果这两个字符不是回文字符串([0: 2]的情况不是回文串),则开始判断[0: 3]的情况,如果这3个字符是回文串,则更新左右指针

    class Solution:
        def longestPalindrome(self, s):
            str_length = len(s)
            left, right = 0, 0
            for i in range(str_length):
                if i-right >= 1 and s[i-right-1:i+2]==s[i-right-1:i+2][::-1]:
                    left=i-right-1
                    right+=2
                    continue
                if i-right>=0 and s[i-right:i+2]==s[i-right:i+2][::-1]:
                    left=i-right
                    right+=1
            return s[left:left+right+1]
    

    6.Z字形变换

    题目

    将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列

    比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时,排列如下:

    L   C   I   R
    E T O E S I I G
    E   D   H   N
    

    之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"LCIRETOESIIGEDHN"

    示例

    输入: s = "LEETCODEISHIRING", numRows = 3
    输出: "LCIRETOESIIGEDHN"
    
    输入: s = "LEETCODEISHIRING", numRows = 4
    输出: "LDREOEIIECIHNTSG"
    解释:
    
    L     D     R
    E   O E   I I
    E C   I H   N
    T     S     G
    

    思路

    设numRows行字符串分别为s1,s2,…,sn,则容易发现:按顺序遍历字符串s时,每个字符c在Z字形中对应的行索引先从s1增大至sn,再从sn减小至s1…,如此反复

    因此,解决方案为:模拟这个行索引的变化,在遍历s中把每个字符填到正确的行res[i]

    按顺序遍历字符串s:

    • 1.res[i] += c:把每个字符c填入对应行 s i s_i si
    • 2.i += flag:更新当前字符c对应的行索引
    • 3.flag = - flag:在达到Z字形转折点时,执行反向
    class Solution:
        def convert(self,s,numRows):
            if numRows < 2:return s
            # 创建和行数对应的空列表
            res = ['' for _ in range(numRows)]
            i, flag = 0, -1
            # 往每行的空列表里填上元素
            for c in s:
                res[i] += c
                if i == 0 or i == numRows - 1:
                    flag = -flag
                i += flag
            return ''.join(res)
    

    7.整数反转

    题目

    给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转

    示例

    输入: 123
    输出: 321
    
    输入: -123
    输出: -321
    
    输入: 120
    输出: 21
    

    注意:假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [− 2 31 2^{31} 231, 2 31 2^{31} 231-1]。请根据这个假设,如果反转后整数溢出那么就返回 0

    class Solution:
        def reverse(self,x):
            temp = x
            temp = str(abs(temp))
            res = int(temp[::-1])
            if res < 2**31 - 1 and -res > -2**31:
                return res if x > 0 else - res
            return 0
    

    8.字符串转换整数(atoi)

    题目

    请你来实现一个 atoi 函数,使其能将字符串转换成整数。

    首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下:

    • 如果第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字字符组合起来,形成一个有符号整数。
    • 假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成一个整数。
    • 该字符串在有效的整数部分之后也可能会存在多余的字符,那么这些字符可以被忽略,它们对函数不应该造成影响。
    • 注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。

    在任何情况下,若函数不能进行有效的转换时,请返回 0

    提示

    本题中的空白字符只包括空格字符 ’ ’ 。
    假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,请返回 INT_MAX (231 − 1) 或 INT_MIN (−231)

    示例

    输入: "42"
    输出: 42
    
    输入: "   -42"
    输出: -42
    解释: 第一个非空白字符为 '-', 它是一个负号。
         我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42
    
    输入: "4193 with words"
    输出: 4193
    解释: 转换截止于数字 '3' ,因为它的下一个字符不为数字
    
    输入: "words and 987"
    输出: 0
    解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
         因此无法执行有效的转换
    
    输入: "-91283472332"
    输出: -2147483648
    解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
         因此返回 INT_MIN (−231)
    
    class Solution:
        def myAtoi(self,str):
            INT_MAX = 2**31 - 1
        	INT_MIN = -2**31
            str = str.lstrip()
            import re
            pattern = r'^[\+\-]?\d+'
            match = re.match(pattern,str)
            if match:
                res = int(match[0])
                print(res)
                return min(max(res, INT_MIN), INT_MAX)
            return 0
    

    9.回文数

    题目

    判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数

    示例

    输入: 121
    输出: true
    
    输入: -121
    输出: false
    解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数
    
    输入: 10
    输出: false
    解释: 从右向左读, 为 01 。因此它不是一个回文数
    
    class Solution:
        def isPalindrome(self,x):
            x = str(x)
            return x == x[::-1]
    

    10.正则表达式匹配

    题目

    给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.''*' 的正则表达式匹配

    '.' 匹配任意单个字符
    '*' 匹配零个或多个前面的那一个元素
    

    说明

    • s 可能为空,且只包含从 a-z 的小写字母。
    • p 可能为空,且只包含从 a-z 的小写字母,以及字符 .*

    示例

    输入:
    s = "aa"
    p = "a"
    输出: false
    解释: "a" 无法匹配 "aa" 整个字符串
    
    输入:
    s = "aa"
    p = "a*"
    输出: true
    解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次
    
    输入:
    s = "ab"
    p = ".*"
    输出: true
    解释: ".*" 表示可匹配零个或多个('*')任意字符('.')
    
    输入:
    s = "aab"
    p = "c*a*b"
    输出: true
    解释: 因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"
    
    输入:
    s = "mississippi"
    p = "mis*is*p*."
    输出: false
    

    思路

    动态规划

    • 状态定义:

      • 设动态规划网格dp,dp[i][j]代表字符串s中前i个字符和p中前j个字符是否匹配,值为True或False
      • 记s第i个字符记为s[m] == s[i - 1];p第j个字符记为p[n] == p[j - 1]
      • 记s和p的长度分别为ls, lp
    • 初始状态:

      • 初始化第一行:dp[0][j] = dp[0][j - 2] and p[j - 1] == ‘*’
      • Tips:p第j个字符记为‘*’,且dp[0][j - 2] 为True
    • 转移方程:

      1.当p[n]为‘*’时:

      ​ 1.当p[n - 1]为‘.'或s[m] == p[n - 1]时:dp[i][j] = dp[i - 1][j];

      ​ Tips:此两种情况代表s[m]和p[n - 1]可以匹配,等价于无s[m]的状态dp[i - 1][j]

      ​ 2.否则:dp[i][j] = dp[i][j - 2];

      ​ Tips:此情况代表s[m]和p[n - 1]无法匹配,p[n - 1]p[n]的组合必须出现0次,等价于没有p[n - 1]p[n]时的状态dp[i][j - 2]

      2.否则,当p[n]为’.‘,或s[m] == p[n]时:dp[i][j] = dp[i - 1][j - 1];

      ​ Tips:此情况代表s[m]和p[n]直接匹配,当前状态等价于未匹配此两字符前的状态dp[i - 1][j - 1]

    • 返回值:

      字符串s中前ls个字符和p中前lp个字符是否匹配,即dp[ls][lp]

    class Solution:
        def isMatch(self, s, p):
            ls, lp = len(s), len(p)
            dp = [[False for _ in range(lp + 1)] for _ in range(ls + 1)]
            dp[0][0] = True
            for j in range(2, lp + 1):
                dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'
            for i in range(1, ls + 1):
                for j in range(1, lp + 1):
                    m, n = i - 1, j - 1
                    if p[n] == '*':
                        if s[m] == p[n - 1] or p[n - 1] == '.':
                            dp[i][j] = dp[i][j - 2] or dp[i - 1][j]
                        else:dp[i][j] = dp[i][j - 2]
                    elif s[m] == p[n] or p[n] == '.':
                        dp[i][j] = dp[i - 1][j - 1]
            return dp[-1][-1]
    

    11.盛水最多的容器

    题目

    给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水

    说明:你不能倾斜容器,且n的值至少为2

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8ItyL0ad-1590828851384)(C:\Users\pxr\Desktop\一些文件夹\md图片\盛水最多的容器.jpg)]

    图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49

    实例

    输入:[1,8,6,2,5,4,8,3,7]
    输出:49
    

    思路

    双指针 + 动态规划

    初始化两个指针,分别指向数组的头和尾,并求取此时容器的容积(木桶原理,以最短的长度为标准),然后分别移动左、右指针,同时动态维护一个最大容积,如果此时的容积大于程序维护的容积,则替换

    class Solution:
        def maxArea(self, height):
            left, right = 0, len(height) - 1
            max_area= 0 
            while left < right:
                width = right - left
                area = width * min(height[left], height[right])
                if area > max_area:
                    max_area = area
                if height[left] < height[right]:
                    left += 1
                else: right -= 1
            return max_area
    

    12.整数转罗马数字

    题目

    罗马数字包含以下七种字符: IVXLCDM

    字符          数值
    I             1
    V             5
    X             10
    L             50
    C             100
    D             500
    M             1000
    

    例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

    通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况

    I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
    X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
    C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900
    

    给定一个整数,将其转为罗马数字。输入确保在 1 到 3999 的范围内

    实例

    输入: 3
    输出: "III"
    
    输入: 4
    输出: "IV"
    
    输入: 9
    输出: "IX"
    
    输入: 58
    输出: "LVIII"
    解释: L = 50, V = 5, III = 3
    
    输入: 1994
    输出: "MCMXCIV"
    解释: M = 1000, CM = 900, XC = 90, IV = 4
    

    思路

    贪心法

    我们每次尽量使用最大的数字来表示,所以,将哈希表按照从大到小的顺序排列,然后遍历哈希表,直到完成整个输入

    class Solution:
        def intToRoman(self, num):
            hashmap = {1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I'}
    		res = ''
            for key in hashmap:
                if num // key != 0 :
                    count = num // key
                    res += hashmap[key] * count
                    num %= key
            return res
    

    13.罗马数字转整数

    题目

    同上题,只是输入是罗马数字,需要转为整数

    思路

    通过观察,只有在遇到特殊情况时,两个字符中左边的字符小于右边的字符,且等于右边的字符代表的数字减左边代表的数

    因此,如果s[i] < s[i+1],就将结果减去s[i]代表的数字,否则,将结果加上s[i]代表的数字

    class Solution:
        def romanToInt(self, s):
            Roman2Int = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
            res = 0
            length = len(s) - 1 # -1的目的是防止越界,因为需要判定index + 1
            for index in range(length):
                if Roman2Int[s[index]] < Roman2Int[s[index + 1]]:
                    res -= Roman2Int[s[index]]
                else:
                    res += Roman2Int[s[index]]
            return res + Roman2Int[s[-1]]
    

    14.最长公共前缀

    题目

    编写一个函数来查找字符串数组中的最长公共前缀。

    如果不存在公共前缀,返回空字符串 ""

    实例

    输入: ["flower","flow","flight"]
    输出: "fl"
    
    输入: ["dog","racecar","car"]
    输出: ""
    解释: 输入不存在公共前缀
    

    说明:所有输入只包含小写字母 a-z

    思路

    先把字符串数组排序(根据a-z的顺序排序),然后取出第一个和最后一个字符串,找出他们的相同前缀就是整个数组的相同前缀

    class Solution:
        def longestCommonPrefix(self,strs):
            if not strs:
                return ''
            strs = sorted(strs)
            first, last = strs[0], strs[-1]
            length = min(len(first), len(last))
            ans = ''
            for i in range(length):
                if first[i] == last[i]:
                    res += first[i]
                break
            return res
    

    15.三数之和

    题目

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

    注意:答案中不可以包含重复的三元组

    实例

    给定数组 nums = [-1, 0, 1, 2, -1, -4],
    
    满足要求的三元组集合为:
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]
    

    思路

    排序 + 双指针(其实是固定了一个指针,另外有两个活动的指针)

    1.特判

    2.对数组进行排序

    3.遍历排序后的数组:

    • 若nums[i] > 0:因为已经排好序,所以后面不可能有三个数加和等于0,直接返回结果
    • 对于重复元素:跳过,避免出现重复解
    • 令左指针 L = i + 1,右指针 R = n - 1,当L < R 时,执行循环:
      • 当nums[i] + nums[L] +nums[R] == 0,执行循环,判断左界和右界是否和下一位置重复,去除重复解,并同时将L, R移到下一位置,寻找新的解
      • 若和大于0,说明nums[R] 太大,R左移
      • 若和小于0,说明nums[L] 太小,L右移
    class Solution:
        def threeSum(self, nums):
            n = len(nums)
            res = []
            if not nums or n < 3:
                return []
            nums = sorted(nums)
            for i in range(n):
                if nums[i] > 0:
                    return res
                # 去除重复解的步骤
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                L = i + 1
                R = n - 1
                while (L < R):
                    if nums[i] + nums[L] + nums[R] == 0:
                        res.append([nums[i], nums[L], nums[R]])
                        # 去除重复解的步骤
                        while (L < R and nums[L] == nums[L + 1]):
                            L += 1
                        while (L < R and nums[R] == nums[R - 1]):
                            R -= 1
                        L += 1
                        R -= 1
                    elif nums[i] + nums[L] + nums[R] > 0 :
                        R -= 1
                    else:
                        L += 1
            return res
    

    16.最接近的三数之和

    题目

    给定一个包括n个整数的数组nums和一个目标值target,找出nums中的三个整数,使得他们的和与target最接近,返回这三个整数的和,假定每组输入只存在唯一答案

    实例

    例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
    
    与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2)
    

    思路

    对数组排序(这点很重要!),思路和上一题类似

    class Solution:
        def threeSumClosest(self, nums, target):
            n = len(nums)
            nums = sorted(nums)
            res = 2**10 # 这里是随便给的一个结果,但是不能太小
            for i in range(n):
                left, right = i+1, n-1
                while left < right:
                    cur = nums[i] + nums[left] + nums[right]
                    if cur == target:
                        return target
                    if abs(cur - target) < abs(res - target):
                        res = cur
                    if cur - target < 0:
                        left += 1
                    else: right -= 1
            return res
    

    17.电话号码的字母组合

    题目

    给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

    给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母

    在这里插入图片描述

    实例

    输入:"23"
    输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
    

    思路

    1.当出现“所有组合”等类似字眼,可能会用到回溯法

    定义函数backtrack(combination, nextdigits),当nextdigit非空时,对于nextdigit[0]中的每一个字母letter,执行回溯backtrack(combination + letter, nextdigit[1:]),直到nextdigit为空,最后将combination加入到结果中

    class Solution:
        def letterCombinations(self, digits):
            if not digits:
                return []
            phone = {
                '2':['a', 'b', 'c'],
                '3':['d', 'e', 'f'],
                '4':['g', 'h', 'i'],
                '5':['j', 'k', 'l'],
                '6':['m', 'n', 'o'],
                '7':['p', 'q', 'r', 's'],
                '8':['t', 'u', 'v'],
                '9':['w', 'x', 'y', 'z']
            }
        def backtrack(combination, nextdigit):
            if len(nextdigit) == 0:
                res.append(combination)
            else:
                for letter in phone[nextdigit[0]]:
                    backtrack(combination + letter, nextdigit[1:])
                    
        res = []
        backtrack('', digits)
        return res
    

    2.队列

    先将输入的digits中第一个数字对应的每个字母入队,然后将出队的元素与第二个数字对应的每个字母组合后入队,直到遍历到digits的结尾,最后队列中的元素就是所求结果

    class Solution:
        def letterCombination(self, digits):
            if not digits:
                return []
            phone = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
            queue = ['']
            for digit in digits:
                for _ in range(len(queue)):
                    tmp = queue.pop(0)
                    # 因为数字是从2开始的,而数组的下标是从0开始,所以需要-2
                    for letter in phone[int(digit) - 2]:
                        queue.append(tmp + letter)
            return queue
    

    18.四数之和

    题目

    给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组

    注意:答案中不可以包含重复的四元组

    实例

    给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。
    
    满足要求的四元组集合为:
    [
      [-1,  0, 0, 1],
      [-2, -1, 1, 2],
      [-2,  0, 0, 2]
    ]
    

    思路

    在三数之和的基础上,依然用双指针法

    1.先排序,指针依次是p, k, i, j,如果nums[p] + 3*nums[p + 1] > target,因为nums升序排列,所以之后的数肯定都大于target,所以,以后不会有比这个更小的数了,直接break

    2.如果nums[p] + 3*nums[-1] < target,那么当前的nums[p]加其余三个数一定小于target,所以直接下一位即可

    3.k和p的判断一样,只是将3变成了2,target变成了target - nums[p]

    同样,为了避免重复结果,某个指针遇到相同的数需要直接跳过

    class Solution:
        def fourSum(self, nums):
            nums = sorted(nums)
            n = len(nums)
            res = []
            p = 0 # p, k, i, j
            while p < n - 3:  
                if nums[p] + 3 * nums[p + 1] > target: 
                    break  
                if nums[p] + 3 * nums[-1] < target:           
                    while p < n - 4 and nums[p] == nums[p + 1]:
                         p += 1
                    p += 1
                    continue
                k = p + 1
                while k < n - 2:   # k 和 p 的判断是一样的
                    if nums[p] + nums[k] + 2 * nums[k + 1] > target: 
                        break
                    if nums[p] + nums[k] + 2 * nums[-1] < target: 
                        while k < n - 3 and nums[k] == nums[k + 1]:
                            k += 1
                        k += 1
                        continue
                    i = k + 1
                    j = n - 1
                    new_target = target - nums[p] - nums[k]
                    while i < j:
                        if nums[i] + nums[j] > new_target:
                            j -= 1
                        elif nums[i] + nums[j] < new_target: 
                            i += 1
                        else:
                            res.append([nums[p],nums[k],nums[i],nums[j]])
                            i += 1
                            j -= 1
                            while i < j and nums[i] == nums[i - 1]: 
                                i += 1 
                            while i < j and nums[j] == nums[j + 1]: 
                                j -= 1 
                    while k < n - 3 and nums[k] == nums[k + 1]: 
                        k += 1
                    k += 1
                while p < n - 4 and nums[p] == nums[p + 1]: 
                    p += 1
                p += 1
            return res
    

    19.删除链表的倒数第N个节点

    题目

    给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点

    实例

    给定一个链表: 1->2->3->4->5, 和 n = 2.
    
    当删除了倒数第二个节点后,链表变为 1->2->3->5
    

    说明:给定的n保证是有效的

    思路

    1.循环两次,第一次拿到节点个数,第二次删除对应节点

    class Solution:
        def removeNthFromEnd(self, head, n):
            count = 0
            temp = head
            while temp:
                count += 1
                temp = temp.next
            # 最后还要-1是因为计数是从0开始
            n = count - n - 1
            
            temp = head
            # 如果要删除的节点是头结点
            if n == -1:
                head = head.next
            else:
                while n:
                    temp = temp.next
                    n -= 1
                temp.next = temp.next.next
            return head
    

    2.双指针法

    第一个指针先走n步,然后两个指针同时开始走,当第一个指针走到末尾的时候,此时第二个指针对应的点就是要删除的点

    class Solution:
        def removeNthFromEnd(self, head, n):
            # 哨兵节点,防止头结点为空的情况
            node = ListNode(0)
            node.next = head
            first = second = node
            # 这里要+1是因为计数从0开始,而删除倒数节点则是直接计数
            for _ in range(n + 1):
                first = first.next
            while first:
                first = first.next
                second = second.next
            second.next = second.next.next
            return node.next
    

    20.有效的括号

    题目

    给定一个只包括 '('')''{''}''['']' 的字符串,判断字符串是否有效

    有效字符串需满足:

    1.左括号必须用相同类型的左括号闭合

    2.左括号必须以正确的顺序闭合

    注意:空字符串可以被认为是有效字符串

    示例

    输入: "()"
    输出: true
    
    输入: "()[]{}"
    输出: true
    
    输入: "(]"
    输出: false
    
    输入: "([)]"
    输出: false
    
    输入: "{[]}"
    输出: true
    

    思路

    利用栈的FILO特性解决

    class Solution:
        def isValid(self, s):
            hashmap = {'(':')', '[':']', '{':'}', '?':'?'}
            # 这里是随意添加了一个值在栈中,防止pop的时候空栈
            left_stack = ['?']
            for ele in s:
                if ele in hashmap:
                    left_stack.append(ele)
                else:
                    left = left_stack.pop()
                	if hashmap[left] != ele:
                    	return False
            return len(left_stack) == 1
    

    21.合并两个有序链表

    题目

    将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

    实例

    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4
    

    思路

    1.直接法,两个链表都是升序的,找到头结点最小的链表,是新链表的表头,然后依次将元素升序连接

    class Solution:
        def mergeTwoLists(self, l1, l2):
            if not l1:
                return l2
            if not l2:
                return l1
            # 创建一个哑节点,作为链表的开头(当中的数字不会被读取)
            temp = ListNode(-1)
            # 创建一个游标,用来遍历节点
            node = temp
            while l1 and l2:
                if l1.val <= l2.val:
                    node.next = l1
                    l1 = l1.next
                else:
                    node.next = l2
                    l2 = l2.next
                node = node.next
            node.next = l1 if l1 else l2
            return temp.next
    

    2.递归

    class Solution:
        def mergeTwoLists(self, l1, l2):
            if not l1: return l2
            if not l2: return l1
            if l1.val <= l2.val:
                l1.next = self.mergeTwoLists(l1.next, l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1, l2.next)
                return l2
    

    22.括号生成

    题目

    数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合

    实例

    输入:n = 3
    输出:[
           "((()))",
           "(()())",
           "(())()",
           "()(())",
           "()()()"
         ]
    

    思路

    回溯法(当拿到一个问题,如果感觉不穷举就没法知道答案,就需要用回溯法)

    回溯法是一个剪枝了的二叉树,我们要的结果是可以good leaf,如果不满足good leaf,就继续向下搜索,搜索的时候要满足一定条件

    在这里插入图片描述

    可以看到,最后的五条黑线就是最终结果,其中左分支都是添加左括号,右分支都是添加右括号

    在什么时候添加左括号?,很明显,最多能添加n个左括号,在递归调用的时候,在能传递到最底层的公用字符串中先添加“(”,然后left - 1,递归调用即可

    什么时候添加右括号?,当左括号的个数大于右括号的个数时添加右括号

    总之,向下搜索需要满足两个条件:

    1.插入数量不超过n

    2.可以插入)的前提是(的数量大于)

    回溯法的代码套路:使用两个变量res和path,res表示最终的结果,path保存已经走过的路径,如果搜到一个状态满足题目的要求,就把path放到res中

    class Solution:
        def generateParenthesis(self, n):
            res = []
            self.dfs(res, n, n, '')
            return res
        
        def dfs(self, res, left, right, path):
            if left == 0 and right == 0:
                res.append(path)
                return 
            if left > 0:
                self.dfs(res, left - 1, right, path + '(')
            if left < right:
                self.dfs(res, left, right - 1, path + ')')
    

    23.合并K个排序链表

    题目

    合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度

    实例

    输入:
    [
      1->4->5,
      1->3->4,
      2->6
    ]
    输出: 1->1->2->3->4->4->5->6
    

    思路

    1.暴力法

    • 遍历所有链表,将所有节点的值放到一个数组
    • 将这个数组排序,然后遍历所有元素得到正确顺序的值
    • 用排序后的数组创建一个新的有序列表
    class Solution:
        def mergeKLists(self, lists):
            nodes = []
            head = point = ListNode(0)
            for ele in lists:
                while ele:
                    nodes.append(ele.val)
                    ele = ele.next
            nodes = sorted(nodes)
            for x in nodes:
                point.next = ListNode(x)
                point = point.next
            return head.next
    

    2.堆排序/优先队列

    利用Python的heapq模块进行堆排序

    补充

    堆就是用数组实现的二叉树,所以它没有使用父指针或者子指针,堆根据”堆属性“来排序,“堆属性”决定了树中节点的位置,堆的特点就是FIFO(先进先出)

    堆的常用方法

    • 构建优先队列
    • 支持堆排序
    • 快速找出一个集合中的最小值(或者最大值)

    堆属性

    堆分为两种:最大堆,和最小堆,两者的差别在于节点的排列方式

    最大堆:父节点的值比每一个子节点的值都要大,所以总是将最大值存放在树的根节点

    最小堆:父节点的值比每一个子节点的值都要小,所以总是将最小值存放在树的根节点

    以上就是所谓的“堆属性”,并且这个属性对堆中的每一个节点都成立,堆常常被当做优先队列使用,因为可以快速访问到“最重要”的元素

    注意

    堆的根节点中存放的是最大或者最小元素,但是其他节点的排序顺序是未知的。例如,在一个最大堆中,最大的那一个元素总是位于 index 0 的位置,但是最小的元素则未必是最后一个元素。唯一能够保证的是最小的元素是一个叶节点,但是不确定是哪一个

    堆排序

    在这里插入图片描述

    同时,对堆中的节点按层进行编号,将这种逻辑结构映射到数组中就是下面这样

    arr: [50, 45, 40, 20, 25, 35, 30, 10, 15]

    这个数组从逻辑上讲就是一个堆结构

    大顶堆:arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

    小顶堆:arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

    堆排序的基本思想与步骤

    堆排序的基本思想:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点,将其与末尾元素进行交换,此时末尾元素就是最大值,然后将n - 1个元素重新构造成一个堆,这样会得到n个元素的次小值,如此反复,可以得到一个有序序列

    class Solution:
        def mergeKLists(self, lists):
            import heapq
            head = point = ListNode(0)
            heap = []
            for ele in lists:
                while ele:
                    heapq.heappush(heap, ele.val)
                    ele = ele.next
            while heap:
                val = heappop(heap)
                point.next = ListNode(val)
                point = point.next
            point.next = None
            return head.next
    

    24.两两交换链表中的节点

    题目

    给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

    你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换

    实例

    给定 1->2->3->4, 你应该返回 2->1->4->3
    

    在这里插入图片描述

    class Solution:
        def swapPairs(self, head):
            thead = ListNode(-1)
            thead.next = head
            c = thead
            while c.next and c.next.next:
                a, b = c.next, c.next.next
                c.next, a.next = b, b.next
                b.next = a
                c = c.next.next
            return thead.next
    

    25.K个一组反转链表

    题目

    给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

    k 是一个正整数,它的值小于或等于链表的长度。

    如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序

    实例

    给你这个链表:1->2->3->4->5
    
    当 k = 2 时,应当返回: 2->1->4->3->5
    
    当 k = 3 时,应当返回: 3->2->1->4->5
    

    说明

    • 你的算法只能使用常数的额外空间。
    • 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换

    思路

    需要把链表节点按照k个一组分组,所以可以使用一个指针head,依次指向每组的头结点,这个指针每次向前移动k步,直至链表结尾

    对于每个分组,我们先判断它的长度是否大于等于k,若是,就反转链表,否则不需要反转

    接下来就是如何反转一个子链表,对于一个子链表,除了反转其本身之外,还需要将子链表的头部与上一个子链表连接,以及子链表的尾部与下一个子链表连接

    在这里插入图片描述

    因此,在反转子链表的时候,我们不仅需要子链表头结点head,还需要有head的上一个节点pre,以便反转完后把子链表再接回pre

    class Solution:
        def reverse(self, head, tail):
            prev = tail.next
            p = head
            while prev != tail:
                nex = p.next
                p.next = prev
                prev = p
                p = next
            return tail, head
        
        def reverseKGroup(self, head, k):
            hair = ListNode(0)
            hair.next = head
            pre = hair
            
            while head:
                tail = pre
                for i in range(k):
                    tail = tail.next
                    if not tail:
                        return hair.next
                nex = tail.next
                head, tail = self.reverse(head, tail)
                pre.next = head
                tail.next = nex
                pre = tail
                head = tail.next
            return hair.next
    

    26.删除排序数组中的重复项

    题目

    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成

    实例

    给定数组 nums = [1,1,2], 
    
    函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
    
    你不需要考虑数组中超出新长度后面的元素
    
    给定 nums = [0,0,1,1,1,2,2,3,3,4],
    
    函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
    
    你不需要考虑数组中超出新长度后面的元素
    

    思路

    因为是排序数组,所以用一个指针指向下标为1的元素,如果前一个元素和这个元素相等,删除前一个元素

    class Solution:
        def removeDuplicates(self, nums):
            pre = 1
            while pre < len(nums):
                if nums[pre - 1] == nums[pre]:
                	nums.pop(pre)
                else:
                    pre += 1
            return len(nums)
    

    27.移除元素

    题目

    给你一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移出后数组的新长度

    不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组

    元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素

    实例

    给定 nums = [3,2,2,3], val = 3,
    
    函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
    
    你不需要考虑数组中超出新长度后面的元素
    
    给定 nums = [0,1,2,2,3,0,4,2], val = 2,
    
    函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
    
    注意这五个元素可为任意顺序。
    
    你不需要考虑数组中超出新长度后面的元素
    
    class Solution:
        def removeElement(self, nums, val):
            while val in nums:
                nums.remove(val)
            return len(nums)
    

    28.实现strStr()

    题目

    实现 strStr() 函数。

    给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1

    实例

    输入: haystack = "hello", needle = "ll"
    输出: 2
    
    输入: haystack = "aaaaa", needle = "bba"
    输出: -1
    

    说明

    当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

    对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符

    思路

    采用正则表达式

    class Solution:
        def strStr(self, haystack, needle):
            if not needle:
                return 0
            import re
            pattern = needle
            res = re.findall(pattern, haystack)
            if res:
                return len(haystack.split(needle)[0])
            return -1
    

    29.两数相除

    题目

    给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符

    返回被除数 dividend 除以除数 divisor 得到的商

    整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2

    实例

    输入: dividend = 10, divisor = 3
    输出: 3
    解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
    
    输入: dividend = 7, divisor = -3
    输出: -2
    解释: 7/-3 = truncate(-2.33333..) = -2
    
    class Solution:
        def divide(self, dividend, divisor):
            sign = (dividend > 0) ^ (divisor > 0)
            dividend = abs(dividend)
            divisor = abs(divisor)
            count = 0
            #把除数不断左移,直到它大于被除数
            while dividend >= divisor:
                count += 1
                divisor <<= 1
            result = 0
            while count > 0:
                count -= 1
                divisor >>= 1
                if divisor <= dividend:
                    result += 1 << count #这里的移位运算是把二进制(第count+1位上的1)转换为十进制
                    dividend -= divisor
            if sign: result = -result
            return result if -(1<<31) <= result <= (1<<31)-1 else (1<<31)-1 
    

    30.串联所有单词的子串

    题目

    给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

    注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序

    实例

    输入:
      s = "barfoothefoobarman",
      words = ["foo","bar"]
    输出:[0,9]
    解释:
    从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
    输出的顺序不重要, [9,0] 也是有效答案
    
    输入:
      s = "wordgoodgoodgoodbestword",
      words = ["word","good","best","word"]
    输出:[]
    
    class Solution:
        def findSubstring(self, s: str, words: List[str]) -> List[int]:
            lefts,rights = 0,0
            if  len(words) == 0:
                return  []
            lens = len(words[0])
            worddict = {}
            currentdict = {}
            results = []
            for  i  in  range(len(words)):
                if  words[i]  not  in  worddict:
                    worddict[words[i]] = 1
                else:
                    worddict[words[i]] = worddict[words[i]]+1
            #统计words中每种字符串的个数,将words中每种字符串放置到worddict中
            cnt = 0
            currentstring = ''
            for  i  in  range(lens):
                lefts,rights = i,i
                #从不同的位置开始打头,比如每一次增长为3的时候,那么长度
                #为0,1,2的时候进行开头都可以
                cnt = 0
                currentdict = {}
                while   lefts <= len(s)-lens*len(words):
                #lefts没有到达最右边的时候(还有能够放下一次完整words部分的时候)
                    while  cnt < len(words) :
                    #cnt为目前已经匹配到words时的长度
                        currentstring = s[rights:rights+lens]
                        #currentstring为往右边走的字符串
                        if  currentstring   not  in  worddict:
                        #跳出的情况1:该字符串不在worddict之中
                            break 
                        elif    currentstring   in   currentdict  and  currentdict[currentstring]+1 > worddict[currentstring]:
                        #跳出的情况2:该字符串在worddict之中,但是出现的次数超出了words所能承受的大小
                            break
                        
                        #匹配成功后将该字符串放入currentdict之中(currentdict统计的是左右指针之间所包含的范围)
                        if  currentstring   not  in  currentdict:
                            currentdict[currentstring] = 1
                        else:
                            currentdict[currentstring] = currentdict[currentstring]+1
                        #匹配成功后继续往右边行走
                        cnt = cnt+1
                        rights = rights+lens
    
                    if  currentdict == worddict:
                        results.append(lefts)
                    if  currentstring  not  in  worddict:
                    #跳出的情况1:右边的字符串不在words之中,此时循环将右侧所有不在words之中的字符串去除,直到找到存在于words之中的字符串为止
                        while   rights+lens <= len(s)  and   s[rights:rights+lens]   not  in   worddict:
                            rights = rights+lens
                        lefts = rights
                        cnt = 0
                        currentdict = {}
                        #此时初始化左右指针并且currentdict设置为空
                    else:
                        if  currentdict[currentstring]  >   worddict[currentstring]:
                        #跳出的情况2:右侧的字符串超过了words的限制,此时将左指针右移,直到左指针移动到超出的那个字符串之前为止
                            while   lefts+lens <= len(s)-lens*len(words)  and    s[lefts:lefts+lens]  != currentstring:
                                lefts = lefts+lens
                        #lefts左指针向前迈出一步,将左侧的那个字符串去除掉(如果之前正好currentdict与worddict完美匹配的时候,将会直接走到这一步)
                        currentdict[s[lefts:lefts+lens]] = currentdict[s[lefts:lefts+lens]]-1
                        cnt = cnt-1
                        lefts = lefts+lens
            return  results
    
    展开全文
  • AA1500民用电池说明书 (中文版) 1 范围 1.1 本规格规定了圆柱密封式镍锌电池的基本性能,技术要求、测试方法及注意事项,本标准只适用于深圳市洁力源科技有限公司所生产的电池。 1.2 产品型号:民用AA1500mAh...
  • JavaScript中,在不连续的时间数据中,构造某时间段内,相同时间间隔的数据
  • 测试数据:用户ID、登入日期 uid,dt guid01,2018-02-28 guid01,2018-03-01 guid01,2018-03-02 guid01,2018-03-04 guid01,2018-03-05 guid01,2018-03-06 guid01,2018-03-07 guid02,2018-03-01 guid02,2018-03-02 ...
  • SQL语句统计连续登陆的三数和以上的用户案例分析 这个问题可以扩展到很多相似的问题:连续几个月充值会员、连续天数有商品卖出、连续打滴滴、连续逾期。 测试数据:用户ID、登入日期 uid,dt guid01,2018-02-28 ...
  • 使用HTK搭建大词汇量语音识别系统,采用的是...、建立任务语法,建立gram  由于timit语音库自带文件中没有HTK能直接使用的任务语法,故我将timit中的发音文件timitdic.txt使用python转换成了任务语法。Python脚本
  • DECLARE @T TABLE (ID INT,NAME VARCHAR(4),STATUS INT)INSERT INTO @TSELECT 1,'aa',0 UNION ALLSELECT 2,'aa',1 UNION A...
  • 一天 耐心的准备所有计算机开机后,即打开电源,首先是BIOS的自检等等,确保每个必要的部件都能正常工作,这个过程我就不再详述了,反正与我们的工作没多大关系。BIOS在找到你的计算机可以进行启动的管道时,就将...
  • 前几天一个朋友提出的:oracle里面怎么查个表中的日期字段的连续日期的缺少的日期。这个问题有点难度,不过还是解决了,有两种方法(其实两种方法都是朋友小虫提出的,我只不过加以验证而已)。 方法: ...
  • CTF-web Xman-2018 第一天 入营msic

    千次阅读 2018-12-01 15:38:25
    广度大,深度不怎么深,涉及的方面有各种加密,流量分析,隐写,文件恢复等 这种类型的题目主要是在于手中的工具要全,很多时候都是依靠工具来完成的,部分是自己如何找到题目的要点,使用对的工具 考的东西:  ...
  • 这些数据结构给出来了实现的代码,实现的难度并不大,一天之内我就把这四个数据结构的测试代码给调通了。  这四个数据结构里,一个是红黑树的变种,对红黑树进行了化简,一个是为了多维查询范围所设计的数据结构。...
  • 个人,每月只有条数据的情况下,连续3个月的月份,减去此人按月份的排序(rank2 列),得到的差(diff 列) 如果是连续的月,那么得到的差应该是相等的
  • 数据分析中的连续性问题

    千次阅读 2019-06-24 23:19:59
    from bb where end_holiday = 1 ) as dd where ee.date_ ) where index_ = 1 order by date_ 实现三 到了实验三我要增加难度了,有下面一些数据,不但要取出连续天数的开始和结束日期,还要求连续需要持续三以上。...
  • HTK英文大词汇连续语音识别

    千次阅读 2017-01-06 17:38:09
    目标也不是个小的语音拨号系统,而是英文的语音识别。当然了,最终结果出来了之后很低,还有很多过程要走。语音识别,肯定不是我这样小打小闹就可以的。本文就主要记录我在训练过程中的步骤以及遇到的一些error。...
  • SQL查询出任意连续日期或时间

    千次阅读 2019-10-09 09:56:02
    查询出一天二十四小时 SELECT CASE WHEN length(mon) = 1 THEN CONCAT('0', mon) ELSE mon END months FROM (SELECT @m := @m + 1 mon FROM 表名, (SELECT @m := 0) a) aa LIMIT 24; 查询出任意两个...
  • Live Space 连续播放音乐教程

    千次阅读 2008-12-24 10:43:00
    一直以为Live Space 里的Windows Media Player 组件只能播放首歌,前两在网上看了说明后发现可以设置多首歌曲的,现在我把它写出来分享给大家.首先,要播放的音乐只能在在线的,你可以在百度里搜到音乐地址,也可以把...
  • 12学好C语言——记录我的C语言学习之路 Day 4: 首先来看段程序: //输出下面4*5的矩阵 /* 1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 4 8 12 16 20 */ //算法1 /*//program 4.1 #include int main...
  • 我在最近工作的时候用到了boost的http_server程序,这个http_server是个...这个框架在接收get请求时没有任何问题,当接收post数据时,当数据大于>2k时,无法正确接收,后来发现sync_read_some函数次只能接收大约
  • 过去段时间,8月13到22号,淘宝商城名鞋馆做了次运营活动,比较累,我也是连续8(包括周末)12点左右离开公司,当然,团队里还有同学更辛苦。这样段经历下来,总会有些可以小结一下的,但因为事情过去没多久...
  • 2017第届河北省大学生程序设计竞赛题解

    万次阅读 多人点赞 2019-05-31 12:22:56
    说实话,这套所谓的“超级密码”其实并不难:对于个给定的字符串,你只要提取其中的数字,然后连在一起构成个整数,再乘以小明的幸运数字513,就是解密后的结果了~比如,字符串“ads2d4,122”,提取后的整数是...
  • 16学完java

    千次阅读 2008-05-01 07:57:00
    Day 01、 从面向过程编程到面向对象编程的思维转变我们知道所有的计算机程序都是由两类元素组成:代码和数据。此外从概念上将讲,程序还可以以他的代码或是数据为核心进行组织编写。也就是说一些程序围绕“正在...
  • 区块链安全—详谈共识攻击(

    千次阅读 2018-11-15 09:53:42
    区块链作为种去中心化的分布式公共数据库,其并没有中央管理机构进行管理工作,而是通过分布式节点共同利用密码学协议共同维护。而各个节点在维护整个系统的的时候要通过底层的共识协议来保证账本的一致性。而在...
  • 、前言 数学离程序员有多近? ifelse也好、for循环也罢,代码可以说就是对数学逻辑的具体实现。所以敲代码的程序员几乎就离不开数学,难易不同而已。 那数学不好就写不了代码吗?????不,一样可以写代码,可以写出...
  • 字符集详解(看就懂系列)

    千次阅读 2017-08-27 11:36:30
    、编码历史与区别 一直对字符的各种编码方式懵懵懂懂,什么ANSI UNICODE UTF-8 GB2312 GBK DBCS UCS……是不是看的很晕,假如您细细的阅读本文你一定可以清晰的理解他们。Let'sGo!  很久很久以前,有群人
  • C语言经典编程实例分析

    千次阅读 多人点赞 2018-10-23 20:50:06
    4、求a+aa+······+a··a(n个a)之和 5、求100-1000之间的水仙花数 6、求斐波那契数列的第40项及前40项的和为多少? 7、将斐波那契数列写入数组并输出 8、求连续子数组的最大和? 9、大小端模式转换与...
  • 一天国王把项链赏赐给了一个学者,并跟他说,你可以带走这条项链,但是王后很喜欢红宝石,蓝宝石,紫水晶,翡翠和钻石这五种,我要你从项链中截取连续的一小段还给我,这一段中必须包含所有的这五种宝石,剩下的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,861
精华内容 4,744
关键字:

一天连续aa