最长子序列 问题陈述 删除 s 中的一些字符，使得它构成字符串列表 d 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回字典序的最小字符串。 12345Input:s = "abpcplea", d = ["ale","apple","monkey","plea"]Output:"apple" 算法实现 采用双指针:遍历给定字符串,因为找的是子集,与字典中的字符串一个个比.如果相等,它俩下标都加一,再判断 字典中的字符串是否和下标相等了,如果相等,证明找到了。 1234567891011121314151617181920212223242526272829303132class Solution{ public String findLongestWord(String s,List<String> d){ char[] sc=s.toCharArray(); String ...

最短无序连续子数组 问题陈述 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。 你找到的子数组应是最短的，请输出它的长度。 123输入: [2, 6, 4, 8, 10, 9, 15]输出: 5解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。 思路一 设置左右边界，L初始化为nums.length, R初始化为0。对数组两两比较，如果前面数大于后面数，则L=min(L, i); R=max(R,j)。 12345678910111213141516class Solution { public int findUnsortedSubarray(int[] nums) {​ int L=nums.length,R=0;​ for(int i=0;i<nums.length-1;i++){​ for(int j=i+1;j<nums.length;j++){​ if(nums[i]>n ...

最小路径和 问题陈述 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 12345678输入:[ [1,3,1], [1,5,1], [4,2,1]]输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。 思路实现 12345678910111213141516171819202122232425262728293031323334353637383940package com.echo.exam;import java.util.Scanner;public class MinPathSum { public static void main(String[] args) { Scanner in=new Scanner(System.in); int m=in.nextInt(); int n=in.nextInt(); int[][] grid=new int[m][n]; ...

无重叠区间 问题陈述 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 12345输入: [ [1,2], [2,3], [3,4], [1,3] ]输出: 1解释: 移除 [1,3] 后，剩下的区间没有重叠。 思路分析 算法思路： 从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。 把所有与 x 区间相交的区间从区间集合 intvs 中删除。 重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集 代码实现 1234567891011121314151617181920public int intevalSchedual(int[][] intvs){ if(intvs.length==0) return 0; //对intvs按区间end升序排列 Arrays.sort(intvs,new Comparator<int[]>(){ public int compare(int[] a,int[] b)& ...

数组中的逆序对 问题陈述 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 思路详解 1、很显然，此题可以双循环列举比较，复杂度为O(n^2)，有没有更好的解法呢？有的，利用归并排序的思想。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556/** * 首先你要知道归并排序的流程： * * 先将数组分成两部分，然后分别将这两部分排好序； * 然后开一个 helper 数组，指针 a 和 b 分别指向这两个部分的第一个元素； * 比较指针 a 所指元素与指针 b 所指元素的大小，将小的元素放进 helper 数组中； * 如果某个指针遍历到对应部分的末尾的话，则需要将另一个指针所指元素以及它后面的元素直接添加到 helper 数组中； * * 最后再将 helper 数组中的数据拷贝到原数组中即可。 * 重点在于在两个指针比较的过程中，如果第一个子数组中 ...

数据库面试知识一 数据库基础知识 为什么要使用数据库 数据保存在内存 优点： 存取速度快 缺点： 数据不能永久保存 数据保存在文件 优点： 数据永久保存 缺点：1）速度比内存操作慢，频繁的IO操作。2）查询数据不方便 数据保存在数据库 1）数据永久保存 2）使用SQL语句，查询方便效率高。 3）管理数据方便 什么是SQL？ 结构化查询语言(Structured Query Language)简称SQL，是一种数据库查询语言。 作用：用于存取数据、查询、更新和管理关系数据库系统。 什么是MySQL? MySQL是一个关系型数据库管理系统，由瑞典MySQL AB 公司开发，属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理系统之一，在 WEB 应用方面，MySQL是最好的 RDBMS (Relational Database Management System，关系数据库管理系统) 应用软件之一。在Java企业级开发中非常常用，因为 MySQL 是开源免费的，并且方便扩展。 数据库三大范式是什么 第一范式：每个列都不可以再拆分。 第二范式：在第一范式的基础上， ...

数值的整数次方 问题陈述 实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。 快速幂解析 快速幂是二分思想的一种应用。 根据二分推导，可通过循环x=x^2操作，每次将幂n降至n/2，直至将幂降为0。 设res=1，则初始状态xn=xnres，在循环二分时，当n为奇数，将多出的一项乘以res，偶数则不用处理，最终x^n=1res。 1234567891011121314151617181920class Solution{ public double myPow(double x,int n){ if(x==0) return 0; long b=n; //由于int范围n∈[−2147483648,2147483647] ，因此当 n = -2147483648时执行 n = -nn=−n 会因越界而赋值出错。解决方法是先将 n 存入 long 变量 b ，后面用 b 操作即可。 double re ...

搜索二维矩阵 问题陈述 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性： 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例: 1234567891011121314现有矩阵 matrix 如下：[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]给定 target = 5，返回 true。给定 target = 20，返回 false。 思路分析 由于矩阵从上到下、从左到右是排序的，我们从左下角元素开始，如果比target小，则往右走；如果比target大，则往上走。如果target存在，则一定能找到。若是在矩阵范围内，没找到，说明不存在target，返回false。 代码实现 12345678910111213141516class Solution{ public boolean searchMatrix( ...

把二叉搜索树转换为累加树 问题陈述 给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。 1234567891011输入: 原始二叉搜索树: 5 / \ 2 13输出: 转换为累加树: 18 / \ 20 13 逆中序遍历法 由于二叉搜索树的特性，左结点<根结点<右结点。因此可以递归右子树，递归回来的值与当前结点值求和得到当前结点值，然后递归左子树。 123456789101112class Solution{ private int sum=0; public TreeNode convertBST(TreeNode root){ if(root!=null){ convertBST(root.right); ...

打开转盘锁 问题陈述 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。 字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。 示例： 1234输入: deadends = ["8888"], target = "0009"输出：1解释：把最后一位反向旋转一次即可 "0000" -> "0009"。 思路分析 ⽐如说从 “0000” 开始，转⼀次，可以穷举出 “1000”, “9000”, “0100”, “0900”… 共 8 种密码。然 ...