笔试题-牛羊吃草问题

2022-6-22 diaba 笔试题

package com.jiucaiyuan.net.question; /** * 牛羊吃草问题:有先吃和有后吃,看谁刚好吃完所有草 * 吃草规则, 吃的时候只能吃4^m次幂份,看谁会胜利 * * @Author jiucaiyuan 2022/6/22 23:11 * @mail services@jiucaiyuan.net */ public class EatGrass { /** * 思路1:先手先吃,尝试所有情况,如果能胜利,就先手胜利,否则后手胜利,暴力尝试 * * @param n ...

阅读全文>>

评论(0) 浏览(842)

笔试题-最少的袋子数装苹果

2022-6-22 diaba 笔试题

package com.jiucaiyuan.net.question; /** * 【问题】小虎去附近的商店买苹果,奸诈的商贩使用了捆绑交易,只提供6个每袋和8个每袋的包装, * 包装不可拆分。可是小虎只想购买恰好n个苹果,小虎想够买尽量少的袋数方便携带。如果不能购买 * 恰好n个苹果,小虎将不会购买,输入一个整数n,表示小虎想购买的苹果个数,返回最小使用多少 * 个袋子,如果无论如何都不能正好装下,返回-1. * 思路: * 思路1:输入n,直接用8类型的袋子看最多需要多少个,n/8,剩下的苹果是否能用6类型的袋子正 * 好装下,如果不行,8类型袋子减少一...

阅读全文>>

评论(0) 浏览(821)

递归DP-找零钱的方法数

2022-6-12 diaba 笔试题

package com.jiucaiyuan.net.question; /** * 找零钱的方法数 * 给定一个数组,表示总共有币种的面值,(不重复的正数数组) * 再给定一个金额数aim,问题是有多少种钱币的组合,可以正好满足指定金额(某一个金额的钱币张数不限) * * @Author jiucaiyuan 2022/6/12 14:31 * @mail services@jiucaiyuan.net */ public class ChangeMethod { /** * @param arr arr都是正数,没有重...

阅读全文>>

评论(0) 浏览(718)

递归DP-走step步后仍在一个区域的概率问题

2022-6-12 diaba 笔试题

package com.jiucaiyuan.net.question; /** * @Author jiucaiyuan 2022/6/5 23:00 * @mail services@jiucaiyuan.net */ public class BobWalkOnGrid { /** * 在N*M的区域范围内,Bob在(i,j)位置,走step步之后,仍然在区域内的点数 * * @param N * @param M * @param i * @param j * @...

阅读全文>>

评论(0) 浏览(729)

最大公约数

2022-6-12 diaba 算法

/** * 求m和n的最大公约数 * * @param m * @param n * @return */ public static long gcd(long m, long n) { return n == 0 ? m : gcd(n, m % n); }

阅读全文>>

评论(0) 浏览(781)

递归DP-中国象棋马跳到目标位置的走法

2022-6-5 diaba 笔试题

package com.jiucaiyuan.net.question; /** * 中国象棋 * * @Author jiucaiyuan 2022/6/5 17:43 * @mail services@jiucaiyuan.net */ public class ChineseChessHorseJump { /** * 象棋,马从(0,0)位置,跳step步到达(x,y)位置的方法数 * * @param x 目的地x轴坐标 * @param y 目的地y轴坐标 * @pa...

阅读全文>>

评论(0) 浏览(872)

递归DP-金币组合最少金币数

2022-6-5 diaba 笔试题

package com.jiucaiyuan.net.question; /** * @Author jiucaiyuan 2022/6/5 11:33 * @mail services@jiucaiyuan.net */ public class CoinAmount { /** * 暴力递归 * 给一个正数数组,每个数表示一枚硬币的面值,给定一个数值,从硬币中选择得到这个金额的最少硬币数 * 比如指定硬币有[1,4,7,2,4,3,5,1,3] * 指定金额10,那么最少硬币数是7+3,两枚硬币,返回2 ...

阅读全文>>

评论(0) 浏览(799)

递归DP-机器人到达目的地方法数

2022-6-5 diaba 笔试题

package com.jiucaiyuan.net.question; /** * @Author jiucaiyuan 2022/6/5 10:34 * @mail services@jiucaiyuan.net */ public class Rabbit { /** * 给了一个固定值n,表示总共有多少个位置 * 开始机器人在s位置上,每次可以迈一步,想要到达e位置,总共要走k步,有多少种走法可以到达e位置 * 机器人可以往左走,也可以往右走 * * @param n 总共位置数 1 ...

阅读全文>>

评论(0) 浏览(807)

位运算-实现加、减、乘、除

2022-6-4 diaba 笔试题

package com.jiucaiyuan.net.question; /** * 问题:给定两个有符号32位整数a和b,不能使用算数运算符,实现加、减、乘、除运算 * 要求:如果给定a、b执行加减乘除运算结果就会导致数据的溢出,那么你实现的函数不必对此负责, * 除此之外,请保证计算过程不发生溢出 * <p> * 直到进位d为0时,最终的a就是a和b的和 * * @Author jiucaiyuan 2022/6/4 22:26 * @mail services@jiucaiyuan.net */ public class Ma...

阅读全文>>

评论(0) 浏览(754)

位运算-判断数是否是2的幂、4的幂

2022-6-3 diaba 笔试题

package com.jiucaiyuan.net.question; /** * <pre> * 判断一个32位正数,是不是2的幂、4的幂 * 2的幂,一个数的二进制只有一个1,一定是2的幂 * 方法1:依靠拿到这个数最右侧的1的方法,然后再和原 数进行比较,如果相等,是,否则不是 * 方法2:如果一个数x只有一个1,那么x-1,原来1变为0,后面所有0都变为1,那么 `x & (x-1) == 0` * 4的幂,一个数的二进制只有一个1,并且 `x & 0101010101 != 0` * </...

阅读全文>>

评论(0) 浏览(835)

位运算-不做比较判断得到两个数中的大数

2022-6-3 diaba 笔试题

package com.jiucaiyuan.net.question; /** * * 题目:给定两个有符号32位整数a和b,返回a和b较大的一个 * 要求:不用做任何比较判断 * * &(与)、|(或)、~(非)和 ^(异或) * * @Author jiucaiyuan 2022/6/3 23:13 * @mail services@jiucaiyuan.net */ public class GetMax { /** * 请保证参数n,不是1就是0的情况下 * 1 ——> 0 ...

阅读全文>>

评论(0) 浏览(824)

笔试题-田忌赛马

2022-5-13 diaba 笔试题

package com.jiucaiyuan.net.algrithm.audition; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; public class MrTianHorseRacing { /** * <pre> * 田忌赛马 * 两个数组没有重复元素,第一个数组固定按照从小道大出场比赛,数组较大的获胜 * 给出第二个...

阅读全文>>

评论(0) 浏览(845)

算法-二叉树遍历-morris遍历

2022-5-10 diaba 算法

package com.jiucaiyuan.net.question; import com.jiucaiyuan.net.algrithm.tree.Node; /** * 【Morris遍历】 * 一种遍历二叉树的方式,时间复杂度是O(N),额外空间复杂度是O(1) * 通过利用原树中大量空闲指针的方式,达到节省空间的目的 * 遍历过程中,更改了底层叶子结点指针,完成遍历后,恢复了指针指向 * * @Author jiucaiyuan 2022/5/10 22:45 * @mail services@jiucaiyuan.net */ pu...

阅读全文>>

评论(0) 浏览(892)

算法-多叉树-组织party最大快乐值

2022-5-7 diaba 算法

package com.jiucaiyuan.net.algrithm.tree; import java.util.List; /** * <pre> * 树形dp套路 * 树形dp套路使用前提: * 如果题目求解目标是S规则,则求解流程可以定成每一个节点为头节点的子树 * 在S规则下的每个答案,并且最终答案一定在其中 * 案例题 * 【题目】派对的最大快乐值 * 员工信息定义如下 * class Employee{ * public int happy; //这名员工带来的快乐值 * List<Employee>...

阅读全文>>

评论(0) 浏览(909)

算法-二叉树-最大距离

2022-5-6 diaba 算法

package com.jiucaiyuan.net.algrithm.tree; /** * 树形dp套路 * <p> * 树形dp套路使用前提: * 如果题目求解目标是S规则,则求解流程可以定成每一个节点为头节点的子树 * 在S规则下的每个答案,并且最终答案一定在其中 * <p> * 案例题 * 【题目】二叉树节点间的最大距离 * 从二叉树的节点a出发,可以向上或者向下走,但是沿途节点只能经过一次, * 到达节点b时路径上节点的个数叫做a到b的距离,那么二叉树任意两个节点 * 之间都有距离,求整棵树上的最大距离 ...

阅读全文>>

评论(0) 浏览(800)

算法-滑动窗口(滑动窗口中的最大值)

2022-5-6 diaba 算法

package com.jiucaiyuan.net.question; import java.util.LinkedList; /** * 滑动窗口结构及滑动窗口应用 * * @Author jiucaiyuan 2022/5/5 23:17 * @mail services@jiucaiyuan.net */ public class WindowMax { private int l; private int r; private int[] arr; // arr[ [l .. r) ] ...

阅读全文>>

评论(0) 浏览(825)

算法-Manacher算法(最长回文子串、回文半径)

2022-5-5 diaba 算法

package com.jiucaiyuan.net.question; /** * Manacher算法 * 解决问题:字符串str中,最长回文子串的长度如何求解? * 如何做到时间复杂度O(N)完成? * * @Author jiucaiyuan 2022/5/2 13:29 * @mail services@jiucaiyuan.net */ public class Manacher { /** * <pre> * <b>求输入字符s的最大回文子串(非子序列)</b> ...

阅读全文>>

评论(0) 浏览(780)

算法-数字字符转化为字母字符种数

2022-4-22 diaba 算法

package com.jiucaiyuan.net.question; /** * 【问题】规定1和A对应,2和B对应,3和C对应... * 那么一个数字字符串,比如"111",可以转化为"AAA","KA","AK" * 给定一个只有数字字符组成的字符串str,返回有多少种转化结果 * * @Author jiucaiyuan 2022/4/22 23:02 * @mail services@jiucaiyuan.net */ public class ConvertNum2Letters { public static int number...

阅读全文>>

评论(0) 浏览(771)

算法-不用额外空间逆序栈

2022-4-22 diaba 算法

package com.jiucaiyuan.net.question; import java.util.Stack; /** * 【问题】不使用额外空间逆序一个栈:给你一个栈,请你逆序这个栈, * 不能申请额外的数据结构,只能使用递归函数,如何实现? * 【思路】通过用递归,利用栈帧局部变量保存,未主动额外申请空间 * * @Author jiucaiyuan 2022/4/22 22:24 * @mail services@jiucaiyuan.net */ public class ReverseStackNoExtraSpace { ...

阅读全文>>

评论(0) 浏览(671)

算法-字符串的全排列

2022-4-21 diaba 算法

package com.jiucaiyuan.net.question; import java.util.ArrayList; import java.util.Comparator; import java.util.List; /** * 【问题】打印一个字符串的全排列列(如果再加一个附加条件:要求不出现重复排列) * 【思路】第一个位置可以选择其中任意一个字符,第二个位置可以选择剩下的n-1个任何一个字符,第三个位置可以选择n-2个任何一个字符,依次类推 * * @Author jiucaiyuan 2022/4/21 22:58 * @mail ...

阅读全文>>

评论(0) 浏览(652)

Powered by emlog 京ICP备15045175号-1 Copyright © 2022