刷题

0.常用法

Character的用法

//判断一个char是不是数字
boolean ans = Character.isDigit();
//判断一个char是不是字母
boolean ans = Character.isLetter();
//判断一个char是不是大写字母
Character.isUpperCase(ch)
//判断一个char是不是小写字母
Character.isLowerCase(ch)

向上取整

1	`int num = Math.ceil(num);`

指数

1	`Math.pow(x, y)`

float转String，且小数点后面指定位数

1 2	`float f = 123.456f; String s = String.format("%.2f", f); // 保留两位小数`

Int转化为二进制

1	`String str = Integer.toBinaryString();`

对数组的[i,j]部分进行排序

1	`Arrays.sort(nums, i, j);`

请将它对10^9 + 7取余

1	`static final int MOD = 1000000007;`

判断两个数组中的内容是否相同

1	`Arrays.equals(array1, array2)`

防止负数相加溢出

1	`int min = Integer.MIN_VALUE / 2;`

控制continue跳转的位置

next:
for (int i = 0; i < strs.length; i++) {
    for (int j = 0; j < strs.length; j++) {
        if (j != i && isSubseq(strs[i], strs[j])) {
            continue next;
        }
    }
    return strs[i].length();
}

这会导致外层循环继续下一次迭代，而不需要执行内层循环的剩余部分。

遍历set

增强for

1.数组

1.1知识点：

二分查找

见二分查找章节

快慢指针
滑动窗口
矩阵题目（主要是模拟，都比较难）
循环数组（503）：1.再开辟一个数组，拼接到原数组；2.遍历时候按2倍数组遍历，i 取 i % nums.length

1.2用法：

//数组的填充

1 2	`char[] c = new char[n]; Arrays.fill(c, '.');`

判断两个数组是否相等：

1	`Boolean flag = Arrays.equals(arr1, arr2);`

数组的自定义排序：

//二维数组排序
//如果 compare(a, b) 返回正数，则意味着元素 a 在排序中应该排在元素 b 的后面。
Arrays.sort(arr, new Comparator<int[]>() {
            public int compare(int[] arr1, int[] arr2) {
                return arr1[0] - arr2[0];
            }
        });

数组初始化

//数组初始化
//1.static
int[] numbers = {1, 2, 3, 4, 5};
int[] numbers = new int[]{1, 2, 3, 4, 5};
//2.dynamic
int[] numbers = new int[5];

//二维数组初始化
//第一种方式：
int a[][]={{1,2,3},{4,5,6}};
//第二种方式；
int[][] ints = new int[4][2];
//第三种方式：第二维的长度可以动态申请
int[][] arr3 = new int[5][];//五行的长度

list的用法

//清空
list.clear();
//升序
Collections.sort(list);
//降序
Collections.sort(list, Collections.reverseOrder());
//删除最近添加的元素
list.removeLast();
//注意这两句的区别，回溯中选择第二个
ans.add(path);
ans.add(new ArrayList<>(path));

1.3困难题目

矩阵题目全部、34.在排序数组中查找元素的第一个和最后一个位置（两次二分，查第一个和最后一个位置）、

2.链表

2.1知识点：

经常需要创造出一个虚拟节点、大部分题目画图模拟即可、合并有序链表（必须快速写）、双向链表（LRU）、链表的归并排序（148）、链表的深拷贝（138）

环形链表：

判断链表是否环：使用快慢指针。
如果有环，如何找到这个环的入口：从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。

2.2用法

双向链表

//双向链表需要自定义，引用LRU一题
class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
}

2.3困难题

148.排序链表、146.LRU

3.哈希表

3.1知识点

有时候用一个int[26]的数组存储字母可能更好。

3.2用法

map和set除了遍历外的各种时间复杂度为O（1）

hashmap的用法

//遍历1.
hashMap.forEach((key, value) -> {
            System.out.println("(" + key + ", " + value + ")");
        });
//遍历2.
for (Map.Entry <Integer, String> entry: map.entrySet()) {
            key = entry.getKey();
            value = entry.getValue();
            
}
//遍历3.
Set<String> set = map.keySet();
for(String key : set){
    ......
}
//判断key是否存在
boolean res = map.containsKey(key);
//获取key对应的value，若不存在获取默认值
int res = map.getOrDefault(key, 0);
//删除某key
map.remove(key);
//判断map是否为空
boolean res = map.isEmpty();

set基本类似
TreeMap的使用

//返回 TreeMap 中最小和最大的键
System.out.println(map.firstKey()); // Alice
System.out.println(map.lastKey()); // David

// 返回 TreeMap 中小于和大于给定键的最近的键
System.out.println(map.lowerKey("Bob")); // Alice
System.out.println(map.higherKey("Bob")); // Charlie

// 返回 TreeMap 中小于等于和大于等于给定键的最近的键
System.out.println(map.floorKey("Bob")); // Bob
System.out.println(map.ceilingKey("Bob")); // Bob

// 返回一个子映射，包含给定范围内的所有键值对
System.out.println(map.subMap("Alice", true, "Charlie", true)); // {Alice=90, Bob=80, Charlie=70}

// 返回一个子映射，包含小于或等于给定键或大于或等于给定键的所有键值对
System.out.println(map.headMap("Charlie", true)); // {Alice=90, Bob=80, Charlie=70}
System.out.println(map.tailMap("Charlie", true)); // {Charlie=70, David=60}

// 返回 TreeMap 中最小和最大的键值对
System.out.println(map.firstEntry()); // Alice=90
System.out.println(map.lastEntry()); // David=60

// 返回 TreeMap 中小于和大于给定键的最近的键值对
System.out.println(map.lowerEntry("Bob")); // Alice=90
System.out.println(map.higherEntry("Bob")); // Charlie=70

// 返回 TreeMap 中小于等于和大于等于给定键的最近的键值对
System.out.println(map.floorEntry("Bob")); // Bob=80
System.out.println(map.ceilingEntry("Bob")); // Bob=80

// 返回并删除 TreeMap 中最小和最大的键值对
System.out.println(map.pollFirstEntry()); // Alice=90
System.out.println(map.pollLastEntry()); // David=60

自定义排序：类似堆

4.字符串

4.1知识点

前缀和(560.)

4.2用法

string的常用法

/*
	1.比较string要用equals()而不是==
	2.string str = “”和string str = null不一样
*/
//string转char
char[] charArr = s.toCharArray();
//char数组转string
String str = new String(charArray);
//string转int
String numberStr = "123";
int number = Integer.valueOf(numberStr);
//int转string
String str = String.valueOf(num);
//切割字符串
String text = "This\tis\ta\tsample\tstring";
String[] words = text.split("\t"); // 使用制表符分割字符串
//去掉开头和结尾的空格
String originalString = "   Hello, world!   ";
String trimmedString = originalString.trim();
//取string的第i位置的字符
str.charAt();
//string的取子串
String str = "Hello, World!";
String substr1 = str.substring(7); // 从索引7开始截取到字符串末尾
String substr2 = str.substring(0, 5); // 从索引 0 开始截取到索引 5（不包括）  左闭右开

//contains只能包含字符串，如果希望检测是否包含某字符使用indexOf

//比较两个字符串对应的数字的大小  “330” “303”进行比较
//如果字符串相等，则返回值为 0。
//如果当前字符串小于参数字符串，则返回一个负整数。
//如果当前字符串大于参数字符串，则返回一个正整数。
int result = str1.compareTo(str2);

stringbuilder的用法

//创建
StringBuilder sb = new StringBuilder();
//string转化为stringbuilder
String str = "Hello";
StringBuilder sb = new StringBuilder(str);
//添加
sb.append("Hello");
//往指定位置插入字符串
sb.insert(5, "beautiful "); // 在索引为 5 的位置插入字符串
//删除字符串
sb.delete(5, 14); // 删除索引从 5 到 13 的字符
//删除固定位置的字符
sb.deleteCharAt(int index);// 删除指定索引处的字符。
//把指定位置处的字符替换为另一个字符
sb.setCharAt(index, newChar);
//获取长度
int length = sb.length();
//获取指定位置的字符
char ch = sb.charAt(0); // 获取索引为 0 的字符
//反转字符串
sb.reverse();
//转化为string
String result = sb.toString();

kmp算法跳过

4.3困难题目

5.栈与队列

5.1知识点

辅助栈（155）、

分数字栈和符号栈（150、394）

单调栈（例子4，2，0，3，2，5）：求右边第一个比它大的元素——单调递减栈（从栈底到栈头）；求右边第一个比它小的元素——单调递增栈、

优先队列、

单调队列：维护某个范围内的最值使用

5.2用法

栈的常用法

//栈
Deque<Character> stack = new ArrayDeque<>();
//常用方法
push();
pop();
isEmpty();
peek() 	//检索但不删除此列表的头（第一个元素）。

队列的常用法

//队列
Queue<Integer> queue = new LinkedList<>();
//常用方法
offer();
poll();
isEmpty();
peek();
//双向队列的方法
offerLast();
offerFirst();

//优先队列
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
//常用方法同队列
//默认是从小到大，可以通过提供一个自定义的 Comparator 来改变 PriorityQueue 的排序方式。
PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            //如果 compare(a, b) 返回正数，则意味着元素 a 在排序中应该排在元素 b 的后面。
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });

5.3困难题目

394.字符串解码、42.接雨水、239.滑动窗口最大值（单调队列）

6.二叉树

6.1知识点

递归三要素（1.确定参数和返回值。2.确定终止条件。3.确定单层递归的逻辑。）
各种遍历方式的非递归写法
各种遍历方式、各种遍历方式+双指针、各种遍历方式+全局变量
深度和高度：（高度和深度是相反的，求高度用后序遍历，求深度用前序遍历）
用回溯法求解二叉树问题（257.二叉树的所有路径）
DFS的应用（437.路径总和Ⅲ）
二叉搜索树（性质、搜索、插入（只往叶子节点插入）、删除（需要调整树的结构）、数组转二叉搜索树）
根据中序+前/后序数据构造二叉树问题：需要额外四个指针，指示两个数据的起点和终点。需要一个map存储一个数组中的元素在另一个数组中的下标位置。

6.2方法

层次遍历模板

6.3困难题目

543.二叉树的直径、450.删除二叉搜索树中的节点、669.修剪二叉搜索树、124.二叉树的最大路径和

7.回溯

本质也是暴力搜索，但是在无法确定多少层for循环时使用

7.1知识点

去重问题

树层去重：同一树层上不能取相同的元素

//在单层逻辑中去重，即for循环中
if(i>0 && used[i-1]==false && candidates[i-1]==candidates[i]){
                continue;
            }
//used[i-1]==false确保了是树层去重，否则是树枝去重。

树枝去重：同一树枝上不能取相同的元素

去重要借助used数组 + 对原始数组排序。

组合问题

切割问题（字符串的切割）
子集问题

组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点。

收集子集要放在终止条件上方，否则会漏掉。

排列问题

使用used数组

棋盘问题

N皇后、解数独

其他

dfs和回溯作比较：岛屿数量和单词搜索这两题。

7.2方法

模板

void backtracking(参数){
	if(终止条件){
        收集结果;
        return;
    }
    for(集合元素){
        处理节点；
        递归函数；
        回溯操作；
    }
    return;
}

//递归三步曲
1.递归函数参数和返回值：形参根据题目来定，返回值一般都是void
2.递归终止条件
3.单层搜索逻辑

辅助变量

//排列问题，去重问题要用used数组，组合问题，切割问题，子集问题用startindex。

//设置两个全局变量
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();

//注意是收集叶子结点的数据还是收集所有结点中的数据。

7.3困难题目

40.组合总和Ⅱ、491.非递减子序列（不能排序的去重借助set去重）、51.N皇后（处理二维数组）

8.贪心

9.动态规划

初始化：递推公式没有考虑到的才需要初始化。

9.1知识点

简单题目
0-1背包问题

问题分类

给了背包的容量，问能不能装满；

给了背包的容量，问最多能装多少价值；

给了背包的容量，有几种方法装满（递归公式不一样）；

给了背包的容量，最多能装几个物品装满；

ps：可能递归公式不一样，但遍历顺序都一样。

递推公式

1.二维

需要二维数组 dp[i][j] : [0,i]物品任取放进容量为j的背包中。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}
//遍历顺序
两层for，先物品后容量或者先容量后物品，对于二维数组实现的0-1背包，顺序都可以。
可以看画表的遍历顺序确定。

2.一维数组

对二维数组的改进，直接把上一层拷贝到当前层

因为从右边开始才能保证你的dp[j-w[i]]这个是上一层的呀

for (int i = 0; i < wLen; i++){
   for (int j = bagWeight; j >= weight[i]; j--){
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
//遍历顺序
先物品后背包，不能颠倒；
且背包应该是倒叙遍历（倒叙保证了物品只被添加一次）。

完全背包

同一件物品可以使用无数次；背包改为正序遍历。

for (int i = 0; i < wLen; i++){
           //for (int j = bagWeight; j >= weight[i]; j--)
           for(int j = weight[i]; j <= bagWeight; j++){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
}

根据不同题目，两层for循环的顺序会有所不同，先物品后背包对应组合问题，先背包后物品对应排序问题。

纯完全背包问题：两层for循环任意

组合问题：先物品后背包

排列问题：先背包后物品（可以剪枝）

打家劫舍：有点像简单的动规问题。
股票问题：

二维dp问题

//递推公式
//需要二维dp数组，dp[i][0]:不持有股票的最大利润，dp[i][1]:持有股票的最大利润。
dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);

//初始化
dp[0][0] = 0;
dp[0][1] = -prices[0];

子序列问题

子序列（不连续）、子序列（连续）、二维子序列（二维dp）、编辑距离（难）、

回文：需要二维dp数组（boolean），i，j表示 i 到 j 范围内的子串是否是回文的；且遍历顺序有讲究。

152.乘积最大子数组

借助两个dp[]数组共同实现。

9.2方法

动规五步曲：

确定dp数组以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组

9.3困难题

343.整数拆分、96.不同的二叉搜索树、213.打家劫舍Ⅱ、编辑距离所有题目、647.回文子串、516.最长回文子序列、123.买股票的最佳时机Ⅲ（状态增加）

10.图论

10.1知识点

DFS、BFS、拓扑排序、

邻接表表示（3067）、

并查集：

将两个元素添加到一个集合中。
判断两个元素在不在同一个集合。

10.2方法

DFS模板

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

DFS三步曲：

确认递归函数，参数
确认终止条件
处理目前搜索节点出发的路径

BFS模板

1	`//类似层序遍历`

邻接表

List<int[]>[] graph = new ArrayList[n];
Arrays.setAll(graph, i -> new ArrayList<>());

for (int[] e : edges) {
    int u = e[0];
    int v = e[1];
    int w = e[2];
    graph[u].add(new int[]{v, w});
    graph[v].add(new int[]{u, w});
}

二分查找

74.搜索二维矩阵和240.搜索二维矩阵Ⅱ：（当每行元素为升序且每行的第一个整数大于前一行的最后一个整数时，可以使用两次二分查找找到任意一个元素；当只有行和列是升序时，无法使用两次二分）

//闭区间[low, high]写法
int low = 0;
int high = arr.length-1;
while (low <= high){
    int mid = (low + high)/2;
    if (arr[mid] < key){
        low = mid + 1;
    }else{
        high = mid -1;
    }
return low;

最终的结果：low的左侧都是low的满足判断条件的，high的右侧都是满足high的判断条件的。
当二分查找结束后，low = high + 1, low - 1指向的一定是 < target的数， high + 1 指向的一定是 > =target的数。
针对>,<,>=,<=的情况

大于：可以看作大于等于target+1的情况

小于：大于等于target的那个数左边的那个数

小于等于：大于target左边的那个数

34.当数组中有重复元素时，使用传统二分无法确定找到的是多个重复元素中的哪个。

数学

求解最大公因数

1
2
3

private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
}

判断是否是质数

boolean isPrime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return n >= 2;
}

位运算

1 2	`//快速计算一个数字二进制中1的个数 int count = Integer.bitCount(num);`

前缀和

一维前缀和

初始化：

定义preSum[0] = 0

计算任意区间的和：

[left,right]区间的和为： preSum[right + 1] - preSum[left]

二维前缀和

初始化二维前缀和

计算任意子矩阵元素和

并查集

用于处理一些不相交集合的合并问题，即连通性问题。

针对无向图。

并查集我们一般用一维数组来记录，二维可以转化为一维。

并查集主要有两个功能：

将两个元素添加到一个集合中。
判断两个元素在不在同一个集合。

class UnionFind {
    int[] parents;

    public UnionFind(int totalNodes) {
        parents = new int[totalNodes];
        for (int i = 0; i < totalNodes; i++) {
            parents[i] = i;
        }
    }
		// 合并连通区域是通过find来操作的, 即看这两个节点是不是在一个连通区域内.
    void union(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 != root2) {
            parents[root2] = root1;
        }
    }

    int find(int node) {
        while (parents[node] != node) {
            // 当前节点的父节点 指向父节点的父节点.
            // 保证一个连通区域最终的parents只有一个.
            parents[node] = parents[parents[node]];
            node = parents[node];
        }

        return node;
    }

    boolean isConnected(int node1, int node2) {
        return find(node1) == find(node2);
    }
}

题目

130、721

树状数组

相当于动态的前缀和，更新查询都是O（logn）,克服了前缀和无法更新的缺点。

使用场景

五分钟丝滑动画讲解 | 树状数组_哔哩哔哩_bilibili

〔manim | 算法 | 数据结构〕完全理解并深入应用树状数组 | 支持多种动态维护区间操作_哔哩哔哩_bilibili

蓝桥杯JAVA-12.树状数组模板（JAVA实现）_java 下载树形模板-CSDN博客

题目

3072、307

使用讲解

拆分[1,i]这个区间，按照二进制分解，13=8+4+1，拆分后形成[13,13] [9,12] [1,8]

//树状数组模板
class BinaryIndexedTree {
    private int[] tree;

    public BinaryIndexedTree(int n) {
        tree = new int[n + 1];
    }
    
	//把下标为i的元素增加x
    public void add(int i, int x) {
        while (i < tree.length) {
            tree[i] += x;
            i += i & -i;
        }
    }
    
	//返回下标[1,i]元素之和
    public int get(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & -i;
        }
        return sum;
    }
}

剑指offer

287.寻找重复数287. 寻找重复数 - 力扣（LeetCode）

240.搜索二维矩阵240. 搜索二维矩阵 II - 力扣（LeetCode）

105.从前序和中序构造二叉树105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

232.用栈实现队列232. 用栈实现队列

509.斐波那契数509. 斐波那契数 - 力扣（LeetCode）

153.寻找旋转数组的最小值153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

79.单词搜索79. 单词搜索 - 力扣（LeetCode）

191.位1的个数191. 位1的个数 - 力扣（LeetCode）

50.Pow(x, n)50. Pow(x, n) - 力扣（LeetCode）

237.删除链表中的节点237. 删除链表中的节点 - 力扣（LeetCode）

82.删除链表中的重复元素82. 删除排序链表中的重复元素 II - 力扣（LeetCode）

10.正则表达式匹配10. 正则表达式匹配 - 力扣（LeetCode）

65.有效数字65. 有效数字 - 力扣（LeetCode）

905.按奇偶排序数组905. 按奇偶排序数组 - 力扣（LeetCode）

19.删除链表的倒数第n个节点19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

142.环形链表Ⅱ142. 环形链表 II - 力扣（LeetCode）

206.反转链表206. 反转链表 - 力扣（LeetCode）

21.合并两个有序数组21. 合并两个有序链表 - 力扣（LeetCode）

572.另一颗树的子树572. 另一棵树的子树 - 力扣（LeetCode）

226.翻转二叉树226. 翻转二叉树 - 力扣（LeetCode）

101.对称二叉树101. 对称二叉树 - 力扣（LeetCode）

54.螺旋矩阵54. 螺旋矩阵 - 力扣（LeetCode）

155.最小栈155. 最小栈 - 力扣（LeetCode）

946.验证栈序列946. 验证栈序列 - 力扣（LeetCode）

102.二叉树的层序遍历

103.二叉树的锯齿形遍历103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

113.路径总和113. 路径总和 II - 力扣（LeetCode）

138.随机链表的复制138. 随机链表的复制 - 力扣（LeetCode）

297.二叉树的序列化和反序列化297. 二叉树的序列化与反序列化 - 力扣（LeetCode）

46.全排列46. 全排列 - 力扣（LeetCode）

47.全排列Ⅱ47. 全排列 II - 力扣（LeetCode）

77.组合77. 组合 - 力扣（LeetCode）

169.多数元素169. 多数元素 - 力扣（LeetCode）

215.数组中第k大元素215. 数组中的第K个最大元素 - 力扣（LeetCode）

295.数据流的中位数295. 数据流的中位数 - 力扣（LeetCode）

53.最大子数组和53. 最大子数组和 - 力扣（LeetCode）

233.数字1的个数233. 数字 1 的个数 - 力扣（LeetCode）

400.第n位数字400. 第 N 位数字 - 力扣（LeetCode）

179.最大数179. 最大数 - 力扣（LeetCode）

91.解码方法91. 解码方法 - 力扣（LeetCode）

64.最小路径和64. 最小路径和 - 力扣（LeetCode）

3.无重复字符的最长字串3. 无重复字符的最长子串 - 力扣（LeetCode）

264.丑数Ⅱ264. 丑数 II - 力扣（LeetCode）

387.字符串中的第一个唯一字符387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

493.翻转对493. 翻转对 - 力扣（LeetCode）

160.相交链表160. 相交链表 - 力扣（LeetCode）

34.在排序数组中查找元素的第一个和最后一个位置34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

268.丢失的数字268. 丢失的数字 - 力扣（LeetCode）

230.二叉搜索树中第k小的元素 230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）

104.二叉树的最大深度

110.平衡二叉树110. 平衡二叉树 - 力扣（LeetCode）

260.只出现一次的数字Ⅲ260. 只出现一次的数字 III - 力扣（LeetCode）

137.只出现一次的数字Ⅱ137. 只出现一次的数字 II - 力扣（LeetCode）

167.两数之和Ⅱ167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

829.连续整数求和829. 连续整数求和 - 力扣（LeetCode）

151.反转字符串中的单词151. 反转字符串中的单词 - 力扣（LeetCode）

189.轮转数组189. 轮转数组 - 力扣（LeetCode）

239.滑动窗口最大值239. 滑动窗口最大值 - 力扣（LeetCode）

1155.掷骰子等于目标和的方法数1155. 掷骰子等于目标和的方法数

121.买卖股票的最佳时机121. 买卖股票的最佳时机 - 力扣（LeetCode）

技巧题目

异或

268、136

非常规题目

单例模式的手写

一个私有构造函数（确保只能单例类自己创建实例）
一个私有静态变量（确保只有一个实例）
一个公有静态函数（给使用者提供调用方法）

//懒汉式一开始不会实例化，什么时候用就什么时候new，才进行实例化
//懒汉模式--线程不安全
public class Singleton{
    private static Singleton uniqueInstance;
    
    private Singleton(){}
    
    public static Singleton getUniqueInstance(){
        if(uniqueInstance == null){
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }
}
//懒汉式--线程安全
public class Singleton {
    private static Singleton uniqueInstance;
    
    private static singleton() {
    }
   
    public static synchronized Singleton getUinqueInstance() {
        if (uniqueInstance == null) {
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }
    
}
//饿汉式--线程安全
public class Singleton {
    
    private static Singleton uniqueInstance = new Singleton();
    
    private Singleton() {
    }
    
    public static Singleton getUniqueInstance() {
        return uniqueInstance;
    }
    
}
//双重检查锁--线程安全--相当于改进的懒汉式
public class Singleton {
    private volatile static Singleton uniqueInstance;
    private Singleton() {
    }
    
    public static Singleton getUniqueInstance() {
        if (uniqueInstance == null) {
            synchronized (Singleton.class) {
                if (uniqueInstance == null) {
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }  
}

排序算法

线程池的使用

public static void fixedThreadPool() {
    // 创建 2 个线程的线程池
    ExecutorService threadPool = Executors.newFixedThreadPool(2);

    // 创建任务
    Runnable runnable = new Runnable() {
        @Override
        public void run() {
            System.out.println("任务被执行,线程:" + Thread.currentThread().getName());
        }
    };

    // 线程池执行任务(一次添加 4 个任务)
    threadPool.submit(runnable);  // 执行方式 1:submit
}
//关闭线程池
threadPool.shutdown();

多线程的使用

八个经典的java多线程编程题目_java线程题目-CSDN博客

多线程轮流输出26个字母怎么实现？

public class Main {

    //字母总数
    private static final int CHARACTER_COUNT = 26;

    //当前索引
    private static volatile int currentIndex = 0;

    //并发线程总数
    private static final int THREAD_COUNT = 5;

    private static final Object LOCK = new Object();

    public static void main(String[] args) {
        for (int i = 0; i < THREAD_COUNT; i++) {
            String threadName = "thread_" + i;
            new Thread(new PrintThread(threadName, i)).start();
        }
    }


    static class PrintThread implements Runnable {

        //线程名
        private final String threadName;

        //线程号
        private final int threadNumber;

        public PrintThread(String threadName, int threadNumber) {
            this.threadName = threadName;
            this.threadNumber = threadNumber;
        }

        @Override
        public void run() {
            // 判断是否完成所有打印任务
            while (currentIndex < CHARACTER_COUNT) {
                //判断是否是当前线程的打印任务
                if (currentIndex % THREAD_COUNT == threadNumber) {
                    //上锁
                    synchronized (LOCK) {
                        if (currentIndex < CHARACTER_COUNT) {
                            //打印字母
                            System.out.println(threadName + "_print_:" + (char) (97 + currentIndex));
                            currentIndex++;
                        }
                    }
                }
            }
        }
    }
}

不使用锁呢？

死锁

public class DeadLockDemo {
    private static Object resource1 = new Object();//资源 1
    private static Object resource2 = new Object();//资源 2

    public static void main(String[] args) {
        new Thread(() -> {
            synchronized (resource1) {
                System.out.println(Thread.currentThread() + "get resource1");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread() + "waiting get resource2");
                synchronized (resource2) {
                    System.out.println(Thread.currentThread() + "get resource2");
                }
            }
        }, "线程 1").start();

        new Thread(() -> {
            synchronized (resource2) {
                System.out.println(Thread.currentThread() + "get resource2");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread() + "waiting get resource1");
                synchronized (resource1) {
                    System.out.println(Thread.currentThread() + "get resource1");
                }
            }
        }, "线程 2").start();
    }
}

ACM模式

面试 | Java 算法的 ACM 模式_java acm模式-CSDN博客

其他

刷题

http://example.com/2023/09/01/算法/刷题/

作者

sxswldy

发布于

2023年9月1日

许可协议

记录nginx的一些配置上一篇