分类: [编程集合]

递增的三元子序列

给定一个未排序的数组,判断这个数组中是否存在长度为 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)的格 ......

剑指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为系统中的特定的那块区域!!并无法复制,所以只能从头遍历,得到该结点的前序结点,删除。 * – 如果链表只有一个结点, ......

java位运算符总结

/* * Java提供的位运算符有:左移( > ) 、无符号右移( >>> ) 、位与( & ) 、位或( | )、位非( ~ )、位异或( ^ ) * 除了位非( ~ )是一元操作符外,其它的都是二元操作符。 */ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465public class 位运算整理{     public static void main(String[] args) {         /* 左移( << )          * 运行结果是2 ......

剑指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 ......