Zehai's Blog

Posted on Edited on In

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;
        }
    }
}

Posted on Edited on In

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

Posted on Edited on In

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
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
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;
    }
}

Posted on Edited on In

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;
    }

Posted on Edited on In

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

理由

  • 解耦
  • 异步
  • 削峰

解耦

通过一个 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 是业内标准的，绝对没问题，社区活跃度很高，绝对不会黄，何况几乎是全世界这个领域的事实性规范。

Posted on Edited on In

递归优化

原因：

在 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)

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

参考资料：

0%