LeetCode之爬楼梯
爬楼梯1.题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
2.分析经典的动态规划题目
我们用 f(x)f(x) 表示爬到第 xx 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出式子：f(x)=f(x−1)+f(x−2)
3.代码1234567891011121314151617class Solution { public int climbStairs(int n) { if(n<=1){ return n; } int ans=2; int pre1=1; int pre2=2; for (int i = 3; i <= n; i++) { ans=pre1+pre2; pre1=pre2; pre2=ans; } ...
LeetCode之移动零
移动零1.题目给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
12输入: [0,1,0,3,12]输出: [1,3,12,0,0]
2.分析先遍历数组，再遍历的过程中，若该数为0则用count记录次数，若不为0，则将该数放在 i - count 位上并该位变为0，直到遍历完成。
3.代码1234567891011121314151617class Solution { public void moveZeroes(int[] nums) { int len = nums.length,count=0; for (int i = 0; i < len; i++) { if(nums[i]==0){ count++; continue; }else if(i==0||count==0){ continue; ...
LeetCode之有效的括号
有效的括号1.题目给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
2.分析这题括号的匹配刚好契合数据结构栈先进后出的特性。。所以就当输入为左括号时就入栈，当为右括号时就弹出栈顶元素进行匹配，匹配成功则继续，失败则直接返回false，这里有两个需要注意的地方就是当字符串长度为1时就肯定没效直接返回false，还有当循环结束了栈里面还有字符那说明也没用相应的匹配也返回false;
3.代码1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { public boolean isValid(String s) { Stack<Character> stack = ...
LeetCode之找到所有数组中消失的数字
找到所有数组中消失的数字1.题目给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为*O(n)*的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
2.分析这题要求找出1到n数租缺少了哪一个，就开一个大小为n的数组，然后遍历nums把每个元素以坐标存在新开的数组中，最后统计看那个坐标的元素为0则就少哪个数。
3.代码12345678910111213141516class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { ArrayList<Integer> ans = new ArrayList<>(); int len = nums.length; int[] count = new int[len+1]; ...
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 ...
