0%

Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
for(int i = 0; i < nums.length - 2; i++){
// 跳过重复元素
if(i > 0 && nums[i] == nums[i-1]) continue;
// 计算2Sum
ArrayList<List<Integer>> curr = twoSum(nums, i, 0 - nums[i]);
res.addAll(curr);
}
return res;
}

private ArrayList<List<Integer>> twoSum(int[] nums, int i, int target){
int left = i + 1, right = nums.length - 1;
ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
while(left < right){
if(nums[left] + nums[right] == target){
ArrayList<Integer> curr = new ArrayList<Integer>();
curr.add(nums[i]);
curr.add(nums[left]);
curr.add(nums[right]);
res.add(curr);
do {
left++;
}while(left < nums.length && nums[left] == nums[left-1]);
do {
right--;
} while(right >= 0 && nums[right] == nums[right+1]);
} else if (nums[left] + nums[right] > target){
right--;
} else {
left++;
}
}
return res;
}
}

Key

tips:很久没有写Java了,花了点时间去整理了一些知识,所以上面的算法其实是ctrl+v的,现在整理一下list相关的知识:

1.List<List>为嵌套的list集合,声明方式

List<List> list = new Array()

or

List<List> list = new ArrayList<>();//recomend

2.List是一个接口,而ArrayList是List接口的一个实现类

List list = new List();//是错误的用法

List list = new ArrayList();//list会丢失ArrayList的trimToSize()方法

ArrayList list=newArrayList()

3.然后明天再回来重新写这道题

缓存

why

  • 高性能

    例如:把查完的值缓存,下次直接访问

  • 高并发

    例如:把请求排队

difference(vs memcached)

特征 redis memchched
数据结构 更复杂的数据结构,更丰富的数据操作
集群 支持 不支持
性能 单核 多核

redis线程模型

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

假设一个 Redis 服务器正在运作, 那么这个服务器的监听套接字的 AE_READABLE 事件应该正处于监听状态之下, 而该事件所对应的处理器为连接应答处理器。

如果这时有一个 Redis 客户端向服务器发起连接, 那么监听套接字将产生 AE_READABLE 事件, 触发连接应答处理器执行: 处理器会对客户端的连接请求进行应答, 然后创建客户端套接字, 以及客户端状态, 并将客户端套接字的 AE_READABLE 事件与命令请求处理器进行关联, 使得客户端可以向主服务器发送命令请求。

之后, 假设客户端向主服务器发送一个命令请求, 那么客户端套接字将产生 AE_READABLE 事件, 引发命令请求处理器执行, 处理器读取客户端的命令内容, 然后传给相关程序去执行。

redis-single-thread-model

执行命令将产生相应的命令回复, 为了将这些命令回复传送回客户端, 服务器会将客户端套接字的 AE_WRITABLE 事件与命令回复处理器进行关联: 当客户端尝试读取命令回复的时候, 客户端套接字将产生 AE_WRITABLE 事件, 触发命令回复处理器执行, 当命令回复处理器将命令回复全部写入到套接字之后, 服务器就会解除客户端套接字的 AE_WRITABLE 事件与命令回复处理器之间的关联。

key

当具备多个索引的时候,如:KEY 联合索引 (a,b,c)为索引,除(b,c)条件索引不会触发该索引表外,(a,b),(a,c),(a,b,c)均会触发上述联合索引,具体可参见explain的key类型,理论应该显示联立索引

如:

EXPLAIN SELECT FROM TABLENAME WHERE a=’2222’ AND b=‘222’*

如果你设置多个单列索引,在explain下,key的值就为其单列的索引,如上述的a列

definition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static class BinaryNode<AnyType>
{
BinaryNode(AnyType theElement)
{
this(theElement, null, null);
}

BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt)
{
element = theElement;
left = lt;
right = rt;
}

AnyType element;
BinaryNode<AnyType> left;
BinaryNode<AnyType> right;
}

private BinaryNode<AnyType> root;

posOrder

1
2
3
4
5
6
7
8
9
public void posOrder(BinaryNode<AnyType> Node)
{
if (Node != null)
{
posOrder(Node.left);
posOrder(Node.right);
System.out.print(Node.element + " ");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void posOrder(BinaryNode<AnyType> Node)
{
Stack<BinaryNode> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
int i = 1;
while(Node != null || !stack1.empty())
{
while (Node != null)
{
stack1.push(Node);
stack2.push(0);
Node = Node.left;
}

while(!stack1.empty() && stack2.peek() == i)
{
stack2.pop();
System.out.print(stack1.pop().element + " ");
}

if(!stack1.empty())
{
stack2.pop();
stack2.push(1);
Node = stack1.peek();
Node = Node.right;
}
}
}

Inner Join

SELECT column_list
FROM t1
INNER JOIN t2 ON join_condition1
INNER JOIN t3 ON join_condition2

WHERE where_conditions;

Example

id name parentid
1 北京市 0
2 海淀区 1
3 北京xx大学 2

select a.name 市,b.name 区,c.name 名
from address a
join address b on b.parentid = a.id
join address c on c.parentid = b.id
join address d on d.parentid = c.id

Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

1
2
3
> Input: ["flower","flow","flight"]
> Output: "fl"
>

Example 2:

1
2
3
4
> Input: ["dog","racecar","car"]
> Output: ""
> Explanation: There is no common prefix among the input strings.
>

Note:

All given inputs are in lowercase letters a-z.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public String longestCommonPrefix(String[] strs) {
int minLength = minLength(strs);
String same = "";
boolean isSame=false;
outer:for(int i=0;i<minLength;i++) {
char sameCharacter = strs[0].charAt(i);
isSame = false;
for(int j=0;j<strs.length;j++) {
if(strs[j].charAt(i)==sameCharacter) {
isSame = true;
}else {
isSame = false;
break outer;
}
}
if(isSame=true)same+=sameCharacter;
}
return same;
}
private int minLength(String[] strs) {
// TODO Auto-generated method stub
if(strs.length==0) {
return 0;
}
int min = strs[0].length();
for(int i=1;i<strs.length;i++) {
if(strs[i].length()<min) {
min = strs[i].length();
}
}
return min;
}
}

key

数学题,没什么关键,但是这个解法,还是存在优化空间

Perfect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) {
return "";
}

String prefix = strs[0];

for (int i = 1; i < strs.length; ++i) {
while (!strs[i].startsWith(prefix)) {
prefix = prefix.substring(0, prefix.length() - 1);

if (prefix.isEmpty()) {
break;
}
}
}

return prefix;
}
}

Problem

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321
Example 2:

Input: -123
Output: -321
Example 3:

Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int reverse(int x) {
if (x == 0) {
return 0;
}
int result =0;
long result_l = 0;
while (x != 0) {
result_l = result_l * 10 + x % 10;
x = x / 10;
}

if(result_l >= Integer.MAX_VALUE||result_l <= Integer.MIN_VALUE) {
return 0;
}else {
result = (int) result_l;
}
return result;
}
}

keys

1.倒序很简单,取余赋给新数就可以了,不过注意JavaScript或者Python的int–>float的情况

2.题目下面其实提示了int的范围,改题目1032个测试数据,有大概7个是超范围的验证数据,所以java中可以巧利用Integer.MAX来进行处理。

perfect

1
2
3
4
5
6
7
8
public int reverse(int x) {
long res = 0;
while (x != 0) {
res = res * 10 + x % 10;
x = x / 10;
}
return (int)res == res ? (int)res : 0;
}

从实习到后来的两份工作也写了不少的项目,在最近的一份工作用到了大量的消息队列(客服系统,会有大量的访客咨询消息),让我重新回顾了一下在大数据面前,为什么要用消息队列,怎么用好消息队列

理由

  • 解耦
  • 异步
  • 削峰

解耦

通过一个 MQ,Pub/Sub 发布订阅消息这么一个模型,不同微服务之间通信会更加解耦,A给BCDEF发送消息的时候,就不需要考虑他们是否宕机,如何重发等,只需要将信息发送到队列里,让他们自己去取就好了

异步

假设用户请求需要写表,那么吧任务放进队列里,等待写入,前端可以先返回,可以减少用户的等待时间,或者采用多个机器同时写数据的不同部分,加快数据的处理

削峰

就和平时用电一样,晚上电网的压力肯定会很大,如果直接把大量请求压到服务器,会直接宕机,但如果把请求排成队列,然后服务器从里面顺序取,虽然会增加延迟,但是不会宕机,满负荷运作而已

实际生产环境

咨询系统大致分为:咨询核心,端模块,微信模块,分配模块等等,访客发送的咨询信息(web)可能先经过端模块,在咨询核心模块处理前进入队列,然后,分配模块根据用户的设置,如接入客服还是机器人,按什么权重进行分配,分配给哪一个业务组进行操作,来减轻咨询核心的压力

缺点

1.系统可用性降低(MQ挂了咋整)

2.复杂度提升(消息没有重复消费,不会丢失)

3.一致性问题有待解决

特性 ActiveMQ RabbitMQ RocketMQ Kafka
单机吞吐量 万级,比 RocketMQ、Kafka 低一个数量级 同 ActiveMQ 10 万级,支撑高吞吐 10 万级,高吞吐,一般配合大数据类的系统来进行实时数据计算、日志采集等场景
topic 数量对吞吐量的影响 topic 可以达到几百/几千的级别,吞吐量会有较小幅度的下降,这是 RocketMQ 的一大优势,在同等机器下,可以支撑大量的 topic topic 从几十到几百个时候,吞吐量会大幅度下降,在同等机器下,Kafka 尽量保证 topic 数量不要过多,如果要支撑大规模的 topic,需要增加更多的机器资源
时效性 ms 级 微秒级,这是 RabbitMQ 的一大特点,延迟最低 ms 级 延迟在 ms 级以内
可用性 高,基于主从架构实现高可用 同 ActiveMQ 非常高,分布式架构 非常高,分布式,一个数据多个副本,少数机器宕机,不会丢失数据,不会导致不可用
消息可靠性 有较低的概率丢失数据 基本不丢 经过参数优化配置,可以做到 0 丢失 同 RocketMQ
功能支持 MQ 领域的功能极其完备 基于 erlang 开发,并发能力很强,性能极好,延时很低 MQ 功能较为完善,还是分布式的,扩展性好 功能较为简单,主要支持简单的 MQ 功能,在大数据领域的实时计算以及日志采集被大规模使用

所以中小型公司,用 RabbitMQ 是不错的选择

大型公司,基础架构研发实力较强,用 RocketMQ 是很好的选择

如果是大数据领域的实时计算、日志采集等场景,用 Kafka 是业内标准的,绝对没问题,社区活跃度很高,绝对不会黄,何况几乎是全世界这个领域的事实性规范。

递归优化

原因:

在 Java 中,每个线程都有独立的 Java 虚拟机栈。栈具有后入先出的特点,递归调用也是需要后调用的方法先返回,因此使用栈来存储递归调用的信息。这些信息存储在栈帧中,每个 Java 方法在执行时都会创建一个栈帧,用来存储局部变量表操作数栈常量池引用等信息。在调用方法时,对应着一个栈帧入栈,而方法返回时,对应着一个栈帧出栈。

img

随着栈帧frame的增多,将会导致Stack Overflow的报错,例如

1
2
3
4
5
6
7
int f(int i)
{
if(i == 1 || i == 2)
return 1;
else
return (f(i - 1) + f(i - 2));
}

解决方法1:递归–>非递归

其实很简单,就是用一个临时变量,来保存中间的值,而不是压入堆栈中,

1
2
3
4
5
6
7
8
9
10
11
//费波纳列数列,前两位是1,之后没位数是前两位数的和
private static void fibonacci(int n) {
int temp1=1,temp2=1,temp;
for (int i = 1; i <=n ; i++) {
temp=temp1+temp2;
temp1=temp2;
temp2=temp;
}
System.out.println();
}
//粘贴于网上

解决办法2:递归–>尾递归

尾递归就是当函数在最后一步(尾部)调用自身,如:

1
2
3
function f(x){
return g(x);
}

以下算法来自阮一峰教程:

1
2
3
4
5
6
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}

factorial(5) // 120

该算法并非是尾递归,因为其在返回值的时候进行了一个乘法操作,所以还是普通的递归,复杂度为O(n),而如果改成尾递归,则:

1
2
3
4
5
6
function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}

factorial(5, 1) // 120

该算法只需要计算

factorial(5,1)

factorial(4,5)

factorial(3,20)

factorial(2,60)

factorial(1,120)

在进入新的递归函数时,尾递归不再需要使用栈帧保存数据,允许抛弃旧的栈帧,那么只需要保存一个栈帧即可

参考资料: