ARTS是什么? Algorithm：每周至少做一个LeetCode的算法题 Review：阅读并点评至少一篇英文技术文章 Tip：学习至少一个技术技巧,总结和归纳日常工作中遇到的知识点 Share：分享一篇有观点和思考的技术文章

Algorithm

完成leetcode算法第1588题。

用最简单粗暴的方法实现一次，时间复杂度为
将前缀和先存入sum数组，后续计算可以直接从数组中拿数据，时间复杂度为 ```java package com.ohyoung.leetcode;

import java.util.Arrays;

/**

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。 *
子数组定义为原数组中的一个连续子序列。 *
请你返回 arr 中所有奇数长度子数组的和。 *
示例 1： *
输入：arr = [1,4,2,5,3]
输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58 *
示例 2： *
输入：arr = [1,2]
输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。 *
@author ohYoung

@date 2021/8/29 9:37 */ public class SumOddLengthSubarrays1588 {

public static void main(String[] args) {

 SumOddLengthSubarrays1588 example = new SumOddLengthSubarrays1588();
 int[] arr = new int[]{1, 4, 2, 5, 3};
 System.out.println(example.sumOddLengthSubarrays(arr));
 arr = new int[]{3};
 System.out.println(example.sumOddLengthSubarrays(arr));
 arr = new int[]{1, 2};
 System.out.println(example.sumOddLengthSubarrays(arr));
 arr = new int[]{10, 11, 12};
 System.out.println(example.sumOddLengthSubarrays(arr));
 System.out.println("=========================");
 arr = new int[]{1, 4, 2, 5, 3};
 System.out.println(example.sumOddLengthSubarrays_2(arr));
 arr = new int[]{3};
 System.out.println(example.sumOddLengthSubarrays_2(arr));
 arr = new int[]{1, 2};
 System.out.println(example.sumOddLengthSubarrays_2(arr));
 arr = new int[]{10, 11, 12};
 System.out.println(example.sumOddLengthSubarrays_2(arr));

}

public int sumOddLengthSubarrays(int[] arr) {

 int sum = 0;
 for (int i = 1; i <= arr.length; i++) {
     // i表示当前奇数子数组的长度
     if (i % 2 == 0) {
         continue;
     }
     for (int j = 0; j < arr.length - i + 1; j++) {
         int m = j;
         int count = 0;
         while (count < i) {
             sum += arr[m];
             m++;
             count++;
         }
     }
 }
 return sum;

}

/**

利用前缀和将每个长度的前缀的和先存储起来，相较于第一种方式时间复杂度降低到O(n^2) */ public int sumOddLengthSubarrays_2(int[] arr) { int[] sum = new int[arr.length + 1]; for (int i = 1; i <= arr.length; i++) {
```
 sum[i] = sum[i - 1] + arr[i - 1];
```
} int res = 0; for (int i = 1; i <= arr.length; i = i + 2) {
```
 for (int l = 0; l < arr.length - i + 1; l++) {
     res += sum[i+l] - sum[l];
 }
```
} return res; }

}

<a name="UXmMP"></a>
# Review
[Introduction to Go packages](https://blog.learngoprogramming.com/definitive-guide-to-go-packages-focus-on-the-fundamentals-to-empower-your-skills-d14aae7cd321)
这是一篇描述Go中"package"概念的文章，主要内容包括：
- 什么是package
- package和其他语言的相似以及区别
- 几个练习帮助熟悉package的概念
<a name="dMFQc"></a>
# Tip
什么是索引下推？
话不多说，直接举例说明。<br />我们现在有张表t_people，存储着全国人民的基本信息
```sql
CREATE TABLE `t_people` (
  `id` bigint unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(64) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  `address` varchar(256) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL,
  `age` int NOT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `joint` (`address`,`age`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

从表结构可以看出，除了有id为主键索引外还建立了address和age的联合索引；
现在我们需要查询湖南省的人口老龄化程度，用到的sql语句如下

 select * from t_people where address like '湖南%' and age > 65;

这条语句的执行过程如下：

在联合索引树上找到以”湖南”开头的数据的主键id；
根据查询到的主键id去主键索引树上拿到所有的信息（回表），取出age判断age>65是否成立，如果符合条件则记录这条数据，否则舍弃。

现在湖南省的常驻人口为6644.49万人，就算符合条件的数据只有100w条，这条语句也会循环6644w次并回表6644w次，这是一个很大的性能消耗，即使有索引也会很慢。

所以，在MySQL5.6的版本中推出了索引下推的优化手段，所以在MySQL5.6及之后，上面的sql语句执行过程如下：
在联合索引树上找到以”湖南”开头的数据，判断age>65是否成立，如果不成立该条数据舍弃，遍历到下一条，如果成立则获取主键id，根据主键id进行回表拿到所有数据并记录下来；

这样改进之后，sql语句执行需要循6644w次，但是只需要回表100w次；性能大大提升。

输出文章 - 字符串匹配算法（二）- Boyer Moore算法

Finish

预计完成时间：2021.08.23 ~ 2021.08.29
实际完成时间：2021.08.29

ARTS - 第2周

Algorithm

Share

Finish