田忌赛马

齐使者如梁,孙膑以刑徒阴见,说齐使。齐使以为奇,窃载与之齐。齐将田忌善而客待之。忌数与齐诸公子驰逐重射。孙子见其马足不甚相远,马有上、中、下、辈。于是孙子谓田忌曰:“君弟重射,臣能令君胜。”田忌信然之,与王及诸公子逐射千金。及临质,“孙子曰:‘今以君之下驷与彼上驷,取君上驷与彼中驷,取君中驷与彼下驷。’既驰三辈毕,而田忌一不胜而再胜,卒得王千金。”

思考一个问题: 田忌和齐威王有相同数量的马,他们要在一场比赛中决出胜负,规则是:每匹马只能和对手比赛一次,胜者得一分,负者得零分,最后得分高的一方获胜。田忌和齐威王都是聪明的人,他们都会采用最优策略,田忌想要赢得齐威王的千金,那么田忌应该怎么安排马匹的顺序呢?

贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法。贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

阅读全文 »

一、问题背景

忙碌的夜晚,我喝着拿铁,坐在电脑旁,在指尖且飞快的敲着键盘的时候,键盘突然打不了字,window窗口栏变灰,应该是窗口失焦了,此时只需要动动鼠标,点击窗口恢复焦点,就可以继续愉悦的敲键盘了。

此起彼伏,窗口又失去了焦点,双手已然在键盘位只能再去移动鼠标..点击窗口…..

周而复始几次后,我终于忍不住了。。

二、问题确认

阅读全文 »

高精算法解决了什么问题?

在利用计算机作数值计算的时候,有时候会遇到这样的问题:

希望计算的数的位数可达几十位甚至几百位,虽然计算机的计算精度也算较高了,但因受到硬件的限制,往往达不到实际问题所要求的精度。

所以,往往在处理对超大精度计算时,都会通过巧妙的算法设计实现。

本算法使用字符串实现,防止数据溢出。

阅读全文 »

内联优化

在内部编译方法的时候,JVM根据内部逻辑分析是否热点代码,如果代码足够热,JVM会对方法内联优化,节省额外的方法调用开销(方法栈帧的生成、参数字段的压入、栈帧的弹出、指令执行地址跳转)。

方法内联是由JIT编译器在运行时完成的。既然涉及到编译,方法内联也是有一定的开销的,包括cpu时间和内存,所以这又是一个trade-off的老问题了。JIT根据以下信息决定是否进行内联:

  • 被调用方法是否足够hot。这个取决于该方法被调用的次数,次数阈值默认值为10,000。即运行时被调用次数超过10,000的方法,可以被认为是hot。
  • 被调用方法大小是否合适。对于过大的方法,JIT认为它是不适合做内联的。这个方法大小阈值由-XX:FreqInlineSize指定,不建议修改。即大于这个阈值size的方法,不考虑进行内联
  • 被调用方法运行时其实现是否可以唯一确定。显然,对于类方法、私有方法和final方法,JIT是可以唯一确定它们的具体实现代码的(这里对应字节码中的invokestatic和invokespecial);另一方面,对于public方法调用,它所指向的具体实现可能是自身、父类、子类的方法实现代码(多态),只有当JIT能唯一确定方法的具体实现时,才有可能完成内联(对应字节码中的invokevirtual和invokeinterface)

另外内联优化不仅仅消除了调用开销,被内联优化的方法会编译成native code(机器码)放在JVM Code Cache nmethod中,使多次调用方法时性能提升。

阅读全文 »

一、权限认证 SpringSecurity

1.引入安全框架SpringSecurity

Spring Security是一个能够为基于Spring的企业应用系统提供声明式的安全访问控制解决方案的安全框架。它提供了一组可以在Spring应用上下文中配置的Bean,充分利用了Spring IoC,DI(控制反转Inversion
of Control ,DI:Dependency Injection 依赖注入)和AOP(面向切面编程)功能,为应用系统提供声明式的安全访问控制功能,减少了为企业系统安全控制编写大量重复代码的工作。

2.Maven

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-security</artifactId>
</dependency>
阅读全文 »

Docker

Docker 是一个开源的应用容器引擎,基于Go 语言并遵从 Apache2.0 协议开源。

Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化。

容器是完全使用沙箱机制,相互之间不会有任何接口(类似 iPhone 的 app),更重要的是容器性能开销极低。

Docker的应用场景

阅读全文 »

问题:


给定一个以字符串表示的非负整数  num,移除这个数中的 k 位数字,使得剩下的数字最小。

注意:

num 的长度小于 10002 且  ≥ k。
num 不会包含任何前导零。

示例 1 :

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :

输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :

输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字,剩余为空就是 0。

一个思路是:

从左到右遍历
对于每一个遍历到的元素,我们决定是丢弃还是保留
问题的关键是:我们怎么知道,一个元素是应该保留还是丢弃呢?

这里有一个前置知识:对于两个数 123a456 和 123b456,如果 a > b, 那么数字 123a456 大于 数字 123b456,否则数字 123a456 小于等于数字 123b456。也就说,两个相同位数的数字大小关系取决于第一个不同的数的大小。

阅读全文 »
0%