最小的K个数
最小的K个数 输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。 示例 1: 输入:arr = [3,2,1], k = 2 输出:[1,2] 或者 [2,1] 示例 2: 输入:arr = [0,1,2,1], k = 1 输出:[0] 这个是答的最快 的一次了因为…之前英语分组的时候用过 12345678910class Solution { public int[] getLeastNumbers(int[] arr, int k) { Arrays.sort(arr); int[] out = new int[k]; for(int i=0;i<k;i++){ out[i]=arr[i]; } return out; }} 不过用Array.sort()感觉应该不太行,再试试基本的排序算法看看 然后写出了一种效率极低的方法… ...
Java内存模型
Java内存模型 并发编程模型的两个关键问题 线程之间如何通信(以何种机制来交换信息) 在命令式编程中,线程之间的通信机制有两种,共享内存和消息传递 Java并发采用的是共享内存模型 Java线程之间的通信总是隐式进行… 线程之间如何同步 同步是指程序中用于控制不同线程间操作发生相对顺序的机制. 在共享内存并发模型里,同步是显式进行的.程序员必须显式指定某个方法或某段代码需要在线程之间互斥执行. 在消息传递的并发模型里,由于消息的发送必须在消息的接收之前,因此同步是隐式进行的 Java内存模型的抽象结构 在Java中,所有实例域,静态域和数组元素都存储在堆内存中,堆内存在线程之间共享. 局部变量和异常处理器参数不会在线程之间共享,因此他们不会有内存可见性问题,也不会受内存模型的影响. 这跟JVM堆栈的知识匹配上了 Java线程之间的通信由Java内存模型控制,JMM决定一个线程对共享变量的写入何时对另一个线程可见 线程之间的共享变量储存在主内存中 每一个线程都有一个私有的本地内存 本地内存存储了该线程以读/写共享变量的副本**.本地内存是JMM的一个抽象概念,并不 ...
0~n-1中缺失的数字
0~n-1中缺失的数字 一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。 示例 1: 12输入: [0,1,3]输出: 2 示例 2: 12输入: [0,1,2,3,4,5,6,7,9]输出: 8 本来以为很简单…结果一直错…因为 少考虑到了很多情况 数组搜索优先考虑二分法 1234567891011class Solution { public int missingNumber(int[] nums) { int i = 0, j = nums.length - 1; while(i <= j) { int m = (i + j) / 2; if(nums[m] == m) i = m + 1; else j = m - 1; } return i; }} 来源:力扣 ...
Java中的锁
Java中的锁 Lock接口 锁是用来控制多个线程访问共享资源的方式,一般来说,一个锁能够防止多个线程同时访问共享资源(有些锁可以允许多个线程并发地访问共享资源,比如读写锁) Java SE5之后,并发包中新增了Lock接口(以及其实现类)来实现锁功能,它提供了与synchronized关键字类似的同步功能,只是在使用的时候需要显示地获取锁和释放锁 虽然缺少了synchronized隐式获取锁的便捷性,但是却拥有了锁获取与释放的可操作性,可中断的获取锁以及超时获取锁等多种synchronized关键字所不具备的同步 123456Lock lock = new ReentranLock();lock.lock();try{}finally{ lock.unlock();} 不需要将获取锁的过程写在try中,因为如果在获取锁(自定义锁的实现)时发生了异常,异常抛出的同时.也会导致锁无故释放. Lock接口提供的synchronized关键字所不具备的主要特性 尝试非阻塞地获取锁 当前线程尝试获取锁,如果这一时刻锁没有被其他线程获取到,则 ...
有意思的1+2+3+...+n
有意思的1+2+3+…+n 求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 题解 123456class Solution { public int sumNums(int n) { boolean x = n > 1 && (n += sumNums(n - 1)) > 0; return n; }} 用到了&&的短路原理…绝了
原子操作的实现原理
原子操作的实现原理 原子(atomic)本意是"不能被进一步分割的最小粒子",而原子操作(atomic operation)意为"不可被中断的一个或者一系列操作" 术语定义 缓存行(Cache line); 缓存的最小操作单位 比较并交换(Compare and swap) CAS操作需要输入两个数值,一个旧值(期望操作前的值)和一个新值,在操作期间先比较旧值有没有变化,如果没有发生变化,才交换成新值,发生了变化则不交换 CPU流水线(CPU pipeline) CPU流水线的工作方式就像工业生产上的装配流水线,在CPU中由56个不同功能的电路单元组成一条指令处理流水线,然后将一条x86指令分成56步再由这些电路单元分别执行,这样就能实现在一个CPU时钟周期完成一条指令,因此提高CPU的运算速度 内存顺序冲突(Memory order violation) 内存顺序冲突一般是由假共享引起的,假共享是指多个CPU同时修改同一个缓存行的不同部分而引起其中一个CPU的操作无效,当出现这个内存顺序冲突时,CPU必须清空流水线 处理器如何实现 ...
平衡二叉树
平衡二叉树 输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 12345 3 / \9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1234567 1 / \ 2 2 / \ 3 3 / \4 4 返回 false 。 题解 1234567891011121314class Solution { public boolean isBalanced(TreeNode root) { return recur(root) != -1; } private int recur(TreeNode root) { if (root == null) return 0; ...
RabbitMQ工作模式
RabbitMQ工作模式 官网对应模式介绍:https://www.rabbitmq.com/getstarted.html 1. Work queues工作队列模式 1.1 模式说明 Work Queues与入门程序的简单模式相比,多了一个或一些消费端,多个消费端共同消费同一个队列中的消息。 应用场景:对于 任务过重或任务较多情况使用工作队列可以提高任务处理的速度。 1.2 代码 Work Queues与入门程序的简单模式的代码是几乎一样的;可以完全复制,并复制多一个消费者进行多个消费者同时消费消息的测试。 生产者 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667package com.itheima.producer;import com.rabbitmq.client.Channel;import com.rabbitmq.client.Connection;impo ...
什么是CAS?
什么是CAS? CompareAndSwapInt CAS乐观锁: 多个线程使用CAS同时更新同一个变量时,只有一个线程更新变量的值其他线程被告知失败,可以再次尝试 CAS有可能带来ABA问题(1->8->1) 如果在乎: AtomicStampedReference 每次改变都需要版本号 AtomicMarkableReference 不在乎改了多少次,只在乎改没改 如果在写回去的时候被打断了,怎么办? 写回去的时候必须保障原子性(硬件底层保证原子性) 并发编程3大特性 可见性 原子性 有序性
滑动窗口的最大值
滑动窗口的最大值 给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 用了最直接的方法 做出来…考虑到每次都比较k个 里面有重复比较的部分 12345678910111213141516class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if(nums.length==0||k==0){ ...