design
13 分钟 读完 (大约 1942 个字)

幂等设计

请求幂等性总结：

1.是否需要幂等。比如查询，insert含唯一索引的表，update set数据，delete by id 等简单场景是天然幂等。不需要额外做幂等操作。无法这样的比如要做数据的累加，就要做幂等。

2.如何判断重复。

业务唯一键，查记录表或流水表，根据记录的有无和状态来判断。

3.实现。

  1. 简单的话接口直接实现, 但通常幂等逻辑是有通用性的
  2. 如果服务多接口使用写幂等工具类
  3. 如果多服务使用一套幂等逻辑，写sdk
  4. 最复杂的多服务间幂等，还无法都获取到记录结果，就要在sdk统一读写幂等表，读写相同的幂等记录做幂等

4.并发处理

  1. 单机情况下，使用java锁synchronized
  2. 使用数据库锁，悲观锁：select for update，乐观锁：update set XXX and version = 2 where version = 1
  3. 使用分布式锁：
    redis锁：1.过期时间导致并发问题，2.主从切换时锁丢失
    zookeeper锁：写能力不如redis

原文：

  1. 维度1 : 是否需要幂等处理？

    1. 查询场景

      select 字段 from 表 where 条件 ，这种是不会对数据产生任何变化，所以查询场景具备天然幂等性；注意这里的幂等是对系统资源的改变，而不是返回数据的结果，即使返回结果不相同但是该操作本身没有副作用，所以幂等

    2. 新增场景

      insert into 表 （order_id，字段） value（1，字段） ：

      1）如果order_id为唯一键，重复操作上面的业务，只会插入一条数据，具备天然幂等性。

      2）如order_id不是唯一键，那上面业务多次操作，数据都会新增多条，不具备幂等性。

    3. 修改场景

      1）直接赋值场景：update 表 set price = 20 where id=1 ；分析： 这种场景不管执行多少次，price都一样，具备天然幂等性；

      2）计算赋值场景：update 表 set price = price + 20 where id=1，每次操作price数据都不一样，不具备幂等性；

    4. 删除场景

      1）delete from 表 where id=1 ，多次操作，结果一样，具备天然幂等性

      2）delete from 表 where price > 20,多次操作，结果一样，具备天然幂等性

      总结：单纯的查询接口，删除接口，没有计算的更新接口，每次执行结果是天然幂等的，其他情况则可能需要做幂等

  2. 维度2 : 是否需要并发控制？

    1. 场景1: 唯一键数据的重复插入

      此场景不需要并发控制，天然并发安全，但需要业务方处理DuplicateKeyException异常

    2. 场景2：转账，若 a >= 100, a -100， b+100

      此场景为了保证数据一致性，事务原子性，需要顺序执行

      总结：除了极其简单的场景外，大部分幂等场景都需要并发控制，需要强锁还是弱锁

  3. 维度3 : 如何判断是重复请求？

    1. 场景1: 无业务主键的新增

      此场景下需要服务端颁发token，通过token判断是否重复，做防重复提交

    2. 场景2: 有业务唯一键的新增

      此场景下可以使用业务唯一键判断是否重复

    3. 场景3: 有业务唯一键的更新

      此场景下可以使用业务数据对应的状态判断是否重复

  4. 维度4 : 重复请求处理方式？

    1. 场景1：消息重复消费

      此场景下，不需要给上游一个返回，重复执行只需要丢弃

    2. 场景2：前端重复提交

      此场景下，需要给用户一个提示，那么重复请求可以直接抛出一个DuplicateReqeustException异常，由上层捕获，前端展示“请不要重复请求”

    3. 场景3: 底层的转账接口

      此场景下，同一笔转账，重复调用第一次若成功了，第二次应该返回相同“成功”，若第一次失败了，第二次返回业务执行结果

      结论：根据不同场景，应该有不同的结束方式，应该由业务方自己决定是丢弃，抛异常，直接返回，还是执行业务逻辑

  5. 维度5 : 重复请求返回是否相同？

    1. 场景1：第一次执行成功，第二次返回应该与第一次相同

    2. 场景2：第一次执行因为代码原因导致的异常而失败，第二次返回应该与第一次相同

    3. 场景3：第一次执行因为网络原因失败，第二次应该执行业务逻辑，返回结果可能不一致

      总结：根据第一次执行的成功和失败，判断第二次应该执行业务逻辑还是直接返回相同结果

  6. 维度6 : 重复请求调用下游如何处理？

    1. 场景1: 业务逻辑中，有调用下游rpc接口，第一次执行失败，第二次重复执行业务逻辑再次调用下游接口

      总结：此场景本质上是一个分布式一致性问题，需要业务方自己解决，或者保证下游接口也是幂等的

  7. 识别相同请求

    1. token机制：每次提交上来的请求，都带上一个token标识，同一个token只处理一次，例如：新增场景的防止重复提交
    2. 业务唯一标识：使用id或者unique key，例如：支付后，支付凭证落库
    3. 业务唯一标识 + 状态：支付后，通过支付凭证号和当前订单状态，更新订单状态
    4. 在业务侧建立同库幂等数据表，记录请求唯一键和执行状态，执行成功后更新状态为成功

  8. 并发处理方式

    1. 单机情况下，使用java锁synchronized

    2. 使用数据库锁，悲观锁：select for update，乐观锁：update set XXX and version = 2 where version = 1

    3. 使用分布式锁：

      redis锁：1.过期时间导致并发问题，2.主从切换时锁丢失

      zookeeper锁：写能力不如redis

  9. 一致性保证

    1. 业务方需保证原子性，本地更新都在一个事务里
    2. 若无法保证分布式事务，下游接口需是幂等的，且本地事务必须重试达到最终一致

SDK设计#

  1. 并发控制
    1. 提供注解，按业务自动划分，提供指定幂等唯一键
    2. 提供并发控制，分布式锁服务（redis或zk），指定分布式锁时间
    3. 提供并发时幂等处理方式，丢弃/抛异常/等待锁
    4. 提供降级选择，不强依赖于锁服务
    5. 提供token注解，防止重复提交
  2. 判断重复请求

处理方式 优点 缺点

方案一 业务方自己判断 业务方需要自己考虑判重

方案二 sdk提供判重接口，由业务方实现 可以实现重复请求的通用处理

方案三 幂等表：在业务侧建立同库幂等数据表，记录请求唯一键和执行状态，执行成功后更新状态为成功 业务方无需再关心判重问题 数据量大，开发量大，复杂度较高

redis
2 分钟 读完 (大约 333 个字)

缓存穿透、击穿、雪崩

缓存穿透#

定义: 访问一个不存在的key，缓存不起作用，请求会穿透到DB，流量大时DB会挂掉。

解决方案：

  1. 缓存空值 （值少时）
  2. 布隆过滤器， 特性: 没有的肯定没有，有的不一定有

缓存击穿#

定义：并发性,一个存在的key，在缓存过期的一刻，同时有大量的并发请求，这些请求都会击穿到DB，造成瞬时DB请求量大、压力骤增。

解决方案：

  1. 分布式锁，在访问key之前，采用分布式锁SETNX（set if not exists）来设置另一个短期key来锁住当前key的访问，访问结束再删除该短期key

缓存雪崩#

定义：大量的key设置了相同的过期时间，或者某台服务器宕机，导致大量缓存在同一时刻全部失效，造成瞬时DB请求量大、压力骤增，引起雪崩。

解决方案：

  1. 将key的过期时间设置时添加一个随机时间，分散过期时间
  2. 如果是热点key，可以加分布式锁，减少并发量
  3. 二级缓存（本地缓存），减少db压力
旅游
6 分钟 读完 (大约 849 个字)

2019国庆上海苏州四日游记

9月30日 外滩 很久以前羊肉串#

接到小菜猫，先去旅馆放下东西，直接去外滩。 南京东路上都是武警，维持秩序，看着有点厉害。我是第二次来外滩，小菜猫是第一次，还是很好看的，人很多，当晚有灯光表演，30分钟一次，我们赶上了一半。海风很舒服。整个外滩的爱国氛围也很浓厚。

外滩

去吃了很久以前羊肉串，吃到晚上12点多，羊肉真的好嫩，当面烤也是特色，配上啤酒，舒服，长肉。

10月01日 武康路#

武康路没有拍什么照片，是一条安静古老的小路，下着小雨，氛围很好

在这里出发去世界上最大的星巴克

一栋星巴克，里面两层。点了一杯奶和一杯咖啡。没有太好喝但环境很好，主要咖啡☕️咱也不懂。里面有些机器在做咖啡，全流程透明化。

下午5点多了，风雨越来越大，继续出发，去豫园&城隍庙，但到了之后风雨太大，也没找到豫园在哪，哈哈，就转地铁回去了。

晚上去吃了和府捞面，办了会员，赠了个虾，嚯，真虾(瞎)

10月2日 蟹面 诚品书店 金鸡湖#

上午出门去吃蟹面，尴尬的是行李太沉，不该带着行李去吃，不过蟹面还是很不错，从没吃过这样式儿的，带汤的那碗很不错，人超级多，排了好一会儿

出发去苏州~

上海到苏州也太快了，半个小时就到了，小菜猫睡了一会儿，我还没睡就到了，放下行李先奔了金鸡湖

诚品书店太安静了，没怎么拍照片，金鸡湖还是很美的，毕竟北方湖还是很少的。见到漂亮的湖，小风一吹，还是很爽。

美美哒

晚上吃了高级台湾自助火锅，到了才发现是自助，不过还是靠实力吃回来了。

10月3日 怡园 留园#

上午要去留园，然后我拉肚子，耽误了坐车，就先去了怡园，没想到怡园还不错，后来发现留园反而因为人多，毫无观赏体验。

怡园

留园就不放了，人太多了，下次不去那么多人的地方了。。

10月4日 归途#

沿途的风光也不错，回家啦

旅游
2 分钟 读完 (大约 238 个字)

2019国庆上海苏州四日游行程计划

2019 国庆上海苏州四天旅行#

行程规划#

北京前往上海 9.30 14:10 - 20:09 G141 检票口 11

9月30日#

住宿 上海家荣酒店公寓(中山公园店)
21点 很久以前羊肉串(中山公园店)

10月1日#

上午 9点
武康路
上午 11点
田子坊
下午1点
豫园&城隍庙 ，明朝时期的私人花园，拥有“城市山林”、“奇秀甲于东南”两种美称，是江南园林中的一颗明珠。
下午4点
东方明珠
南京路步行街
下午7点半
外滩 外滩观光隧道

10月2日#

上午9点
中华艺术宫
上午12点
退房
下午14:41 上海前往苏州 14:41 - 15:15 D3010 检票口 25A
住宿 骏怡连锁酒店
下午4点半
诚品书店
金鸡湖
阳澄湖大闸蟹

10月3日#

上午9点
拙政园
苏州博物馆
下午1点
虎丘
留园
网师园夜景

10月4日#

苏州前往北京 10.4 11:40 - 17:10 G128 检票口 A1

2 分钟 读完 (大约 345 个字)

指针算法

LinkedList

014-链表中倒数第k个结点#

双指针，快指针先走k-1步，然后快慢指针一起走，当快指针走到最后一个节点，慢指针指向倒数第K个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k ==0 ){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        for(int i=0;i<k;i++){
            if(fast == null){
                return null;
            }
            fast=fast.next;
        }
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
}

041-和为S的连续正数序列(滑动窗口思想) *#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ArrayList<ArrayList<integer> > FindContinuousSequence(int sum) {
	ArrayList<ArrayList<integer>> p=new ArrayList<ArrayList<integer>>();
	//因为是连续的，构成等差数列，用等差数列的求和公式
	int low=1,hight=2;
	while(low<hight) {
		int temp=(low+hight)*(hight-low+1)/2;
		//如果相等，说明这个连续的数列可以构成和为sum
		if(temp==sum) {
			ArrayList<integer> a=new ArrayList<integer>();
			for(int i=low;i<=hight;i++) {
				a.add(i);
			}
			p.add(a);
			//继续找下一组
			low++;
		}else if (temp<sum) {
			hight++;
		}else {
			low++;
		}
	}
	return p;
}

042-和为S的两个数字(双指针思想) *#

左右双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    int l = 0, r = array.length - 1;
    while (l < r) {
        if (array[l] + array[r] == sum) {
            list.add(array[l]);
            list.add(array[r]);
            break;
        } else if (array[l] + array[r] > sum) {
            r--;
        } else {
            l++;
        }
    }
    return list;
}

盛最多水的容器#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxAreaSize = 0;
    int h = 0, w = 0;
    while (left < right) {
        h = Integer.min(height[left], height[right]);
        w = right - left;
        maxAreaSize = Integer.max(w * h, maxAreaSize);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxAreaSize;
}

三数之和#

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
public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList();
    // 排序
    Arrays.sort(nums);
    int l,r,sum;
    // 固定最左边的数字, 保证不重复
    for (int i=0; i<nums.length; i++) {

        if(i > 0 && nums[i] == nums[i-1]) continue;

        l = i+1;
        r = nums.length - 1;
        while (l < r) {
            sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                result.add(Arrays.asList(nums[i],nums[l],nums[r]));
                while (l < r && nums[l] == nums[l + 1]) l++;   // 去重
                while (l < r && nums[r] == nums[r - 1]) r--;   // 去重
                l++;
            } else if (sum < 0) {
                l++;
            } else {
                r--;
            }
        }
    }
    return result;
}
5 分钟 读完 (大约 794 个字)

链表算法

LinkedList

014-链表中倒数第k个结点#

双指针，快指针先走k-1步，然后快慢指针一起走，当快指针走到最后一个节点，慢指针指向倒数第K个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head == null || k ==0 ){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        for(int i=0;i<k;i++){
            if(fast == null){
                return null;
            }
            fast=fast.next;
        }
        while(fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
}

015-反转链表#

  1. 无需额外空间，依次反转，三个指针
  2. 用栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode reverseList(ListNode head) {
        // 判断链表为空或长度为1的情况
    if(head == null || head.next == null){
        return head;
    }
    ListNode pre = null; // 当前节点的前一个节点
    ListNode cur = head;
    ListNode next = null; // 当前节点的下一个节点
    while( cur != null){
        next = cur.next; // 记录当前节点的下一个节点位置；
        cur.next = pre; // 让当前节点指向前一个节点位置，完成反转
        pre = cur; // pre 往右走
        cur = next;// 当前节点往右继续走
    }
    return pre;
}

016-合并两个有序链表#

和归并一样

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
public ListNode Merge(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    } 
    if (list2 == null) {
        return list1;
    }
    
    ListNode headNode = new ListNode(-1);
    ListNode pNode = headNode;
    pNode.next = null;
    
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            pNode.next = list1;
            pNode = list1;
            list1 = list1.next;
        } else {
            pNode.next = list2;
            pNode = list2;
            list2 = list2.next;
        }
    }
    
    if (list1 != null) {
        pNode.next = list1;
    }
    if (list2 != null) {
        pNode.next = list2;
    }
    return headNode.next;
}

036-两个链表的第一个公共结点#

思路1： 长的先走k步, 再快慢一起
思路2： 两个指针从两个链表走，如果一个走完就走另一个，这样先走短的指针会先走长的k步，其实第二条的时候后半部分是一样的，前面的长度相同，所以这时候走到后面肯定是一样的.

1
2
3
4
5
6
7
8
9
10
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if (pHead1 == null || pHead2 == null) return null;
    ListNode p1 = pHead1;
    ListNode p2 = pHead2;
    while (p1 != p2) {
        p1 = p1 == null ? pHead2 : p1.next;
        p2 = p2 == null ? pHead1 : p2.next;
    }
    return p1;
}

055-链表中环的入口结点#

先快慢节点，确定有环，并找到相交节点，再从相交节点和开始节点同时开始，当相等的时候，就是环的入口节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode entryNodeOfLoop(ListNode pHead) {
    if(pHead==null|| pHead.next==null|| pHead.next.next==null) return null;
    ListNode fast=pHead.next.next;
    ListNode slow=pHead.next;
    /////先判断有没有环
    while(fast!=slow){
        if(fast.next!=null&& fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }else{
            //没有环,返回
            return null;
        }
    }
    //循环出来的话就是有环，且此时fast==slow.
    fast = pHead;

    while(fast!=slow){
        fast=fast.next;
        slow=slow.next;
    }

    return slow;
}

056-删除链表中重复的结点#

假的头结点，三个指针，pre、cur、next, 判断是相等去掉中间重复 还是 整体后移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode deleteDuplication(ListNode pHead)
{
    ListNode head = new ListNode(-1);
    head.next = pHead;
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.next != null && cur.val == cur.next.val) {
            while (cur.next != null && cur.val == cur.next.val) {
                cur = cur.next;
            }
            pre.next = cur.next;
            cur = cur = cur.next;
        } else {
            pre = pre.next;
            cur = cur.next;
        }
    }
    return head.next;
}

19. 删除链表的倒数第N个节点#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;

    for (int i = 0; i < n + 1; i++) {
        first = first.next;
        if (first == null) {
            return dummy;
        }
    }

    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}
2 分钟 读完 (大约 225 个字)

栈&队列算法

021-栈的压入、弹出序列 *#

循环压入序列，先压入，再判断是否可以弹出，如果可以，循环弹出，更新弹出序列下标，最终如果栈正好为空，则表示成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean IsPopOrder(int [] pushA,int [] popA) {
    if (pushA.length == 0 || popA.length == 0 || popA.length != pushA.length)
        return false;
    Stack<Integer> stack = new Stack<>();
    int j = 0;
    for (int i = 0; i < pushA.length; i++) {
        stack.push(pushA[i]);

        while (!stack.isEmpty() && stack.peek() == popA[j]){
            stack.pop();
            j++;
        }
    }
    return stack.isEmpty();
}

215. 数组中的第K个最大元素#

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findKthLargest(int[] nums, int k) {
    if (nums.length < k) {
        return -1;
    }
    Queue<Integer> queue = new PriorityQueue<Integer>((a, b) -> a - b);
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        queue.offer(num);
        if (queue.size() > k) {
            queue.poll();
        }
    }
    return queue.peek();
}
7 分钟 读完 (大约 1040 个字)

二叉树算法

- 二叉树的打印，前中后序遍历, 递归&非递归#

非递归先序遍历#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> preOrder(BinaryTree node) {

    List<Integer> list=new ArrayList<Integer>();
    if(node==null) return list;
    Stack<BinaryTree> stack= new Stack<BinaryTree>();
    while(node!=null || !stack.empty()) {
        if(node!=null){
            list.add(node.val);
            stack.push(node);
            node=node.left;
        } else {
            node=stack.pop();
            node=node.right;
        }
   } 
   return list;
}

非递归中序遍历#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> inOrder(BinaryTree node) {

    List<Integer> list=new ArrayList<Integer>();
    if(node==null) return list;
    Stack<BinaryTree> stack= new Stack<BinaryTree>();
    while(node!=null || !stack.empty()) {
        if(node!=null){
            stack.push(node);
            node=node.left;
        } else {
            node=stack.pop();
            list.add(node.val);
            node=node.right;
        }
   } 
   return list;
}

非递归后序遍历#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> postOrder(BinaryTree node) {

    List<Integer> list=new ArrayList<Integer>();
    if(node==null) return list;
    Stack<BinaryTree> stack= new Stack<BinaryTree>();
    while(node!=null || !stack.empty()) {
        if(node!=null){
            list.add(0, node.val);
            stack.push(node);
            node=node.right;
        } else {
            node=stack.pop();
            node=node.left;
        }
   } 
   return list;
}

022-从上往下打印二叉树 *#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(root == null) return result;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            result.add(temp.val);
            if(temp.left != null) queue.offer(temp.left);
            if(temp.right != null) queue.offer(temp.right);
        }
        return result;
    }
}

060-把二叉树打印成多行#

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
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    if(pRoot == null){
        return list;
    }
    Queue<TreeNode> queue = new LinkedList();
    //根节点入队列
    queue.offer(pRoot);
    //当队列不是空
    while(!queue.isEmpty()){
        //放里面，记录当前节点个数
        int size  = queue.size();
        ArrayList<Integer> temp = new ArrayList();
        //遍历一次是一层
        for(int i=0;i<size;i++){
            TreeNode node = queue.poll();
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
            temp.add(node.val);
        }
        list.add(temp);
    }
    return list;
}

059-按之字形顺序打印二叉树 *#

按行打印的部分，按奇偶来改变头插尾插

023-二叉搜索树的后序遍历序列 *#

同非递归二叉树的后序遍历， 思路: 先序是 abc, acb, 的反转 bca即需要的后序遍历。使用栈， 与先序写法差不多，只是先push right, 再left, list.add用头插.

024-二叉树中和为某一值的路径#

回溯

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
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    find(root, target, 0, new ArrayList<Integer>(), result);
    return result;
}

private void find(TreeNode node, int target, int sum, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result) {

    sum += node.val;
    path.add(node.val);

    if (node.left == null && node.right == null && sum == target) {
        result.add(new ArrayList<>(path));
        path.remove(path.size() - 1);
        return;
    }
    
    if (node.left != null) {
        find(node.left, target, sum, path, result);
    }
    if (node.right != null) {
        find(node.right, target, sum, path, result);
    }
    path.remove(path.size() - 1);
}

038-二叉树的深度#

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int TreeDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    
    if (root.left == null && root.right == null) {
        return 1;
    }
    
    int leftDepth = TreeDepth(root.left);
    int rightDepth = TreeDepth(root.right);
    
    return 1 + Integer.max(leftDepth, rightDepth);
}

二叉树层次遍历#

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
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> levels = new ArrayList<List<Integer>>();
    if (root == null) return levels;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    int level = 0;
    while ( !queue.isEmpty() ) {
      // start the current level
      levels.add(new ArrayList<Integer>());

      // number of elements in the current level
      int level_length = queue.size();
      for(int i = 0; i < level_length; ++i) {
        TreeNode node = queue.remove();

        // fulfill the current level
        levels.get(level).add(node.val);

        // add child nodes of the current level
        // in the queue for the next level
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
      }
      // go to next level
      level++;
    }
    return levels;
}

114. 二叉树展开为链表#

直接展开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void flatten(TreeNode root) {
    TreeNode node = root;
    while (node != null) {
        
        // 
        if (node.left == null) {
            node = node.right;
            continue;
        }

        // 找到左分支的最右节点
        TreeNode pre = node.left;
        while (pre.right != null) {
            pre = pre.right;
        }        

        // pre 替换node 右分支的位置
        pre.right = node.right;
        node.right = node.left;
        node.left = null;
        node = node.right;
    }
}

236. 二叉树的最近公共祖先#

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

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
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    Stack<TreeNode> stack = new Stack();
    Map<TreeNode, TreeNode> son2ParentMap = new HashMap();
    stack.push(root);
    son2ParentMap.put(root, null);
    while (!son2ParentMap.containsKey(p) || !son2ParentMap.containsKey(q)) {
        TreeNode node = stack.pop();
        if (node.left != null) {
            son2ParentMap.put(node.left, node);
            stack.push(node.left);
        }
        if (node.right != null) {
            son2ParentMap.put(node.right, node);
            stack.push(node.right);
        }
    }
    Set<TreeNode> sets = new HashSet();
    while (p != null) {
        sets.add(p);
        p = son2ParentMap.get(p);
    }
    while (!sets.contains(q)) {
        q = son2ParentMap.get(q);
    }
    return q;
}

105. 从前序与中序遍历序列构造二叉树#

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
public TreeNode buildTree(int[] preorder, int[] inorder) {
    return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
}

private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {
    // preorder 为空，直接返回 null
    if (p_start == p_end) {
        return null;
    }
    int root_val = preorder[p_start];
    TreeNode root = new TreeNode(root_val);
    //在中序遍历中找到根节点的位置
    int i_root_index = 0;
    for (int i = i_start; i < i_end; i++) {
        if (root_val == inorder[i]) {
            i_root_index = i;
            break;
        }
    }
    int leftNum = i_root_index - i_start;
    //递归的构造左子树
    root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index);
    //递归的构造右子树
    root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end);
    return root;
}

101. 对称二叉树#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }
}

101. 平衡二叉树#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}
2 分钟 读完 (大约 304 个字)

hashmap算法

034-第一个只出现一次的字符#

1.使用hashmap
2.indexof lastindexof

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        for (int i = 0; i < str.length(); i++) {
            char t = str.charAt(i);
            if (str.indexOf(t) == i && str.lastIndexOf(t) == i){
                return i;
            }
        }
        return -1;
    }
}

03-无重复字符的最长子串 *#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int lengthOfLongestSubstring(String s) {
    char[] chars = s.toCharArray();
    int len = chars.length;
    int left =0, right = 0;
    int max = 0;
    Integer index;
    Map<Character, Integer> indexMap = new HashMap();
    for (;right < len;right ++) {
        char c = chars[right];
        if ((index = indexMap.get(c)) != null && index >= left) {
            left = index + 1;
        }
        indexMap.put(c, right);
        max = Math.max(max, right - left + 1);
    }
    return max;
}

146.实现lru#

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class LRUCache {

    class DNode {
        int key;
        int val;
        DNode pre;
        DNode next;
    }

    private DNode head;
    private DNode tail;
    private HashMap<Integer, DNode> cache = new HashMap<Integer, DNode>();
    private int capacity;
    private int size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new DNode();
        tail = new DNode();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        // cache
        DNode node = cache.get(key);
        if (node == null) return -1;
        // 移到最前面
        moveToHead(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        DNode node = cache.get(key);
        if (node != null) {
            node.val = value;
            moveToHead(node);
        } else {
            node = new DNode();
            node.key = key;
            node.val = value;
            cache.put(key, node);
            addFirst(node);
            size++;

            if (size > capacity) {
                cache.remove(tail.pre.key);
                removeNode(tail.pre);
                size--;
            }
        }
    }

    private void moveToHead(DNode node) {
        // 删除节点
        removeNode(node);
        // 放到首节点后面
        addFirst(node);
    }

    private void removeNode(DNode node) {
        DNode pre = node.pre;
        DNode next = node.next;
        pre.next = next;
        next.pre = pre;
    }

    private void addFirst(DNode node) {
        DNode next = head.next;
        node.next = next;
        node.pre = head;

        head.next = node;
        next.pre = node;
    }
}
2 分钟 读完 (大约 234 个字)

动态规划算法

动态规划

030-连续子数组的最大和#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int FindGreatestSumOfSubArray(int[] array) {
	//设置指针从0开始向右移动，如果当前指针 + 前面指针代表的和为sum，计算max
	//如果sum > 0 移动 sum = sum
	//如果素sum < 0 移动 sum归零 重写跳转指针
	if(array == null){
		return 0;
	}
	int i = 0;
	int max = Integer.MIN_VALUE;
	int sum = 0;
	while(i < array.length){
		sum = array[i] + sum;
		max = max > sum ? max : sum;
		if(sum < 0){
			sum = 0;
		}
		i++;
	}
	return max;
}

62. 不同路径#

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

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
public int uniquePaths(int m, int n) {
    int[][] res = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0)
                res[0][j] = 1;
            else if (j == 0)
                res[i][0] = 1;
            else
                res[i][j] = res[i - 1][j] + res[i][j - 1];
        }
    }
    return res[m - 1][n - 1];
}

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[n - 1];
}
关注我

链接

分类

标签云

List concurrenthashmap design framework git hadoop hashmap innodb java jvm kafka maven mybatis mysql netty network pcursor redis rss spring springboot storm tair vim zookeeper 并发 旅游 机器学习 生活 索引 线上问题 英语 设计模式 读书笔记 锁 面经

最新文章

归档

标签

List 1
concurrenthashmap 1
design 8
framework 1
git 1
hadoop 2
hashmap 9
innodb 2
java 15
jvm 3
kafka 1
maven 1
mybatis 3
mysql 11
netty 3
network 2
pcursor 1
redis 3
rss 1
spring 1
springboot 5
storm 1
tair 1
vim 1
zookeeper 2
并发 4
旅游 3
机器学习 1
生活 2
索引 2
线上问题 1
英语 1
设计模式 1
读书笔记 1
锁 1
面经 1

最新文章

归档

标签

List 1
concurrenthashmap 1
design 8
framework 1
git 1
hadoop 2
hashmap 9
innodb 2
java 15
jvm 3
kafka 1
maven 1
mybatis 3
mysql 11
netty 3
network 2
pcursor 1
redis 3
rss 1
spring 1
springboot 5
storm 1
tair 1
vim 1
zookeeper 2
并发 4
旅游 3
机器学习 1
生活 2
索引 2
线上问题 1
英语 1
设计模式 1
读书笔记 1
锁 1
面经 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×