20210227 395. 至少有 K 个重复字符的最长子串

题目

https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/

题解

1.暴力

两个指针left和right,最开始left为0,right不断向后扫描,并记录扫描过字符串的个数,一旦都大于k,记录数值,然后得到这一趟最大值,之后left++,重复扫描,获得最大值(超时)

public int longestSubstring(String s, int k) {
int result = 0;
for (int i = 0; i < s.length() - k + 1; i++) {
result = Math.max(subLongest(s.substring(i), k), result);
}
return result;
}

public int subLongest(String s, int k) {
int result = 0;
Map<Character, Integer> map = new HashMap<>();
boolean flag = false;
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
List<Integer> elCount = new ArrayList<>(map.values());
Collections.sort(elCount);
if (elCount.get(0) >= k) {
flag = true;
result = Math.max(result, i);
}
}
if (flag) {
return ++result;
} else {
return 0;
}
}

2 递归分治

首先我们可以获得的字符串中,一定是不存在小于k个数字的字符的比如afaddcbbb,k=2 我们不论是怎么挑选字符都不可能包括f和c,因为f和c只有一个所以我们可以把字符串分成a,add,bbb,同时这三个也可以按照上边的再次切割,add中就被切成了dd,因为这个子串中a只有一个,这个时候我们dd就是这个子串的最大值,然后返回比较最大的就可以的,很明显可以想到递归,递归的终止条件就是,不可以在分了,或者本身length都已经小于k,一定分不出来了

public int longestSubstring(String s, int k) {
List<String> subStrArray = split(s, k);
if (s.length() < k) {
return 0;
}
if (subStrArray.size() == 0) {
return s.length();
}
int result = 0;
for (String subStr : subStrArray) {
result = Math.max(longestSubstring(subStr, k), result);
}
return result;
}

private List<String> split(String s, int k) {
Map<Character, Integer> countMap = new HashMap<>();
Set<Character> removeSet = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
countMap.put(s.charAt(i), countMap.getOrDefault(s.charAt(i), 0) + 1);
}
for (Character c : countMap.keySet()) {
if (countMap.get(c) < k) {
removeSet.add(c);
}
}
if (removeSet.size() == 0) {
return new ArrayList<>();
}
List<String> result = new ArrayList<>();
int beginIndex = 0;
for (int endIndex = 0; endIndex < s.length(); endIndex++) {
if (removeSet.contains(s.charAt(endIndex))) {
result.add(s.substring(beginIndex, endIndex));
beginIndex = endIndex + 1;

}
}
result.add(s.substring(beginIndex));
return result;
}

20210226 78. 子集

题目

https://leetcode-cn.com/problems/subsets/

题解

例如abc字符串我们可以先枚举只有一个字符的所有字符串[a],[b],[c],然后在枚举只有两个字符串的时候,枚举两个字符串可以按照一个字符串为基础,分别插入一个字符,并且为了保持不重复,所以只能从上一个字符串的最大值开始插入值,[a,b][a,c],[b,c]这里[b]后是不可以插入a的因为在原数组里面b的index是比a大的,这样就不会有重复的情况。等到我们插入的字符串大小和nums的length一样长,证明枚举完毕

public List<List<Integer>> subsets(int[] nums) {
    //  a b c d/ ab ac ad ,bc,bd,cd ,abc,abd ,acd,bcd
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>());
    for (int i = 0; i < nums.length; i++) {
        List<Integer> tmpList = new ArrayList<>();
        tmpList.add(nums[i]);
        result.add(tmpList);
    }
    int maxListLength = 1;
    //记录上一次result第一次插入的index,比如我要插入第三个值的时候,我需要知道第一个两个值的index在哪里
    int index = 0;
    while (maxListLength < nums.length) {
        int temLength = result.size();
        for (int i = index; i < temLength; i++) {
            List<Integer> tmpList = new ArrayList(result.get(i));
            int tmpIndex = getIndex(nums, tmpList.get(tmpList.size() - 1));
            for (int j = ++tmpIndex; j < nums.length; j++) {
                List<Integer> tmpListI = new ArrayList<>(result.get(i));
                tmpListI.add(nums[j]);
                result.add(tmpListI);
            }
            index++;
        }
        maxListLength++;
    }
    return result;
}

private int getIndex(int[] nums, Integer integer) {
    for (int i = 0; i < nums.length; i++) {
        if (integer == nums[i]) {
            return i;
        }
    }
    return 0;
}
简化

上边的思路是每次都把所有size可能出现的情况都枚举出来,但是我们可以以空集合为最基础的list,每次都把后边的值加入,比如最开始是[],然后把a加入变成[][a],在把b加入[],[a],[b][a,b]然后在加入c.变为[],[a],[b],[a,b],[c],[bc],[abc],这种是枚举所有在index之前的字母的子串,代码复杂度大大简化

public List<List<Integer>> subsets1(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    result.add(new ArrayList<>());
    for (int i = 0; i < nums.length; i++) {
        // 这个和上边那个同理,因为每次result都是add的,而我们需要循环的边界是上次result的size所以需要记录一下
        int temLength = result.size();
        for (int j = 0; j < temLength; j++) {
            List<Integer> tmpList = new ArrayList<>(result.get(j));
            tmpList.add(nums[i]);
            result.add(tmpList);
        }
    }
    return result;
}

20210226 1178. 猜字谜

题目

https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/

题解

1 暴力

求word和puzzle里面包含的所有charSet,然后再遍历puzzle,看puzzle的charSet是否contains wordCharSet并且pluzzle的第一个字符需要在word里面,时间复杂度O(word.length*pluzz.length) 超时

public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
List<Set<Character>> wordKeyList = new ArrayList<>();
List<Set<Character>> puzzlesList = new ArrayList<>();
for (int i = 0; i < words.length; i++) {
Set<Character> temSet = new HashSet<>();
for (int j = 0; j < words[i].length(); j++) {
temSet.add(words[i].charAt(j));
}
wordKeyList.add(temSet);
}
// 抽函数
for (int i = 0; i < puzzles.length; i++) {
Set<Character> temSet = new HashSet<>();
for (int j = 0; j < puzzles[i].length(); j++) {
temSet.add(puzzles[i].charAt(j));
}
puzzlesList.add(temSet);
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < puzzles.length; i++) {
Set<Character> pluzzSet = puzzlesList.get(i);
int subResult = 0;
for (int j = 0; j < words.length; j++) {
Set<Character> wordSet = wordKeyList.get(j);
if (pluzzSet.containsAll(wordSet) && Arrays.asList(words[j])
.get(0)
.contains(puzzles[i].charAt(0) + "")) {
subResult++;
}
}
result.add(subResult);
}
return result;
}
2. hash+子序列

这道题主要的时间就是在寻找word是否都包含在puzzle里面,因为都是由小写字母组成的,所以word可以压缩成一个26位的字符串,0代表有,1代表没有,存到map中,map的value代码在word中出现的次数比如aaa,和aa其实在统计上是一样的,直接就是10000…. value是2,现在的问题就拓展到puzzle可以组合成多少个子串,如果word在这些子串里面就算是谜底.这个问题就是 http://www.menglingqiang.com/2021/02/26/20210226-78-%e5%ad%90%e9%9b%86/

同时因为word必须包含pluzzle的第一个字母,所以我们算子集的时候没有pluzzle[0]的都不能要,所以生成子集的时候base应该是{pluzzle[0]}而不是{}

public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
Map<String, Integer> wordMap = new HashMap<>();
for (int i = 0; i < words.length; i++) {
String tmpHashArray = getHashArray(words[i]);
wordMap.put(tmpHashArray, wordMap.getOrDefault(tmpHashArray, 0) + 1);
}
Map<String, List<String>> puzzlesMap = new HashMap<>();
for (int j = 0; j < puzzles.length; j++) {
puzzlesMap.put(puzzles[j], getPuzzlesList(puzzles[j]));
}
List<Integer> result = new ArrayList<>();
for (int i = 0; i < puzzles.length; i++) {
List<String> tmpList = puzzlesMap.get(puzzles[i]);
int tmpResult = 0;
for (int j = 0; j < tmpList.size(); j++) {
tmpResult += wordMap.getOrDefault(tmpList.get(j), 0);
}
result.add(tmpResult);
}
return result;
}

private List<String> getPuzzlesList(String puzzle) {
Set<Character> hashSet = new HashSet<>();
for (char ch : puzzle.toCharArray()) {
hashSet.add(ch);
}
List<String> subStringList = new ArrayList<>();
//因为word必须要有puzzle的第一个字母所以生成的子序列必须要有第一个字符
subStringList.add(puzzle.charAt(0) + "");
hashSet.remove(puzzle.charAt(0));
for (char value : hashSet) {
int tmpLength = subStringList.size();
for (int j = 0; j < tmpLength; j++) {
subStringList.add(subStringList.get(j) + value);
}
}
List<String> result = new ArrayList<>();
for (int i = 0; i < subStringList.size(); i++) {
result.add(getHashArray(subStringList.get(i)));
}
return result;
}

public String getHashArray(String str) {
int[] result = new int[26];
for (int i = 0; i < str.length(); i++) {
result[str.charAt(i) - 'a'] = 1;
}
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i < result.length; i++) {
stringBuffer.append(result[i]);
}
return stringBuffer.toString();
}

mysql第四天

B+树索引适用的条件(左缀原则)

二级索引包含所有索引值和主键,所以当查询值可以覆盖索引值的时候不需要进行回表,这也是尽量不使用select * 的原因,因为我们二级索引都是按照从左到右的顺序排列大小,比如建立联合索引name,birthday,phone_number,索引中的排序如图

image_1dmo2n5c11ij019unpjtpf21tdr9.png-121.1kB

所以当我们排序按照从左到右的顺序或者左边相等,右边排序,就可以使用到索引,例如order by name,birthday phone_number. select name where name=”a” order by birthday.因为字符串一般排序都是按照前边的字母序,比如先比较第一个字母大小,然后再比较第二个以此类推,所以前缀也是可以用到的比如 like “ac%”,group by同样可以使用索引,只要顺序和建立的相同.但是不要随便建立索引,第一是占用空间,第二我们在增删改数据的时候索引同时需要调整,也是很耗时间的.

eg:主键尽量按照顺序插入,不然随机插入可能会造成页分裂.消耗性能,索引列尽可能小,重复度低

MySQL 的数据目录

每个库对应一个文件夹,每次建表会有一个ibd文件和frm文件(8.0之后都到ibd文件里面了),这个文件可以存放到系统表空间或者独立表空间(innodb)

myisam 会有山中文件 frm(表结构) myd(数据) myi(索引)

由于文件和表名一致,所以表名和大小受限于文件命名的最大值和系统的最大存储.\

MySQL系统数据库简介

我们前边提到了MySQL的几个系统数据库,这几个数据库包含了MySQL服务器运行过程中所需的一些信息以及一些运行状态信息,我们现在稍微了解一下。

  • mysql这个数据库贼核心,它存储了MySQL的用户账户和权限信息,一些存储过程、事件的定义信息,一些运行过程中产生的日志信息,一些帮助信息以及时区信息等。
  • information_schema这个数据库保存着MySQL服务器维护的所有其他数据库的信息,比如有哪些表、哪些视图、哪些触发器、哪些列、哪些索引吧啦吧啦。这些信息并不是真实的用户数据,而是一些描述性信息,有时候也称之为元数据。
  • performance_schema这个数据库里主要保存MySQL服务器运行过程中的一些状态信息,算是对MySQL服务器的一个性能监控。包括统计最近执行了哪些语句,在执行过程的每个阶段都花费了多长时间,内存的使用情况等等信息。
  • sys这个数据库主要是通过视图的形式把information_schemaperformance_schema结合起来,让程序员可以更方便的了解MySQL服务器的一些性能信息。

20210224 832. 翻转图像

题目

https://leetcode-cn.com/problems/flipping-an-image/

题解

这个就按照题解来就可以,先翻转,在变值,其中翻转和变值可以同时做以中心为轴,先交换在变值可以从2n优化到n/2

public int[][] flipAndInvertImage(int[][] A) {
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < A[i].length / 2; j++) {
            //先调换
            int tmp = A[i][j];
            A[i][j] = A[i][A[i].length - j - 1];
            A[i][A[i].length - j - 1] = tmp;
            //在翻转
            A[i][j] = A[i][j] ^ 1;
            A[i][A[i].length - j - 1] = A[i][A[i].length - j - 1] ^ 1;
        }
        //如果是奇数个,需要手动翻转一下
        if (A[i].length % 2 == 1) {
            A[i][A[i].length / 2] = A[i][A[i].length / 2] ^ 1;
        }
    }
    return A;
}

20210223 1052. 爱生气的书店老板

题目

https://leetcode-cn.com/problems/grumpy-bookstore-owner/

题解

1.暴力求解

这个问题其实可以简化成两个数组相乘之后求和其中一个数组是0,1数组,这个数组可以有一段X长度均为1,如何更改可以让这两个数组的每一项的乘积只和最大

暴力的话就是枚举所有长度X为1,之后求解去除最大值,时间复杂度O(n*n)

public static int maxSatisfied(int[] customers, int[] grumpy, int X) {
boolean isAllZero = true;
int result = 0;
for (int i = 0; i < grumpy.length; i++) {
if (grumpy[i] == 1) {
isAllZero = false;
result = Math.max(result, getSubResult(customers, grumpy, X, i));
}
}
if (isAllZero) {
result = Math.max(result, getSubResult(customers, grumpy, grumpy.length, 0));
}
return result;
}

public static Integer getSubResult(int[] customers, int[] grumpy, int X, int beginIndex) {
int[] tGrumpy = Arrays.copyOf(grumpy, grumpy.length);
for (int i = 0; i < X && beginIndex + i < grumpy.length; i++) {
tGrumpy[beginIndex + i] = 0;
}
int result = 0;
for (int i = 0; i < grumpy.length; i++) {
result += customers[i] * (tGrumpy[i] ^ 1);
}
return result;
}

2.先求baseSum(不改变值的乘积和),然后就可以简化成X长度子串的最大和,这个里面在求baseSum的时候如果是会加进去,将原数组设置成0,这样在后边遍历的时候就不用有减的操作了,比如原来是1,2,3,4,对应1011(注意这里既是1和0不代表生气数组,对应生气数组是反过来)如果将2的位置设置成0,在前置指针划过2位置时,新的数组不需要再判断baseSum里面有没有加过这个2,只关系后置指针即可

public static int maxSatisfied1(int[] customers, int[] grumpy, int X) {
int baseResult = 0;
for (int i = 0; i < customers.length; i++) {
if (grumpy[i] == 0) {
baseResult += customers[i];
customers[i] = 0;
}
}
int result = 0;
int maxVal = 0;
for (int i = 0; i < customers.length; i++) {
if (i < X) {
maxVal = maxVal + customers[i];
} else {
maxVal = maxVal + customers[i] - customers[i - X];
}
result = Math.max(result, maxVal);
}
return Math.max(result, maxVal) + baseResult;
}

Mysql 第三天

B+树索引

昨天主要是单个页面中的查询,首先页的存储是固定的16kb一旦超过了就会有多个页,所以就会产生页目录

image_1caba0afo11fa1cli1nu070m16bg1j.png-119.1kB

于此同时页目录也会有满的时候所以,页目录也会有一个”目录”

image_1cacafpso19vpkik1j5rtrd17cm3a.png-158.1kB

此上就是B+树索引

对于聚簇索引来说我们页面里面都是根据主键排序的,叶子节点里面也有一列里面,所有的数据,但是对于二级索引来说,排序就是按照相关的索引排序,但是有这么一种情况,主键是不能重复的,但是二级索引没有这个限制一旦重复了,我插入一个新的值,应该如何插入那?例如下图,索引值都是橙色的1,我再次插入一个1的时候应该插入到页面5还是页面4那?所以二级索引不光会用索引值排序,一旦索引排序一样,还会用主键排序,这样就可以保持唯一性.

image_1cp9vthl71h9n8091dkdjek16qg1j.png-58.6kB

MyISAM中的索引方案简单介绍

mysiam的索引和数据是分开存放的,通过索引是可以找到对应数据的内存偏移量,然后再找到对应的真实数据,这个和innodb是不一样的,innodb都是通过查找主键,然后再通过聚簇索引的叶子节点找到真正的数据.

Mysql 第二天

InnoDB记录存储结构

InnoDB采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位,InnoDB中页的大小一般为 16 KB。也就是在一般情况下,一次最少从磁盘中读取16KB的内容到内存中,一次最少把内存中的16KB内容刷新到磁盘中。

InnoDB行格式

个人理解行格式主要就是记录mysql的数据存储格式,mysql读取到行数据需要知道,每个字段的大小,真实的数据,是否为空,是否删除等信息,这些信息如何存储到,并且可以解析就是行格式的定义

COMPACT行格式
image_1c9g4t114n0j1gkro2r1h8h1d1t16.png-42.4kB

Compact行格式中,把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位,从而形成一个变长字段长度列表,各变长字段数据占用的字节数按照列的顺序逆序存放,我们再次强调一遍,是逆序存放!(之所以逆序存放,是因为我们读取的时候指针会放在真实记录和额外记录中间,所以逆序更容易获取到前边的数据,提高缓存命中率)

比如一个表有c1,c2,c3三个列,新建顺序同样也是1,2,3内容分别是aaaa,bbb,d换成十六进制就是0x04,0x03,0x01,存放如图,逆序放置

image_1c9gbruvo504dlg1qsf19nbeu878.png-37kB

null值列表,用0和1表示是否为null,0时不为null,同时mysql都是整数字节,即即使有3个列,也得申请8个bit空间位,没有的用0填写(只记录可以为null的列,非null的列比如主键,不记录,因为没有意义)

行溢出

mysql的每一页都是由大小的,如果真实数据超过大小,在真实记录数据的地方,有两种操作,一种是记录部分真实信息,剩一部分空间存一个地址,这个地址可以引到真实的信息,另一种是直接都放到引入的页

InnoDB数据页结构

mysql定义一页至少要有两行数据

上边的mysql的行记录里面有一些头信息,我们在页里面需要查询相关数据,我们这个时候就需要知道最大值和最小值,方便二分,同时msyql会自动生成两个伪记录(最大值,最小值记录)主要是为了方便查找

image_1c9qs1mn2t3j1nt344116nk15uf2p.png-119.7kB

槽属于page Directory部分,我们通过这个槽来二分

image_1d6g64af2sgj1816ktl1q22dehp.png-189.1kB

删除某个几率的时候同理,只需要将next_record指向下一个即可,不会立即删除空间,如果有新的记录插入,会将这部分空间重新利用

20210221 766. 托普利茨矩阵

题目

https://leetcode-cn.com/problems/toeplitz-matrix/

题解

遍历先找横着遍历对角线,在竖着遍历对角线,最后一位只有一个不需要遍历

public boolean isToeplitzMatrix(int[][] matrix) {
int lSize = matrix.length;
int hSize = matrix[0].length;
int h = 0;
int l = 0;
while (h < hSize - 1) {
l = 0;
int tempH = h;
while (tempH < hSize - 1 && l < lSize - 1) {
if (matrix[l][tempH] != matrix[l + 1][tempH + 1]) {
return false;
}
tempH++;
l++;
}
h++;
}
h = 0;
l = 0;
while (l < lSize - 1) {
h = 0;
int tempL = l;
while (tempL < lSize - 1 && h < hSize - 1) {
if (matrix[tempL][h] != matrix[tempL + 1][h + 1]) {
return false;
}
tempL++;
h++;
}
l++;
}
return true;
}

刚写的时候,在hSize,lSize和遍历inxex i,j上混淆了,一旦i++,j++会影响遍历,其实只用+1就可以这样不会改变原值,代码也比较简单

public boolean isToeplitzMatrix(int[][] matrix) {
for (int i = 0; i < matrix.length - 1; i++) {
for (int j = 0; j < matrix[0].length - 1; j++) {
if (matrix[i][j] != matrix[i + 1][j + 1]) {
return false;
}
}
}
return true;
}