- 博客(20)
- 收藏
- 关注
RSS订阅原创 第九届蓝桥杯国赛JavaB组第二题：最大乘积（全排列）
对于1~9的九个数字，我们往中间插入乘号，它们的乘积也可能是1~9组成的一个排列，如：132 * 965874 = 127495368135627 * 948 = 128574396612 * 954783 = 584327196 那么求它们的乘积最大是多少。 思路：直接对1~9执行全排列，每次拍好后尝试往中间插入乘号并计算它们的积，如果积只包含1~9且不存在重复数字，则与之前记录的最大值比较。p...
2018-05-29 14:43:14
1132
原创 优先队列的基本操作实现与应用（Java实现）
优先队列实质上是一颗完全二叉树，其所有的父节点都比子节点大（或小），也被称为大根堆（或小根堆），其堆顶的元素一定是这组元素的最大（小）值。 和其他数据结构一样，堆有构造、插入、删除、查找等操作。下面举例用了一个int类型的arr数组存放元素，top记录堆底元素的下标。构造一个堆：由于堆实质是一颗完全二叉树，因此可以用数组方便地表示。构造一个堆时，有两种方法，一种是将元素依次插入，每次插入时都对此做...
2018-04-02 13:41:59
934
原创 二叉树递归、非递归遍历（Java实现）
遍历是对一颗二叉树最基本的操作，有前序遍历、中序遍历、后序遍历和层次遍历四种，都可以通过递归或者数据结构实现。假定叶子结构如下：static class leaf{ int value; leaf left,right; leaf(int i){ this.value = i; } public String toString() { ...
2018-03-30 19:12:33
328
原创 求两链表是否相交（Java实现）
求两个链表相交的思路与求环比较相似，下面我们来看下几种常见的思路，假定节点结构为：static class node{ Object value; node next; node(Object o){ this.value = o; }}头结点也已经声明好了：static node head1;static node head2; 思路 1：逐个尝试，...
2018-03-29 13:28:30
1127
原创 求一个链表是否有环、环的长度、环的入口（Java实现）
求一个链表是否有环是比较常问的面试题，下面我们来看下三种常见的思路，假定节点结构为：static class node{ Object value; node next; node(Object o){ this.value = o; }}头结点也已经声明好了：static node head; 思路1：用两个指针指向头结点，一个指针每次向前走一步，然...
2018-03-28 23:04:51
1502
原创 滑雪问题（记忆化搜索）
题目：Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11...
2018-03-28 17:41:50
3194
原创 反转链表（Java实现）
反转链表是最基础的数据结构练习题，主要是注意一下边界处理和指针方向，下面提供了两种常用思路。假定节点结构为：static class node{ Object value; node next; node(Object o){ this.value = o; }}头结点也已经声明好了：static node head;思路1：头插法。public st...
2018-03-28 13:24:31
233
原创 求数对的排列（回溯法）
题目：今有7对数字，两个1，两个2，两个3，…两个7，把它们排成一行。 要求两个1间有1个其它数字，两个2间有2个其它数字，以此类推，两个7之间有7个其它数字。如下就是一个符合要求的排列： 17126425374635求出符合该要求的所有数字对排列 思路：回溯法的典型应用，对所有的数字对进行全排列，如果填充数字时不符合条件的话直接回溯即可。代码如下：public class Main { ...
2018-03-26 22:02:27
377
原创 求上楼梯的方案总数（递推）
题目：有一个n级的楼梯，每次可以迈一步或者迈两步，那么上这个楼梯有多少种不同的方法？如2级的楼梯，可以迈两次一步，也可以迈一次两步，共有两种方法。 思路1：很容易就想到使用递归去求解。边界条件为楼梯1级时，共有一种方法，楼梯2级时，共有两种方法。publicstaticlong dfs(longl) { if(l==1) return 1; if(l==2) ...
2018-03-26 14:45:03
1138
原创 不用临时变量交换两个数（离散、位运算）
题目：不用临时变量交换两个数的值。思路1：先用其中一个变量存放它们的积，积除以另一个数即得原来的数。a = a * b;b = a / b;a = a / b;思路2：乘法可能会导致溢出，所以可以改用加法或减法，因为Java的整型采用补码，加减法即使溢出也不会导致被截掉，最后结果依然正确。a = a + b;b = a – b;a = a – b;思路3：如果熟悉位运算的话可以直接用^运算来代替，...
2018-03-25 22:08:59
172
原创 Java中的浅拷贝与深拷贝
Java中的对象都有一个方法叫clone（），是从Object类中继承而来的，它的作用是复制一个对象并返回，除了在堆中的地址不一样以外，对象里的实例变量、方法都与原对象完全一致。调用该方法前必须先重写clone（），而重写则需要先实现Cloneable接口，直接重写会抛出CloneNotSupportedException异常。下面举个例子：class person implements Cl...
2018-03-25 20:48:51
142
原创 求大小为n的素数环（回溯法）
题目：将1~n的整数进行排列，使之两两相邻的数的和为素数，同时头尾相加也为素数，这样的排列成为素数环。输入一个n，请打印出所有的素数环。input：4output：2 1 4 3 2 3 4 1 3 2 1 4 3 4 1 2 思路：很经典的全排列算法，可以直接对1~n进行全排列，排列好后检查是否满足素数环的要求，但这样时间复杂度高达O（n！），我的电脑在当n=12时结果出的很慢了。这时可...
2018-03-25 17:15:29
451
原创 BigDecimal类型的应用
与BigInteger一样，当浮点数的长度过大导致double无法表示时，就要使用BigDecimal类型来表示。使用前需要导入java.math.BigDecimal包，支持各种常见的运算。方法 参数类型 返回类型BigDecimal int BigDecimalBigDecimal St...
2018-03-24 21:34:37
227
原创 BigInteger类型的应用
Java中最大的整型数据类型是long，可以表示2^63-1~-2^63，但有时需要表示更大的数，就要使用BigInteger类型。使用前首先要导入java.math.BigInteger包，BigInteger理论上支持无限位长度，内部通过一系列算法将一个大数拆分后进行保存，同时也支持各种常见的运算。方法 ...
2018-03-24 19:53:29
172
原创 愚人节的礼物（栈）
题目：四月一日快到了，Vayko想了个愚人的好办法——送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Vayko为了愚人，准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。用()表示一个盒子，B表示礼物，Vayko想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。例子：input：（（（））（（）（B）））output: 3思...
2018-03-24 16:28:56
437
原创 反转字符串（字符串处理）
比较简单的一题，而且可以通过多种方法解决。思路1：使用递归。边界条件即为字符串的长度为1。public static String reverse1(String s) { if(s==null||s.length()==0) return s; return s.length()==1?s:reverse1(s.substring(1))+s...
2018-03-24 16:10:06
893
原创 求序列中最大连续子序列之和（递推）
题目：先读入一个数n，然后读入n个数，求n个数中最大连续子序列之和思路：直接递推即可。import java.util.Scanner;public class Main { public static void main(String []args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int a[] =...
2018-03-24 15:31:24
582
原创 求一个数的素数对个数（枚举、筛素数法）
题目：给定一个数n，求它可以是多少对不同的素数对相加之和。思路1：直接枚举，找出从2到n/2的素数，然后判断n与该素数的差是否为素数。实现非常简单，代码如下：import java.util.Scanner;public class Main { public static void main(String []args) { Scanner in = new Scanner(System.in...
2018-03-24 14:51:33
974
1
原创 求n个数中前k大的数（排序）
这题两种思路，一种很直接的思路就快排，另一种是堆，我们来看下这两种算法的区别。第一种是快排，直接用快排将n个数排成有序，然后将前k大的数输出。平均时间复杂度为O（nlogn），空间复杂度为O（logn）。代码献上：public static void quickSort(int arr[],int k) { Arrays.sort(arr); for(int...
2018-03-23 21:46:17
9242
原创 统计一个字符串中出现次数最多的字符（HashMap）
我的思路是用一个HashMap来统计字符中每个字符出现的次数，并记录下出现次数最多的字符。编程实现是先将字符串转化成一个字符数组，然后遍历字符数组，以字符为键、出现次数为值将其插入HashMap中，每次插入先默认它是首次出现，put的同时用一个int的包装类来接受HashMap的返回值（用put（）插入重复键时，HashMap会把原来的值返回。这里必须用一个包装类来接受，因为这个返...
2018-03-23 21:23:24
6271
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人