贪心者，若不犯人，远甚奉献；奉献者，受困于感，舍大为小；
分治递归：递归是一种方法调用方式，深度调用，形式类似于栈的进出。分治的思想最简单的形式就是归并排序，同归讲一个问题拆分为多个问题来求解。分治和递归之所以有联系，是因为大多数场景下，分治的算法，都是同归递归调用来求解的。这样的问题往往也可以通过动态规划来求解
常见题型：
- 归并排序、求平方根、指数pow计算
- 恢复IP地址：25525511135（长度为4满足，遍历长度为255的长度3）
- 子串上的全排列(使用深度遍历，就是暴力nm)
贪心算法：贪心即每次都找最好的结果。宽泛而言，贪心算法并不是一个准确的算法，即他不能得到一个最优值，而只是尽可能得到一个级大值或极小值。类似于爬上算法、遗传算法等等，主要用于工程优化中，因为实际上而言，只要每一步都保证采用最好的方案，最终的方案往往并不差，会逐渐接近最优值。
贪心算法的准确值只能应用在部分场景下，或者说全盘扫描+记忆算法。
常见题型：
- 最大连续子数组
2 跳棋游戏，最快跳出棋盘 - 二维平面最多有多少个点在同一平面
4 求直方图最大面积-矩阵中矩形最大面积 - 字符串中的最小字符串
package com.nowcoder.leetcode.division;
import java.util.ArrayList;
import java.util.Arrays;
/**
* @description: 分治递归
* @author: zoutai
* @create: 2019/4/17
**/
public class Solution {
public static void main(String[] args) {
int n = 1000;
while (n >= 0) {
System.out.println(n);
if (new Solution().sqrt(n) != ((int) Math.sqrt(n))) {
System.out.println("false");
}
n--;
}
}
/**
* 和没有重复元素的 Permutation 一题相比，只加了两句话：
* 1.Arrays.sort(nums) // 排序这样所有重复的数
* 2.if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { continue; } // 跳过会造成重复的情况
*/
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<>();
//使用bool数组代替是否被访问过,节约查找时间
boolean[] visited = new boolean[num.length];
Arrays.sort(num);
dfs2(rst,visited,list,num);
return rst;
}
private void dfs2(ArrayList<ArrayList<Integer>> rst, boolean[] visited, ArrayList<Integer> list, int[] num) {
if(list.size()==num.length){
// 深拷贝
rst.add(new ArrayList<>(list));
return;
}
for(int i=0;i<num.length;i++){
if(visited[i]){
continue;
}
if(i>0 && num[i]==num[i-1] && !visited[i-1]) {
// 未被访问，说明上一个序列访问了，重复跳过
continue;
}
list.add(num[i]);
visited[i] = true;
dfs2(rst,visited,list,num);
visited[i]=false;
list.remove(list.size()-1);
}
}
/**
* 元素的全排列
* permutations-全排列
* 只有方法，全部列举
* 给出一个具有重复数字的列表，找出列表所有不同的排列。
* [1,1,2]have the following unique permutations:
* [1,1,2],[1,2,1], and[2,1,1].
*/
public ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<>();
//使用bool数组代替是否被访问过,节约查找时间
boolean[] visited = new boolean[num.length];
dfs(rst,visited,list,num);
return rst;
}
private void dfs(ArrayList<ArrayList<Integer>> rst, boolean[] visited, ArrayList<Integer> list, int[] num) {
if(list.size()==num.length){
// 深拷贝
rst.add(new ArrayList<>(list));
return;
}
for(int i=0;i<num.length;i++){
if(visited[i]){
continue;
}else {
list.add(num[i]);
visited[i] = true;
dfs(rst,visited,list,num);
visited[i]=false;
list.remove(list.size()-1);
}
}
}
/**
* powx-n
*/
public double pow(double x, int n) {
boolean isNegative = false;
if (n < 0) {
x = 1 / x;
isNegative = true;
// 防止溢出
n = -(n + 1);
}
double sum = 1;
double temp = x;
while (n > 0) {
if (n % 2 == 1) {
sum *= temp;
}
temp *= temp;
n /= 2;
}
if (isNegative) {
sum *= x;
}
return sum;
}
/**
* sqrtx
* 直接在1-n,二分查找
*/
public int sqrt(int x) {
if (x < 0) {
throw new IllegalArgumentException();
}
if (x <= 1) {
return x;
}
int start = 1;
int end = x;
int mid = 0;
// 记住5的开放是2，这里需要间隔1个
// 当剩下两个数时，右边的不相等，则取左边小的数
while (start + 1 < end) {
mid = (start + end) / 2;
// 使用x / mid，防止溢出
if (mid == x / mid) {
return mid;
} else if (mid < x / mid) {
start = mid;
} else {
end = mid;
}
}
if (end > x / end) {
return start;
}
return end;
}
/**
* restore-ip-addresses
* 恢复IP地址
* 给一个由数字组成的字符串。求出其可能恢复为的所有IP地址。
*/
public ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> list = new ArrayList<>();
ArrayList<String> rst = new ArrayList<>();
// 长度不符合
if (s.length() < 4 || s.length() > 12) {
return rst;
}
helper(rst, list, s, 0);
return rst;
}
private void helper(ArrayList<String> rst, ArrayList<String> list, String s, int start) {
// list大小满足要求
if (list.size() == 4) {
// 没有使用所有的s
if (start != s.length()) {
return;
}
// 拼接字符串返回
StringBuffer sb = new StringBuffer();
for (String string : list) {
sb.append(string).append(".");
}
sb.deleteCharAt(sb.length() - 1);
rst.add(sb.toString());
return;
}
// 遍历，长度为3
for (int i = start; i < s.length() && i < start + 3; i++) {
String temp = s.substring(start, i + 1);
if (isValid(temp)) {
list.add(temp);
helper(rst, list, s, i + 1);
// 回退
list.remove(list.size() - 1);
}
}
}
private boolean isValid(String temp) {
if (temp.charAt(0) == '0') {
// 移除开头是0的非数字，比如01,010；
return temp.equals("0");
}
int digit = Integer.valueOf(temp);
return (digit >= 0 && digit <= 255);
}
}
package com.nowcoder.leetcode.greed;
import java.util.Stack;
/**
* @description: 贪心算法
* @author: zoutai
* @create: 2019/4/17
**/
public class Solution {
public static void main(String[] args) {
int[] arr = {2, 1, 5, 6, 2, 3};
int[] arr2 = {2,3,1,1,4};
System.out.println(new Solution().jump(arr2));
}
/**
* maximum-subarray
* 求最大连续子数组
* 可以dp也可以贪心
* [−2,1,−3,4,−1,2,1,−5,4], --> [4,−1,2,1]
*/
public int maxSubArray(int[] A) {
if(A==null || A.length==0){
return 0;
}
// 临时最大值和最大值
int sum = 0;
// 直接定义为第一个，防止就一个值
int max = A[0];
// 只要遇到为负数的就sum清零，重新计数
for(int i : A){
sum+=i;
max=Math.max(max,sum);
if(sum<0){
sum=0;
}
}
return max;
}
/** Jump Game II
* 给出一个非负整数数组，你最初定位在数组的第一个位置。
* 数组中的每个元素代表你在那个位置可以跳跃的最大长度。
* 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
* 注：可以少跳，比如数组为0+A[0]=2，可以调到1，并不一定要跳到2
* 比如：2 3 1 1 4
* 第一个区间为0-0 能够跳的区间为0-2
* 第二个区间即0-2 能够跳的区间就是2-4 这里不用再管2之前的
*/
public int jump(int[] A) {
if(A==null || A.length==0){
return 0;
}
int start =0,end =0;
int sum=0;
int farthest = start;
while (farthest < A.length-1) {
// 扫描一个区间，取最大值，记一个数
for (int i = start; i <= end; i++) {
farthest = Math.max(farthest, i + A[i]);
}
// 更新首位数值，计数+1
start = end;
end = farthest;
sum++;
}
return sum;
}
/**jump-game
* 给出一个非负整数数组，你最初定位在数组的第一个位置。
* 数组中的每个元素代表你在那个位置可以跳跃的最大长度。
* 判断你是否能到达数组的最后一个位置。
* @param A
* @return
*/
public boolean canJump(int[] A) {
if(A==null || A.length==0){
return false;
}
int last = A.length-1;
int len = A.length;
// 直接从最后遍历，只有当前节点跳过一步，能超过后续节点，就表明能够达到
for(int i=len-2;i>=0;i--){
if((i+A[i])>=last){
last = i;
}
}
return last == 0;
}
/**
* 给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的最短子串。
* 使用前后指针扫描
* 参考：https://www.jianshu.com/p/ce80b4c07c22
*/
public String minWindow(String S, String T) {
// 记录目标字符串每个字母出现次数
int[] srcHash = new int[256];
for (char ch : T.toCharArray()) {
srcHash[ch]++;
}
// 用于记录窗口内每个字母出现次数
int[] destHash = new int[255];
// 用于扫描的指针，单个临时位置指针：start头固定指针位置，i为结尾指针扫描
int start = 0, i = 0;
// 用于保存最终的起始位置指针
int begin = -1, end = 0;
// 记录匹配的数目，用于判断扫描停止信号
int found = 0;
int minLength = Integer.MAX_VALUE;
// 右指针右移：从start处向后遍历扫描
for (start = i = 0; i < S.length(); i++) {
// 1. 将第一个元素数目+1
destHash[S.charAt(i)]++;
// 元素数目小于或等于表示当前字符匹配目标字符：
// 2. 比如：I.当不匹配时，目标字符值为0，一定小于；
// II.当目标字符有2个A，如AA，当前字符读取了3个A，如AAA，也不符合,这种情况在下面2处会判断
if (destHash[S.charAt(i)] <= srcHash[S.charAt(i)]) {
found++;
}
// 长度相同：右指针到达节点了
if (found == T.length()) {
// 左指针右移，移除前面不满足的元素
// 将开头没用的都跳过，没用是指该字符出现次数超过了目标串中出现的次数，并把它们出现次数都减1
while (start < i && (destHash[S.charAt(start)] > srcHash[S.charAt(start)])) {
destHash[S.charAt(start)]--;
start++;
}
// 左指针到达节点
if (i - start < minLength) {
//修改最大长度值，并修改临时结果指针
minLength = i - start;
begin = start;
end = i;
}
// 一次查找完成：移除头结点。
// 即移除一个满足的节点，继续查找更小的
// 计数-1、数量-1、头指针右移一位
destHash[S.charAt(start)]--;
found--;
start++;
}
}
if (begin == -1) {
return "";
} else {
return S.substring(begin, end + 1);
}
}
/**
* 求矩阵中最大矩形面积
* 参考：https://zhuanlan.zhihu.com/p/26456269
* 按行累加，转换为求解直方图最大面积
*/
public int maximalRectangle(char[][] matrix) {
//分为两段
int m = matrix.length;
int n = m == 0 ? 0 : matrix[0].length;
int[][] height = new int[m][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '0') {
height[i][j] = 0;
} else {
height[i][j] = i == 0 ? 1 : height[i - 1][j] + 1;
}
}
}
int maxArea = 0;
for (int i = 0; i < m; i++) {
int area = largestRectangleArea(height[i]);
if (maxArea < area) {
maxArea = area;
}
}
return maxArea;
}
/**
* 求直方图中最大矩形面积
* 测试案例：2 1 5 6 2 3
*/
public int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
Stack<Integer> stack = new Stack<Integer>(); //维护单调递增
int max = 0;
for (int i = 0; i <= height.length; i++) {
int curt = (i == height.length) ? -1 : height[i];
while (!stack.isEmpty() && curt <= height[stack.peek()]) { //如果栈顶高度大于当前高度
int h = height[stack.pop()]; //保存栈顶元素信息
int w = stack.isEmpty() ? i : i - stack.peek() - 1; //如果栈已经为空，宽度为i，否则i-s.top()-1
max = Math.max(max, h * w);
}
stack.push(i); //压入栈中
}
return max;
}
// 这个函数有错误
private int maxAreaInHist(int[] height) {
if (height == null) {
return 0;
}
if (height.length == 1) {
return height[0];
}
// 栈用于记录下标位置，用于计算矩阵的底长
Stack<Integer> stack = new Stack<>();
int i = 0, max = 0;
while (i < height.length + 1) {
// 栈为空或者栈顶元素长度小于当前长度，则入栈
if (stack.isEmpty() || (height[stack.peek()] <= height[i])) {
stack.push(i++);
} else if (i == height.length + 1) {
// 否则出栈
int t = stack.pop();
// 如果栈为null，底的长度直接为i-0:即整个长度；否则则为前后栈顶到当前位置的长度
// 高的长度为height[t]
max = Math.max(max, height[t] * (stack.isEmpty() ? i - 0 : i - stack.peek() - 1));
}
}
return max;
}
// 记住：只要是总加油量大于总耗油量，就可以走出
// 具体需要画图理解，另外：不能反着走
// 给出二维平面上的n个点，求最多有多少点在同一条直线上。
public int canCompleteCircuit(int[] gas, int[] cost) {
// 用于记录油的总数，小于0，表示不可能走通
int sum = 0;
// 记录是否能够连续走通一段，遍历
int remain = 0;
// 遍历，从前到后
int len = gas.length;
int start = 0;
for (int i = 0; i < len; i++) {
sum += gas[i] - cost[i];
remain += gas[i] - cost[i];
// 不能连续走通，测从下一起点开始
if (remain < 0) {
remain = 0;
start = i + 1;
}
}
return sum >= 0 ? start : -1;
}
}
多为自己，便可少劳烦他人
版权声明：本文为SoundSlow原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。