Leetao's Blog

Talk is cheap, show me the code

0%

发表于 更新于

前言

在 Mybatis 3.3.1 版本之后, Mybatis 支持批量插入返回自增主键 ID,相关 PR 可以参考
Support insert multiple rows and write-back id, 但是使用的时候有一些注意事项,我在用的时候查了很多资料,发现网上基本上都是只提到一部分,大部分人都是测试失败了,因此整理了一下.

使用

XML 形式

1
2
3
4
5
6
7
<insert id="insertList" useGeneratedKeys="true" keyProperty="id">
  INSERT INTO country (countryname,countrycode )
  VALUES
  <foreach collection="list" item="item" separator=",">
    (#{item.countryname},#{item.countrycode})
  </foreach>
</insert>

注意: keyProperty=”id” 和 collection=”list”,这两点不能有任何改变,否则就没办法成功获取插入后的 id

注解形式

1
2
3
4
5
6
7
8
9
@Insert("<script>
 INSERT INTO country (countryname,countrycode )
  VALUES
  <foreach collection=\"list\" item=\"item\" separator=\",\">
    (#{item.countryname},#{item.countrycode})
  </foreach>
</script>")
@Options(useGeneratedKeys = true, keyProperty = "id", keyColumn = "id")
int batchInsert((@Param("list") List<Country> countryList);

注意: @Param(“list”), collection=”list” 以及 keyProperty=”id” 这三点不能有任何改变,否则就没有办法成功

参考链接

Support insert multiple rows and write-back id.More about insert multipl…
Support insert multiple rows and write-back id

发表于 更新于

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
感谢 Marcos 贡献此图。

示例:

1
2
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路

思路一:

结合数据和图,可以看出能够存积水的位置 i ,始终满足条件:

  1. height[i] < height[i-n]
  2. height[i] < height[i+m]

其中 m,n 均大于 0,同时判定两个条件会很麻烦,我们试着先找出所有高度中最高的,以这个最高的将这个高度数组分为左右两边,然后依次从 left 遍历到最高的,从 right 遍历到最高的,遍历过程中,只需要找出局部最高 part_max,
局部最高与其余高度值的差值和即为积水和

以给的例子为例,[0,1,0,2,1,0,1,3,2,1,2,1]:

  1. max_height = 3. 所在索引为 7
  2. 以左边为例,从左到最高的数组为 [0,1,0,2,1,0,1], 对于的局部最高的数组为 [0,1,1,2,2,2,2]
  3. 高度差依次为:[0,0,1,0,1,2,1]
  4. 则左边积水和为 5
  5. 同理可求右边为 1
  6. 则最终结果为 6

思路二:

双指针:假设数组 height, 长度为 n, left_max = right_max = 0, 面积为 area = 0 ,两个指针left,right 初始分别位于 0, n - 1 的位置

  1. height[left] < height[right], 有解法一中可以知道,这个时候只要找到 left_max > height[left] 就可以积水了,所以有: 
             1.  如果 height[left] > left_max: left_max = height[left]
         2.  否则 area += left_max - height[left]
         3.  left += 1
  2. height[left] >height[right]:
    1. 如果 height[right] > right_max: right_max = height[right]
    2. 否则 area += right_max - height[right]
    3. right -= 1

解法

解法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def trap(self, height: List[int]) -> int:
        
        height_len = len(height)
        
        if height_len < 3:
            return 0
        
        max_value = 0
        max_index = 0
        for key,value in enumerate(height):
            if value > max_value:
                max_value = value
                max_index = key
        
        # 面积      
        area = 0
  
        # left -> max
        part_max = height[0]
        for left in range(max_index):
            if height[left] > part_max:
                part_max = height[left]
            else:
                area += part_max - height[left]
        # right -> max
        part_max = height[height_len-1]
        for right in range(height_len-1,max_index,-1):
            if height[right] > part_max:
                part_max = height[right]
            else:
                area += part_max - height[right]
        
        return area

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def trap(self, height: List[int]) -> int:
        height_len = len(height)
        if height_len < 3:
            return 0
        left_max = right_max = 0
        left,right = 0, height_len - 1
        area = 0
        
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    area += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    area += right_max - height[right]
                right -= 1
        return area

发表于 更新于

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

1
2
3
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

1
2
3
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路

先排序然后遍历，排序按照 start 值大小排序，排序完后，遍历排序后的列表 sorted_list，假设当前元素位置 i, 判断 sorted_list[i-1].end >= sorted_list[i]，说明两个区间有重合，将 sorted_list[i].start = sorted_list[i-1].end，注意判断 sorted_list[i-i].end 是否大于 sorted_list[i].end，如果大于，则 sorted_list[i].end = sorted_list[i-1].end

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def merge(self, intervals: List[Interval]) -> List[Interval]:
        sorted_start_list = sorted(intervals,key=lambda x:x.start)
        list_len = len(sorted_start_list)
        res_list = []
        count = 0
        i = 1
        while i < list_len - count:
            if sorted_start_list[i-1].end >= sorted_start_list[i].start:
                if sorted_start_list[i-1].end > sorted_start_list[i].end:
                    sorted_start_list[i].end = sorted_start_list[i-1].end
                sorted_start_list[i].start = sorted_start_list[i-1].start
                sorted_start_list.remove(sorted_start_list[i-1])
                count += 1
                i -= 1
            i += 1
        return sorted_start_list

发表于 更新于

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

1
2
3
4
5
6
7
输入: 
        [[1,1,0],
         [1,1,0],
         [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。

示例 2:

1
2
3
4
5
6
7
输入: 
        [[1,1,0],
         [1,1,1],
         [0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
注意：N 在[1,200]的范围内。对于所有学生，有M[i][i] = 1。如果有M[i][j] = 1，则有M[j][i] = 1。

思路

方法一 :DFS,遍历所有人,对于每个人寻找他的好友,然后再找他好友的好友,这样深度优先遍历下去，通过 visited 数组记录是否已经遍历完这个人,遍历到相同朋友圈, visited[i] 则标识为已经遍历过,不再次纳入朋友圈个数统计中

方法二: 并查集,将有关系的人放在一个集合中

解法

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        len_m = len(M)
        visited = [0 for i in range(len_m)]
        friend_count = 0
        
        def dfs(M,i,visited,len_m):
            visited[i] = 1
            for j in range(len_m):
                if M[i][j] == 1 and visited[j] == 0:
                    dfs(M,j,visited,len_m)
            
        for i in range(len_m):
            if visited[i] == 0:
                friend_count += 1
                dfs(M,i,visited,len_m)
        return friend_count

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        len_m = len(M)
   
        self.parent = [i for i in range(len_m)] # init 
        
        def find_set(i):
            if i == self.parent[i]:
                return i
            return find_set(self.parent[i])
        
        def union(i,j):
            find_i, find_j = find_set(i),find_set(j)
            self.parent[find_j] = find_i
        
        for i in range(len_m):
            for j in range(len_m):
                if M[i][j]:
                    union(i,j)
        return len([i for i in range(len_m) if find_set(i) == i])

发表于 更新于

给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。

示例:

1
2
3
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

思路

思路一: 通过 dict(哈希表) 去实现:
遍历列表,假设字典为 hash_dict, 列表为 nums, 元素为 num, 最大长度 max_len = 0,如果 num 不在字典中,判断 num - 1, num + 1 是否 hash_dict 中,对应值分别为 left, right, 不在则值为 0, 然后获取累加值 cur_len = 1 + left + right,然后取 max_len 和 cur_len 的最大值, 然后将 cur_len 依次赋值给 hash_dict[num],hash_dict[num-1],dict[num+1]

思路二: 直接遍历列表:
遍历列表,假设列表为 nums, 先用 set 去重,得到新的 nums,元素为 num,最大长度为 max_len = 0, 当前长度为 cur_len, 首先 num 肯定在 nums 中,然后判断 num+1 是否在 nums, … , nums + N 是否在 nums 中, 然后判断 max_len 和 cur_len 的长度,取最大值,为了防止重复遍历数组,我们在循环前,先判断 num -1 是否在 nums 中,如果在,就说明存在 num - 1 进行了循环

解法

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hash_dict = {}
        max_len = 0
        for num in nums:
            if num not in hash_dict:
                left = hash_dict.get(num-1,0)
                right = hash_dict.get(num+1,0)
                cur_len = 1 + left + right
                max_len = max(max_len, cur_len)
                hash_dict[num] = cur_len
                hash_dict[num - left] = cur_len
                hash_dict[num + right] = cur_len
        return max_len

解法二 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_len = 0
        nums = set(nums)
        for num in nums:
            if num -1  not in nums:
                current_num = num
                current_len = 1
                while current_num + 1 in nums:
                    current_len += 1
                    current_num += 1
                max_len = max(max_len,current_len)     
        return max_len

发表于 更新于

前言

凡是使用过 Flask,可能对 Flask 中 session 不陌生, 我们通常用 session 保存特定的用户信息,从而达到在 request 请求之间共享数据的目的,需要注意的一点 flask 中的 session 是基于 cookies 实现的,也就意味着着受制于 cookies,一旦出于某种原因 cookies 失效了,也就意味着 session 也会随之失效.

使用

关于 session 的使用方法也很简单, session[key] = value, 但是也存在需要注意的地方,接下来看一个例子

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from flask import Flask, session
app = Flask(__name__)
app.secret_key = "123"  # 使用 session 之前,必须要设置 secret_key

@app.route('/')
def create(): #1
    session['xxx'] = ['1','2','3']
    print(",".join(session['xxx']))
    return ",".join(session['xxx'])

@app.route('/rm/<id>')
 def rm(id): #2
    session['xxx'].remove(id)
    print(",".join(session['xxx']))
    return ",".join(session['xxx'])

@app.route('/add/<id>')
def add(id): #3
    session['xxx'].append(id)
    print(",".join(session['xxx']))
    return ",".join(session['xxx'])

@app.route('/test')
def out_print(): #4
     print(session['xxx'])
     print(",".join(session['xxx']))
     return ",".join(session['xxx'])
     
if __name__ == '__main__':
    app.run()

有趣的事情来了,我们按照 #1, #2(请求参数为2),#4, #3(请求参数为4), #4 的方式来请求 url,那么返回结果依次应该是什么呢?

结果

1
2
3
4
5
1,2,3
1,3
1,2,3
1,2,3,4
1,2,3

看一下截图:

原因

是不是觉得很奇怪,为什么我对 session 的修改没有生效? 这是因为 session 中有一个属性叫做 modified, 如果 session 发现其值有修改，如果修改的对象是可变的对象，则改修不会自动生效，除非手动设置 modified = True，也就是说我们需要上述的例子中 session 及时的被修改，需要在修改值后加入如下代码：

1
session.modified = True

彩蛋

对于上述例子，在执行第二步之前，大家可以打开 Google 浏览器调试模式，找到 Application tab 页下的 Cookies，会发现里面有个 session-id 的 cookies，大家可以试着把它修改或者清空后再执行步骤 2，会有意想不到的彩蛋哟

参考

Flask.session

发表于 更新于

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

1
2
3
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").

示例2:

1
2
3
输入: s1= "ab" s2 = "eidboaoo"
输出: False
注意：输入的字符串只包含小写字母两个字符串的长度都在 [1, 10,000] 之间

解法

Sliding Window Algorithm(滑动窗口算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def checkInclusion(self, s1, s2):
        l1 = len(s1)
        l2 = len(s2)
        if s1 == s2:
            return True
        if l2 < l1:
            return False
        s = "abcdefghijklmnopqrstuvwxyz"
        dict1 = {}
        dict2 = {}

        for i in range(len(s)):
            dict1[s[i]] = 0
            dict2[s[i]] = 0

        for i in range(l1):
            dict1[s1[i]] += 1
            dict2[s2[i]] += 1

        if dict1 == dict2:
            return True

        for i in range(l2 - l1):
            dict2[s2[i]] -= 1
            dict2[s2[i + l1]] += 1
            if dict1 == dict2:
                return True
        return False

发表于 更新于

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

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

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        sum_node = ListNode(-1)
        head = sum_node
        carry = 0
        while l1 and l2:
            sum_val = l1.val + l2.val + carry
            val = sum_val % 10
            carry = sum_val // 10
            sum_node.next = ListNode(val)
            sum_node = sum_node.next
            l1 = l1.next
            l2 = l2.next
        
        while l1:
            sum_val = l1.val + carry
            val = sum_val % 10
            carry = sum_val // 10
            sum_node.next = ListNode(val)
            l1 = l1.next
            sum_node = sum_node.next
        
        while l2:
            sum_val = l2.val + carry
            val = sum_val % 10
            carry = sum_val // 10
            sum_node.next = ListNode(val)
            l2 = l2.next
            sum_node = sum_node.next
        
        if l1 is None and l2 is None and carry > 0:
            sum_node.next = ListNode(carry)
            
        return head.next

发表于 更新于

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

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

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

解法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        str_len = len(s)
        slow_cur = 0
        hash_dict = {}
        max_len = 0
        for fast_cur in range(str_len):
            if s[fast_cur] in hash_dict:
                max_len = max(max_len, fast_cur-slow_cur)
                slow_cur = max(hash_dict[s[fast_cur]] + 1,slow_cur)
            hash_dict[s[fast_cur]] = fast_cur
        return max(max_len, str_len-slow_cur)

发表于 更新于

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

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestPalindrome(self, s: str) -> str:
        str_len = len(s)
        max_len = 1
        start_index = 0

        dp = [[0]*str_len for _ in range(str_len)]

        for i in range(str_len):
            dp[i][i] = 1

        for j in range(str_len):
            for i in range(j - 1, -1, -1):
                if j == i+ 1 and s[j] == s[i]:
                    dp[i][j] = 2
                if j > i+1 and dp[i+1][j-1] > 0 and s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    start_index = i
        return s[start_index:start_index + max_len]