分类: [算法]

有序矩阵中第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 ......

第一个缺失的正数

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。 示例 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 ......

剑指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)的格 ......

剑指offer——矩阵中的路径

题目描述 请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串”bcced”的路径,但是矩阵中不包含”abcb”路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。 解题思路   这是一个可以用回朔法解决的 ......

剑指offer——删除链表的节点

/* * 给定单向链表的头指针和一个结点指针,定义一个函数在0(1)时间删除该结点 * * 【抖机灵】 * 正常删除链表节点都得给个头指针和要删除的结点,然后从头开始遍历寻找 * 但是要求时间复杂度是1,下面抖个机灵: * 我们可以直接复制这个结点的下一个结点,然后再将这个结点的下一个结点删除。over * 【注意】 * – 要删除的结点是尾结点 * – 没办法,NULL为系统中的特定的那块区域!!并无法复制,所以只能从头遍历,得到该结点的前序结点,删除。 * – 如果链表只有一个结点, ......

剑指offer——打印从1到最大的n位数

题目: 输入数字n,按顺序打印出从1最大的n位十进制数。 比如输入3,则打印出1、2、3、4、5、6…… 一直到最大的3位数即999。 /* * 【注意】 * 大数问题:–>用数组 * 法1: * 模拟大数相加,从0开始,每次加1, * 直到arr的最高位(倒数第n+1位)有进位时,即最大的n位数已经打印完毕。 * * 法2: * 递归 * 打印1 ~ n位的所有十进制数,其实就是从第1位开始设置0~9的全排列,直到递归将最后一个位置设置完毕,开始打印。 */ 12345678910111213141516171819202122232425262728293031 ......