设计模式谈
设计模式谈
1、单例模式
**定义：**确保某一个类只有一个实例，而且自行实例化并向整个系统提供这个实例。【是线程安全的】
使用场景：
1、要求生成唯一序列号的环境。
2、在整个项目中需要一个共享访问点或共享数据。例如一个 Web 页面上的计数器，可以不用把每次刷新都记录到数据库中，使用单例模式保持计数器的值，并确保是线程安全的。
3、创建一个对象需要的资源过多。如要访问IO和数据库资源。
4、需要定义大量的静态常量和静态方法。（如工具类）
2、工厂模式
**定义：**定义一个用以创建对象的接口，让子类决定实例化哪一个类。
**使用场景：**jdbc连接数据库、硬件访问、降低对象的产生和销毁。
3、抽象工厂模式
**定义：**为创建一组相关或相互依赖的对象提供一个接口，而且无需指定他们的具体类。
使用场景：
1、一个对象族（或是一组没有任何关系的对象）有着相同的约束。
2、涉及到不同的操作系统。
4、模板方法模式
**定义：**定义一个操作中算法的框架，而将一些步骤延迟到子类中。使得子类可以不改变一个算法的框架即可重定义算法的某个具体步骤。
使用场景：
1、多个子类有公共的方 ...
让字符串成为回文串的最少插入次数
让字符串成为回文串的最少插入次数
问题陈述
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
示例
123输入：s = "mbadm"输出：2解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
思路分析
回文问题一般都是从字符串的中间向两端扩散，构造回文串也是类似的。
我们定义一个二维的dp数组，dp[i][j]的定义如下：对字符串s[i..j]，最少需要进行dp[i][j]次插入才能变成回文串。
我们想求整个s的最少插入次数，根据这个定义，也就是想求dp[0][n-1]的大小（n为s的长度）。
同时，base case 也很容易想到，当i == j时dp[i][j] = 0，因为当i == j时s[i..j]就是一个字符，本身就是回文串，所以不需要进行任何插入操作。
状态转移方程
如果我们现在想计算dp[i][j]的值，而且假设我们已经计算出了子问题dp[i+1][j-1]的值了，你能不能想办法推出dp[i][j]的值呢？
既然 ...
被围绕的区域
被围绕的区域
问题陈述
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X
思路分析
由题，题目中说被包围的区间不会存在于边界上，所以我们会想到边界上的 O 要特殊处理，只要把边界上的 O 特殊处理了，那么剩下的 O替换成 X 就可以了。问题转化为，如何寻找和边界联通的 O，我们需要考虑如下情况。
1234X X X XX O O XX X O XX O O X
这时候的 O 是不做替换的。因为和边界是连通的。为了记录这种状态，我们把这种情况下的 O 换成 # 作为占位符，待搜索结束之后，遇到 O 替换为 X（和边界不连通的 O）；遇到 #，替换回 O(和边界连通的 O)。
代码实现
1234567891011121314151617181920212223242526272829303132333435363738public ...
表示数值的字符串
表示数值的字符串
问题陈述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、“0123"都表示数值，但"12e”、“1a3.14”、“1.2.3”、“±5”、"-1E-16"及"12e+5.4"都不是。
解题思路
**常规思路：**根据条件判断可能出现的情况，最终返回结果。
**进阶解法：**自动状态机。
12345678910111213141516171819202122232425class Solution{ public isnumber(String s){ if(s==null||s.length()==0) return false; boolean isDigit=false,isDot=false,is_eE=false; char[] ch=s.trim().toCharArray();//删去字符串前后空格转换 ...
荷兰三色旗问题
荷兰三色旗问题
问题陈述
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
算法实现
12345678910111213141516171819202122232425/**设置三个指针，分别指向首尾和当前位，遍历数组，如果为2则交换到尾部，为0则交换到首部。**/class Solution{ public void sortColor(int[] nums){ int p0=0,p2=nums.length-1,cur=0; int temp; while(cur<=p2){ if(nums[cur]==0){ temp=nums[p0]; nums[p0++]=nums[cur]; nums[cur++]=t ...
航班预订统计
航班预订统计
问题陈述
这里有 n 个航班，它们分别从 1 到 n 进行编号。
我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。
请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。
示例：
12输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5输出：[10,55,45,25,25]
思路分析
类似公交车上下车
记录每个位置上车多少人、下车多少人，上车人数和下车人数的差就是当前车站人数变化，这些人到站后下一站则应减少这些人（注意：坐到终点的人，不需要被减少）
把每站之前的上车人数累加则可以得出当前车上人数
代码实现
12345678910111213141516public class FightBooking { public int[] corpfightBooking(int[][] bookings,int n){ int[] counte ...
股票买卖Ⅲ
股票买卖Ⅲ
问题陈述
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
123456示例 1:输入: [3,3,5,0,0,3,1,4]输出: 6解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
思路实现
1234567891011121314151617181920212223242526272829303132//只能进行两次交易，求最大利润。private static int buySockets3(int[] prices){ if(prices==null || prices.length==0) return 0; int len= prices. ...
组合总和Ⅰ
组合总和Ⅰ
问题陈述
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
123456输入：candidates = [2,3,6,7], target = 7,所求解集为：[ [7], [2,2,3]]
思路实现
12345678910111213141516171819202122class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> combinations=new ArrayList<>(); List<Integer> res=new ArrayList<>(); backtrack(combinati ...
组合
组合
问题陈述
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
12345678910输入: n = 4, k = 2输出:[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]
思路实现
同样可以用一个决策树进行回溯求解。
1234567891011121314151617181920class Solution { public List<List<Integer>> combine(int n, int k) { List<List<Integer>> combinations=new ArrayList<>(); List<Integer> res=new ArrayList<>(); backtrack(combinations,res,n,k,1);//n的遍历范围为1~n return combinations; } ...
移动零
移动零
问题陈述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
12输入: [0,1,0,3,12]输出: [1,3,12,0,0]
代码实现
12345678910111213class Solution{ public void moveZeros(int[] nums){ int index=0; for(int num:nums){//将所有非零元素移到队首 if(num!=0){ nums[index++]=num; } } while(index<nums.length){//剩下的就是0啦 nums[index++]=0; } }}