Skip to content

使用java实现基本的算法,探究jvm,多线程,java特性

Notifications You must be signed in to change notification settings

jiujiujiujiujiuaia/Algorithm-java

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

59 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Algorithm-java

  • 使用java实现经典算法
  • 探究jvm相关内容

JVM

参数类型

参数类型有标准类型,非标准类型

  • 标准类型就是一些类似于java -help, java -version,这里就不多数说了.
  • 非标准类型一种是以-X开头,例如-Xint,-Xcomp等等
  • 非标准类型另一种是以-XX开头
    • -XX:[+-][name],加号表示使用这个参数,减号表示不使用这个参数
    • -XX:[key]=[value],eg:-XX:MaxGcPauseMillis=500
    • Xms,Xmx这两个常见的其实可以写成 -XX:InitialHeapSize=?,-XX:MaxHeapSize=?

bin目录下的工具

通过jdk自带的一些工具,我们可以做对jvm进程的初始参数以及参数值等等进行一个查看

  • (查看运行的jvm及其唯一id)jps -l就可以查看当前服务器进程及其id
  • (查看jvm运行时参数)jinfo -flag +参数名称 + id,就可以获得-XX参数的值或者使用过没有。例如jinfo -flag MaxHeapSize 11944 就可以获得最大堆内存的值

算法

  • 滑动窗口
  • 双指针
  • 动态规划
  • 二叉树相关

链表问题

单链表(链表为空和只有一个节点的情况)

  • 插入节点是需要找到插入位置的前一个指针和后一个指针
  • 删除特别重要,删除某个节点时,要找到这个节点的前一个节点,然后前一个节点连接到当前节点的后一个节点

动态规划

一开始对于动态规划的初印象就是,这个算法太神奇了把,竟然可以在有多种选择的情况下,找到最优的情况(比如数塔问题,怎么就可以不在暴力的情况下开天眼 找到正确的路线),后来就慢慢的有了思路,首先,记忆化的存储能够帮助你减少重复计算,其次,我一般都是自底向上的思考,把一个问题拆分 成小问题,然后直到初始状态,小问题是知道结果的,把小问题的结果保存下来,大问题就迎刃而解了,最终,也发现了一些问题 大多数情况下,dp问题好像用暴力去求解的情况是 2^n*数据大小,也就是说选或者不选这个物品,并且,有时候自顶向下更方便。

  • 累积类型
    • (一维度dp问题) 数塔,爬楼梯,偷房子等等,在一个约束条件下满足最大最小化问题(eg:某规则下最大值是多少)
    • (二维度dp问题) 背包等问题,在两个约束条件下满足最大最小化问题(eg:不超过容量的前提下最大的价值是多少)
  • 次序类型
    • LIS(最长子序列字串等等)

背包问题

  • 简单背包

最普遍的做法是对于每一个物品,比较选择这个物品和前面物品价值总和不选择这个物品价值总和哪个更大 换句话说,每一步的状态,只和当前物品以及上一个物品有关->那么我们就可以把空间从[n个物品][质量w]的数组 优化成为[2][w]。 还可以利用一维数组进行进一步的优化,只有质量大于数组下标才进行比较大小,数组下标小于质量的话,则保持之前的结果

  • 完全背包

相比较前者,每一个物品不限量的拿取。最普遍的做法是不超过容量的前提下算出最多,能拿几个本次物品 ,然后循环次数,只拿一个,拿两个,拿三个...这样比较看拿几个价值最大,间接的转换成了简单背包问题(相当于添加了重复的物品) 优化的策略非常巧妙,利用二进制的思想,不从拿一个遍历到拿n个,从1,2,4...左移一位的方式遍历,这样的话拿某个物品6次,原来需要遍历6次,现在只需要知道拿两次和拿四次的结果,只遍历了三次

数组相关

双指针

algorithm.leetcode 283 26 27 80 这几题思路类似,遍历数组一次,双指针,一个指针负责遍历,一个指针k负责表示[0,k]区间内的元素都是符合题目要求的。 当判断不等于目标值时,直接交换,否则k指针不进行++,k指针停留在为目标值得索引上面,等待下一次交换。

双指针相关(填满方格水问题)algorithm.leetcode 11

就像是木桶原理一样,木桶能装多少水取决于最短的那块木板,那么对于一个数组,如果左指针小于右指针,那么该数组的子数组以左指针开头的矩阵都会比这个小,因此只需要把左指针++,再找看有没有 比这个矩阵大的(至于证明的话,比如[1,2,3,4,5]这样一个数组,以1为左基准的话,除了5以外的右基准无论比1大或者小组成的矩阵都会比之前的矩阵小,所以就不用管以1为左基准)

双指针之滑动窗口解法 leetcode209 algorithm.leetcode 76

因为题目要求是连续子数组,因此维护一个滑动窗口来解决问题 另一道也是用滑动窗口得思想解题,同时可以提炼出这类题目得解法,右指针不断右移是扩大窗口范围(也是因为没有达到条件所以才扩大),一旦达到了 要求,左指针缩小范围来寻找最大最小值

计数索引算法

适用于小整数键值的算法,例如老师分组之类的问题。先计算频率,然后根据频率算出前n个组总人数(那么n+1组的第一个人就是下一个了),这样就 完成了排序。

低位优先排序(LSD)

适用于固定长度的字符串排序,例如车牌号,ip等等排序。之所以称作低位,是因为其从右往左,依次使用计算索引算法排序。

字符相关数组问题

一定要和面试官沟通好,确认题目的字符集,结果如果多个,返回的顺序是怎样的,如果找不到结果,应该返回什么

查找专题

hashmap和set的基本使用 algorithm.leetcode 349,350

hashmap根据值排序输出 algorithm.leetcode 451

这道题挺喜欢的,一直都不知道如何按照hashmap值排序输出,经过这道题才知道可以用桶排序的特殊情况进行操作

有趣的二进制

  • 小鼠毒药

有100瓶药,有一瓶是毒药,最多几次小老鼠可以试出来哪一瓶是毒药? 这个问题借鉴的二进制的思想,每每看到这种题目都会感叹“简单”的二进制的强大之处,现在讲讲的思路。 100瓶药最多用7位二进制表示,比如100就是01100100,那么我只需要七只小鼠,第一只小鼠只喝第一位为1的,第二只小鼠只喝第二位为1的,到时候如果1,3,5小鼠死掉了 不就说明了毒药的编号是1010100?这背后朴素的思想就是二进制可以用很少的位数表示很大的数字,并且她只有两种状态,特别适合解决这类问题

  • 监狱枪毙犯人问题

有100个犯人要枪毙,第一排,报道奇数就留下,偶数就枪毙。第二排,报道奇数就留下,报道偶数就枪毙。请问你想不死,要站再第几个? 这个问题就利用了二进制表示奇数偶数的特性,奇数最后一位为1,偶数最后一位数为0。第一轮报数死的都是最后一位为1的,也就是1,3,5,7。。第二轮把2,4,6,8捉过来报数 每个编号只表示之前的一半了,在二进制中,除以2,就是右移一位,舍弃低位,因为100最多用7位表示,也就说最多七轮枪决还有一个人剩下来,那个人就是第64号。

About

使用java实现基本的算法,探究jvm,多线程,java特性

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages