有序矩阵中第K小的元素

Kth Smallest Element in a Sorted Matrix 给定一个 n x n 矩阵,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。 请注意,它是排序后的第k小元素,而不是第k个元素。 示例: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,返回 13。 说明: 你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。 方法一:简单粗暴,遍历K次,每次找最小的值,将其赋值为MAX,这样第K次遍历找到的就是第K小的值 方法二:利用小顶堆(Java中的PriorityQueue优先队列),第K个出队的即为第k小的值 12345678910111213publ ......

图解SQL的inner join、left join、right join、full outer join的区别

left join(左联接):返回左表中的所有记录以及和右表中的联接字段相等的记录。 right join(右联接):返回右表中的所有记录以及和左表中的联接字段相等的记录。 inner join(等值联接):只返回两个表中联接字段相等的记录。 举例如下: ——————————————– 表A记录如下: aID     aNum 1     a20050111 2     a20050112 3     a20050113 4     a20050114 5     a20050115 表B记录如下: bID     b ......

第一个缺失的正数

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3: 输入: [7,8,9,11,12] 输出: 1 说明: 你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。 为了找出缺失的,我们先将每个元素都放到一个属于他们的位置上去。放完以后,第一次出现元素的值和所在位置不对应,就可以找到缺失的值。 如何定义:属于某个元素的位置? 假设某个元素为5, 那么它就该被放到index = 4的位置上去,即需要保证 nums[i] = i + 1 所以,对于某一个可能要交换的 ......

最长连续序列

给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。 解法一: 暴力解法,先对数组排序,然后对数组去重,然后再遍历数组找最长的连续序列,因为排序的时间复杂度无法达到O(N),所以不符合题目要求; 解法二: 采用hashset(元素不可重复)第一次遍历完成去重; 第二次遍历的过程中,不断寻找num-1和num+1;获取最大长度,代码如下: 123456789101112131415161718192021public static int longestCo ......

递增的三元子序列

给定一个未排序的数组,判断这个数组中是否存在长度为 3 的递增子序列。 数学表达式如下: 如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1, 使得 arr[i] < arr[j] < arr[k] ,返回 true ; 否则返回 false 。 说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1) 。 示例 1: 输入: [1,2,3,4,5] 输出: true 示例 2: 输入: [5,4,3,2,1] 输出: false 暴力破解法,时间耗费的是 O(N*N*N)。如果是需要找递增的二元组的话完全可以使用 O(N)的遍历方法,但是在解题中,第二个数和第三个数进行对比的前提是第二个数大于第一个数 ......

打家劫舍

你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。 示例 1: 输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2: 输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号 ......

买卖股票的最佳时机

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 暴力,时间复杂度O(n*n) 123456789101 ......

Java异常处理

异常指不期而至的各种状况,如:文件找不到、网络连接失败、除0操作、非法参数等。异常是一个事件,它发生在程序运行期间,干扰了正常的指令流程。 Java 异常的概念 Java语言在设计的当初就考虑到这些问题,提出异常处理的框架的方案,所有的异常都可以用一个异常类来表示,不同类型的异常对应不同的子类异常(目前我们所说的异常包括错误概念),定义异常处理的规范,在JDK1.4版本以后增加了异常链机制,从而便于跟踪异常。 Java异常是一个描述在代码段中发生异常的对象,当发生异常情况时,一个代表该异常的对象被创建并且在导致 ......

Java中equals和==的区别

平时在学Android和Java语言的时候,总是碰到“equals”和“==”这两个字符,老感觉差不多;其实还是有一些区别的,今天干脆把它们彻底弄清楚。 一、java当中的数据类型和“==”的含义: 基本数据类型(也称原始数据类型) :byte,short,char,int,long,float,double,boolean。他们之间的比较,应用双等号(==),比较的是他们的值。 引用数据类型:当他们用(==)进行比较的时候,比较的是他们在内存中的存放地址(确切的说,是堆内存地址)。 注:对于第二种类型,除非是同一个new出来的对象,他们的比较后的结果为true,否则比较后结果为 ......

剑指offer——机器人的运动范围

题目: 地上有个 m 行 n 列的方格。一个机器人从坐标(0,0)的格子开始移动,它每一次可以向左、右、上、下移动一格,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 举例分析 例如,当 k 为 18 时,机器人能够进入方格(35,37),因为 3+5+3+7=18 但它不能进入方格(35,38),因为 3+5+3+8=19 请问该机器人能够达到多少格子? 解题思路 和前面的矩阵中的路径类似,这个方格也可以看出一个 m*n 的矩阵。同样在这个矩阵中,除边界上的格子之外其他格子都有四个相邻的格子。 机器人从坐标(0,0)开始移动。当它准备进入坐标为(i,j)的格 ......