Java-03

目录

算法

1.小美的因子查询

2.小美的密码

3.小美的数组删除

4.小美和大富翁

知识点

InnoDB中的行级锁是怎么实现的？

介绍一下Java中的IO流

讲讲Java的跨平台原理

COUNT（1）与COUNT（*）区别

Redis

为什么要用缓存

使用 Redis 的好处

什么是 RedisRedis 是一个开源（BSD 许可）、基于内存、支持多种数据结构的存储系统，可以作为数据库、缓

为什么 使用 Redis 而不是用 Memcache

为什么 Redis 单线程模型效率也能那么高

Redis 的线程模型

为什么 Redis 需要把所有数据放到内存中

Redis 的同步机制

Redis关于数据结构的优化

Redis主从同步，从从同步

第一次主从同步（全量同步）

从从同步（链式复制）

---

算法

1.小美的因子查询

很简单的一道题。

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n=sc.nextInt();for(int i=0;i<n;i++){int k=sc.nextInt();if(k%2==0){System.out.println("YES");}else{System.out.println("NO");}}}
}

也可以使用-来判断是否为偶数

if ((k & 1) == 0)

2.小美的密码

 

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine();String p0 = sc.nextLine();Set<String> set = new HashSet<>();int[]strings = new int[1001];for (int i = 0; i < n; i++) {String p = sc.nextLine();if (!set.contains(p)) {set.add(p);++strings[p.length()];}}int sum = 0;for (int i = 1; i < p0.length(); i++) {sum += strings[i];}int max = sum + strings[p0.length()];System.out.println(++sum + " " + max);}
}

3.小美的数组删除

共20个案例，只过了17个案例。 

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int T = in.nextInt();for (int t = 0; t < T; t++) {int n = in.nextInt();long k = in.nextLong();long x = in.nextLong();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = in.nextInt();}long minCost = Math.min(calculateSequentialCost(n, x), calculateMexCost(a, k));System.out.println(minCost);}in.close();}private static long calculateSequentialCost(int n, long x) {return (long) n * x;}private static long calculateMexCost(int[] a, long k) {Set<Integer> present = new HashSet<>();for (int num : a) {present.add(num);}int mex = 0;while (present.contains(mex)) {mex++;}return k * mex;}
}

上面代码只预测了两种情况，

一种是执行n次全部删除，也就是n*x。

一种是找出数组中那个从未出现的最小非负整数，k*mex。

下面的则直接AC：

（倒序求非负最小整数）

import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int t = in.nextInt();for (int i = 0; i < t; i++) {int n = in.nextInt();long k = in.nextInt();long x = in.nextInt();HashSet<Integer> set = new HashSet<>();int[] as = new int[n];for (int j = 0; j < n; j++) {as[j] = in.nextInt();}long min = x * n;int cur = 0;for (int j = n - 1; j >= 0; j--) {set.add(as[j]);while (set.contains(cur)) {cur++;}min = Math.min(x * j + k * cur, min);}System.out.println(min);}}
}

4.小美和大富翁

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;public class Main {static List<List<Integer>> list = new ArrayList<>();static boolean[] vis = new boolean[5];static int[] b = new int[4];private static void fun(int cnt) {if (cnt == 4) {list.add(Arrays.asList(b[0], b[1], b[2], b[3]));return;}for (int i = 1; i <= 4; i++) {if (!vis[i]) {vis[i] = true;b[cnt++] = i;fun(cnt);vis[i] = false;cnt --;}}return;}public static void main(String[] args) {Scanner in = new Scanner(System.in);Arrays.fill(vis, false);int n = in.nextInt();int[] a = new int[n + 1];for (int i = 1; i <= n; i++) {a[i] = in.nextInt();}fun(0);int x = n / 10;int y = n % 10;int now = 0;long ans = 0;for (int i = 0; i < x; i++) {long res = (long)-1e18;boolean q = false;for (List<Integer> lst : list) {int u = now;long temp = 0;int j = 0;for (j = 0; j < 4; j++) {u += lst.get(j);temp += 1l * a[u];if (ans + temp < 0) break;}if (j == 4) q = true;res = Math.max(res, temp);}if (!q) {System.out.println(-1);return;}now += 10;ans += res;}long res = ans;boolean q = (now == n);for (List<Integer> lst : list) {int u = now;long temp = 0;for (int i = 0; i < 4; i++) {u += lst.get(i);if (u > n) break;temp += 1l * a[u];if (res + temp < 0) break;if (u == n) {q = true;ans = Math.max(ans, res + temp);break;}}}System.out.println(q ? ans : -1);}
}

恭喜我获得一个勋章🎖️ 

知识点

InnoDB中的行级锁是怎么实现的？

InnoDB行锁是通过给索引上的索引项加锁来实现的，只有通过索引条件检索数据，InnoDB才使用行级锁，否则，InnoDB将使用表锁

介绍一下Java中的IO流

Java中的IO流主要有4个基类：InputStream、OutputStream、Reader、Writer。其中，InputStream代表字节输入流，OutputStream代表字节输出流，Reader代表字符输入流，Writer代表字符输出流。其他的IO流都是从这4个基类派生而来的，并且子类的名字往往以基类的名字结尾。之后Java提供了新的IO模型（NIO），这种IO模型是基于IO多路复用实现的。

讲讲Java的跨平台原理

在说这个之前，我们先了解一下：

平台：指的是操作系统（Windows，Linux，Mac）。

跨平台：是指Java语言编写的程序，一次编译后，可以在多个系统平台上运行。

实现跨平台：

JVM充当了Java程序与底层操作系统的中间层，提供了跨平台的能力，使得Java程序可以在不同的操作系统上运行。不是能在所有的平台上运行，关键是该平台是否能安装相应的虚拟机，也就是说只要该系统可以安装相应的Java虚拟机（JVM），该系统就可以运行Java程序。

JVM在执行Java字节码时，实际上最终还是把字节码解释成具体平台上的机器指令执行。

COUNT（1）与COUNT（*）区别

它们返回结果是相同的，即满足条件的记录数或所有记录的条数，它们在性能方面也几乎是相同的，在实际使用中也没有实质性的差别。

Redis

为什么要用缓存

使用缓存的目的就是提升读写性能。而实际业务场景下，更多的是为了提升读性能，带来更好的性

能，带来更高的并发量。 Redis 的读写性能比 Mysql 好的多，我们就可以把 Mysql 中的热点数据缓

存到 Redis 中，提升读取性能，同时也减轻了 Mysql 的读取压力。

使用 Redis 的好处

• 读取速度快，因为数据存在内存中，所以数据获取快；
• 支持多种数据结构，包括字符串、列表、集合、有序集合、哈希等；
• 支持事务，且操作遵守原子性，即对数据的操作要么都执行，要么都不支持；
• 还拥有其他丰富的功能，队列、主从复制、集群、数据持久化等功能。

什么是 Redis
Redis 是一个开源（BSD 许可）、基于内存、支持多种数据结构的存储系统，可以作为数据库、缓

存和消息中间件。它支持的数据结构有字符串（strings）、哈希（hashes）、列表（lists）、集合

（sets）、有序集合（sorted sets）等，除此之外还支持 bitmaps、hyperloglogs 和地理空间（

geospatial ）索引半径查询等功能。

它内置了复制（Replication）、LUA 脚本（Lua scripting）、LRU 驱动事件（LRU eviction）、事

务（Transactions）和不同级别的磁盘持久化（persistence）功能，并通过 Redis 哨兵（哨兵）和

集群（Cluster）保证缓存的高可用性（High availability）。

为什么 使用 Redis 而不是用 Memcache

Memcache 与 Redis 区别：

• Redis 和 Memcache 都是将数据存放在内存中，都是内存数据库。不过 Memcache 还可用于缓存其他东西，例如图片、视频等等。
• Memcache 仅支持key-value结构的数据类型，Redis不仅仅支持简单的key-value类型的数据，同时还提供list，set，hash等数据结构的存储。
• 虚拟内存– Redis 当物理内存用完时，可以将一些很久没用到的value 交换到磁盘
• 分布式–设定 Memcache 集群，利用 magent 做一主多从; Redis 可以做一主多从。都可以一主一从
• 存储数据安全– Memcache 挂掉后，数据就没了； Redis 可以定期保存到磁盘（持久化）
• Memcache 的单个value最大 1m ， Redis 的单个value最大 512m 。
• 灾难恢复– Memcache 挂掉后，数据不可恢复; Redis 数据丢失后可以通过 aof 恢复
• Redis 原生就支持集群模式， Redis3.0 版本中，官方便能支持Cluster模式了， Memcached 没有原生的集群模式，需要依赖客户端来实现，然后往集群中分片写入数据。
• Memcached 网络IO模型是多线程，非阻塞IO复用的网络模型，原型上接近于 nignx 。而 Redis 使用单线程的IO复用模型，自己封装了一个简单的 AeEvent 事件处理框架，主要实现类 epoll，kqueue 和 select ，更接近于Apache早期的模式。

为什么 Redis 单线程模型效率也能那么高

1. C语言实现，效率高

2. 纯内存操作

3. 基于非阻塞的IO复用模型机制

4. 单线程的话就能避免多线程的频繁上下文切换问题

5. 丰富的数据结构（全称采用hash结构，读取速度非常快，对数据存储进行了一些优化，比如亚

索表，跳表等）

Redis 的线程模型

Redis 内部使用文件事件处理器 file event handler ，这个文件事件处理器是单线程的，所以 Redis 才叫做单线程的模型。它采用 IO 多路复用机制同时监听多个 socket ，根据 socket 上的事件来选择对应的事件处理器进行处理。

文件事件处理器的结构包含 4 个部分：

1. 多个 socket 。

2. IO 多路复用程序。

3. 文件事件分派器。

4. 事件处理器（连接应答处理器、命令请求处理器、命令回复处理器）。

多个 socket 可能会并发产生不同的操作，每个操作对应不同的文件事件，但是 IO 多路复用程序会监听多个 socket，会将 socket 产生的事件放入队列中排队，事件分派器每次从队列中取出一个事件，把该事件交给对应的事件处理器进行处理。

为什么 Redis 需要把所有数据放到内存中

Redis 将数据放在内存中有一个好处，那就是可以实现最快的对数据读取，如果数据存储在硬盘

中，磁盘 I/O 会严重影响 Redis 的性能。而且 Redis 还提供了数据持久化功能，不用担心服务器重

启对内存中数据的影响。其次现在硬件越来越便宜的情况下，Redis 的使用也被应用得越来越多，

使得它拥有很大的优势。

Redis 的同步机制

Redis 支持主从同步、从从同步。如果是第一次进行主从同步，主节点需要使用 bgsave 命令，再将

后续修改操作记录到内存的缓冲区，等 RDB 文件全部同步到复制节点，复制节点接受完成后将

RDB 镜像记载到内存中。等加载完成后，复制节点通知主节点将复制期间修改的操作记录同步到复

制节点，即可完成同步过程

Redis关于数据结构的优化

• 哈希（Hash）结构：Redis的哈希结构可以高效地存储对象，通过键直接访问哈希表中的字段，从而减少内存使用并提高读取速度。
• 压缩列表（ziplist）：当哈希、列表、集合或有序集合的元素数量较少且元素大小较小时，Redis会使用压缩列表来存储，这可以减少内存的使用。
• 跳表（Skip List）：在有序集合中，Redis使用跳表来实现快速的区间查询。

Redis主从同步，从从同步

第一次主从同步（全量同步）

1. 建立连接：

• • 从节点通过发送PSYNC命令给主节点来请求同步。
  • 如果是从节点第一次同步，或者之前没有同步的历史，那么会进行全量同步。

1. 主节点执行bgsave：

• • 主节点接收到同步请求后，会执行一个bgsave命令。
  • bgsave命令会在后台生成一个子进程，该子进程负责创建当前数据库的快照（RDB文件），而主进程仍然可以继续处理客户端的请求。

1. 传输RDB文件：

• • 一旦RDB文件创建完成，主节点会将这个文件传送给从节点。
  • 传输过程中，主节点会继续将所有写命令记录到缓冲区中，确保从节点在加载RDB文件后能够接收到这些命令。

1. 从节点加载RDB文件：

• • 从节点接收到RDB文件后，会开始加载这个文件到内存中，从而与主节点的数据状态保持一致。

1. 同步缓冲区命令：

• • 当从节点加载完RDB文件后，会通知主节点将缓冲区中的所有写命令发送给它。
  • 主节点将缓冲区中的命令以Redis协议格式发送给从节点，从节点会执行这些命令，以确保其数据状态与主节点保持一致。

1. 持续同步：

• • 在全量同步完成后，主节点会继续将新的写命令发送给从节点，实现持续的复制。
  • 如果主节点和从节点之间的连接断开，从节点会尝试重新连接，并请求部分同步（如果可能的话），这样可以避免重新执行全量同步。

从从同步（链式复制）

在某些情况下，从节点也可以作为其他从节点的主节点，形成链式复制。这种情况下，同步过程如下：

1. 从节点A（作为主节点）完成了与原主节点的全量同步。
2. 从节点B请求与从节点A同步。
3. 从节点A将它的RDB文件（可能已经是同步过程中的一个中间状态）发送给从节点B。
4. 从节点B加载RDB文件，并请求从节点A发送后续的写命令。

• 主节点的缓冲区大小：主节点的复制缓冲区大小由repl-backlog-size配置项控制。如果从节点断开连接的时间过长，导致缓冲区中的数据被覆盖，那么从节点将无法进行部分同步，而必须重新执行全量同步。
• 网络带宽：全量同步会涉及到大量数据的传输，因此需要足够的网络带宽。
• 从节点的性能：从节点加载RDB文件的速度也影响着同步的效率。

 

近日总结：看到一段有意思的。

她看着我，

我便也看着她，

她就扭过头去不看我，

我也低下头去不看她，

她便又悄悄地瞅我，

我抬头捉住她的目光，

她就又把头撇过去了。

害，这小妮子。