LeetCode之买卖股票的最佳时机
买卖股票的最佳时机1.题目给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
示例 1:
1234输入:[7,1,5,3,6,4]输出:5解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
示例 2:
123输入:prices = [7,6,4,3,1]输出:0解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
2.分析方法1:动态规划: 创建一个dp数组记录状态 dp 0 为该天持有股票手上的现金数额 ,dp 1 为该天不持有股票手上的现金数额,注意起始状态 dp 0为 -当天的股价,dp 1 ...
LeetCode之两数之和
两数之和1.题目给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
2.分析可以看出这题基本思路就是遍历nums的每一个元素num,然后寻找该数组中是否存在target-num的值。
3.代码1234567891011121314151617181920212223242526272829class Solution { public int[] twoSum(int[] nums, int target) { int[] ans = new int[2]; int len = nums.length; for(int i=0;i<len;i++){ int num = nums[i]; int temp = target - num; ...
LeetCode之合并两个有序链表
合并两个有序链表1.题目将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
2.分析使用递归算法,一直判断把问题交给下个子问题,直到链表到最后递归结束。
3.代码123456789101112131415class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1==null){ return l2; }else if(l2==null){ return l1; }else if(l1.val<l2.val){ l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoL ...
LeetCode之汉明距离
汉明距离1.题目两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y,计算它们之间的汉明距离。
注意:0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2
解释:1 (0 0 0 1)4 (0 1 0 0) ↑ ↑
上面的箭头指出了对应二进制位不同的位置。
2.分析
先x异或y将相同二进制位变为0,不相同的二进制位变为1
再用Integer内置bitCount函数计算有多少个1
3.代码12345class Solution { public int hammingDistance(int x, int y) { return Integer.bitCount(x^y); }}
LeetCode_多数元素
多数元素1.题目给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
示例 1:
12输入:[3,2,3]输出:3
示例 2:
12输入:[2,2,1,1,1,2,2]输出:2
2.个人分析
方法1:可以开map记录然后遍历map统计得出答案
方法2:先排序再遍历数组边遍历边统计
官方方法:排序返回n/2 下标的值
官方方法2:摩尔投票法
3.代码1234567891011121314151617181920class Solution { public int majorityElement(int[] nums) { int len = nums.length; Arrays.sort(nums); int temp=1; int ans=nums[0]; for (int i = 1; i < len; i++) { if(nums ...
桥接模式
桥接模式1.定义桥接模式是将抽象部分与它的实现部分分离,使它们都可以独立地变化。它是一种对象结构型模式,又称为柄体(Handle and Body)模式或接口(interface)模式。它是用组合关系代替继承关系来实现,从而降低了抽象和实现这两个可变维度的耦合度。
2.具体实现2.1代码123456789101112131415161718192021222324252627282930313233343536373839package 设计模式;public class BridgePattern { public static void main(String[] args) { Implementor imple = new ConcreteImplementorA(); Abstraction abs = new RefinedAbstraction(imple); abs.Operation(); }}//实现化角色interface Implementor { pu ...
策略模式
策略模式1.定义在策略模式(Strategy Pattern)中,一个类的行为或其算法可以在运行时更改。这种类型的设计模式属于行为型模式。
2.具体实现2.1代码123456789101112131415161718192021222324252627282930313233343536373839404142package 设计模式;public class StrategyPattern { public static void main(String[] args) { Context c = new Context(); c.setStrategy(new ConcreteStrategyA()); c.strategyMethod(); c.setStrategy(new ConcreteStrategyB()); c.strategyMethod(); }}//抽象策略类interface Strategy { public void s ...
外观模式
外观模式1.定义外观模式(Facade Pattern)隐藏系统的复杂性,并向客户端提供了一个客户端可以访问系统的接口。这种类型的设计模式属于结构型模式,它向现有的系统添加一个接口,来隐藏系统的复杂性。
2.具体实现2.1代码1234567891011121314151617181920212223242526272829303132333435363738package 设计模式;public class FacadePattern { public static void main(String[] args) { Facade facade = new Facade(); facade.method(); }}//外观类 集成了多个子系统类class Facade { private SubSystem01 obj1 = new SubSystem01(); private SubSystem02 obj2 = new SubSystem02(); private SubS ...
享元模式
享元模式1.定义它使用共享物件,用来尽可能减少内存使用量以及分享资讯给尽可能多的相似物件;它适合用于只是因重复而导致使用无法令人接受的大量内存的大量物件。主要用于减少创建对象的数量,以减少内存占用和提高性能。这种类型的设计模式属于结构型模式,它提供了减少对象数量从而改善应用所需的对象结构的方式。(例如各种池技术就是使用的享元模式)
2.具体实现2.1代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960package 设计模式;public class FlyweightPattern { public static void main(String[] args) { FlyweightFactory factory = new FlyweightFactory(); Flyweight f01 = factory.getFlyweight("a&qu ...
代理模式
代理模式1.定义为其他对象提供一种代理以控制对这个对象的访问。在某些情况下,一个对象不适合或者不能直接引用另一个对象,而代理对象可以在客户端和目标对象之间起到中介的作用。
2.具体实现2.1代码
静态代理:静态代理中,我们对目标对象的每个方法的增强都是手动完成的,十分不灵活;从 JVM 层面来说, 静态代理在编译时就将接口、实现类、代理类这些都变成了一个个实际的 class 文件。
1234567891011121314151617181920212223242526272829303132333435package 设计模式;public class ProxyPattern01 { public static void main(String[] args) { IphoneProxy iphoneProxy = new IphoneProxy(new IphoneFactoryImpl()); iphoneProxy.create(); }}//服务类接口interface IphoneFactory ...