分类目录归档:Java

java算法-滑动窗口的最大值


题目描述

给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值。

例如,如果输入数组 [2, 3, 4, 2, 6, 2, 5, 1] 及滑动窗口的大小 3,那么一共存在 6 个滑动窗口,它们的最大值分别为 [4, 4, 6, 6, 6, 5]

注意:

  • 数据保证 k 大于 0,且 k 小于等于数组长度。

样例

输入:[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

解法

利用双向队列,保证队列头部存放的是最大值的下标,当队列头部下标过期时弹出。

细节:

  • 当数组元素小于队列头部下标对应的元素时,在队列尾部中插入数组元...

阅读全文...

java算法-扑克牌的顺子


题目描述

从扑克牌中随机抽 5 张牌,判断是不是一个顺子,即这5张牌是不是连续的。

2~10 为数字本身,A1J11Q12K13,大小王可以看做任意数字。

为了方便,大小王均以 0 来表示,并且假设这副牌中大小王均有两张。

样例1

输入:[8,9,10,11,12]

输出:true

样例2

输入:[0,8,9,11,12]

输出:true

解法

  • 对数组排序;
  • 计算出 0 的个数 zeroCount
  • 从第一个不是 0 的数字开始遍历,与后一个数字比较,如果相等,直接返回 false;否则累计 gap
  • 判断 zeroCount 是否大于等于 gap
...

阅读全文...

java算法-翻转单词顺序


题目描述

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。

为简单起见,标点符号和普通字母一样处理。

例如输入字符串 "I am a student.",则输出 "student. a am I"

样例

输入:"I am a student."

输出:"student. a am I"

解法

先对字符串按空格切割成数组,再逆序数组后,最后将元素拼接并返回。

/**
 * @author bingo
 * @since 2018/12/12
 */

class Solution {
    /**
     * 翻转单词
     *
     * @param s ...

阅读全文...

java算法-左旋转字符串


题目描述

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

请定义一个函数实现字符串左旋转操作的功能。

比如输入字符串 "abcdefg" 和数字 2,该函数将返回左旋转 2 位得到的结果 "cdefgab"

注意:

  • 数据保证 n 小于等于输入字符串的长度。

样例

输入:"abcdefg" , n=2

输出:"cdefgab"

解法

先翻转前 n 个字符,再翻转后面的字符,最后整体翻转。

/**
 * @author bingo
 * @since 2018/12/12
 */

class Solution {

    /**
     * 左旋转字符串
  ...

阅读全文...

java算法-和为S的两个数字


题目描述

输入一个数组和一个数字 s,在数组中查找两个数,使得它们的和正好是 s。

如果有多对数字的和等于s,输出任意一对即可。

你可以认为每组输入中都至少含有一组满足条件的输出。

样例

输入:[1,2,3,4] , sum=7

输出:[3,4]

解法

利用 set 记录元素即可。

import java.util.HashSet;
import java.util.Set;

/**
 * @author bingo
 * @since 2018/12/10
 */

class Solution {
    /**
     * 在数组中找出和为target的两个数
     *
...

阅读全文...

java算法-和为S的连续正数序列


题目描述

输入一个正数 s,打印出所有和为 s 的连续正数序列(至少含有两个数)。

例如输入 15,由于 1+2+3+4+5=4+5+6=7+8=15,所以结果打印出 3 个连续序列 1~5、4~6 和 7~8。

样例

输入:15

输出:[[1,2,3,4,5],[4,5,6],[7,8]]

解法

用两个指针 p, q 指示序列的最小值和最大值。如果序列和大于 s,则从序列中去掉较小的值,即 ++p;如果序列和小于 s,则序列向右再包含一个数字,即 ++q

当 p 超过 s 的一半时,停止。

import java.util.*;

/**
 * @author bingo
 * @...

阅读全文...

java算法-数组中唯一只出现一次的数字


题目描述

在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题:

  • 如果要求只使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?

解法

分别累加数组中每个元素的二进制中出现的数字,那么出现三次的数字,二进制位上最后累加的结果一定能被 3 整除。不能被 3 整除的位,就属于只出现一次的数字。

/**
 * @author bingo
 * @since 2018/12/10
 */

class Solution {
    /**
     * 找出数组中只出现一次的数字,其它数字都出现三次
...

阅读全文...

java算法-平衡二叉树


题目描述

输入一棵二叉树的根结点,判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

注意:

  • 规定空树也是一棵平衡二叉树。

样例

输入:二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示,
    5
   / \
  7  11
    /  \
   12   9

输出:true

解法

解法一

求每个节点左右孩子的深度,判断该节点是否平衡。

这种方法需要重复遍历节点多次,不推荐。

/**
 * @author bingo
 * @since 2018/12/10
 */

...

阅读全文...

java算法-数组中只出现一次的两个数字


题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

样例

输入:[1,2,3,3,4,4]

输出:[1,2]

解法

如果数组有一个数字出现一次,其它数字都出现两次。那么我们很容易通过异或 ^ 运算求出来。

而现在是有两个数字出现一次,那么我们考虑一下怎么将这两个数字隔开,之后我们对隔开的数组分别进行异或,不就求出来了?

我们先异或,求得的结果是两个不相同的数字异或的结果,结果一定不为 0。那么它的二进制表示中一定有 1。我们根据这个 1 在二进制中出现的位置。将数组划分,这样,两个只出现一次的数字就会...

阅读全文...

java算法-数组中数值和下标相等的元素


题目描述

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。

请编程实现一个函数找出数组中任意一个数值等于其下标的元素。

例如,在数组 [-3, -1, 1, 3, 5] 中,数字 3 和它的下标相等。

样例

输入:[-3, -1, 1, 3, 5]

输出:3

注意:如果不存在,则返回 -1。

解法

二分法查找。

  • 当前元素等于对应的下标,直接返回该下标;
  • 当前元素大于该下标,在左边查找;
  • 当前元素小于该下标,在右边查找。
/**
 * @author bingo
 * @since 2018/12/10
 */

class Solution {
    /**
     *...

阅读全文...