- 1. 二维数组中查找
- 2. 替换空格
- 3.从头到尾打印链表
- 4. 重建二叉树
- 5. 用两个栈实现队列
- 5. 旋转数组的最小数字
- 6. 斐波那契数列
- 7. 青蛙跳台阶
- 8. 变态跳台阶
- 9. 矩阵覆盖
- 10. 二进制中1的个数
- 11. 数值的整数次方
- 12 打印1到最大的n位数
- 13 在O（1）时间删除链表结点
- 14 调整数组顺序使奇数位于偶数前面
- 15. 链表倒数第k个结点
- 16 翻转链表
- 17 合并两个排序的链表
- 18 判断父子树是否相等
- 19二叉树镜像
- 20 逆时针打印矩阵
- 21包含min函数的栈
- 22 栈的压入弹出
- 23 从上往下打印二叉树
- 24 二叉搜索树的后序遍历序列
- 25 ? 二叉树中和为某一值的路径
- 26 复杂链表的复制
- 27 二叉搜索树与双向链表
- 28 字符串的排列
- 29 数组中出现次数超过一半的数字 - 思路： - 更巧妙的思路： - 实用技巧
- 30 快速排序
- 31 连续子数组的最大和
- 32 把数组排成最小的数
- 33 丑数
- 34 第一个只出现一次的字符
- 35 数组中的逆序对
- 36 两个链表的第一个公共节点
- 37 数字在排序数组中出现的次数
- 38 二叉树的深度
- 39 平衡二叉树
- 40 数组中只出现一次的数字
- 41 和为S的连续正数数列
- 42 和为S的两个数字——双指针
- 43 左旋转字符串
- 44 翻转单词顺序
- 45 圆圈中最后剩下的数
- 46 有限制的求1+2+3+……+n
- 47 用位运算做加法
- 48 把字符串转化成整数
- 49 数组中重复的数字
- 50 构建乘积数组
- ？51 正则表达式匹配
- 51 正则表达式科学计数法
- 52 字符流中第一个不重复的字符
- 53 链表中环的入口结点——快慢指针 - 两个结论：
- 54 删除链表中的重复结点
- 55 二叉树的下一个结点
- 56 对称的二叉树
- 57 之字形打印二叉树
- 58 序列化二叉树
- 59 二叉搜索树的第k个结点
- 60 数据流中的中位数
- 61 滑动窗口的最大值
- 62 矩阵中的路径
- 63 机器人的运动范围
- 64 剪绳子
- # lk 会议贪心
- lk 多次求和构造目标数组
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：从右上角开始找，如果比目标大，舍弃下面一行，如果比目标小，舍弃左边一列，如果相等，就返回。
public class Solution {
public boolean Find(int target, int [][] array) {
int row = 0;
int col = array[0].length - 1;
//从右上角开始找
while(row <= array.length - 1&& col >= 0){
if(array[row][col] > target){
col--;
continue;
}
else if(array[row][col] < target){
row++;
continue;
}
else return true;
}
return false;
}
}注意边界值判断
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：
- 使用库函数 string.replaceAll(" ","%20");
- 开辟新的空间存储
- 扩展字符串，从尾进行扫描
import java.util.*;
public class Solution {
public String replaceSpace(StringBuffer str) {
//1.return str.toString().replaceAll(" " , "%20");
/*2.
StringBuilder sb = new StringBuilder();
for(int i = 0;i < str.length();i++){
char x = str.charAt(i);
if(x == ' '){
sb.append("%20");
}else{
sb.append(x);
}
}
return sb.toString();
*/
//3.
int spaceNum = 0;
for(int i = 0;i < str.length();i++){
if(str.charAt(i) == ' ')
spaceNum++;
}
int oldSize = str.length();
int newSize = oldSize+2*spaceNum;
str.setLength(newSize);
int i = oldSize - 1,j = newSize - 1;
while(i >= 0&& oldSize < newSize){
if(str.charAt(i) == ' '){
str.setCharAt(j--,'0');
str.setCharAt(j--,'2');
str.setCharAt(j--,'%');
}else{
str.setCharAt(j--,str.charAt(i));
}
i--;
}
return str.toString();
}
}注意使用API str.length()、str.setLength(newLength)、str.setCharAt(j--,'0')、sb.append()
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
思路：
- 使用系统栈的递归
- 每次插入ArrayList第0个位置，让底层自己去移动
- 遍历链表存入ArrayList，倒序放入另一个ArrayList
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
//使用系统栈的递归
ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode){
if(listNode != null){
printListFromTailToHead(listNode.next);
list.add(listNode.val);
}
return list;
}
/*每次插入第0个位置，让底层自己去移动
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
ListNode tmp = listNode;
while(tmp != null){
list.add(0,tmp.val);
tmp = tmp.next;
}
return list;
}*/
/*
遍历链表存入ArrayList，倒序放入另一个ArrayList
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> temp = new ArrayList<Integer>();
ArrayList<Integer> res = new ArrayList<Integer>();
//if(listNode.next == null)
// return res;
ListNode tmp = listNode;
while(tmp != null){
temp.add(tmp.val);
tmp = tmp.next;
}
for (int i = temp.size()-1;i >= 0;i--){
res.add(temp.get(i));
}
return res;
}*/
}注意链表的数据结构，每次用的时候需要把纸取出来 ListNode node = listNode;
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
前序遍历：根、左、右
中序遍历：左、根、右
后序遍历：左、右、根
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.*;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
//递归终止条件
if(pre.length == 0 || in.length == 0)
return null;
//由前序遍历得到该二叉树的根结点
TreeNode root = new TreeNode(pre[0]);
//在中序中找前序的根，进行左右子树分割
for(int i = 0;i < in.length;i++){
if(in[i] == root.val){
//将左子树看成一棵二叉树调用该方法，可以得到左子树根结点，即上面根结点的左子结点
//copyOfRange这个函数左闭右开，所以要到i+1，应该是往后数i个
root.left = reConstructBinaryTree(
Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
//右子树
root.right = reConstructBinaryTree(
Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
break;
}
}
return root;
}
}Arrays.copyOfRange 函数，左闭右开
思路：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
-
如果stack1不为空，全部弹出在弹入stack2，顶端是最早进去的
-
如果stack1为空，直接弹出stack2顶端元素
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack2.size() != 0)
return stack2.pop();//2的顶端始终是最早进去的
else{
while(stack1.size() > 0){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}别忘了返回值和参数
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
暴力循环直接找
import java.util.ArrayList;
//直接寻找法
public class Solution {
public int minNumberInRotateArray(int [] array) {
int n = array.length;
if(n == 0)
return 0;
for(int i = 0;i < n -1;i++){
if(array[i] > array[i+1])
return array[i+1];
}
return array[0];
}
}二分查找用于查找有序的数组中的值，题目所给数组在两段范围内有序，我们可以将给定数组分为两种情况：
- 其实并没有旋转，例如 {1,2,3,4,5}，旋转后也是 {1,2,3,4,5}，这样可以直接使用二分查找
- 如题所示，旋转了一部分，例如 {1,2,3,4,5}，旋转后为 {3,4,5,1,2}，需要限定特殊条件后使用二分查找
当数组如情况 1，有个鲜明的特征，即数组左边元素 < 数组右边元素，这时我们直接返回首元素即可 当数组如情况 2，此时有三种可能找到最小值：
- 下标为 n+1 的值小于下标为 n 的值，则下标为 n+1 的值肯定是最小元素
- 下标为 n 的值小于下标为 n-1 的值，则下标为 n 的值肯定是最小元素
- 由于不断查找，数组查找范围内的值已经全为非降序（退化为情况1）
再讨论每次二分查找时范围的变化，由于情况数组的情况 1 能直接找到最小值，需要变化范围的肯定是情况 2：
- 当下标为 n 的值大于下标为 0 的值，从 0 到 n 这一段肯定是升序，由于是情况 2，最小值肯定在后半段
- 当下标为 n 的值小于下标为 0 的值，从 0 到 n 这一段不是升序，最小值肯定在这一段
import java.util.*;
public class Solution {
public int minNumberInRotateArray(int [] nums) {
if (nums.length == 1) {
return nums[0];
}
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[l] < nums[r]) {
return nums[l];//根本没有旋转
}
if (nums[mid] > nums[mid + 1]) {//中间的比右边的还大了，
//中间再过去右边一个是最小的
return nums[mid + 1];
}
if (nums[mid] < nums[mid - 1]) {//中间的比左边的还小了，
//中间再过去左边一个是最小的
return nums[mid];
}
if (nums[mid] > nums[0]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return 0;
}
}大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
public class Solution {
public int Fibonacci(int n) {
/*递归
if(n == 0)
return 0;
if(n == 1)
return 1;
else
return Fibonacci(n-1)+Fibonacci(n-2);
*/
//循环
int[] res = {0,1};
if(n < 2)
return res[n];
int one = 1; //存储n-1项的值
int two = 0; //存储n-2项的值
int fab = 0; //存储结果
for(int i = 2;i <= n;i++){
fab = one + two;//计算和
two = one;//更新
one = fab;//更新
}
return fab;
}
}更精妙，用one来存n-1项的值
public class Solution {
public int Fibonacci(int n) {
if(n == 0){
return 0;
}else if(n == 1){
return 1;
}
int sum = 1;
int one = 0;
for(int i=2;i<=n;i++){
sum = sum + one;//第n项
one = sum - one;//第n-1项
}
return sum;
}
}一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
public class Solution {
public int JumpFloor(int target) {
if(target <= 2){
return target;
}
//递归
//return JumpFloor(target-1)+JumpFloor(target-2);
//动态规划
int sum = 2;
int one = 1;
for(int i = 3;i <= target;i++){
sum = sum + one;
one = sum - one;
}
return sum;
}
}一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
- 找规律
import java.util.*;
public class Solution {
public int JumpFloorII(int target) {
/*
f(n)=f(n-1)+f(n-2)+...+f(1)
f(n-1)=f(n-2)+...f(1)
得:f(n)=2*f(n-1)
*/
return 1<<(target-1);
}
}-
dp
-
若楼梯阶级 n = 3
- 跳 3 步到 3：没有剩下步数没跳的，只有这样一种跳法
- 跳 2 步到 3：剩下的是第一步没跳，起始跳到第一步只有一种
- 跳 1 步到 3：剩下的是第二步没跳，起始跳到第二步有两种
求得，n = 3 时，有 4 种跳法
-
若楼梯阶级 n = 4
- 跳 4 步到 4：没有剩下步数没跳的，只有这样一种跳法
- 跳 3 步到 4：剩下的是第一步没跳，起始跳到第一步只有一种
- 跳 2 步到 4：剩下的是第二步没跳，起始跳到第二步只有两种
- 跳 1 步到 4：剩下的是第三步没跳，起始跳到第三步有四种
求得，n = 4 时，有 8 种跳法
-
若楼梯阶级 n = n
- 跳 x 步到 n 有几种的和，跟前 n - 1 种状态有关
那么，设置一个数组即可，在求的过程中把值都暂时放在数组里，最后求的时候遍历数据这些求好的对应的阶级种数之和即为新的下级阶梯种数
-
import java.util.*;
public class Solution {
public int JumpFloorII(int target) {
if(target < 2)
return target;
int [] dp = new int[target+1];
Arrays.fill(dp,1);//初始化每一种都可以直接从 0 跳到 n
dp[0] = 0; //从 0 跳到 0 为 0 种，因为 n = 0，没法跳
for(int i = 2;i < dp.length;i++){
for(int j = i-1;j >= 1;j--){
dp[i] += dp[j];//第 n 个状态是由前 n - 1 种状态推导出来，就是累加！
}
}
return dp[target];
}
}我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？
- n = 1 的时候
- 只能横着覆盖，一种
- n = 2 的时候
- 可以横着和竖着覆盖，两种
- n = 3 的时候
- 第三级横着覆盖，用了一级，剩下 n = 2，有两种覆盖方法
- 第三季竖着覆盖，用了两级，剩下 n = 1，有一种覆盖方法
- 总共有 3 种
- n = 4 的时候
- 第 4 级横着覆盖，用了一级，剩下 n = 3，有三种覆盖方法
- 第 4 级竖着覆盖，用了两级，剩下 n = 2，有两种覆盖方法
- 总共有 5 种方法
- n = n 的时候
- 第 n 级横着覆盖，用了一级，剩下 n = n - 1，所以关注第 n - 1 种有几种覆盖方法
- 第 n 级竖着覆盖，用了两级，剩下 n = n - 2，所以关注第 n - 2 种有几种覆盖方法
- 总和为两种情况的总和
从 n = 1 到 n = 4 的示意图如下：
所以回答上面的问题，涂掉最后一级矩阵的时候，可以选择使用横向完成，也可以使用竖向完成，横向涂剩下 n - 1 阶，竖向涂剩下 n - 2 阶
关注 n - 1 与 n - 2 时的涂法有几种，这就是斐波那契数列
public class Solution {
public int RectCover(int target) {
if(target <= 2){
return target;
}
int sum = 2;
int one = 1;
for(int i = 3;i <= target;i++){
sum += one;
one = sum - one;
}
return sum;
}
}输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
正数的原反补码都是原码，符号位0
负数的符号位为1，反码：绝对值部分01互换，补码：反码加1
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n != 0){
count++;
n = (n-1)&n;
//把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0
//那么一个整数的二进制表示中有多少个1，就可以做多少次减1与的操作
}
return count;
}
}正数右移：保持为正数，相当于/2。
负数右移：保持为负数，移位前是负数，移位后保持是负数，因此移位后最高位设为1。如果一直右移，最终会变成-1，即(-1)>>1是-1。
正数左移：不保持为正数，相当于*2。（注意：1左移31时为负数最大值）
负数左移：不保持为负数，在左移的过程中会有正有负的情况。所以切记负数左移不会特殊处理符号位。如果一直左移，最终会变成0。
相关题目
-
用一条语句判断一个整数是不是2的整数次方。
也就是判断是否有且只有一个1，进行-1再&，看这个1有没有变成0；
-
两个整数m和n，计算需要改变m的二进制中多少位才能得到n
- 求这两个数的异或
- 统计异或结果中1的位数（-1&）
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
- n为偶数：a^n = a^(n/2) * a^(n/2)
- n为奇数：a^n = a^(n-1)/2 * a^(n-1)/2 * a
// 递归写法
public class Solution {
public static double Power(double base, int exp) {
boolean flag = exp < 0;
if (flag) {
exp = -exp;//判断小数点位置
}
double result = getPower(base, exp);
return flag ? 1 / result : result;
}
//递归函数
public static double getPower(double base, int exp) {
if (exp == 0) {
return 1;
}
if (exp == 1) {
return base;
}
double ans = getPower(base, exp >> 1);//>>代替除以2
ans *= ans;//平方
if ((exp & 1) == 1) { //与运算代替求余运算，判断奇偶，如果==1 为奇
ans *= base;
}
return ans;
}
}与运算代替求余运算，判断奇偶，如果(exp & 1) ==1 为奇数，否则为偶数
有时候要做一些取余（模）的运算，而除数恰好是2的次方数常量（因为做程序时，经常会把一些会重复运算的关键数值取成2、4、8等），可用如下方法： 取i除以4的余数，用：num=i&3 取i除以8的余数，用：num=i&7 取i除以16的余数，用：num=i&15
n位所有十进制数就是n个从0到9的全排列：我们把数字的每一位都从0到9排列一遍，就得到了所有的十进制数，数字排在前面的0我们不打印
我们不需要遍历直到这个目标节点之前的节点，只需要把它后面的复制过来，再把它指向它后面的后面的
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
不考虑位置相对顺序时
public class Solution {
public void reOrderArray(int [] array) {
int size = array.length;
if(size <= 0)
return;
int begin = 0,end = size-1;
while(begin < end){
//向后移动begin，直到指向偶数
while(begin < end &&(array[begin] & 0x1) != 0){
begin++;
}
//向前移动end，直到指向奇数
while(begin < end &&(array[end] & 0x1) == 0){
end--;
}
if(begin < end){
int tp = array[begin];
array[begin] = array[end];
array[end] = tp;
}
}
}
}使用队列：
/*
*使用队列实现，时间复杂度和空间复杂度都为O(n)
*/
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public void reOrderArray(int [] array) {
Queue<Integer> queue = new LinkedList<Integer>();
for(int i=0;i<array.length;i++){
if(array[i]%2==1){
queue.add(array[i]);
}
}
for(int i=0;i<array.length;i++){
if(array[i]%2==0){
queue.add(array[i]);
}
}
for(int i=0;i<array.length;i++){
array[i]=queue.poll();
}
}
}-
i++往前走碰到偶数停下来，j = i+1 -
若
a[j]为偶数，j++前进，直到碰到奇数a[j]对应的奇数插到a[i]位置，j经过的j-i个偶数依次后移
-
如果
j==len-1时还没碰到奇数，证明i和j之间都为偶数了，完成整个移动
public class Solution {
public void reOrderArray(int [] array) {
int size = array.length;
if(size <= 1)
return;
int i = 0;
while(i < size){
int j = i+1;
if((array[i] & 0x1) == 0){//如果当前为偶数
while((array[j] & 0x1) == 0){
if(j == size-1)//中间都是偶数
return;
j++;
}//j处的值为奇数
int count = j-i;
int temp = array[i];
array[i] = array[j];
while(count > 1){
array[i+count] = array[i+count-1];//数组后移
count--;
}
array[i+1] = temp;
}
i++;
}
}
}输入一个链表，输出该链表中倒数第k个结点。
快慢指针
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k==0) //判空
return null;
ListNode begin = head;
ListNode end = head;//改名为faset和slow更形象
for(int i = 0;i < k;i++){
if(end == null)
return null;//这个不能忘，用于处理k大于链表长度
end = end.next;
}
while(end != null){
begin = begin.next;
end = end.next;//快慢指针同时前移
}
return begin;//返回慢指针
}
}输入一个链表，反转链表后，输出新链表的表头。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
//头插法
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null)
return null;
ListNode newHead = new ListNode(-1);//辅助头结点
while(head != null){
ListNode tmp = new ListNode(head.val);//每次都要new 一个结点，不划算
tmp.next = newHead.next;
newHead.next = tmp;
head = head.next;
}
return newHead.next;//返回头结点的下一个
}
}另一种，两个临时结点记录前后结点，然后把当前结点摘下来判断
用pre记录当前节点的前一个节点
用next记录当前节点的后一个节点
- 当前节点a不为空，进入循环，先记录a的下一个节点位置next = b;再让a的指针指向pre
- 移动pre和head的位置，正因为刚才记录了下一个节点的位置，所以该链表没有断，我们让head走向b的位置。
- 当前节点为b不为空，先记录下一个节点的位置，让b指向pre的位置即a的位置，同时移动pre和head
- 当前节点c不为空，记录下一个节点的位置，让c指向b，同时移动pre和head，此时head为空，跳出，返回pre。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pre = null;//前一个结点
ListNode p = null;//下一个结点
while(head != null){
p = head.next;//先用p指针记录，保存着当前结点的下一个结点地址。
head.next = pre;//让当前结点与链表断开并指向前一个结点pre。
pre = head;//pre指针指向当前结点，相当于右移一个结点
head = p;////head指向p(保存着原链表中head的下一个结点地址)
//其实存在一个循环依赖关系，顺序不可以变
}
return pre;
}
}递归实现
//递归
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode temp = head.next;//保存下一个节点
ListNode newHead = ReverseList(head.next);//整体思维，宏观语义
temp.next = head;//连上头与递归部分，这部分在递归的栈中已经存储过了
head.next = null;//调整尾部
return newHead;//返回头节点
}
}输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
递归：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null)
return list2;
if(list2 == null)
return list1;//这一段的判空处理
ListNode p;
if(list1.val <= list2.val){
p = list1;
p.next = Merge(list1.next,list2);
}else{
p = list2;
p.next = Merge(list1,list2.next);
}
return p;
}
}一般方法
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode h = new ListNode(-1);
ListNode cur = h;
while(list1 != null && list2 !=null){
if(list1.val<=list2.val){
cur.next = list1;
list1 = list1.next;
}else{
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
if(list1!=null) cur.next = list1;
if(list2!=null) cur.next = list2;
return h.next;
}
}输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
用两个递归，遍历子树和判断父子树左右节点还是否相等，
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false;
if(root1 != null && root2 != null){
if(root1.val == root2.val){
result = DoesRoot1HaveRoot2(root1,root2);
}
if(!result)
result = HasSubtree(root1.left,root2);
if(!result)
result = HasSubtree(root1.right,root2);
}
return result;
}
public boolean DoesRoot1HaveRoot2(TreeNode root1,TreeNode root2){
if(root2 == null)//2 子树已经循环完毕，代表全部匹配
return true;
if(root1 == null)//1 大树已经循环完毕，并未成功匹配
return false;
//2 1两句顺序不能反，看谁先遍历到null，肯定是子树先到null
if(root1.val != root2.val)
return false;
return DoesRoot1HaveRoot2(root1.left,root2.left)
&& DoesRoot1HaveRoot2(root1.right,root2.right);
}
}操作给定的二叉树，将其变换为源二叉树的镜像。
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
先序遍历这棵树的每个结点，如果遍历到的结点有子节点，就交换两个子节点。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root == null)
return ;
if(root.left == null && root.right == null)
return;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left != null)
Mirror(root.left);
if(root.right != null)
Mirror(root.right);
}
}输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
仔细看看人家的代码真的好巧妙
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> result = new ArrayList<>();
if(matrix == null)return result;
int low = 0;
int high = matrix.length-1;
int left = 0;
int right = matrix[0].length-1;
while(low <= high && left <= right){//不满足条件就会直接退出
//向右
for(int i=left; i <= right; i++)
result.add(matrix[low][i]);
//向下
for(int i = low+1; i <= high; i++)
result.add(matrix[i][right]);
//向左 有可能出现特殊的情况只有一列，这时候已经不用向左了
if(low < high){
for(int i= right-1; i >= left; i--)
result.add(matrix[high][i]);
}
//向上 有可能出现特殊的情况只有一行，这时候已经不需要向上了
if(left < right){
for(int i = high-1; i >= low+1; i--)
result.add(matrix[i][left]);
}
low++;
high--;
left++;
right--;
}
return result;
}
}转圈圈的条件，只要保证不重复便立即就行了
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
- 设置一个辅助栈，元素个数与stack1相等，保存现在的最小值，当push进的元素node小于stack2的栈顶时，stack2也push(node)否则还是push之前的元素。
import java.util.Stack;
public class Solution {
private Stack<Integer> stack1 = new Stack<>();
private Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
stack1.push(node);
if (stack1.empty()) {
stack2.push(node);
} else {
int min = Math.min(node, stack2.peek());
stack2.push(min);
}
}
public void pop() {
if(stack1.empty())
return;
stack1.pop();
stack2.pop();
}
public int top() {
return stack1.peek();
}
public int min() {
return stack2.peek();
}
}//不知道为啥会报错，我觉得是对的- 冗余法，冗余曾经的最小值
import java.util.Stack;
public class Solution {
private static Stack<Integer> stack = new Stack<>();
//private Stack<Integer> stack2 = new Stack<>();
private static Integer minElement = Integer.MAX_VALUE;
public void push(int node) {
if(stack.empty()){
minElement = node;
stack.push(node);
}else{
if(node <= minElement){
//push更小的值的时候保留之前的值
stack.push(minElement);
minElement = node;//更新最小值
}
stack.push(node);
}
}
public void pop() {
//增加最后一个元素以及栈为空时候的检测
if(stack.size() == 0)return;
if(minElement == stack.peek()){
if(stack.size() > 1){
stack.pop();
minElement = stack.peek();//最小值为原来的最小值
}else{
minElement = Integer.MAX_VALUE;
}
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minElement;
}
}输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
定义一个栈，边进边看看要不要出
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int p = 0;
for(int i = 0;i < pushA.length;i++){
stack.push(pushA[i]);
while(!stack.isEmpty() && stack.peek() == popA[p]){
stack.pop();
p++;
}
}
return p == popA.length ;
}
}从上往下打印出二叉树的每个节点，同层节点从左至右打印。
广度优先遍历，借用LinkedList队列
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> result = new ArrayList<>();
if(root == null)
return result;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
TreeNode node;
queue.offer(root);
while(!queue.isEmpty()){
node = queue.poll();
result.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
return result;
}
}输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
二叉搜索树的左子肯定小于根节点，右子肯定大于根节点，所以后序遍历数组中最后一个元素肯定是中不溜的元素。遍历数组，如果碰到比数组最后一个值要大的元素，那么它后面的所有元素都要比最后一个大。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
int l = sequence.length;
if (l <= 0)
return false;
int root = sequence[l - 1];//取最后一个
for(int i = 0;i < l-1;i++){
if(sequence[i] < root)
continue;
if(sequence[i] > root){
for(int j = i;j < l-1;j++)
if(sequence[j] <= root)
return false;
}
}
return true;
}
}
结合图中分析：
- 一棵 BST ：左孩子 < 根结点 < 右孩子
- 一棵 BST 的左子树或者右子树都是 BST
后序遍历是，左右根：[3, 4, 9, 5, 12, 11, 10]，结合图再从左往右分析后序序列，分析子树，可以发现：
发现对于每一棵子树，它的根结点总是对应该子树的后序序列的最后一个数
那么，只需要不断地确定出左子树区间和右子树区间，并且判断：左子树区间的所有结点值 < 根结点值 < 右子树区间所有结点值，这个条件是否满足即可
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
int l = sequence.length;
if (l <= 0)
return false;
return isBST(sequence,0,l - 1);
}
//判断当前区间是否是后序BST
public boolean isBST(int []seq,int start,int end){
if(start >= end)
return true;
int root = seq[end];
int split = start;
for(;start < end && seq[split] < root; split++);//找到分隔符，当前的"根节点"
for(int i = split;i < end;i++){
if(seq[i] < root)
return false;
}
return isBST(seq,0,split - 1)&&isBST(seq,split,end - 1);
}
}输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}*/
public class Solution {
private ArrayList<ArrayList<Integer>> result = new ArrayList<>();
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null)
return result;
list.add(root.val);
target -= root.val;
if(target == 0 && root.left == null && root.right == null)
result.add(new ArrayList<Integer>(list));
ArrayList<ArrayList<Integer>> result1 = FindPath(root.left,target);
ArrayList<ArrayList<Integer>> result2 = FindPath(root.right,target);
list.remove(list.size()-1);
return result;
}
}输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
- 用一个 hashmap 建立新旧链表节点的对应的结点关系
- 迭代旧链表，从而在 hashmap 中更新新链表的 next 与 random 两个字段
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.*;
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead == null)
return null;
RandomListNode p1 = pHead;
RandomListNode p2 = pHead;
HashMap<RandomListNode,RandomListNode> map = new HashMap<>();
//存入新旧链表节点的对应关系
while(p1 != null){
map.put(p1,new RandomListNode(p1.label));
p1 = p1.next;
}
//迭代旧链表，更新hashmap中的next与random字段
while(p2 != null){
if(p2.next != null){
map.get(p2).next = map.get(p2.next);
}else{
map.get(p2).next = null;
}
map.get(p2).random = map.get(p2.random);
p2 = p2.next;
}
return map.get(pHead);
}
}解法二：
/*
*解题思路：
*1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
*2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
*3、拆分链表，将链表拆分为原链表和复制后的链表
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if(pHead == null) {
return null;
}
RandomListNode currentNode = pHead;
//1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
while(currentNode != null){
RandomListNode cloneNode = new RandomListNode(currentNode.label);
RandomListNode nextNode = currentNode.next;
currentNode.next = cloneNode;
cloneNode.next = nextNode;
currentNode = nextNode;
}
currentNode = pHead;
//2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
while(currentNode != null) {
currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
currentNode = currentNode.next.next;
}
//3、拆分链表，将链表拆分为原链表和复制后的链表
currentNode = pHead;
RandomListNode pCloneHead = pHead.next;
while(currentNode != null) {
RandomListNode cloneNode = currentNode.next;
currentNode.next = cloneNode.next;
cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
currentNode = currentNode.next;
}
return pCloneHead;
}
}输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
- 递归中序遍历
- 数组转化为双向链表
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return null;
}
ArrayList<TreeNode> list = new ArrayList<>();
SaveInList(pRootOfTree,list);
return Convert(list);
}
//中序遍历，在list中按遍历顺序保存
public void SaveInList(TreeNode node,ArrayList<TreeNode> list){
if(node.left != null){
SaveInList(node.left,list);
}
list.add(node);
if(node.right != null){
SaveInList(node.right,list);
}
}
//遍历list，修改指针
public TreeNode Convert(ArrayList<TreeNode> list){
for(int i = 0;i < list.size() - 1;i++){
list.get(i).right = list.get(i+1);
list.get(i+1).left = list.get(i);
}
return list.get(0);
}
}非递归遍历：
class BiTreeAndDoubleLinkedList {
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) {
return null;
}
return convert(pRootOfTree);
}
private TreeNode convert(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
LinkedList<TreeNode> queue = new LinkedList<>();
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
if (!stack.isEmpty()) {
cur = stack.pop();
queue.offer(cur);
cur = cur.right;
}
}
for (int i = 0; i < queue.size(); i++) {
TreeNode left = i == 0 ? null : queue.get(i - 1);
TreeNode right = i == queue.size() - 1 ? null : queue.get(i + 1);
queue.get(i).left = left;
queue.get(i).right = right;
}
return queue.get(0);
}
}输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
先学习回溯的基本套路，这里使用回溯法解，那么思考回溯的那些玩意有啥：
- path 是啥 ？StringBuilder
- paths 是啥 ？TreeSet
- 状态重置哪一些东西？重置使用状态 visited[] 以及 StringBuilder 的最后一个字符
具体是这样的：
- 排列组合中用过的字符不能再用，所以要用 boolean visited[] 来标记哪一个用过，用过了就不能再组合
- 题目说可能有重复字母，TreeSet 刚好存的值不能重复，所以用 TreeSet，假如用 List 存会存在：
- S = "aa"
- List = ["aa", "aa"]
- 第一个是第一个 a 开头的，第二个是第二个 a 开头的
- 最后，将 TreeSet 的值放入 ArrayList 返回即可，这是题目要求的
import java.util.*;
public class Solution {
private ArrayList<String> res = new ArrayList<>();//存放最终结果
private TreeSet<String> paths = new TreeSet<>();//存放不重复的组合
private StringBuilder path = new StringBuilder();
private boolean[] visited;
public ArrayList<String> Permutation(String str) {
if(str == null||str.equals("")){
return res;
}
char[] strs = str.toCharArray();
Arrays.sort(strs);
visited = new boolean[strs.length];
combination(strs,0);//字符串数组，已经排好了多少个字符了
res.addAll(paths);
return res;
}
private void combination(char[] strs,int len){
if(len == strs.length){//回溯点
paths.add(path.toString());
return;
}
for(int i = 0;i < strs.length;i++){
if(!visited[i]){
visited[i] = true;
path.append(strs[i]);
combination(strs,len+1);
//回溯，状态重置
visited[i] = false;
path.deleteCharAt(path.length()-1);
}
}
}
}数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
用preValue记录上一次访问的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；如果不同count--，减到0的时候就要更换新的preValue值了，因为如果存在超过数组长度一半的值，那么最后preValue一定会是该值。
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0)
return 0;
int preValue = array[0];//记录上一次的记录
int count = 1;//preValue出现的次数
for(int i = 1;i < array.length; i++){
if(array[i] == preValue)
count++;
else{
count--;
if(count == 0){
preValue = array[i];
count = 1;
}
}
}
int num = 0;//需要判断是否真的是大于一半数
for(int i = 0;i < array.length; i++)
if(array[i] == preValue)
num++;
return (num > array.length/2)?preValue:0;
}
}- 排序，取中间的数字，设为i
- 用i过滤数组，如果为i的个数超过半数，则i为所求，否则结果为0
代码如下
`public` `int` `MoreThanHalfNum_Solution(``int` `[] array) {`` ``Arrays.sort(array);`` ``int` `i=array[array.length/``2``];`` ``return` `IntStream.of(array).filter(k->k==i).count()>array.length/``2``?i:``0``;``}`Arrays.sort(array);可以对数组进行排序Stream实例.filter(过滤规则)可对流中的数据进行筛选
void main(){
QSort(L,1,L.length);
}
//快速排序
void QSort(SqList &L,int low,int high){
if(low < high){
pivotloc = Partition(L,low,high);
QSort(L,low,pivotloc-1);
QSort(L,pivotloc+1,high);
}
}
//找中心点位置
int Partition(SqList &L,int low,int high){
//开头存放low的元素
L.r[0] = L.r[low];
pivotkey = L.r[low].key;
while(low < high){
while(low < high && L.r[high].key >= pivotkey)
--high;
L.r[low] = L.r[high];
while(low < high && L.r[low].key <= pivotkey)
++low;
L.r[high] = L.r[low];
}
L.r[low] = L.r[0];
return low;
}public class QuickSort {
//快速排序
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSortCore(arr, 0, arr.length - 1);
}
//快速排序核心算法——递归
public static void quickSortCore(int[] arr, int lo, int hi) {
if (lo < hi) {
int mid = partition(arr, lo, hi); // divide array to two parts
quickSortCore(arr, lo, mid - 1); // sorted left part
quickSortCore(arr, mid + 1, hi); // sorted right part
}
}
//寻找中间点，分区
public static int partition(int[] arr, int lo, int hi) {
// random swap reduce rate of baddest case appear
swap(arr, lo + (int) Math.random() * (hi - lo + 1), hi);
// divide orginal array to smaller and equal or bigger two part
int small = lo - 1;
while (lo < hi) {
if (arr[lo] < arr[hi]) {
swap(arr, ++small, lo++);
} else {
lo++;
}
}
// put pivot into middle
swap(arr, ++small, hi);
// return middle position
return small;
}
// swap array element in i and j
public static void swap(int[] arr, int i, int j) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 5, 4, 6, 9, 8};
quickSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int len = array.length;
if(len <= 0)return 0;
int[] dp = new int[len];
int max = array[0];
dp[0] = array[0];
for(int i = 1;i < len; i++){
int newMax = array[i] + dp[i-1];
if(newMax > array[i])
dp[i] = newMax;
else
dp[i] = array[i];
if(dp[i] > max)
max = dp[i];
}
return max;
}
}典型的动态规划。dp[n]代表以当前元素为截止点的连续子序列的最大和，如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，因为当前数字加上一个正数一定会变大；如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。使用一个变量max记录最大的dp值返回即可。
public int FindGreatestSumOfSubArray(int[] array) {
int max = array[0];
for (int i = 1; i < array.length; i++) {
array[i] += array[i - 1] > 0 ? array[i - 1] : 0;
max = Math.max(max, array[i]);
}
return max;
}输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
* 解题思路：
* 先将整型数组转换成String数组，然后将String数组排序，最后将排好序的字符串数组拼接出来。关键就是制定排序规则。
* 排序规则如下：
* 若ab > ba 则 a > b，
* 若ab < ba 则 a < b，
* 若ab = ba 则 a = b；
* 解释说明：
* 比如 "3" < "31"但是 "331" > "313"，所以要将二者拼接起来进行比较
import java.util.*;
public class Solution {
public String PrintMinNumber(int [] numbers) {
if(numbers == null || numbers.length == 0)
return "";
int len = numbers.length;
String[] str = new String[len];
StringBuilder sb = new StringBuilder();
for(int i = 0;i < len;i++){
str[i] = String.valueOf(numbers[i]);
}
//排序
Arrays.sort(str,new Comparator<String>(){
@Override
public int compare(String s1,String s2){
String c1 = s1+s2;
String c2 = s2+s1;
return c1.compareTo(c2);
}
});
for(int i = 0;i < len;i++){
sb.append(str[i]);
}
return sb.toString();
}
}把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
题解：
（1）丑数数组： 1
乘以2的队列：2
乘以3的队列：3
乘以5的队列：5
选择三个队列头最小的数2加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（2）丑数数组：1,2
乘以2的队列：4
乘以3的队列：3，6
乘以5的队列：5，10
选择三个队列头最小的数3加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（3）丑数数组：1,2,3
乘以2的队列：4,6
乘以3的队列：6,9
乘以5的队列：5,10,15
选择三个队列头里最小的数4加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（4）丑数数组：1,2,3,4
乘以2的队列：6，8
乘以3的队列：6,9,12
乘以5的队列：5,10,15,20
选择三个队列头里最小的数5加入丑数数组，同时将该最小的数乘以2,3,5放入三个队列；
（5）丑数数组：1,2,3,4,5
乘以2的队列：6,8,10，
乘以3的队列：6,9,12,15
乘以5的队列：10,15,20,25
选择三个队列头里最小的数6加入丑数数组，但我们发现，有两个队列头都为6，所以我们弹出两个队列头，同时将12,18,30放入三个队列；
……………………
疑问：
1.为什么分三个队列？
丑数数组里的数一定是有序的，因为我们是从丑数数组里的数乘以2,3,5选出的最小数，一定比以前未乘以2,3,5大，同时对于三个队列内部，按先后顺序乘以2,3,5分别放入，所以同一个队列内部也是有序的；
2.为什么比较三个队列头部最小的数放入丑数数组？
因为三个队列是有序的，所以取出三个头中最小的，等同于找到了三个队列所有数中最小的。
实现思路：
我们没有必要维护三个队列，只需要记录三个指针显示到达哪一步；“|”表示指针,arr表示丑数数组；
（1）1
|2
|3
|5
目前指针指向0,0,0，队列头arr[0] * 2 = 2, arr[0] * 3 = 3, arr[0] * 5 = 5
（2）1 2
2 |4
|3 6
|5 10
目前指针指向1,0,0，队列头arr[1] * 2 = 4, arr[0] * 3 = 3, arr[0] * 5 = 5
（3）1 2 3
2| 4 6
3 |6 9
|5 10 15
目前指针指向1,1,0，队列头arr[1] * 2 = 4, arr[1] * 3 = 6, arr[0] * 5 = 5
………………
import java.util.*;
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index <= 0)
return 0;
int p2 = 0,p3 = 0,p5 = 0;
int[] result = new int[index];
result[0] = 1;
for(int i = 1;i < index;i++){
result[i] = Math.min(2*result[p2],(Math.min(3*result[p3],5*result[p5])));
if(result[i] == 2*result[p2]) p2++;
if(result[i] == 3*result[p3]) p3++;
if(result[i] == 5*result[p5]) p5++;
}
return result[index - 1];
}
}在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.
其实主要还是hash，利用每个字母的ASCII码作hash来作为数组的index。首先用一个58长度的数组来存储每个字母出现的次数，为什么是58呢，主要是由于A-Z对应的ASCII码为65-90，a-z对应的ASCII码值为97-122，而每个字母的index=int(word)-65，比如g=103-65=38，而数组中具体记录的内容是该字母出现的次数，最终遍历一遍字符串，找出第一个数组内容为1的字母就可以了，时间复杂度为O(n)
public class Solution {
public int FirstNotRepeatingChar(String str) {
int[] words = new int[58];
for(int i = 0;i < str.length();i++){
words[(int)str.charAt(i)-65] += 1;
}
for(int i = 0;i < str.length();i++){
if(words[(int)str.charAt(i)-65] == 1)
return i;
}
return -1;
}
}在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
题目保证输入的数组中没有的相同的数字数据范围： 对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5
示例1
1,2,3,4,5,6,7,0
7
题解：
在归并排序的过程中 后一个数组的数如小于前一个数组的数，则一定能够构成逆序对且逆序对的数目可计算，因为待归并的两个数组提前已经归并排序过，所以不会出现像前面那样少统计或者多统计的情况出现。 思路：[A，B]中的逆序对=[A]的逆序对+[B]中的逆序对+将A，B混排在一起的逆序对 而将A，B混排在一起的逆序对求解看下面：
public class Main {
public int cnt;
private void MergeSort(int[] array,int start,int end){
if(start >= end) return;
int mid = (start+end)/2;
MergeSort(array,start,mid);
MergeSort(array,mid+1,end);
MergeOne(array,start,mid,end);
}
private void MergeOne(int[] array,int start,int mid,int end){
int[] temp = new int[end - start + 1];
int k = 0,i = start,j = mid+1;
while(i <= mid && j <= end){
//如果i指向的元素小于j指向的元素，则不能构成逆序对
if(array[i] < array[j])
temp[k++] = array[i++];
//如果i指向的元素大于j指向的元素，那么i之后的元素也和j指向的元素构成了逆序对
else{
temp[k++] = array[j++];
cnt = (cnt + (mid - i + 1))%1000000007;
}
}
while(i <= mid){
temp[k++] = array[i++];
}
while(j <= end){
temp[k++] = array[j++];
}
for(int l=0; l<k; l++){
array[start+l] = temp[l];
}
}
public int InversePairs(int [] array) {
MergeSort(array, 0, array.length-1);
return cnt;
}
}输入两个链表，找出它们的第一个公共结点。
分析：
如果两个单向链表有公共结点，那么这两个节点之后的所有结点都是重合的，不可能出现分叉。
如果有公共结点，那么公共结点出现在两个链表的尾部
首先遍历两个链表得到它们的长度，知道长的链表比短的长多少个结点。第二次遍历的时候，在较长的链表上先走若干步，接着同时在两个链表上遍历，找到的第一个相同结点就是他们的第一个公共结点。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
class Main {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2){
//表头不相等 则肯定有共同尾部
if(pHead1 == null|| pHead2 == null)
return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
//寻找公共结点
if(p1 != p2){
//判断谁先走到了头，先走到头的回到另外一个链表头
//相当于减去两个链表的长度差，从相同长度开始遍历
if(p1 == null){
p1 = pHead2;
}if(p2 == null){
p2 = pHead1;
}
}
}
return p1;
}
}想到二分法
public class Main {
//在分别找到第一个k和最后一个k的下标之后，计算出现次数
public int GetNumberOfK(int [] array , int k) {
if(array.length == 0||array == null)
return 0;
int firstIndex = GetFirstK(array,k);
int lastIndex = GetLastK(array,k);
return lastIndex - firstIndex;
}
private int GetFirstK(int[] array,int k){
int l = 0,r = array.length - 1,mid;
while(l <= r){
mid = (l+r) >> 1;
if(array[mid] < k)
l = mid + 1;
else
r = mid - 1;//找第一个k，相等时向前找
}
return l;
}
private int GetLastK(int[] array,int k){
int l = 0,r = array.length - 1,mid;
while(l <= r){
mid = (l+r) >> 1;
if(array[mid] <= k)//找最后一个k，相等时向后找
l = mid + 1;
else
r = mid - 1;
}
return l;
}
}输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public int TreeDepth(TreeNode root) {
if(root == null)
return 0;
if(root.left == null&&root.right == null)
return 1;
int left = TreeDepth(root.left);
int right = TreeDepth(root.right);
return left > right ? left + 1 : right + 1;
}
}输入一棵二叉树，判断该二叉树是否是平衡二叉树。
最直接的做法，遍历每个结点，借助一个获取树深度的递归函数，根据该结点的左右子树高度差判断是否平衡，然后递归地对左右子树进行判断。
public classSolution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) {
return true;
}
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 &&
IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
}
private int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}这种做法有很明显的问题，在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。如果改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
return getDepth(root) != -1;
}
//使用后序遍历，一边遍历一边判断每个结点是不是平衡的
//先判断左右子树，如果左右子树不为平衡二叉树，那么就没必要判断了，直接跳出。
private int getDepth(TreeNode root){
if(root == null)
return 0;
int left = getDepth(root.left);
if(left == -1)
return -1;
int right = getDepth(root.right);
if(right == -1)
return -1;
return Math.abs(left-right) > 1 ? -1 : Math.max(left,right) + 1;
}
}一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
分析：
当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。
依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int xor1 = 0;
for(int i = 0;i < array.length;i++){
xor1 = xor1^array[i];
}
//在xor1中找到第一个不同的位对数据进行分类，分类为两个队列对数据进行异或求和找到我们想要的结果
int index = 1;
while((index & xor1) == 0){
index = index << 1;//求最右边的
}
int result1 = 0,result2 = 0;
for(int i = 0;i < array.length;i++){
if((index & array[i]) == 0)
result1 ^= array[i];
else
result2 ^= array[i];//分类，异或一起进行
}
num1[0] = result1;
num2[0] = result2;
}
}HashMap方法：
import java.util.HashMap;
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
//哈希算法
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i=0; i < array.length; i++){
if(map.containsKey(array[i]))
map.put(array[i],2);
else
map.put(array[i],1);
}
int count = 0;
for(int i=0; i < array.length; i++){
if(map.get(array[i]) == 1){
if(count == 0){
num1[0] = array[i];
count++;
}else
num2[0] = array[i];
}
}
}
}小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
import java.util.ArrayList;
public class Main {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
//存放结果
ArrayList<ArrayList<Integer> > result = new ArrayList<>();
//两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
int plow = 1,phigh = 2;
while(phigh > plow){
//由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
int cur = (phigh + plow) * (phigh - plow + 1) / 2;
//相等，那么就将窗口范围的所有数添加进结果集
if(cur == sum){
ArrayList<Integer> list = new ArrayList<>();
for(int i=plow;i<=phigh;i++){
list.add(i);
}
result.add(list);
plow++;
//如果当前窗口内的值之和小于sum，那么右边窗口右移一下
}else if(cur < sum){
phigh++;
}else{
//如果当前窗口内的值之和大于sum，那么左边窗口右移一下
plow++;
}
}
return result;
}
}输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
对应每个测试案例，输出两个数，小的先输出。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> result = new ArrayList<>();
if(array == null || array.length < 0)
return result;
//双指针，离得越近乘积越大
int p1 = 0,p2 = array.length - 1;
while(p1 < p2){
int cur = array[p1]+array[p2];
if(cur == sum){
result.add(array[p1]);
result.add(array[p2]);
break;
}else if(cur < sum){
p1++;
}else
p2--;
}
return result;
}
}汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
public class Solution {
public String LeftRotateString(String str,int n) {
if(str == null || "".equals(str))
return "";
int l = str.length();
if(n > l)
n = n%l;
String s1 = str.substring(0,n);
String s2 = str.substring(n,l);
//substring(begin,end)
//该子字符串从指定的 beginIndex 处开始， endIndex:到指定的 endIndex-1处结束。
return s2+s1;
}
}牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
public class Solution {
public String ReverseSentence(String str) {
char[] chars = str.toCharArray();
Reverse(chars,0,chars.length-1);//先反转整个句子
int thisBlank = -1;
for(int i = 0;i < chars.length;i++){
if(chars[i] == ' '){
int nextBlank = i;
Reverse(chars,thisBlank+1,nextBlank-1);
thisBlank = nextBlank;
}
}
//最后一个单词单独反转
Reverse(chars,thisBlank+1,chars.length-1);
return new String(chars);
}
public void Reverse(char[] chars,int low,int high){
while(low < high){
char temp = chars[low];
chars[low] = chars[high];
chars[high] = temp;
low++;
high--;
}
}
}每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
思路一：
用数学归纳法推导出递推公式，设有n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。令f[i]表示i个人时最后胜利者的编号，则有递推公式：
f[1]=0; f[i]=(f[i-1]+m)%i; (i>1)
这个公式用递归和循环都能完成：
递归：
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n <= 0 || m <= 0)
return -1;
if(n == 1)
return 0;
else
return (LastRemaining_Solution(n-1,m)+m)%n;
}
}循环:
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n <= 0 || m <= 0)
return -1;
int last = 0;
for(int i = 2;i <= n;i++)
last = (last+m) % i;
return last;
}
}思路二：
用数组模拟过程
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n <= 0 || m <= 0)
return -1;
int[] array = new int[n];
int i = -1,step = 0,count = n;
while(count > 0){
i++;//指向上一个被删除的下一个元素
if(i >= n)
i = 0;//超了就从头开始
if(array[i] == -1)
continue;
step++; //计算步数
if(step == m){ //如果数到了
array[i] = -1;//标记删除
step = 0;
count--;
}
}
return i;
}
}求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
//其实只要先看我们手里有什么牌就能一步一步想到利用短路特性了
//我们手里现在可以使用（按优先级高低）单目运算符：++和--,双目运算符：+,-，移位运算符<<和>>，关系运算符>,<等，逻辑运算符&&，||,&,|,^，赋值=
//单目和双目的作用是一样的，移位显然没有规律性，因为一个二进制位并不能区分某个数和其他数，这也就排除了&,|,^,因为不需要做位运算了
//关系运算符要和if匹配，但这是不行的，这时看看剩下的运算符只能选&&,||了
//如果做过Java笔试题，会对这两个运算符非常敏感，他们有短路特性，前面的条件判真（或者假）了，就不会再执行后面的条件了
//这时就能联想到--n,直到等于0就能返回值。
public class Solution {
public int Sum_Solution(int n) {
int sum = n;
boolean flag = (sum>0)&&((sum+=Sum_Solution(--n))>0);
return sum;
}
}写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
首先看十进制是如何做的： 5+7=12，三步走 第一步：相加各位的值，不算进位，得到2。 第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。 第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。 同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111 第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。 第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。 第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。 继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
public class Solution {
public int Add(int num1,int num2) {
while(num2 != 0){//没有进位的时候跳出循环
int temp = num1^num2;//异或操作 相当于相加各位的值，但是不进位
num2 = (num1 & num2) << 1;//与操作后面添0，相当于计算进位值
num1 = temp;
}
return num1;
}
}将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
输入一个字符串,包括数字字母符号,可以为空
如果是合法的数值表达则返回该数字，否则返回0
示例1
+2147483647
1a33
2147483647
0
利用正则表达式
public class Solution {
public int StrToInt(String str) {
// \d代表[0-9] 但是要写成\\d才行。
if(!str.matches("[1-9,+,-]\\d+")) return 0;
int len = str.length();
int i = len-1;
long res = 0; //long类型，避免溢出。不能用int
while(i>=0&&str.charAt(i)>='0'&&str.charAt(i)<='9'){
res += Math.pow(10,len-1-i)*(str.charAt(i)-'0');
i--;
}
res = (str.charAt(0) == '-' ? -res : res);
//溢出就返回0，用long类型的res来比较，
//如果定义为int res,那再比较就没有意义了，int范围为[-2147483648,2147483647]
if(res>Integer.MAX_VALUE|| res<Integer.MIN_VALUE)return 0;
return (int)res;
}
}在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
将输入数组排序，再判断相邻位置是否存在相同数字，如果存在，对 duplication 赋值返回，否则继续比较
import java.util.*;
public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers == null || length == 0){
return false;
}
Arrays.sort(numbers);
for(int i=0;i<length-1;i++){
if(numbers[i] == numbers[i+1]){
duplication[0] = numbers[i];
return true;
}
}
return false;
}
}时间复杂度：O(nlogn) 空间复杂度：O(1)
利用 HashSet 解决，从头到尾扫描数组，每次扫描到一个数，判断当前数是否存在 HashSet 中，如果存在，则重复，对 duplication 赋值返回，否则将该数加入到 HashSet 中
import java.util.*;
public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
Set<Integer> set = new HashSet<>();
for(int i =0 ;i<length;i++){
if(set.contains(numbers[i])){
duplication[0] = numbers[i];
return true;
}else{
set.add(numbers[i]);
}
}
return false;
}
}时间复杂度：O(n)O(n) 空间复杂度：O(n)O(n)
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...*A[i-1]A[i+1]...*A[n-1]。不能使用除法。
下三角用连乘可以很容求得，上三角，从下向上也是连乘。
因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。
import java.util.ArrayList;
public class Solution {
public int[] multiply(int[] A) {
int length = A.length;
int[] B = new int[length];
if(length > 0){
B[0] = 1;
//计算下三角连乘，从上往下
for(int i = 1;i < length;i++){
B[i] = B[i-1]*A[i-1];
}
int temp = 1;
//计算上三角，从下往上，从倒数第二行开始
for(int j = length-2; j >= 0;j--){
temp *= A[j+1];
B[j] *= temp;
}
}
return B;
}
}请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
public class Solution {
public boolean match(char[] str, char[] pattern)
{
return matchStr(str,0,pattern,0);
}
public boolean matchStr(char[] str,int i,char[] pattern,int j){
//边界
if(i == str.length && j == pattern.length)
return true;
else if(j == pattern.length)//模式串为空
return false;
boolean flag = false;
// 模式串下一个字符是'*'
boolean next = (j+1 < pattern.length && pattern[j+1] == '*');
if(next){
// 要保证i<str.length，否则越界
if(i < str.length && (pattern[j] == '.' || str[i] == pattern[j]))
return matchStr(str, i, pattern, j + 2)
|| matchStr(str, i + 1, pattern, j);
else
return matchStr(str, i, pattern, j + 2);
}else{//如果模式串下一个不是'*'
if (i < str.length && (pattern[j] == '.' || str[i] == pattern[j])) {
return matchStr(str, i + 1, pattern, j + 1);
} else {
return false;
}
}
}
}动态规划：
使用动态规划自底向上方法。
定义boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]，初始化dp[s.length()][p.length()] = true，表示当两者都为空时匹配。
如何得到dp[i][j]的值？
首先判断s.charAt(i)和p.charAt(j)是否匹配，匹配的条件是两个字符相同，或者p.charAt(j)是'.'。
然后判断p.charAt(j + 1)是不是'*'
-
若是，由于'*'可匹配0个字符，当
dp[i][j + 2] == true时dp[i][j] = true，另外当目前的字符匹配且
d[i + 1][j] == true时dp[i][j] = true。 -
如果
p.charAt(j + 1)不是'*'，则dp[i][j] = true当且仅当目前的字符匹配且dp[i + 1][j + 1] == true。最后返回
dp[0][0]。
class Solution {
public boolean isMatch(String s, String p) {
int sLength = s.length(), pLength = p.length();
boolean[][] dp = new boolean[sLength + 1][pLength + 1];
dp[sLength][pLength] = true;
for (int i = sLength; i >= 0; i--) {
for (int j = pLength - 1; j >= 0; j--) {
boolean charMatch = i < sLength && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
if (j < pLength - 1 && p.charAt(j + 1) == '*')
dp[i][j] = dp[i][j + 2] || charMatch && dp[i + 1][j];
else
dp[i][j] = charMatch && dp[i + 1][j + 1];
}
}
return dp[0][0];
}
}请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
public class Solution {
public boolean isNumeric(char[] str) {
String s = new String(str);
return s.matches("[\\+\\-]?(\\d*\\.\\d+|\\d+\\.?)([eE][\\+\\-]?\\d+)?");
}
}还有一种正则表达式：
s.matches("^[+-]?\\d*(?:\\.\\d*)?(?:[eE][+\\-]?\\d+)?$");^ 和 美元符号框定正则表达式，它指引这个正则表达式对文本中的所有字符都进行匹配。如果省略这些标识，那么只要一个字符串中包含一个数字这个正则表达式就会进行匹配。如果仅包含 ^ ，它将匹配以一个数字开头的字符串。如果仅包含$ ，则匹配以一个数字结尾的字符串。
`[-+]?`
正负号后面的 ? 后缀表示这个负号是可选的,表示有0到1个负号或者正号
`\\d*`
\d的含义和[0-9]一样。它匹配一个数字。后缀 * 指引它可匹配零个或者多个数字。
`(?:\\.\\d*)?`
(?: …)?表示一个可选的非捕获型分组。* 指引这个分组会匹配后面跟随的0个或者多个数字的小数点。
`(?:[eE][+\\-]?\d+)?`
这是另外一个可选的非捕获型分组。它会匹配一个e(或E)、一个可选的正负号以及一个或多个数字。
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
如果当前字符流没有存在出现一次的字符，返回#字符。
Java版的，使用一个HashMap来统计字符出现的次数，同时用一个ArrayList来记录输入流，每次返回第一个出现一次的字符都是在这个ArrayList（输入流）中的字符作为key去map中查找。
import java.util.*;
public class Solution {
ArrayList<Character> list = new ArrayList<>();
HashMap<Character,Integer> map = new HashMap<>();
//Insert one char from stringstream
public void Insert(char ch)
{
list.add(ch);
if(map.containsKey(ch))
map.put(ch,map.get(ch)+1);
else
map.put(ch,1);
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
char c = '#';
for(char key : list){
if(map.get(key) == 1){
c = key;
break;
}
}
return c;
}
} 设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。以下是两个结论证明：
1、设置快慢指针，假如有环，他们最后一定相遇。
2、两个指针分别从链表头和相遇点继续出发，每次走一步，最后一定相遇与环入口。
证明结论1：设置快慢指针fast和low，fast每次走两步，low每次走一步。假如有环，两者一定会相遇（因为low一旦进环，可看作fast在后面追赶low的过程，每次两者都接近一步，最后一定能追上）。
证明结论2：
设：
链表头到环入口长度为--a
环入口到相遇点长度为--b
相遇点到环入口长度为--c
**
则：相遇时
快指针路程=a+(b+c)k+b ，k>=1 其中b+c为环的长度，k为绕环的圈数（k>=1,即最少一圈，不能是0圈，不然和慢指针走的一样长，矛盾）。
慢指针路程=a+b
快指针走的路程是慢指针的两倍，所以：
（a+b）*2=a+(b+c)k+b
化简可得：
a=(k-1)(b+c)+c 这个式子的意思是： 链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度。其中k>=1,所以k-1>=0圈。所以两个指针分别从链表头和相遇点出发，最后一定相遇于环入口。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
//快慢指针
ListNode low = pHead;
ListNode fast = pHead;
while(fast != null&&fast.next != null){
low = low.next;
fast = fast.next.next;
if(low == fast)//到达相遇点
break;
}
if(fast == null||fast.next == null)
return null;
low = pHead;//low从结点起点开始
while(low != fast){
low = low.next;
fast = fast.next;//fast从相遇点出发，速度和low一样
}
//最终在环入口相遇
return low;
}
}在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
- 首先添加一个头节点，以方便碰到第一个，第二个节点就相同的情况
- 设置 pre ，last 指针， pre指针指向当前确定不重复的那个节点，而last指针相当于工作指针，一直往后面搜索。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
if(pHead == null || pHead.next == null)
return pHead;
ListNode Head = new ListNode(0);//设置头结点
Head.next = pHead;
ListNode p1 = Head;//保存不重复的结点
ListNode p2 = Head.next;//工作指针
while(p2 != null){
if(p2.next != null && p2.val == p2.next.val){
//寻找最后一个相等的
while(p2.next != null && p2.val == p2.next.val)
p2 = p2.next;
p1.next = p2.next;//重复结点一个都不保留
p2 = p2.next;
}else{
p1 = p1.next;
p2 = p2.next;
}
}
return Head.next;
}
}给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
（1）若该节点存在右子树：则下一个节点为右子树最左子节点（如图节点 B ）
（2）若该节点不存在右子树：这时分两种情况：
2.1 该节点为父节点的左子节点，则下一个节点为其父节点（如图节点 D ）
2.2 该节点为父节点的右子节点，则沿着父节点向上遍历，知道找到一个节点的父节点的左子节点为该节点，则该节点的父节点下一个节点（如图节点 I ，沿着父节点一直向上查找找到 B （ B 为其父节点的左子节点），则 B 的父节点 A 为下一个节点）。
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
class Main{
//中序遍历：左中右
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode == null)
return pNode;
if(pNode.right != null){//结点有右子树
pNode = pNode.right;
while(pNode.left != null){//右子树的最左边结点
pNode = pNode.left;
}
return pNode;
}else if(pNode.next != null && pNode.next.left == pNode){
//父节点不为空，没有右子树，且pNode为父节点的左结点
return pNode.next;//父结点就是下一个
}else if(pNode.next != null && pNode.next.right == pNode){
//没有右子树，且pNode为父节点的右结点
while(pNode.next != null && pNode.next.left != pNode){
pNode = pNode.next;//向上遍历
}
return pNode.next;
}else{
//无左右子树，当前结点为根节点
return pNode.next;
}
}
}请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同
左子树的右子树和右子树的左子树相同即可，采用递归
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
if(pRoot == null)
return true;
return comRoot(pRoot.left,pRoot.right);
}
boolean comRoot(TreeNode left,TreeNode right){
if(left == null) return right == null;
if(right == null) return false;
return (left.val == right.val)
&&comRoot(left.right,right.left)
&&comRoot(left.left,right.right);
}
}非递归：
出栈成对：
1.若都为空，继续；
2.一个为空，返回false;
3.不为空，比较当前值，值不等，返回false；
入栈也成对：
boolean isSymmetricalDFS(TreeNode pRoot){
if(pRoot == null)
return true;
Stack<TreeNode> s = new Stack<>();//栈
s.push(pRoot.left);
s.push(pRoot.right);
while(!s.empty()) {
TreeNode right = s.pop();//成对取出
TreeNode left = s.pop();
if(left == null && right == null) continue;
if(left == null || right == null) return false;
if(left.val != right.val) return false;
//成对插入
s.push(left.left);
s.push(right.right);
s.push(left.right);
s.push(right.left);
}
return true;
}boolean isSymmetricalBFS(TreeNode pRoot){
if(pRoot == null)
return true;
Queue<TreeNode> s = new LinkedList<>();//队列
s.offer(pRoot.left);
s.offer(pRoot.right);
while(!s.isEmpty()) {
TreeNode left= s.poll();//成对取出
TreeNode right= s.poll();
if(left == null && right == null) continue;
if(left == null || right == null) return false;
if(left.val != right.val) return false;
//成对插入
s.offer(left.left);
s.offer(right.right);
s.offer(left.right);
s.offer(right.left);
}
return true;
}请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
用栈的特性来帮助实现之字形顺序，不用遇到偶数层就reverse
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
int layer = 1;
Stack<TreeNode> s1 = new Stack<TreeNode>();//存放奇数层结点
s1.push(pRoot);
Stack<TreeNode> s2 = new Stack<TreeNode>();//存放偶数层结点
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
while(!s1.isEmpty() || !s2.isEmpty()){
if(layer%2 != 0){
ArrayList<Integer> temp = new ArrayList<>();
while(!s1.isEmpty()){
TreeNode node = s1.pop();
if(node != null){
temp.add(node.val);
System.out.print(node.val+" ");
s2.push(node.left);
s2.push(node.right);
}
}
if(!temp.isEmpty()){
list.add(temp);
layer++;
System.out.println();
}
}else{
ArrayList<Integer> temp = new ArrayList<>();
while(!s2.isEmpty()){
TreeNode node = s2.pop();
if(node != null){
temp.add(node.val);
System.out.print(node.val+" ");
s1.push(node.right);
s1.push(node.left);
}
}
if(!temp.isEmpty()){
list.add(temp);
layer++;
System.out.println();
}
}
}
return list;
}
}请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
String Serialize(TreeNode root) {
if(root == null)
return "#";
else
return root.val+"!"+Serialize(root.left)+"!"+Serialize(root.right);
}
int index = -1;
TreeNode Deserialize(String str) {
String[] strs = str.split("!");
int len = strs.length;
index++;//索引每次++
if(index > len)
return null;
TreeNode node = null;
if(!strs[index].equals("#")){
node = new TreeNode(Integer.parseInt(strs[index]));
node.left = Deserialize(str);
node.right = Deserialize(str);
}
return node;
}
}给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
开辟空间存储遍历结果
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
ArrayList<TreeNode> list = new ArrayList<>();
TreeNode KthNode(TreeNode pRoot, int k)
{
Middle(pRoot);
if(k >= 1 && list.size() >= k)
return list.get(k-1);
return null;
}
//中序遍历
void Middle(TreeNode node){
if(node != null){
Middle(node.left);
list.add(node);
Middle(node.right);
}
}
}中序遍历计数，中序遍历的顺序就是从小到大
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
TreeNode treeNode = null;
int count = 0;
TreeNode KthNode(TreeNode pRoot, int k)
{
if(pRoot == null || k <= 0)
return null;
dfs(pRoot,k);
return treeNode;
}
//中序遍历
void dfs(TreeNode root,int k){
if(count < k && root.left != null)
dfs(root.left,k);
if(++count == k)
treeNode = root;
if(count < k && root.right != null)
dfs(root.right,k);
}
}如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
- 先用java集合PriorityQueue来设置一个小顶堆和大顶堆
- 主要的思想是：因为要求的是中位数，那么这两个堆，大顶堆用来存较小的数，从大到小排列；
- 小顶堆存较大的数，从小到大的顺序排序，显然中位数就是大顶堆的根节点与小顶堆的根节点和的平均数。
- ⭐保证：小顶堆中的元素都大于等于大顶堆中的元素，所以每次塞值，并不是直接塞进去，而是从另一个堆中poll出一个最大（最小）的塞值
- ⭐当数目为偶数的时候，将这个值插入大顶堆中，再将大顶堆中根节点（即最大值）插入到小顶堆中；
- ⭐当数目为奇数的时候，将这个值插入小顶堆中，再讲小顶堆中根节点（即最小值）插入到大顶堆中；
- ⭐取中位数的时候，如果当前个数为偶数，显然是取小顶堆和大顶堆根结点的平均值；如果当前个数为奇数，显然是取小顶堆的根节点
理解了上面所述的主体思想，下面举个例子辅助验证一下。
例如，传入的数据为：[5,2,3,4,1,6,7,0,8],那么按照要求，输出是"5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
那么整个程序的执行流程应该是（用min表示小顶堆，max表示大顶堆）：
- 5先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[5],max=[无]，avg=[5.00]
- 2先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[5],max=[2],avg=[(5+2)/2]=[3.50]
- 3先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[3,5],max=[2],avg=[3.00]
- 4先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[4,5],max=[3,2],avg=[(4+3)/2]=[3.50]
- 1先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[3,4,5],max=[2,1]，avg=[3/00]
- 6先进入小顶堆，然后将小顶堆中最小值放入大顶堆中，此时min=[4,5,6],max=[3,2,1],avg=[(4+3)/2]=[3.50]
- 7先进入大顶堆，然后将大顶堆中最大值放入小顶堆中，此时min=[4,5,6,7],max=[3,2,1],avg=[4]=[4.00]
- 0先进入小顶堆，然后将小顶堆中最大值放入小顶堆中，此时min=[4,5,6,7],max=[3,2,1,0],avg=[(4+3)/2]=[3.50]
- 8先进入大顶堆，然后将大顶堆中最小值放入大顶堆中，此时min=[4,5,6,7,8],max=[3,2,1,0],avg=[4.00]
import java.util.*;
public class Solution {
//小顶堆
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
//大顶堆
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(15,new Comparator<Integer>(){
public int compare(Integer o1,Integer o2){
return o2-o1;
}
});
//记录偶数个还是奇数个
int count = 0;
//每次插入小顶堆的是当前大顶堆中最大的数
//每次插入大顶堆的是当前小顶堆中最小的数
//这样保证小顶堆中的数永远大于等于大顶堆中的数
//中位数就可以方便地从两者的根结点中获取了
public void Insert(Integer num) {
//个数为偶数的话，则先插入到大顶堆，然后将大顶堆中最大的数插入小顶堆中
if(count % 2 == 0){
maxHeap.offer(num);
int max = maxHeap.poll();
minHeap.offer(max);
}else{
//个数为奇数的话，则先插入到小顶堆，然后将小顶堆中最小的数插入大顶堆中
minHeap.offer(num);
int min = minHeap.poll();
maxHeap.offer(min);
}
count++;
}
public Double GetMedian() {
//当前个数为偶数，取大小根堆的根节点平均值
if(count % 2 == 0){
return new Double(minHeap.peek() + maxHeap.peek())/2;
}else{
//奇数个取小根堆的堆顶元素
return new Double(minHeap.peek());
}
}
}给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
//标志位数组
boolean[] flag = new boolean[matrix.length];
for(int i = 0;i < rows;i++)
for(int j = 0;j < cols;j++)
//循环遍历二维数组，找到起点等于str第一个元素的值，
//再递归判断四周是否有符合条件的----回溯法
if(judge(matrix,i,j,rows,cols,flag,str,0))
return true;
return false;
}
//judge(初始矩阵，索引行坐标i，索引纵坐标j，矩阵行数，矩阵列数，
//待判断的字符串，字符串索引初始为0即先判断字符串的第一位)
private boolean judge(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,char[] str,int k){
//先根据i和j计算匹配的第一个元素转为一维数组的位置
int index = cols*i+j;
//递归出口
if(i < 0||j < 0||i >= rows||j >= cols||matrix[index] != str[k]||flag[index] == true){
return false;
}
//若k已经到达str末尾了，说明之前的都已经匹配成功了，直接返回true即可
if(str.length - 1 == k)
return true;
//要走的第一个位置置为true，表示已经走过了
flag[index] = true;
//回溯，递归寻找，每次找到了就给k加一，找不到，还原
if(judge(matrix,i-1,j,rows,cols,flag,str,k+1) ||
judge(matrix,i+1,j,rows,cols,flag,str,k+1) ||
judge(matrix,i,j-1,rows,cols,flag,str,k+1) ||
judge(matrix,i,j+1,rows,cols,flag,str,k+1) )
{
return true;
}
//走到这，说明这一条路不通，还原，再试其他的路径
flag[index] = false;
return false;
}
}地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
public class Solution {
public int movingCount(int threshold, int rows, int cols)
{
int[][] flag = new int[rows][cols];
return helper(0,0,rows,cols,flag,threshold);
}
private int helper(int i,int j,int rows,int cols,int[][] flag,int threshold){
if(i < 0||j < 0||i >= rows||j >= cols|| numSum(i) + numSum(j) > threshold||flag[i][j] == 1)
return 0;
flag[i][j] = 1;
return helper(i - 1,j,rows,cols,flag,threshold) +
helper(i,j - 1,rows,cols,flag,threshold) +
helper(i + 1,j,rows,cols,flag,threshold) +
helper(i,j + 1,rows,cols,flag,threshold) + 1;
}
private int numSum(int i){
int sum = 0;
do{
sum += i%10;
}while((i = i/10) > 0);
return sum;
}
}给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
动态规划：
public class Solution {
public int cutRope(int n) {
//n<=3的情况，m>1必须要分段，例如：3必须分成1、2；1、1、1 ，n=3最大分段乘积是2
if(n == 2)
return 1;
if(n == 3)
return 2;
int[] dp = new int[n+1];
/*
下面3行是n>=4的情况，跟n<=3不同，4可以分很多段，比如分成1、3，
这里的3可以不需要再分了，因为3分段最大才2，不分就是3。记录最大的。
*/
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
int res = 0;//记录最大值
for(int i = 4;i <= n;i++){
for(int j = 1;j <= i/2;j++)
res = Math.max(res,dp[j]*dp[i-j]);
dp[i] = res;
}
return dp[n];
}
}贪心：
上式中除法向下取整 当n≤3时，只有 当n==2时f(x)=1； 当n==3时f(x)=2;
public class Solution {
public int cutRope(int n) {
//n<=3的情况，m>1必须要分段，例如：3必须分成1、2；1、1、1 ，n=3最大分段乘积是2
if(n == 2)
return 1;
if(n == 3)
return 2;
int x = n % 3;//余数
int y = n / 3;
if(x == 0)//没有2，全是3
return (int)Math.pow(3,y);
else if(x == 1)//2个2
return 2*2*(int)Math.pow(3,y-1);
else //1个2
return 2*(int)Math.pow(3,y);
}
}给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
请你返回你可以参加的 最大 会议数目。
示例 1：
输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。
示例 2：
输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4
示例 3：
输入：events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
输出：4
示例 4：
输入：events = [[1,100000]]
输出：1
示例 5：
输入：events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
输出：7
提示：
1 <= events.length <= 10^5events[i].length == 21 <= events[i][0] <= events[i][1] <= 10^5
题解：
class Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1]) return o1[0] - o2[0];
return o1[1] - o2[1];
}
});
int res = 0;
Set<Integer> used = new HashSet<>();
for (int i = 0; i < events.length; i++) {
for (int j = events[i][0]; j <= events[i][1]; j++) {
if (used.contains(j)) continue;
else {
used.add(j);
res++;
break;
}
}
}
return res;
}
}class Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events, Comparator.comparingInt(e -> e[0]));
PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(e -> e[1]));
int lastDay = 0, count = 0;
int[] event;
int len = events.length, i = 0;
while (i < len || !queue.isEmpty()) {
if (queue.isEmpty() || i < len && events[i][0] <= Math.max(lastDay + 1, queue.peek()[0])) {
queue.offer(events[i++]);
} else {
event = queue.poll();
if (event[1] > lastDay) {
lastDay = Math.max(lastDay + 1, event[0]);
count++;
}
}
}
return count;
}
}class Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events, new Comparator<int[]>() {
public int compare(int[] i1, int[] i2) {
return i1[0] - i2[0];
}
});
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
public int compare(int[] i1, int[] i2) {
return i1[1] - i2[1];
}
});
int cur = 1;
int res = 0;
int index = 0;
while (index < events.length || !pq.isEmpty()) {
while (index < events.length && events[index][0] == cur) {
pq.offer(events[index++]);
}
while (!pq.isEmpty() && pq.peek()[1] < cur) {
pq.poll();
}
if (!pq.isEmpty()) {
res++;
pq.poll();
}
cur++;
}
return res;
}
}给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作：
- 令
x为你数组里所有元素的和 - 选择满足
0 <= i < target.size的任意下标i，并让A数组里下标为i处的值为x。 - 你可以重复该过程任意次
如果能从 A 开始构造出目标数组 target ，请你返回 True ，否则返回 False 。
示例 1：
输入：target = [9,3,5]
输出：true
解释：从 [1, 1, 1] 开始
[1, 1, 1], 和为 3 ，选择下标 1
[1, 3, 1], 和为 5， 选择下标 2
[1, 3, 5], 和为 9， 选择下标 0
[9, 3, 5] 完成
示例 2：
输入：target = [1,1,1,2]
输出：false
解释：不可能从 [1,1,1,1] 出发构造目标数组。
示例 3：
输入：target = [8,5]
输出：true
提示：
N == target.length1 <= target.length <= 5 * 10^41 <= target[i] <= 10^9
class Solution {
public boolean isPossible(int[] target) {
Arrays.sort(target);
int sum = 0;
int n = target.length;
if((target[0] == target[n-1]) && (target[0] == 1))
return true;//递归出口
for(int i = 0;i < n - 1;i++)
sum += target[i];
target[n-1] -= sum;
if(sum < 1)
return false;
else return isPossible(target);
}
}