【数据结构】数组与字符串

发表于2021-12-01更新于2022-03-01字数统计3.5k阅读时长27分

二维数组常见题目

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

1 2	输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

思路：定义两个点：左上角和右下角。这两个点每次都在同一层的边框上，只要确定了这两个点，就可以顺时针方向遍历这一层框的元素（四条边上的元素）。遍历完毕后再将左上角向右下方向移动一格，右下角向左上方向移动一格。从而使得边框向内层收缩，然后重复上一步骤即可。

例如下图使用不同颜色代表每一层的各个边，两个箭头代表两个边界点的移动方向：

其中，在打印当前层的边框时，需要特别注意：分别打印四条边时，每次循环的终止是在该边的另一端点（另一条边的起点）的前一个位置，不能将该端点也打印，而应该将其作为下一条边的起点时被打印。以上图为例，最外层的遍历每次只能遍历四个格子，不能遍历到该行/列的最后一个，因为这一个元素是下一条边的起点，不能提前遍历了。

代码：

public class PrintMatrixSpiralOrder {
    public static void printMatrixSpiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length < 1) {
            return;
        }
        int topRow = 0;
        int topCol = 0;
        int downRow = matrix.length - 1;
        int downCol = matrix[0].length - 1;
        while (topRow <= downRow && topCol <= downCol) {
            // 打印当前边界后，左上角向右下移动一步，右下角向左上移动一步，缩小边界框，继续循环
            printEdge(matrix, topRow++, topCol++, downRow--, downCol--);
        }

    }

    public static void printEdge(int[][] matrix, int topRow, int topCol, int downRow, int downCol) {
        if (topRow > downRow || topCol > downCol) {
            // 如果左上角在右下角的右下方，代表越界了，直接返回
            return;
        }
        if (topRow == downRow) {
            // 如果左上角和右下角在同一行，则只需要打印这一行即可
            while (topCol <= downCol) {
                System.out.print(matrix[topRow][topCol] + ' ');
                topCol++;
            }
        } else if (topCol == downCol) {
            // 如果左上角和右下角在同一列，则只需要打印这一列即可
            while (topRow <= downRow) {
                System.out.print(matrix[topRow][topCol] + ' ');
                topRow++;
            }
        } else {
            // 普通情况，四轮循环打印四条边
            int curRow = topRow;
            int curCol = topCol;
            // 注意！！！ curCol 不能等于 downCol，否则在到达角点时，进行curCol++后会使得curCol越界
            while (curCol < downCol) {
                System.out.print(matrix[curRow][curCol] + " ");
                curCol++;
            }
            while (curRow < downRow) {
                System.out.print(matrix[curRow][curCol] + " ");
                curRow++;
            }
            while (curCol > topCol) {
                System.out.print(matrix[curRow][curCol] + " ");
                curCol--;
            }
            while (curRow > topRow) {
                System.out.print(matrix[curRow][curCol] + " ");
                curRow--;
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
                          { 13, 14, 15, 16 } };
        printMatrixSpiralOrder(matrix);
    }
}

阅读全文

【Spring】Spring Security

发表于2021-11-30更新于2022-03-14字数统计7.5k阅读时长53分

Spring Security 简介

Spring 是非常流行和成功的 Java 应用开发框架，Spring Security 正是 Spring 家族中的成员。Spring Security 基于 Spring 框架，提供了一套 Web 应用安全性的完整解决方案。

正如你可能知道的关于安全方面的两个主要区域是“认证”和“授权”（或者访问控制），一般来说，Web 应用的安全性包括 用户认证（Authentication）和用户授权（Authorization） 两个部分，这两点也是 Spring Security 重要核心功能。

用户认证：指的是验证某个用户是否为系统中的合法主体，也就是说用户能否访问该系统。用户认证一般要求用户提供用户名和密码。系统通过校验用户名和密码来完成认证过程。通俗点说就是系统认为用户是否能登录
用户授权：指的是验证某个用户是否有权限执行某个操作。在一个系统中，不同用户所具有的权限是不同的。比如对一个文件来说，有的用户只能进行读取，而有的用户可以进行修改。一般来说，系统会为不同的用户分配不同的角色，而每个角色则对应一系列的权限。通俗点讲就是系统判断用户是否有权限去做某些事情。

历史

“Spring Security 开始于 2003 年年底,““spring 的 acegi 安全系统”。起因是 Spring 开发者邮件列表中的一个问题，有人提问是否考虑提供一个基于 spring 的安全实现。

Spring Security 以“The Acegi Secutity System for Spring” 的名字始于 2013 年晚些时候。一个问题提交到 Spring 开发者的邮件列表，询问是否已经有考虑一个机遇 Spring 的安全性社区实现。那时候 Spring 的社区相对较小（相对现在）。实际上 Spring 自己在2013 年只是一个存在于 ScourseForge 的项目，这个问题的回答是一个值得研究的领域，虽然目前时间的缺乏组织了我们对它的探索。

考虑到这一点，一个简单的安全实现建成但是并没有发布。几周后，Spring 社区的其他成员询问了安全性，这次这个代码被发送给他们。其他几个请求也跟随而来。到 2014 年一月大约有 20 万人使用了这个代码。这些创业者的人提出一个 SourceForge 项目加入是为了，这是在 2004 三月正式成立。

在早些时候，这个项目没有任何自己的验证模块，身份验证过程依赖于容器管理的安全性和 Acegi 安全性。而不是专注于授权。开始的时候这很适合，但是越来越多的用户请求额外的容器支持。容器特定的认证领域接口的基本限制变得清晰。还有一个相关的问题增加新的容器的路径，这是最终用户的困惑和错误配置的常见问题。

Acegi 安全特定的认证服务介绍。大约一年后，Acegi 安全正式成为了 Spring 框架的子项目。1.0.0 最终版本是出版于 2006 -在超过两年半的大量生产的软件项目和数以百计的改进和积极利用社区的贡献。Acegi 安全 2007 年底正式成为了 Spring 组合项目，更名为"Spring Security"。

对比

Spring Security 特点：

和 Spring 无缝整合。
全面的权限控制。
专门为 Web 开发而设计。
旧版本不能脱离Web 环境使用。新版本对整个框架进行了分层抽取，分成了核心模块和Web 模块。单独引入核心模块就可以脱离Web 环境。
重量级。

Shiro 特点：

Apache 旗下的轻量级权限控制框架。
轻量级。Shiro 主张的理念是把复杂的事情变简单。针对对性能有更高要求的互联网应用有更好表现。
通用性：
- 好处：不局限于Web 环境，可以脱离Web 环境使用。
- 缺陷：在Web 环境下一些特定的需求需要手动编写代码定制。

Spring Security 是 Spring 家族中的一个安全管理框架，实际上，在 Spring Boot 出现之前，Spring Security 就已经发展了多年了，但是使用的并不多，安全管理这个领域，一直是 Shiro 的天下。

相对于 Shiro，在 SSM 中整合 Spring Security 都是比较麻烦的操作，所以，Spring Security 虽然功能比 Shiro 强大，但是使用反而没有 Shiro 多（Shiro 虽然功能没有Spring Security 多，但是对于大部分项目而言，Shiro 也够用了）。

自从有了 Spring Boot 之后，Spring Boot 对于 Spring Security 提供了自动化配置方案，可以使用更少的配置来使用 Spring Security。

模块划分

阅读全文

【数据结构】并查集

发表于2021-11-30更新于2021-11-30字数统计866阅读时长6分

并查集

并查集中有三个哈希表，存储三种信息：

元素表：存储用户传入的数据类型 V 到自定义包装类型 Element <V>间的映射（装饰器模式）。该表用于根据用户传入的变量查询自定义的包装类型变量
父节点表：存储每个元素的父节点的信息（头节点的父节点是其自身）
秩表：存储每个集合中元素节点的个数（只有每个集合的头节点才存储在该表中）

并查集的主要思想：

查找某个元素的头节点：从父节点表中不断遍历当前元素的父节点，直到父节点等于自身，即找到了头节点
判断两个元素所在的集合是否相同：寻找每个元素所在集合的头节点，判断二者是否相等
合并两个集合：将节点数量少的集合的头节点的父节点设置为节点多的集合的父节点（节点数量存储在秩表中）

一种通用的并查集模板：

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class UnionFind {
   public static class Element<V> {
      private V value;
      public Element(V v) {
         this.value = v;
      }
   }

   public static class UnionFindSet<V> {
      // 保存每个V对象与其对应的包装类对象Element<V>
      public Map<V, Element<V>> elementMap;
      // 保存每个节点的父元素
      public Map<Element<V>, Element<V>> fatherMap;
      // 保存每个头节点所在并查集的大小（只有头结点才保存该信息，代表该头结点所在的并查集有多少节点）
      public Map<Element<V>, Integer> rankMap;

      // 初始化并查集时需要给每个元素单独创建自己所在的集合
      public UnionFindSet(List<V> list) {
         elementMap = new HashMap<>();
         fatherMap = new HashMap<>();
         rankMap = new HashMap<>();

         for (V v : list) {
            Element<V> element = new Element<V>(v);
            elementMap.put(v, element);
            fatherMap.put(element, element);
            rankMap.put(element, 1);
         }
      }

      public Element<V> findHead(Element<V> element) {
         // 创建一个栈，用于在寻找element头节点的过程中，将途径元素都记录下来，
         // 并在找到头节点后依次弹出，重新设置其父节点为找到的头节点，做到路径压缩（扁平化）
         Stack<Element<V>> path = new Stack<>();
         // 不创建额外的变量，复用element不断指向新的父节点，直到指向头结点
         while (element != fatherMap.get(element)) {
            path.push(element);
            element = fatherMap.get(element);
         }

         // 找到头节点后，将栈中每个节点都重新设置父节点
         while (!path.isEmpty()) {
            fatherMap.put(path.pop(), element);
         }
         return element;
      }

      public boolean isSameSet(V a, V b) {
         if (!elementMap.containsKey(a) || !elementMap.containsKey(b)) {
            // 如果集合中都不存在这两个元素，则直接返回false
            return false;
         }

         // 判断两个节点的头结点是否相等，如果不相等，则不在同一个集合中
         return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
      }

      public void union(V a, V b) {
         if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
            Element<V> aH = findHead(elementMap.get(a));
            Element<V> bH = findHead(elementMap.get(b));
            if (aH != bH) {
               Element<V> big = rankMap.get(aH) >= rankMap.get(bH) ? aH : bH;
               Element<V> small = big == aH ? bH : aH;
               // 更新小的头的父节点为大的头
               fatherMap.put(small, big);
               // 更新新的头
               rankMap.put(big, rankMap.get(big) + rankMap.get(small));
               // 移除旧的头
               rankMap.remove(small);
            }
         }
      }
   }
}

阅读全文

【数据结构】哈希表

发表于2021-11-28更新于2022-03-08字数统计6.8k阅读时长37分

哈希

https://blog.csdn.net/u011240877/article/details/52940469

哈希，又称“散列”。

散列（hash）英文原意是“混杂”、“拼凑”、“重新表述”的意思。

在某种程度上，散列是与排序相反的一种操作，排序是将集合中的元素按照某种方式比如字典顺序排列在一起，而散列通过计算哈希值，打破元素之间原有的关系，使集合中的元素按照散列函数的分类进行排列。

在介绍一些集合时，我们总强调需要重写某个类的 equals() 方法和 hashCode() 方法，确保唯一性。这里的 hashCode() 表示的是对当前对象的唯一标示。计算 hashCode 的过程就称作哈希。

为什么需要哈希

我们通常使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某个元素是否存在的过程中，数组和链表都需要挨个循环比较，而通过哈希计算，可以大大减少比较次数。使得每次查找操作的时间复杂度为 O(1)。

哈希函数

哈希的过程中需要使用哈希函数进行计算。

哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算出该元素存储位置的函数。表示为：address = H [key]

常见的哈希函数构造方法：除留余数法。具体做法：首先将关键字key进行一个编码运算（例如MD5编码），生成对应的哈希值（MD5码的范围为 0 ~ 2^64 - 1）。然后该哈希值被某个不大于散列表长度 m 的数 p 求余，得到散列地址。即 H(key) = key % p, p < m。

哈希函数的特性：经过哈希函数计算得到的散列地址是均匀分布的，经过 % 也还是均匀分布的。即使两个数字相差很小，经过哈希函数后二者也会大相径庭。这种特性被很好地应用在一致性哈希原理中，使得众多虚拟节点平均地分布在整个哈希域中，从而很好地做到数据库的负载均衡。

常见的哈希算法：MD5 算法和 SHA 算法。

哈希表

在 Java 中哈希表的实现为 HashMap，其底层保存有一个 Entry 数组。通过重写的 hashCode() 方法计算出当前 POJO 对象的哈希值，从而将对象放到不同的位置，相同的哈希值的对象串联在一条链表上。当添加的对象过多导致链表长度过长时，哈希表会进行扩容，增加 Entry 数组的长度，此时会重新计算每个元素的哈希值（因为计算哈希值时的 m 和 p 发生了变化），将其重新分布在扩容后的哈希表上，这个过程是会消耗一定的时间的（JVM会开启另一个线程执行扩容工作，因此扩容过程并不会怎么影响用户线程时间）。

时间复杂度分析：

单次插入、修改或删除哈希表中某个元素的时间复杂度为 O(k)，k 为串联链表上元素的个数，当 k 较小时可以认为是 O(1) 级别的
哈希表N个元素扩容的时间复杂度为 O(N*logN)，单次扩容的理论时间复杂度为 O(logN)。实际工程上通过增大 k 值以减少扩容次数，可以使得单次扩容的时间复杂度接近于 O(1)

借助于哈希表设计数据结构

思路：借助两个哈希表，一个存储的 key : value 为 key : index，另一个存储的为 index : key。等概率删除则借助于哈希表的平均分布的特性，在 index 范围内随机生成一个数字，删除以该数字为 index 的数据即可做到随机删除。

细节：需要在每次删除后将 index 最大的元素交换到当前删除的位置，从而避免删除过程中的索引不连续出现的空洞现象。

阅读全文

【算法】动态规划

发表于2021-11-28更新于2022-03-04字数统计15.1k阅读时长108分

动态规划的思想

首先进行暴力尝试，然后建立记忆搜索表进行缓存，最后建立严格表结构。

直接使用暴力递归，会将所有情况都进行尝试，这样时间复杂度较高，有很多之前尝试过的答案会在其他分支仍然进行尝试。因此可以在暴力递归的基础上建立记忆搜索表（缓存表），将已经尝试过的答案缓存到表中，这样在其他分支就不需要再次尝试了，可以直接从基友搜索表里获取结果，从而节省了大量的时间，该方法又被称为记忆化递归法。最后可以根据暴力尝试的推导公式建立严格表结构，从而省去递归操作，在严格表中通过递推快速得到结果。

暴力递归就是尝试：

把问题转化为规模缩小了的同类问题的子问题
有明确的不需要继续进行递归的条件（base case）
有当得到了子问题的结果之后的决策过程
不记录每一个子问题的解

暴力递归的常用技巧：

在递归过程中不保存结果，而是在调用到 base case（栈底）时才执行保存，因为到 base case 时说明当前这条路是走得通的，那么走到底时就可以保存结果了，如果某条路走不通（例如八皇后问题中可能某些路就走不通）则不会到 base case，从而不会保存。
在递归过程中通过修改 char[] 或 int[] 里的值来节省空间，在调用子问题前先修改原数组（要注意暂存起来修改前的值），并在子问题执行完毕后将其原始值保存回去，从而做到保持原数组的正确性，不影响其他的递归栈

上述技巧使用举例：例如要保存一个字符串的所有子序列：

递归过程中在修改 char[] 数组当前位置的值为空 ''，代表不考虑当前字符的情况，修改后进入子问题，得到不考虑当前位置字符时的结果；然后该子问题的方法栈调用完毕后，再将原始值赋值回去，再调用一次子问题，代表考虑当前字符的情况，又可以得到一种结果
递归到底时，再保存当前 char[] 中的内容到结果列表里。

阅读全文

【算法】贪心算法

发表于2021-11-28更新于2022-03-02字数统计9.1k阅读时长62分

贪心算法常见题目

阅读全文

【算法】单调栈

发表于2021-11-25更新于2021-12-22字数统计2.5k阅读时长19分

单调栈结构

遍历整个数组，使用一个栈记录数组中的元素索引。

所有元素不重复的情况

当寻找某个元素左右距离他最近的比他小的元素时，栈底元素的值小于栈顶元素的值。例如栈中：[2 -> 3 -> 4(栈顶)。新来一个元素1，其值小于4，则找到了当前栈顶4左右侧距离他最近的比他小的元素3和1。将4弹出，记录其左右侧的3和1，然后继续。
当寻找某个元素左右距离他最近的比他大的元素时，栈底元素大于栈顶元素。例如栈中：[4 -> 3 -> 2(栈顶)。新来一个元素5，其值大于2，则找到了当前栈顶2左右侧距离他最近的比他大的元素3和5。

规律：

整体是满足单调性的。当发现新来的元素破坏了栈中的单调性时，将栈顶元素弹出（其余元素不弹出，新来的元素也不在此时入栈，而是进行下一轮判断是否可以入栈），记录此时新的栈顶元素作为其左侧最近元素，记录新来的元素为其右侧最近元素。
栈中保存的元素始终是按照升序或降序排列的，肯定满足单调性。这是因为中途破坏单调性的元素都被弹出并记录了，还在栈中的都是单调排序的。
找某个元素左右比他小的，栈中是升序排列；找某个元素左右比他大的，栈中是降序排列。

有元素重复的情况

当有元素重复时，栈中不能单单只存储一个 Integer 类型变量，而应该存储一个 ArrayList，将相同值的元素存储到同一个 List 中。

算法整体顺序一致，区别在于弹栈时弹出的是一个 List，需要将这个 List 中的所有元素都遍历一次，加入到 res[][] 中；另外，在获取左侧的元素索引值时，需要获取到栈顶第二个 List 里的最后一个元素（这个元素是最靠近当前弹出栈的元素的，因为整体是单调的，越靠后的，越在 List 的后面）。

代码：

public class MonotonousStack {

   public static int[][] getNearLessNoRepeat(int[] nums) {
      if (nums == null || nums.length < 1) {
         return null;
      }

      Stack<Integer> stack = new Stack<>();
      int[][] res = new int[nums.length][2];

      for (int i = 0; i < nums.length; i++) {
         // 如果遇到栈顶元素大于当前元素，说明栈顶元素找到了其左侧小于它的第一个元素（栈顶下的第二个的元素）
         // 如果新来的元素仍是按照升序或降序排列，则都不会弹栈，因为仍然是符合单调性的，只有在破坏单调性时才弹栈记录
         while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
            int popIndex = stack.pop();
            // 弹出的栈顶元素左侧的最小值就是新的栈顶元素（或不存在，对应栈空）
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            // 存储这个栈顶元素的左侧小于它的第一个元素索引 leftLessIndex 和其右边小于它的第一个元素索引 i
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = i;
         }
         // 跳出while循环时，i位置的元素已经能插入到栈中并满足栈中的单调性了，此时将i压入栈中
         stack.push(i);
      }

      // 遍历完数组后，栈中可能还存在一些元素，这些元素的最近元素还没保存到res里
      // 将栈中元素依次弹出，其左侧最近值就是下一个栈中元素，右侧最近值不存在，保存-1
      while (!stack.isEmpty()) {
         int popIndex = stack.pop();
         int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
         res[popIndex][0] = leftLessIndex;
         res[popIndex][1] = -1;
      }
      return res;
   }


   public static int[][] getNearLess(int[] nums) {
      if (nums == null || nums.length < 1) {
         return null;
      }

      Stack<List<Integer>> stack = new Stack<>();
      int[][] res = new int[nums.length][2];
      for (int i = 0; i < nums.length; i++) {
         while (!stack.isEmpty() && nums[stack.peek().get(0)] > nums[i]) {
            // 获取到list集合，里面可能存着多个相同值的元素
            List<Integer> popList = stack.pop();
            // 左边最小的元素为新的栈顶集合里的最后一个元素，因为最后一个元素是最靠近当前元素的（因为栈结构的单调性）
            int leftLessIndex = stack.isEmpty() ? -1 :stack.peek().get(stack.peek().size() - 1);
            // 遍历当前list里的元素（值相同），为其赋上左边最小元素索引（是相同的）以及右侧元素（i）
            for (Integer popIndex : popList) {
               res[popIndex][0] = leftLessIndex;
               res[popIndex][1] = i;
            }
         }
         // 将i加入到栈中，注意分两种情况：
         //   1. i的值和当前栈顶元素的值不相同，则新建一个list，将该list入栈
         //   2. i的值和当前栈顶元素的值相同，则将i加入到栈顶元素的list里的最后一个位置
         // 注意要带上 !stack.isEmpty() && ，必须要有元素才行
         if (!stack.isEmpty() && nums[stack.peek().get(0)] == nums[i]) {
            // 相同时，直接加入到栈顶的list中
            stack.peek().add(i);
         } else {
            // 不同时，新建一个list，入栈
            List<Integer> list = new ArrayList<>();
            list.add(i);
            stack.push(list);
         }
      }

      // 全部遍历完毕后，依次弹栈，记录栈中元素的左侧最小信息到res中
      while (!stack.isEmpty()) {
         List<Integer> popList = stack.pop();
         for (Integer popIndex : popList) {
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = -1;
         }
      }

      return res;
   }

   // for test
   public static int[] getRandomArrayNoRepeat(int size) {
      int[] arr = new int[(int) (Math.random() * size) + 1];
      for (int i = 0; i < arr.length; i++) {
         arr[i] = i;
      }
      for (int i = 0; i < arr.length; i++) {
         int swapIndex = (int) (Math.random() * arr.length);
         int tmp = arr[swapIndex];
         arr[swapIndex] = arr[i];
         arr[i] = tmp;
      }
      return arr;
   }

   // for test
   public static int[] getRandomArray(int size, int max) {
      int[] arr = new int[(int) (Math.random() * size) + 1];
      for (int i = 0; i < arr.length; i++) {
         arr[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
      }
      return arr;
   }

   // for test
   public static int[][] rightWay(int[] arr) {
      int[][] res = new int[arr.length][2];
      for (int i = 0; i < arr.length; i++) {
         int leftLessIndex = -1;
         int rightLessIndex = -1;
         int cur = i - 1;
         while (cur >= 0) {
            if (arr[cur] < arr[i]) {
               leftLessIndex = cur;
               break;
            }
            cur--;
         }
         cur = i + 1;
         while (cur < arr.length) {
            if (arr[cur] < arr[i]) {
               rightLessIndex = cur;
               break;
            }
            cur++;
         }
         res[i][0] = leftLessIndex;
         res[i][1] = rightLessIndex;
      }
      return res;
   }

   // for test
   public static boolean isEqual(int[][] res1, int[][] res2) {
      if (res1.length != res2.length) {
         return false;
      }
      for (int i = 0; i < res1.length; i++) {
         if (res1[i][0] != res2[i][0] || res1[i][1] != res2[i][1]) {
            return false;
         }
      }

      return true;
   }

   // for test
   public static void printArray(int[] arr) {
      for (int i = 0; i < arr.length; i++) {
         System.out.print(arr[i] + " ");
      }
      System.out.println();
   }

   public static void main(String[] args) {
      int size = 10;
      int max = 20;
      int testTimes = 2000000;
      for (int i = 0; i < testTimes; i++) {
         int[] arr1 = getRandomArrayNoRepeat(size);
         int[] arr2 = getRandomArray(size, max);
         if (!isEqual(getNearLessNoRepeat(arr1), rightWay(arr1))) {
            System.out.println("Oops!");
            printArray(arr1);
            break;
         }
         if (!isEqual(getNearLess(arr2), rightWay(arr2))) {
            System.out.println("Oops!");
            printArray(arr2);
            break;
         }
      }
   }
}

阅读全文

【算法】滑动窗口

发表于2021-11-24更新于2022-03-01字数统计6.5k阅读时长44分

滑动窗口模板

模板一

滑动窗口模板一：适用于窗口大小固定，整体向右移动。

此时只使用一个变量，代表右边界，不断向右移动。代码：

public int[] template01(int[] nums, int k) {
    int ans = 0;
    int sum = 0;
    int maxSum = 0;
    for (int i = 0; i < nums.length; i++) {
        // 更新当前窗口内的累加和
        sum += nums[i];
        // 第一次满足该条件时，[0,i] 区间形成了第一个窗口
        // 此时就该记录该区间内的数字和的
        // 之后i不断++，窗口的右边界不断右移，左边界 i-k+1 也不断右移
        if (i >= k - 1) {
            if (sum > maxSum) {
                maxSum = sum;
                ans = i - k + 1;
            }
            // 窗口即将整体右移，更新sum：减去左边界的值
            sum -= nums[i - k + 1];
        }
    }
}

这种方式当退出循环时无需其他操作，因为最后一个窗口位置的情况也考虑在内了。

模板二

滑动窗口模板二：适用于窗口任意大小。

此时需要两个指针 left 与 right，二者根据题目的要求进行右移。代码：

public int template02(String s) {
    int left = 0;
    int right = 0;
    // 词频表
    Map<Character, Integer> freq = new HashMap<>();
    int maxCount = 0;

    while (right < s.length()) {
        // 如果当前字符已经被访问过，则right不动，left++
        if (freq.containsKey(s.charAt(right))) {
            // 清掉left的字符的频次
            freq.remove(s.charAt(left));
            // 此时[left, right-1]区间即为一个局部不重复子串区间
            // 更新最大值
            maxCount = Math.max(maxCount, (right - left));
            // left右移
            left++;
        } else {
            // 如果当前字符没有被访问过，righ++
            // 先更新当前字符的词频
            freq.put(s.charAt(right), 1);
            // right右移
            right++;
        }
    }
    // 跳出后还要额外判断一次当前的left和right间的距离
    maxCount = Math.max(maxCount, (right - left));
    return maxCount;
}

这种方式需要在最后 right 跳出循环后，额外判断此时的 [left, right) 区间内的情况。

模板三

模板三和模板二较为相似，区别在于模板三中内层不是 if 判断，而是 while 循环，一直在循环内移动 left，直到满足条件后退出，再更新当前局部最佳子区间的指标（例如长度）：

public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) {
        return 0;
    } 
    int left = 0;
    int right = 0;
    int count = 0;
    int product = 1;
    // 外层更新 right
    // 每次移动一次right，计算当前right必须包含且作为最后一个位置时的子数组个数（可能为0，代表不可行）
    for (; right < nums.length; right++) {
        // 先更新right在内的指标
        product *= nums[right];
        // 内层while循环更新left直到满足条件退出
        while (product >= k) {
            // 不断移走left，直到某个位置满足小于k
            product /= nums[left];
            left++;
        }
        // 更新当前局部最佳子区间 [left, right] 内的长度
        count += right - left + 1;  
    }
    return count;
}

可使用滑动窗口的题目有：

最小包含子串长度
最多有 K 个不同字符的最大子串长度
正好有 K 个不同整数的子数组数量
累加和至少为 K 的最短子数组长度
至少有 K 个重复字符的最长子串

阅读全文

【算法】位运算

发表于2021-11-24更新于2022-03-02字数统计4.4k阅读时长32分

位运算

位运算技巧

位移运算：

// 有符号右移，会在最高位自动补 1
n >> 1;
// 无符号右移，最高位不会补 1
n >>> 1;

获取每个数字最右侧为 1 的位数：

// 以补码加一的形式将 n 取相反数
rightOne = n & (~n + 1);
// 等价于直接取反
rightOne = n & -n;

将二进制数字 n 最右侧的 1 变为 0，其余不变：

// 最右侧的 1 变为 0，此 1 右边的 0 都变为 1
n = n - 1;
// 最右侧的 1 变为 0
n = n & (n - 1);

统计二进制中 1 的个数：

public int hammingWeight(int n) {
    // 遍历 0-31 位，记录有几个 1
    int res = 0;
    while (n != 0) {
        // 累加上当前位
        res += n & 1;
        // 注意是无符号右移
        n >>>= 1;
    }
    return res;
}

判断某个数字的符号：

// 负数的最高位为 1，正数的最高位为 0
// n 先右移 31 位，得到其最高位的值，然后与 1 取异或，即可得到其符号
// 如果 n 为负数，其最高位 1 经过异或就是 0，反之就是 1
int sign = ((n >> 31) & 1) ^ 1;

判断一个 32 位正数是不是 2 的幂、4 的幂：

// 如果是2的幂，则其二进制位上只可能有一位为1，其他位都是0
// 例如 4：00000100  8:00001000。一次移动一位
// 这样其与自身减去一取与，得到的就是0。因为所有1都错位了
public static boolean is2Power(int n) {
    // 将最右侧的 1 变为 0
    return (n & (n - 1)) == 0;
}

// 如果是4的幂，前提得是2的幂。
// 然后找规律，4的幂的数字只可能有一位是1，并且该位肯定是在第1,2,4,6,8,10...中的某一个，其他位都为0
// 例如 16：00010000  32:0010000。一次移动两位
public static boolean is4Power(int n) {
    // 0x55555555：010101....01010101。0101四位组成一个0x5，共8个
    return (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}

使用位运算完成取相反数操作：

// 一个数的相反数 = 该数取补码 + 1
public static int negNum(int n) {
    return ~n + 1;
}

判断数字奇偶性：

1
2
3

x & 1;  // 因为如果 x 的最低位为1，则代表其肯定是某一个2的倍数加上了1，所以肯定是奇数
// 等价于
x % 2;

阅读全文

【算法】技巧总结

发表于2021-11-24更新于2022-03-02字数统计2.7k阅读时长19分

常用 API

数组

初始化数组：

// 如果不赋值，则[]内需要指定大小
int[] nums = new int[n];
// 如果同时要赋值的话，[]内不带值
int[] nums = new int[]{1,2,3,4};

// 二维数组
int[][] nums = new int[m][n];
int[][] nums = new int[][]{{1,3},{1,2},{4,5},{3,7}};

// 字符串数组的初始化与整型类似
char[] cstr = new char[n];
char[] cstr = new char[]{'a', 'b', 'c'};
// 也可以从String对象中提取出对应的字符串数组
char[] cstr = new String("abc").toCharArray();

// String数组的初始化需要带()
String[] str = new String()[n];
String[] str = new String()[]{"aaa", "bbb", "ccc"};
// 或者使用字面量形式
String[] str = {"aaa", "bbb", "ccc"};

总结：初始化时，若要通过{}赋值，则数组的[]内不能带数字；如果不赋值，则必须要带数字。因为使用{}赋值时，编译器会根据赋值的数量自动算出数组长度，因此[]内就不能加数字了。

数组操作：

int[][] nums = new int[][]{{1,3},{1,2},{4,5},{3,7}};

// 根据二维数组的某一位进行排序
// 最简洁的Lambda表达式
Arrays.sort(nums, (o1, o2) -> o1[0] - o2[0]);
// 或可以写多行的形式
Arrays.sort(nums, (o1, o2) -> {
    o1[0] - o2[0]
});
// 或匿名内部类
Arrays.sort(nums, new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b){
        if(a[0]==b[0]){
            return a[1] - b[1];
        }else {
            return a[0] - b[0];
        }
    }
});


// 对数组集合进行反转
Collections.reverse(list);
// 集合的排序
Collections.sort(list, (o1, o2) -> o1 - o2);

// 从原始组中复制出来一份 [0, k]
Arrays.copyOf(arr, k);

// 数组快速填充数值
char[] board = new char[n];
Arrays.fill(board, '.'); // 快速填充
board[record[row]] = 'Q';


// 将数组中每个元素值都设置为 1
int[] arr = new int[10];
Arrays.fill(arr, 1);

// list 转 int[]
int[] ans = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
    ans[i] = list.get(i);
}

// List 中嵌套 int[] 时转换为 int[][]
List<int[]> list = new ArrayList();
int[][] ans = list.toArray(new int[list.size()][]);

字符串

// 将数字转换为字符串（在字符串问题中非常常用）
String s = String.valueOf(num);
// 将字符串转换为数字
int n = Integer.parseInt(s);
// 或
int n = Integer.valueOf(s);

s.substring(a,b); // 截取 s 在区间 [a, b) 上的子字符串

char c = s.charAt(i); // 获取 s 在第 i 位置上的字符


s = s.trim(); // String 字符串删除首尾空格

Character.isLetter(ch);     // 判断某个字符是否是字母
Character.toLowerCase(ch);  // 将某个字母转为小写字母 
char[] str = s.toLowerCase();  // 将 String 转换成小写字母数组

// StringBuilder的API
// 添加字符串
sb.append(new String("123"));
// 删除字符串某个位置的元素
sb.deleteCharAt(i);

集合

LinkedList中add，addLast，offer，pollLast，removeLast等区别：https://blog.csdn.net/cpppp66/article/details/115759578。

addLast() 仅仅将元素链接到队列尾部。然而 add() 不仅将元素链接到队列尾部，还返回true。
offer() 直接调用了 add() 方法。所以在 LinkedList中 add() 与 offer() 的使用相当于是一样的

总结：

需要链接元素到队列尾时优先用 offer()
查看元素优先使用 peek()
删除元素优先使用 poll()

特别情况：

想要在指定索引位置链接元素可以使用 add(int index, E element)
获取指定索引的元素可以使用 get(int index)
修改指定索引的元素可以使用 set(int index, E newElement)

其他：

// 对数组集合进行反转
Collections.reverse(list);
// 集合的排序
Collections.sort(list, (o1, o2) -> o1 - o2);

// 从原始组中复制出来一份 [0, k]
Arrays.copyOf(arr, k);

一些深度优先遍历问题，通常做法是创建一个全局的集合 path，其将随着递归栈的调用而被不断修改。在递归到底部满足条件进行保存结果时，注意需要另外创建一个新的集合变量，存储该 path 中的值，以防其随着递归栈的返回被修改。具体做法为：res.add(new LinkedList<Integer>(path))

代码：

List<List<Integer>> res = new LinkedList<List<Integer>>();
Deque<Integer> path = new LinkedList<Integer>();

public void dfs(TreeNode curr, int target) {
    // 假设如果满足某种条件，就将当前分支的内容保存到总结果集合 res 中
    // 则需要另外创建一个新的集合变量，存储该 path 中的值，以防其随着递归栈的返回被修改
    if (target == 0) {
        res.add(new LinkedList<Integer>(path));
    }
}

哈希表


Set<Integer> set = new HashSet<>();
// HashSet 添加元素
for (int i = 0; i < arr.length; i++) {
    set.add(arr[i]);
}
// 遍历 HashSet
for (Integer cur : set) {
    if (set.contains(cur + k)) {
        res.add(Arrays.asList(cur, cur + k));
    }
}


Map<String, Integer> map = new HashMap<>();
// 遍历 HashMap
for (Entry<String, Integer> entry : map.entrySet()) {
    // 获取每一个 key
    String str = entry.getKey();
    // 获取每一个 value
    Integer times = entry.getValue();
}

概率

// 随机获得一个[0, i]内的随机整数，注意是左闭右开，是不包含 i + 1 的
int d = rand.nextInt(i + 1);

// 随机生成 0-4 + 1 = 0-5 的数字
int d = (int)(Math.random() * 5) + 1;

阅读全文