分类目录归档:Java

java算法-二叉树的深度


题目描述

输入一棵二叉树的根结点,求该树的深度。

从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

样例

输入:二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示:
    8
   / \
  12  2
     / \
    6   4

输出:3

解法

递归即可。

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

/**
 * Definition for a binary tree node.
 * public clas...

阅读全文...

java算法-两个链表的第一个公共结点


题目描述

输入两个链表,找出它们的第一个公共结点。

样例

给出两个链表如下所示:
A:        a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

输出第一个公共节点c1

解法

先遍历两链表,求出两链表的长度,再求长度差 |n1 - n2|

较长的链表先走 |n1 - n2| 步,之后两链表再同时走,首次相遇时的节点即为两链表的第一个公共节点。

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

阅读全文...

java算法-数字在排序数组中出现的次数


题目描述

统计一个数字在排序数组中出现的次数。

例如输入排序数组 [1, 2, 3, 3, 3, 3, 4, 5] 和数字 3,由于 3 在这个数组中出现了 4 次,因此输出 4。

样例

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

输出:4

解法

找出第一个 k 和最后一个 k 出现的位置。

找第一个 k 时,利用二分法,如果 nums[m] == k,判断它的前一个位置是不是也是 k,如果不是,说明这是第一个 k,直接返回。如果是,那么递归在左边查找第一个 k。

找最后一个 k 也同理。

/**
 * @author bingo
 * @since 2018/1...

阅读全文...

java算法-0到n-1中缺失的数字


题目描述

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0n-1 之内。

在范围 0n-1n 个数字中有且只有一个数字不在该数组中,请找出这个数字。

样例

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

输出:3

解法

找出第一个与下标不对应的数字即可。

特殊情况:

  • 下标都对应,那么应该返回 最后一个数+1
  • 缺失的数字是第一个,那么返回 0。
/**
 * @author bingo
 * @since 2018/12/8
 */

class Solution {
    /**
     * 获取0~n-1缺失的数字
     *
     * ...

阅读全文...

java算法-礼物的最大价值


题目描述

在一个 m×n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。

你可以从棋盘的左上角开始拿格子里的礼物,并每次向左或者向下移动一格直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物,请计算你最多能拿到多少价值的礼物?

解法

写出递推式,res 表示获得的最大礼物。

res[i][j] = Math.max(res[i - 1][j], res[i][j - 1]) + grid[i][j];
/**
 * @author bingo
 * @since 2018/12/8
 */

class Solution {
    /**
     * 获取礼...

阅读全文...

java算法-最长不含重复字符的子字符串


题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

假设字符串中只包含从 az的字符。

解法

动态规划。

res[i] 表示以 s[i] 字符结尾的最长不重复字符串的长度。判断 s[i]

  • s[i] 在前面没出现过,那么 res[i] = res[i - 1] + 1
  • s[i] 在前面有出现过,判断它上一次出现的位置 indexi 的距离 dres[i - 1] 的大小关系:
    • d <= res[i - 1],说明它被包含在 res[i - 1] 构成的子串中,那么 res[i] = d
    • d > re...

阅读全文...

java算法-把数组排成最小的数


题目描述

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

例如输入数组 [3, 32, 321],则打印出这3个数字能排成的最小数字321323

解法

import java.util.Arrays;

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

class Solution {

    /**
     * 打印数组元素组成的最小的数字
     *
     * @param nums 数组
     * @return 最小的数字
     */
    public String p...

阅读全文...

java算法-把数字翻译成字符串


题目描述

给定一个数字,我们按照如下规则把它翻译为字符串:

0 翻译成 ”a”,1 翻译成 ”b”,……,11 翻译成 ”l”,……,25 翻译成 ”z”。

一个数字可能有多个翻译。例如 12258 有 5 种不同的翻译,它们分别是 ”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

解法

先写入递推式,res 表示共有多少种翻译方法。看最后一个字符,判断它与前一个字符能否构成有效翻译,计算 res[i]:

  • 能,那么 res[i] = res[i - 1] + res[i - 2]
  • 不能,那么 res[i...

阅读全文...

java算法-连续子数组的最大和


题目描述

输入一个非空整型数组,数组里的数可能为正,也可能为负。 数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)

解法

动态规划法。

res[i] 表示以第 i 个数字结尾的子数组的最大和,那么求出 max(res[i]) 即可。

  • res[i] = array[i], if res[i - 1] < 0
  • res[i] = res[i - 1] + array[i], if res[i - 1] >= 0
/**
 * @author bingo
 * @since 2018/12/7
 */

public class S...

阅读全文...

java算法-数字序列中某一位的数字


题目描述

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。

在这个序列中,第 5 位(从 0 开始计数)是 5,第 13 位是 1,第 19 位是 4,等等。

请写一个函数求任意位对应的数字。

解法

举个栗子,求序列第 1001 位。

序列的前 10 位是 0~9, 这 10 个只有一位的数字。显然第 1001 位在这 10 个数字之后,因此这 10 个数字可以直接跳过。再从后面序列中找第 991(991=1001-10) 位的数字。接下来有 90 个两位数,共 180 位,由于 991>180,所以继续跳过。从 881 找...最后可以找到对...

阅读全文...