数组题目中的一些方法与特征
关键字
有序无序从数组中任取几个数，还是从数组中确保顺序，取连续的几个数，例如：求连续数构成子数组，连续数最大值从数组中取任意的数，还是从数组中取确定的数
方法
- 首先需要明白数组是一种连续存储的数据结构，因此可以按照顺序遍历真个数组，对于求数组中两个数的和，数组中的重叠元素，数组中
连续子数组都可以采用多层遍历的方法，暴力法进行解决- 上面的暴力法比较粗暴，时间复杂度往往是O(N^2 N^3)，因此需要进行改进 ；改进的策略可以总结为如下:
数组是否可以先进行排序，再进行折半查找
2、
数组是否在排序的基础上，进行双指针，向中部逼近,（尤其当数组需要求和的时候）；指针如何移动
3、
若求某个范围，进行大小比较的时候，是否可以再双指针的基础上构建滑动窗口，来进行求解，关键是如何移动指针，就是通过移动指针来满足条件;例如：求两数的和=某值，求面积的最大值
4、
采用快慢指针的方式,上面的为首尾指针，快慢指针可以将序列数组划分为若干部分，进行分析;在数组或字符串，链表的去重时可能会用到
5、
数组是否可以空间换时间，将中间的计算结果进行存储，方便后来进行计算，例如hashMap存储中间计算的和，存储之前遍历的元素，关键是在hashMap中存储的是什么；
题目note
- 数组中的两个数的和----->
- 数组中三个树的和
排序数组中两个数的和- 数组中连续子数组的和为
k- 数组中连续子数组中的和为
k*n- 数组中连续子数组的乘积小于k
- 数组的
反转- 成最多水的容器
分析：要求求数组中两个数的和=target，关键是如何找到这两个数，也就是从数组中查找两个数的变形，那么首先可以使用
暴力法
- 对于每个值nums[i]，可以遍历数组中的其他值，来进行判断，=两个值的和是否等于target
时间复杂度为O(n^2);- 上面的复杂度太高，那么是否有某种方法进行改进呢？是否可以用空间换时间的策略，可以尝试
map,先遍历下数组将每个值与其对应的索引放入到map值，再遍历下数组中的每个值，判断target-nums[i]是否在Map中；那么时间复杂度为O(n)，空间复杂度为O(n)扩展:若没有要求求出数组的索引，就是单纯的求数组中值的组合，办么我们可以先对数组进行排序，再定义两个指针left,right，初始化为数组的首元素与末尾元素，进行夹逼的方式进行逼进，若两个值>target则right左移一位，若两个值<target则left右移一位；直到left<right
package AarrayProblem;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/3/29 0029 22:32
* 数组中两数之和
*
* 在数组中求数组的和
* 这其实也是在数组中查找元素的变形，关键是在数组中查找两个元素，
* 这两个元素的和要满足某种要求
*
*
* （1） 可以遍历对于每个确定的值nums[i]遍历整个数组，若数组中存在target-nums[i]则存在
* 时间复杂度为o(n^2)
*
* (2) 上面的时间复杂度比较大，我们是否可以尝试采用空间换时间的策略：
* 我们需要一种更有效的方法来检查数组中是否存在目标元素，因为结果是返回索引，那么我们可以
* 使用 value--index 的map数据结构，
* 先遍历数组将所有 value-index加入到hashMap中，然后再计算在 hashMap中是否包含target-arr[i]
* 时间复杂度：O（n) 空间复杂度：O（n)
*
* （3）对于数组我们是否可以采用先对其排序，然后再进行操作
*/
public class Problem1 {
//暴力遍历整个数组
//时间复杂度：O（n^2)
//对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费O(N)时间
public int[] twoSum(int[] nums, int target) {
int[] rs= new int[2];
int length = nums.length;
for(int i=0;i<length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
rs[0]=i;
rs[1]=j;
}
}
}
return rs;
}
//使用一个hashMap以空间换时间
//一个简单的实现使用了两次迭代，在第一次迭代中，我们将每个元素的值和它的索引添加到表中
//然后在第二次迭代中，我们检查每个元素所对应的目标(target-nums[i]）是否存在于表中；
//时间复杂度：O(n);我们把包含有n个元素怒的列表遍历两次，由于哈希表将查找时间缩短到O(1)，所以时间爱你复杂度为O(N)
//空间复杂度:O(N)
//小结：当时间复杂度比较大的时候，我们可以思考是否可以用空间换时间解决
//那么常用的空间可以采用:HashMap、queueu、statck、priorityQueur
//在以后的问题中要想清楚每种何时采用什么样的数据结构
public int[] twoSum1(int[] nums, int target){
Map<Integer,Integer> map = new HashMap<>();
//将value---key存放到map中
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
//遍历
for(int i=0;i<nums.length;i++){
//保证 不是同一个数 并且两个数的和=target
if(map.containsKey(target-nums[i])&&(map.get(target-nums[i])!=i)){
return new int[] {i,map.get(target-nums[i])};
}
}
return null;
}
//一遍hash表
//在遍历hash表的时候就判断在hash表中是否包含 target-value值
public int[] twoSum2(int[] nums, int target){
Map<Integer,Integer> map = new HashMap<>();
//遍历数组
for(int i=0;i<nums.length;i++){
int value = nums[i];
if(map.containsKey(target-value)){
return new int[]{i,map.get(value)};
}
map.put(nums[i],i);
}
return null;
}
//这种方法也叫双指针法
//在leetcode4中可以采用这种方法
//是否可以先对数组进行排序
//要返回的是索引的位置这意味着不能对数组进行排序
//若没有要求返回的是数组的索引位置而就是返回数组的选值的问题，那么就可以采用这种方法
public int[] twoSum3(int[] nums, int target){
//先进行排序
Arrays.sort(nums);
int left =0;
int right = nums.length-1;
while(left<right){
int value = nums[left]+nums[right];
if(value == target){
return new int[] {left,right};
}else if(value>target){//两个计算的值大于taRGET则说明，right向后退意味
right--;
}else{
left++;
}
}
return null;
}
public static void main(String[] args) {
Problem1 problem1 = new Problem1();
int[] arr = {3,2,4};
int[] rs = problem1.twoSum3(arr,6);
}
}
- 首先，
受题目一的影响，可以采用暴力法，三层遍历，穷举每种可能，进行判断(但这种方法 在测试的时候超时);时间复杂度为O(N^3)- 可以采用题目一种的
双指针的方法，遍历每个值nums[i]，定义两个指针left和right初始值分别为i+1和nums.length-1，每次判断nums[left]+nums[right]+nums[i]的和是否为target，否则进行指针移动，注意在移动的时候要注意去重,时间复杂度为O(N^2)
package AarrayProblem;
import java.util.*;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/3/29 0029 23:28
*
* 三数之和
*/
public class Problem15 {
//暴力方法：三层循环核心从数组中任意挑选三个数字
//难点：不包含重复的三元数组
//固定一个转换为 二个数的和
//通过 311/313个测试用例
//
//暴力破解的方法失效:超出时间限制】
public List<List<Integer>> threeSum(int[] nums) {
int length = nums.length;
List<List<Integer>> rs = new ArrayList<>();
//数组中任意三个树的和
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
for(int t=j+1;t<nums.length;t++){
//进行判断
if((nums[i]+nums[j]+nums[t]==0)){
ArrayList<Integer> r = new ArrayList<>();
r.add(nums[i]);
r.add(nums[j]);
r.add(nums[t]);
Collections.sort(r);
if(!rs.contains(r))
rs.add(r);
}
}
}
}
return rs;
}
//先确定一个数，在去求另外连个数的和
//简化成leetcode2
//显然不能用hashMap：使用hashMap如何使用
//存在超时限制
public List<List<Integer>> threeSum1(int[] nums){
List<List<Integer>> list = new ArrayList<>();
Map<Integer,Integer> map = new HashMap<>();
//首次遍历将所有元素加入到HashMap中
//若两个元素重复则可能覆盖
//则将索引作为key，值作为vaklue
for(int i=0;i<nums.length;i++){
map.put(i,nums[i]);
}
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
map.remove(i);
map.remove(j);
int value = 0-nums[i]-nums[j];
if(map.containsValue(value)){//在map中包含，并且不包含当前遍历的map[i],map[j]
//这里存在问题
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(nums[i]);
arrayList.add(nums[j]);
arrayList.add(value);
Collections.sort(arrayList);
if(!list.contains(arrayList))
list.add(arrayList);
}
map.put(i,nums[i]);
map.put(j,nums[j]);
}
}
return list;
}
//采用双指针法：（夹逼法）——。
//1、先对数组进行排序
//2、边里数组的每个元素：nums[i]
//2.1、定义连个初始指针 left------>nums[i+1]
// right------>nums.length-1
//若nums[left]+nums[right]+arr[i]==0 ;为了防止重复元素的出现 去重，while(left<right && nums[left]==nums[left+1]) left++;
//若value<0则left++
//若value>0 则rtight--(和小了则单方面移动右指针）
public List<List<Integer>> threeSum2(int[] nums){
List<List<Integer>> rs = new ArrayList<>();
int lenght = nums.length;
if(lenght<3) return rs;
//1、对数组排序
Arrays.sort(nums);
for(int i=0;i<lenght;i++){
//需要判断，去重
//当连续的两个数相等时取后面的一个数
if(i>0&&nums[i]==nums[i-1]) continue;
//左右两个指针锁对应的值的和应该为value
//定义两个指针
int left = i+1;
int right = lenght-1;
while(left<right) {
int sum = nums[i]+nums[left]+nums[right];
if (sum==0){
//添加元素
rs.add(Arrays.asList(nums[i],nums[left],nums[right]));
//需要去除重复元素
while(left<right&&nums[left]==nums[left+1]){
left++;
}
while(left<right&&nums[right]==nums[right-1]){
right--;
}
left++;
right--;
}else if(sum>0){//当前的计算结果的值大于value，则应该将右指针做移动
right--;
}else if(sum<0){//当前计算结果的值小于value，则应该将左指针右移动，选择更大的数
left++;
}
}
}
return rs;
}
public static void main(String[] args) {
Problem15 problem15 = new Problem15();
int[] arr = {0,0,0};
List<List<Integer>> RS =problem15.threeSum2(arr);
System.out.println(RS);
}
}
分析：可以使用暴力法：四层循环
O(N^4)
参考：两数之和，三数之和，是否可以借助指针呢,两个指针遍历。
这里的难点是如何去重;
- 使用四个指针(i<j<left<right)，固定最小的i和j，left=j+1,rigth=length-1
- 使用双层循环，遍历所有i和j;
- 使用动态指针left和right根据sum的和
nums[i]+nums[j]+nums[left]+nums[right]调整数组的和；若和大于target则right左移动，若小于target则left右移动- 当left和righ相遇时，表示本轮遍历已经结束，开始下一轮
如何解决重复问题
确保移动指针后，对应的数字要发生改变
当i和j每次更新的时候，要进行判断，若和前一次相等则continue当sum=target，时需要移动left和right的指针，此时也需要进行判断数字是否相等，不断判断，直到找到数字不相等指针所在位置
package AarrayProblem;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/3/31 0031 16:14
* 四数之和
*/
public class Problem18 {
//这道题目中要求：任取四个数，因此可以对数组进行排序等操作
//采用暴力的算法：O（n^4)
//是否可以采用双指针的做法：
//先对数组进行排序
//然后
//核心如何去重，去重
public List<List<Integer>> fourSum(int[] nums, int target) {
//首先对数组进行排序
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
//假如数组的长度小于4则返回空
if(nums.length<4){return list;}
for(int i=0;i<nums.length-3;i++){
//当前后两次的值相等的时候跳过;确保nums[i]的值发生了改变
//若当前的元素在前面遍历过程中出现过则跳过
if(i>=1&&nums[i]==nums[i-1]) continue;
for(int j=i+1;j<nums.length-2;j++){
//当前后两次的值相等的时候跳过
//若当前元素在前面遍历过程中出现则跳过
if(j>i+1&&nums[j]==nums[j-1]) continue;
//左右指针初始化
int left = j+1;
int right = nums.length-1;
//动态调整左右指针
while(left<right) {
//计算和
int sum = nums[i] + nums[j] + nums[left] + nums[right];
//假如和的值为target
if (sum == target) {
List<Integer> l = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
list.add(l);
//去除重复元素
while(left<right&&nums[left]==nums[left+1]) left++;
while(left<right&&nums[right]==nums[right-1]) right--;
//最后要加上，因为前面的判断是当前元素和下一个元速进行判断
left++;
right--;
} else if (sum > target) {//假如sum>target，则需要将右指针左移
//这里也可以进行判断:当前元素和前一个元素相等，则right--
//这里不假循环判断也行
while(left<right&&nums[right]==nums[right-1]) right--;
right--;
} else {
while(left<right&&nums[left]==nums[left+1]) left++;
left++;
}
}
}
}
return list;
}
public static void main(String[] args) {
Problem18 problem18 = new Problem18();
// int[] arr = {-3,-2,-1,0,0,1,2,3};
int[] arr = {-1,0,1,2,-1,-4};
List<List<Integer>> rs;
rs=problem18.fourSum(arr,-1);
System.out.println(rs);
}
}
分析：与上提类似，只不过上提中要求三数的和是某个确定的值，而此题中，要求三个数
最接近某个值，因为其类似性，因此我们可以采用相同的思路
可以采用暴力法:三层遍历整个数组，穷举每种可能，进行差值的比较，若发现插值小，则进行更新可以采用双指针法:
- 先对数组进行
排序时间复杂度为O(nlogn)- 在数组nums中，进行遍历，每遍历一个值利用其下标i，形成一个固定值
nums[i]- 再适应前指针指向
start=i+1处，后指针指向end=nums.length-1也就是结尾处根据sum=nums[i]+nums[start]+nums[end的结果，判断sum与目标target的距离，如果更近则更新结果ans- 同时判断
sum与target的大小关系，因为数组有序，如果sum>target，则ebd--,如果sum<target则start++，若sum==target则说明距离为0则直接返回结果- 整个遍历过程，固定值为n,双指针为n此，时间复杂度为
O(n^2)
package AarrayProblem;
import java.util.Arrays;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/3/31 0031 15:17
* 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
* 找出 nums 中的三个整数，使得它们的和与 target 最接近。
* 返回这三个数的和。假定每组输入只存在唯一答案。
*/
public class Problem16 {
//求三数之和 然后求其与target的差 去差最小的值
//可以用三层循环解决问题：暴力法
//这种方法返回的 不是连续的子数组
//时间复杂度为O(n^3)
public int threeSumClosest(int[] nums, int target) {
int length = nums.length;
//差值
int com =Integer.MAX_VALUE;
//存储最终返回的值
int min = 0;
for(int i=0;i<length;i++){
for(int j=i+1;j<length;j++){
for(int t=j+1;t<length;t++){
int sum = nums[i]+nums[j]+nums[t];
if(Math.abs(com)>Math.abs(sum-target)) {min = sum; com=sum-target;}
}
}
}
return min;
}
//可以尝试使用双指针法
//时间复杂度：O(N^2)
//首先对数组进行排序，然后使用指针
//关键如何对指针进行操作
//双指针法：思路，对数组排序，然后确定一个数，在左右指针运动过程中，记录与三数之和域target绝对值差最小
//核心不断缩小与target数之间的差距：关键如何动指针
public int threeSumClosest1(int[] nums, int target){
//先对数组进行排序
Arrays.sort(nums);
int length = nums.length;
int com = Integer.MAX_VALUE;//存储最小的差
int min = 0;
for(int i=0;i<nums.length;i++){
int left =i+1;
int right = length-1;
while(left<right){
int sum = nums[i]+nums[left]+nums[right];
//假如差值小于则更新；并且尝试求
if(Math.abs(com)>Math.abs(sum-target)){
min = sum;
com=sum-target;
}
//当前值的和小于target的话则移动左指针 右面移动
if(sum<target){
left++;
}else if(sum>target){
right--;
}else{
return min;
}
}
}
return min;
}
public static void main(String[] args) {
int[] arr={1,1,-1,-1,3};
int target = -1;
Problem16 problem16 = new Problem16();
int value = problem16.threeSumClosest1(arr,-1);
System.out.println(value);
}
}
- 首先可以采用
暴力的方法- 核心
数组有序，则可以采用双指针法
package AarrayProblem;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/3/30 0030 10:33
* 两数之和----输入有序数组
* 核心 有序数组
* 双指针法
*/
public class Problem167 {
//暴力法：O(N^2)
//能通过但是超出时间限制
public int[] twoSum1(int[] numbers, int target){
int length = numbers.length;
for(int i=0;i<length;i++){
for(int j=i+1;j<length;j++){
if(numbers[i]+numbers[j]==target){
return new int[]{i+1,j+1};
}
}
}
return null;
}
//HashMap法:时间复杂度为O(n)
public int[] twoSum2(int[] numbers, int target){
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<numbers.length;i++){
int value = numbers[i];
int componenty = target-value;
if(map.containsKey(componenty)){
return new int[]{Math.min(i+1,map.get(componenty)+1),Math.max(i+1,map.get(componenty)+1)};
}
map.put(numbers[i],i);
}
return null;
}
//双指针法
//时间复杂度为：O（n)
//使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
//
//如果两个指针指向元素的和 sum == targetsum==target，那么得到要求的结果；
//如果 sum > targetsum>target，移动较大的元素，使 sumsum 变小一些；
//如果 sum < targetsum<target，移动较小的元素，使 sumsum 变大一些。
//数组中的元素最多遍历一次，时间复杂度为 O(N)O(N)。只使用了两个额外变量，空间复杂度为 O(1)O(1)。
public int[] twoSum(int[] numbers, int target) {
//左指针
int left = 0;
//右指针
int right = numbers.length-1;
//不断遍历的条件
while(left<right){
//
int value = numbers[left]+numbers[right];
//假如满足值相等
if(value==target){
return new int[]{left+1,right+1};
//移动指针
}else if(value>target){
right--;
}else if(value<target){
left++;
}
}
return null;
}
//对于有序数组可以二分查找:在查找right的时候；
//使用二分查找先找到第一个大于target的值
public static void main(String[] args) {
Problem167 problem167 = new Problem167();
int[] arr = {2,7,11,15};
int[] a = problem167.twoSum2(arr,9);
System.out.println(Arrays.toString(a));
}
}
有序数组 没有顺序，且需要求连续的k个子数组的情况，则不能对其排序，既不能使用
二分法，也不能使用指针法
- 暴力法：
穷举每种可能，对连续的值进行求和看起值是否为k- 前缀法：
上面的计算的复杂度太高，我们是否可以空间换时间，定义一个sum[]数组，数组存放从起始位置到现在为止的nunm的和，需要求某个区间的和，之间让两个sum相减就可以了时间复杂度为O(N^2)- 哈希表法：
利用哈希表，在表中记录sum值，判断在表中是否存在sum-k,以及sum-k出现的次数;这时hash表中存放的就是[sum,sum出现的次数]
package AarrayProblem;
import java.util.HashMap;
import java.util.Map;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/3/30 0030 11:10
* 和为k的子数组：
* 数组没有顺序 也不能排序
* 可以采用递归
*/
public class Problem560 {
//暴力的方法：
//考虑规定的nums数组的每个可能的数组，找到每个子数组 的元素总和，并检查使用给定K获得
//总和是否相等，当总和等于k时，我们可以递增用于存储所需要结果的count
//时间复杂度为O(N^3) 超时限制
public int subarraySum1(int[] nums, int k){
int count=0;
int length = nums.length;
//开始的点：start
for(int start=0;start<length;start++){
//结束的点 end
for(int end=start;end<length;end++){
//计算开始点到结束点的结果
int sum =0;
//遍历进行计算
for(int j=start;j<=end;j++){
sum=sum+nums[j];
}
//得到的结果为0
if(sum==k){
count++;
}
}
}
return count;
}
//使用累加和
//因为在上面的计算中有大量的求和重复计算，我们是否可移将这些求和的中间结果进行存储
//这样就是一种以空间换时间的思路：时间复杂度为O(N^2) 空间复杂度：O(N)
public int subarraySum2(int[] nums, int k){
int count=0;
//计算累加和
int[] sum = new int[nums.length+1];
sum[0] = 0;
//将所有的子数组的和进行存储
for(int i=1;i<=nums.length;i++ ){
sum[i]=sum[i-1]+nums[i-1];
}
//二维遍历整个数组 计算 从start索引到end索引位置处对应值的差
for(int start=0;start<nums.length;start++){
for(int end=start+1;end<nums.length;end++){
if(sum[end]-sum[start]==k){
count++;
}
}
}
return count;
}
//不需要额外的空间
//外层循环遍历所有的start，内层循环遍历所有的end，在遍历end的时候记录一下sum的值
//时间复杂度：O(N^2) 空间复杂度O(1)
public int subarraySum3(int[] nums, int k){
int count = 0;
for(int start=0;start<nums.length;start++){
//保存计算的中间和
int sum = 0;
for(int end=start;end<nums.length;end++){
sum=sum+nums[end];
if(sum==k){
count++;
}
}
}
return count;
}
//利用hash表处理
//在hash表中记录 sum[i] 以及sum[i] 出现的次数
//若 sum[i] 与 sum[j]的差为k，则表明i到j之键的和为k
//若在i之前存储的map中存在 sum-k对应的值 说明之前到现在 sum增加了k
//秒啊 秒
public int subarraySum4(int[] nums, int k){
//map记录sum以及对应sum的次数
Map<Integer,Integer> map = new HashMap<>();
//记录sum的和
int sum =0;
map.put(0,1);
for(int i=0;i<nums.length;i++){
sum = sum+nums[i];
//在map之前存储了sum-k;说明从之前的某个或者某几个位置增加了k，也就是序列和为k
if(map.containsKey(sum-k)){
count+=map.get(sum-k);
}
//将sum的值加1
map.put(sum,map.getOrDefault(sum,0)+1);
}
return count;
}
int count = 0;
//采用递归的方法
public int subarraySum(int[] nums, int k) {
//遍历以每个元素开始的数组
for(int i=0;i<nums.length;i++) {
//在这里进行递归判断
findValueInArray(nums, i, k);
}
return count;
}
//在数组中和为k的连续子树组
public void findValueInArray(int[] nums,int start,int k){
//取nums子数组中的第一个元素
int value = k-nums[start];
//当k-numsstart位0的时候说明找到了，技术值加1
if(value==0){
count++;
}
//当数组中还有元素的时候，则不断的进行相加进行判断
if(start+1<nums.length){
//在接下来连续的start+1开始的连续数组开始
findValueInArray(nums,start+1,value);}
}
//
//
public static void main(String[] args) {
int[] nums = {0,0,0,0,0,0,0,0,0,0};
Problem560 problem560 = new Problem560();
int size = problem560.subarraySum(nums,0);
System.out.println(size);
}
}
- 暴力法：
和题目560类似，穷举每种可能，进行判断- Hash法：
可以在hash表中存储一些中间结果，之后再计算的时候利用hash表，在hash表中判断是否存在某个条件，与上提类似，借助hash表法；关键在hash表中存储什么中间值？分析：若两个和的差为n*k，也就是 sum[i]-sum[j]是k的倍数与，那么 sum[i]%k==sum[j]%k,因此可以在hash表中存放sum[i]%k以及索引值，用来判断不子数组的和是否大于2
package AarrayProblem;
import java.util.HashMap;
import java.util.Map;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/3/30 0030 16:13
* 给定一个包含非负数的数组和一个目标整数 k，
* 编写一个函数来判断该数组是否含有连续的子数组，
* 其大小至少为 2，总和为 k 的倍数，
* 即总和为 n*k，其中 n 也是一个整数。
*
*/
public class Problem523 {
//暴力法：超出时间限制
//遍历所有的可能
public boolean checkSubarraySum(int[] nums, int k) {
//计算数组长度
int length = nums.length;
//开始的位置
for(int start=0;start<length;start++){
//结束的位置
for(int end=start+1;end<length;end++){
//
int sum = 0;
for(int j =start;j<=end;j++){
//将值加上去
sum+=nums[j];
//若是第一次计算则跳过
if(j==start) continue;
//若k==0则区别对待
if(k==0){
if(sum==0)
return true;
}else if(sum%k==0){
return true;
}
}
}
}
return false;
}
//暴力法的时间复杂度太高
//可以利用hashMap，
//遍历一遍nums将 从开始到nums处的和求出来
// sum1 sum2 sum3 sum4
//则 sum2-sum1之间的值就是 1-2的和
//则 sum3-sum2的差就是 2-3的和
//之后 sum-n*k + n*k 也就是之前的map中若存在 sum-n*k的值则表明
//map里面存删
//在这里关键是保存在hash中key对应的value值保存的是什么
//只要sum的值已经被放入了hashMap中了，代表有两个索引i和j
//它们之间的元素和是k的整倍数，因此只要hashMap中有相同的sum%k
public boolean checkSubarraySum1(int[] nums, int k) {
//定义数组的长度
int length = nums.length;
//顶以map存放hashMap
Map<Integer, Integer> map = new HashMap<>();
map.put(0,-1);
int sum =0;
//遍历整个数组
for (int i = 0; i < nums.length; i++) {
//计算和
sum += nums[i];
//假如k!=0
if (k != 0)
sum = sum % k;
if (map.containsKey(sum)) {
//两个数的位置>1
if (i - map.get(sum) > 1)
return true;
} else
map.put(sum, i);
}
return false;
}
public static void main(String[] args) {
Problem523 problem532 = new Problem523();
int[] ar = {0,1,0};
System.out.println(problem532.checkSubarraySum1(ar,0));
}
}
上面一到题目是求最大子数组的和，这道题目试求子序列的和
可采用动态规划和暴力法
package AarrayProblem;
import java.util.HashMap;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/8 0008 13:36
* 最大子序列和
*/
public class Problem53 {
//时间复杂度为o(n^2) 超出
public int maxSubArray(int[] nums) {
int max = Integer.MIN_VALUE;
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,0);
int sum = 0;
for(int i=0;i<nums.length;i++){
sum = sum+nums[i];
map.put(i+1,sum);
}
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<=nums.length;j++){
if(map.get(j)-map.get(i)>max) max = map.get(j)-map.get(i);
}
}
return max;
}
//动态规划
//这道题采用动态规划：
//动态规划的是首先对数组进行遍历，当前最大连续子序列和为sum,结果为ans
//使用dp[i]表示以索引i结尾的最大和的连续子数组的和，得出状态转移方程：
//
//dp[i] = Math.max(nums[i], dp[i-1] + nums[i])
//
//作者：antione
//链接：https://leetcode-cn.com/problems/maximum-subarray/solution/jian-dan-yi-dong-de-dong-tai-gui-hua-yao-dian-fen-/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
public int maxSubArray1(int[] nums){
//dp[i】丁酉为数组nums中以nums[i]结尾的最大连续子串和
int[] dp = new int[nums.length];//定义状态数组
dp[0]=nums[0];
int max = nums[0]; //初始化最大值
for(int i=1;i<nums.length;i++){
//当前
dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);//根据状态转移矩阵更新数组
if(max<dp[i]) max=dp[i];
}
return max;
}
//优化空间复杂度的状态规划
public int maxSubArray2(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num: nums) {
if(sum > 0) {
sum += num;
} else {
sum = num;
}
ans = Math.max(ans, sum);
}
return ans;
}
public static void main(String[] args) {
int[] arr ={1};
Problem53 problem53 = new Problem53();
int min = problem53.maxSubArray(arr);
System.out.println(min);
}
}
- 这道题和之前的求数组中连续求和有相似点，不过之前的问题是求
等于某个值，而这里要求是小于某个值，因此可以尝试采用滑动窗口的方法- 注意
滑动窗口是一种常用的方法 它使用于要求连续的数据
像求数组中前k个数的最大值，也可以采用滑动窗口的方法
- 定义两个指针 left与right确定滑动窗口的连个边界
- 对reight进行枚举，right从0到arr.length
- 对于每个right，确定其对应的left，left的确定为当乘积大于要求的值时，将Left右移动，不断右移，压缩这个滑动窗口的大小；
- 通过left与right此事可以确定整个滑动窗口的大小，这时就可以计算在此right下的子数组的个数
right-left+1
package AarrayProblem;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/3/30 0030 22:34
* 给定一个正整数数组 nums。
* 找出该数组内乘积小于 k 的连续的子数组的个数。
*/
public class Problem713 {
//可以采用暴力法：遍历数组中的所用值的乘积：时间复杂度为O(N^3)
//暴力法：超出时间限制
public int numSubarrayProductLessThanK(int[] nums, int k) {
int count = 0;
for(int start=0;start<nums.length;start++){
for(int end=start;end<nums.length;end++){
int sum = 1;
for(int j=start;j<=end;j++){
sum=sum*nums[j];
}
if(sum<k) {
count++;
}else{
break;
}
}
}
return count;
}
//双指针法:移动窗口法
//顶以两个指针：
// 对于每个right指针，需要在其左侧找到
//注意窗口移动条件的
//对于每个固定的
/*
双指针法，如果一个子串的乘积小于k，那么他的每个子集都小于k，
而一个长度为n的数组，他的所有连续子串数量是1+2+...n，但是会和前面的重复。
比如例子中[10, 5, 2, 6]，第一个满足条件的子串是[10]，第二个满足的是[10, 5]
，但是第二个数组的子集[10]和前面的已经重复了，因此我们只需要计算包含最右边的数字的子串数量，
就不会重复了，也就是在计算[10, 5]这个数组的子串是，
只加入[5]和[10, 5]，而不加入[10]，这部分的子串数量刚好是r - l + 1
*/
public int numSubarrayProductLessThanK2(int[] nums, int k){
//左右指针
int left=0;
int right=0;
//计算次数
int count =0 ;
//乘积
int prod =1;
//右指针不断右移动
for(;right<nums.length;right++){
//对于每个right计算其值
prod = prod*nums[right];
//移动左子帧
while(prod>=k) prod=prod/nums[left++];
//这里的公式是如何得出的
count+=right-left+1;
}
return count;
}
public static void main(String[] args) {
Problem713 problem713 = new Problem713();
int[] arr = {10,5,2,6};
int num= problem713.numSubarrayProductLessThanK(arr,100);
System.out.println(num);
}
}
注意，这里不是求连续子数组的和或者连续子数组的技，而是在数组中确定两个位置，在这两个位置的差*两个位置处值最下值 最大
求面积表达是=(endIndex-startIndex)*Math.min(height[endIndex],height[startIndex])
- 首先，可以使用暴力法，从任意起点到任意位置，求取所有的乘积，取出最大的值，就是结果，时间复杂度为O(n)
- 可以尝试使用
hashMap吗？ 不能，因为hashMap我们通常是用来存储中间的结果中，这道题中没有中间值存储。（排除）- 可以尝试使用
双指针吗,我们分析一下，定义两个指针left,right分别指向数组的首部和尾部，进行计算；接下来的问题是如何更新指针，需要记住的是数组的指针再移动时，只能移动一个，我们要移动的时候，width在不断减小，倘若，移动指针对应的值较大的面积肯定会减小，因此移动指针对应值较小的指针
package AarrayProblem;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/3/31 0031 11:09
* 盛最多的水
*/
public class Problem11 {
//求最优解
//可以使用暴力的方法
//面积 = （大的索引-小的索引） * （min(两个索引对应小的值))
//求连续子区间的最值
//暴力破解法：时间复杂度：O(n^2) 空间复杂度：O（1）
//求任意区间的最大值
public int maxArea(int[] height) {
int length = height.length;
int max = 0;
for(int start=0;start<length;start++){
for(int end=start+1;end<length;end++){
int area = (end-start)*Math.min(height[start],height[end]);
if(area>max) max = area;
}
}
return max;
}
//上面的时间复杂度太大了
//是否可以尝试其他的方法
//用空间换时间
//要是乘积最大 就要确保 高度与索引的最大
//这种方法背后的思路在于，两线段之间形成的区域总是会受到其中较短哪条长度的限制
//关键指针如何移动：移动长度较短的那条
//width已经不断减少了，要想得到一个更大面积的，height必须要越高越好，因此必须移动较小的一端
public int maxArea1(int[] height){
//双指针
int left = 0;
int right = height.length-1;
int max =0 ;
while(left<right){
int area = (right-left)*Math.min(height[left],height[right]);
if(area>max)
{
max=area;
}
//移动指针所指向的长度较短的指针的位置
//分析下为什么么呢？
//我们如何移动指针呢？
//肯定不可能两个一起动，那么动哪一条呢？动长的肯定回
if(height[left]>height[right]) right--;
else left++;
}
return max;
}
}
若数组 为旋转，在数组中查找一个特定元素target的过程为
target=nums[mid]则直接返回target<nums[mid]则target位于左侧区间[left,mid)，令right=mid-1，在左侧区间查找target>nums[mid]则target位于右侧区间(mid,right]，令left=mid+1,在右侧区间查找在二分查找，可以分为下列几种
while(left<=right)，这种应对传统的找目标值的问题while(left<right)，这种应对 几乎所有二分问题，例如第一个大于（等于）target的索引，看到target易购的问题，这种思想采用每一步都做排除法
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;
int middle = left+(right-left)/2;
//注意这种查找的是:这里是左闭右开[left,right)
while(left<right){
if(nums[middle]==target){
return middle;
//需要在左区间进行查找[left,middle)
}else if(nums[middle]>target){
right = middle;
}else{
//需要在右区间进行查找
left= middle+1;
}
middle = left+(right-left)/2;
}
return -1;
}
public int[] searchRange(int[] nums, int target){
int[] res = {-1,-1};
if(nums.length==0) return res;
res[0]=foundLeft(nums,target);
res[1]=foundRight(nums,target);
return res;
}
//在数组中第一次出现某个元素的位置
//采用二分查找的排除法
public int foundLeft(int[] nums,int target){
int left = 0;
int right = nums.length-1;
int middle = left+(right-left)/2;
//
while(left<right){
//数组是递增的，如果在middle出的元素小于target则在左半部分一定没有
//小于一定不是解：
if(nums[middle]<target){
//在右半部分查找 [middle+1,right]
left=middle+1;
}else{
//否则在左半部分查找
//注意这里为什么取middle [left,middle]
//因为middle可能就是结果值
right = middle;
}
middle=left+(right-left)/2;
}
if(nums[left]==target) return left;
else return -1;
}
//在数组中查找最后一次出现某个元素的位置
//采用二分查找法
public int foundRight(int[] nums,int target){
int left =0;
int right = nums.length-1;
//取左中卫树
int middle= left+(right-left+1)/2;
while(left<right){
//先排除何时不可能出现在区间
//数组是递增的，当MiddLE出的元素大于target则值只能出现在左半区间
//
if(nums[middle]>target){
//在左半区间查找 [left,middle-1]
right = middle-1;
}else{
//否则只能在右半区间查找 [middle,right)
//只要是left=middle就需要向上取中位数
left = middle;
}
middle= left+(right-left+1)/2;
}
if(nums[left]==target) return left;
else return -1;
}
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
int middle = left+(right-left)/2;
if(target>nums[right]) return right+1;
while(left<right){
//数组是递增数组
//加入当前置 < target 说明 需要向后面查找；并且结果只能出现在后面
//target<当前值 结果只能出现在前面 ；
//严格小于target的元素一定不是解
if(nums[middle]<target){
//下一轮搜索区间[middle+1,right]
left = middle+1;
}else{
right = middle;
}
middle = left+(right-left)/2;
}
return left;
}
这道题目在
剑指Offer中出现过;
核心：排序数组的查找;可以采用二分查找，需要注意的是这道题如何进行二分查找
二分查找的过程就是在不但收缩左右边界，而怎么缩小区间是关键
这道题，由于数组被旋转，所以左侧或右侧区间不连续，在这种情况下，如何判断target位于哪个区间？
根据旋转数组的特性，当元素不重复时，如果
nums[i] <= nums[j]，说明区间 [i,j] 是「连续递增」的。
package AarrayProblem;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/3 0003 11:19
* 索旋转排序数组
*/
public class Problem33 {
//双指针
//至少有一部分数据是递增的
//这里 关键就是如何移动指针
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
//注意这里的等于号
while(left<=right){
int middle = left+(right-left)/2;
if(nums[middle]==target) return middle;
//判断出来至少左半部分递增
if(nums[middle]>=nums[left]){
//从左面查找
//这个很关键：根据这个判断
//数据落在这个区间
//必须加上target
//那么 right = middl-1
if(nums[middle]>=target&&nums[left]<=target){
right=middle-1;
}else{
left=middle+1;
}
}else{//右半部分递增
//目标值落在这个区间
if(nums[right]>=target&&nums[middle]<=target){
left=middle+1;
}else{
right=middle-1;
}
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {3,1};
Problem33 problem33 = new Problem33();
int t =problem33.search(arr,1);
System.out.println(t);
}
}
这道题和上题目类似，不同点在于
这题包含重复数据
- 难点在于
nums[mid]=nums[left'时无法判断target位于左侧还是右侧，此时无法缩小区间，，退化为顺序查找- 另一种是令left++，去掉一个干扰项
package AarrayProblem;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/3 0003 12:07
* 搜索螺旋排序数组ii
*/
public class Problem81 {
public boolean search(int[] nums, int target) {
//定义左子帧
int left = 0;
//定义右子帧
int right = nums.length-1;
//特殊条件的判断
if(nums.length==0) return false;
if(nums[0]==target) return true;
//不断查找
while(left<=right){
//中间值
int middle = left+(right-left)/2;
//找到
if(nums[middle]==target) return true;
//坐班部分升序 1 3 1 1 1 这种有可能误判
//因此这种情况需要处理，nums[middle]==nums[left] 此时中间具体是上升还是啥的不清楚
//可以跳过 left++处理即可
if(nums[middle]==nums[left]){
left++;
}
//下面就和常规的处理一样了
//坐班部分递增
else if((nums[middle]>nums[left])){
if(nums[middle]>=target&&nums[left]<=target) right=middle-1;
else left = middle+1;
}else{//右半部分升序
if(nums[middle]<=target&&nums[right]>=target) left = middle+1;
else right=middle-1;
}
}
return false;
}
public static void main(String[] args) {
int[] nums = {1,1,3,1};
Problem81 problem81 = new Problem81();
System.out.println(problem81.search(nums,1));
}
}
核心问题如何缩小区间
package AarrayProblem;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/3 0003 14:06
* 寻找旋转数组中的最小的值
*/
public class Problem153 {
public int findMin(int[] nums) {
//定义最小值
int min = Integer.MAX_VALUE;
//定义左子帧
int left = 0;
//定义右滋镇
int right = nums.length-1;
//中间值
int middle = left+(right-left)/2;
while(left<=right){
//左侧递增：最小值只能出现在最左端
if(nums[middle]>=nums[right]){
//判断
if(min>nums[left]) min=nums[left];
//在在mid的右侧进行查找是否还有最小哦值
left = middle+1;
}else{//右侧递增
//最小值只能出现在最左daunt
if(min>nums[middle]) min=nums[middle];
right = middle-1;
}
middle = left+(right-left)/2;
}
return min;
}
public static void main(String[] args) {
int[] nums = {1};
Problem153 problem153 = new Problem153();
int min= problem153.findMin(nums);
System.out.println(min);
}
}
核新问题：解决重复
class Solution {
public int findMin(int[] nums) {
int min = Integer.MAX_VALUE;
int left = 0;
int right = nums.length-1;
int middle = left+(right-left)/2;
while(left<=right){
//在这个区间存在相等的值
if(nums[middle]==nums[left]){
if(min>nums[left]) min = nums[left];
left++;
//在左侧递增
}else if(nums[middle]>nums[left]){
if(nums[left]<min) min = nums[left];
left = middle+1;
}else{//在右侧递增
if(nums[middle]<min) min=nums[middle];
right = middle-1;
}
middle=left+(right-left)/2;
}
return min;
}
}
- 可以采用暴力的方式，进行过滤
使用两个指针，快慢指针的方式，进行去重;相当于使用两个指针堆数组进行逻辑划分,一个指针为cur指向已经去重数组的尾部;一个指针head之下ing委屈虫数组的首部;当head指向的数据=cur指向的数据则将head加1,否则将head的数据复制到cur处
package AarrayProblem;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/3/31 0031 17:54
* 删除排序数组中的重复项
* 数组去重：不使用额外的内存
*
*/
public class Problem26 {
//这道题目一个重要特点是 ：数组是排序的
//暴力的方法：时间复杂度为O(N^3)
//
public int removeDuplicates(int[] nums) {
//原数组的长度
int length = nums.length;
//遍历原来的数组
for(int i=0;i<length;i++){
//定义一个指针，遍历数组
int left = i;
while(left<length-1&&nums[left+1]==nums[left]) left++;
left++;
//重复元素的个数(
int duplicate =left-i;
//需要移动元素的个数
int moved = duplicate-1;
//当需要移动元素个数>=1时此时就需要进行移动
if(moved>0){
//需要移动元素的个数
for(int t=0;t<length-left;t++){
//进行覆盖
nums[i+t+1]=nums[i+t+moved+1];
}
//此时数组中的不重复的元素个数（在此次遍历的情况下）
length=length-moved;
}
}
return length;
}
//双指针：快慢指针，首尾指针的思想
//首先注意数组是有序的，那么重复的元素一定会相邻
//要求删除重复元素怒，实际上是将不重复的元素怒移动到数组的左侧
//考虑用两个指针，一个在前记作p，一个在后记作q(快慢指针）
// 首选比较p和q位置的元素是否相等
// 如果相等，q后移一位
// 如果不相等，将 q位置的元素赋值到p+1位置上，p后移动1位，q后移动一位
//在数组内部 逻辑上将其划分连个数组 无
// 1、已经判断好的无重复的数组
//2、尚未判断是否存在重复元素的
//使用两个指针，分别指向这两个逻辑数组，其中指向第一个逻辑数组的尾部为cur
//使用head指向第二个逻辑数组的头部，表明待去重的数组
public int removeDuplicates1(int[] nums){
//指向当前无重复数组的尾部
int cur = 0;
//指向当前要遍历数组的头部
int head =1;
if(nums.length<2) return nums.length;
//遍历指针不断后移
while(head<nums.length){
//加入 遍历数组的头部与已经无重复数组的尾部元素相等
//则说明存在重复元素怒 需要将head++
if(nums[head]==nums[cur]) head++;
else{//发现不是重复元素，则将不重复元素添加到不重复数组中
nums[++cur]=nums[head];
head++;
}
}
//因为是从0开是的，所以需要+1
return cur+1;
}
public static void main(String[] args) {
Problem26 problem26 = new Problem26();
int[] arr ={1,1,2};
int length = problem26.removeDuplicates1(arr);
System.out.println(length);
}
}
桶上一体类似，我们可以采用快慢指针的方法:
- 定义连个指针
left和right(left指向不包含该值的末尾逻辑数组，righjt指向还未遍历的逻辑数组的首部）- 当nums[right]与给定的值相等时，递增right跳过该元素，只要
nums[rigjt]!=value,就将nums[right]复制到nums[left+1]中
package AarrayProblem;
import java.util.Arrays;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/1 0001 00:02
*/
public class Problem27 {
//移除数组中指定元素
//参考钱买你一体
//可以使用双指针，即快慢指针
//先对数组进行排序
public int removeElement(int[] nums, int val) {
//在数组中找到这个位置，使用快慢指针法
//left指向 不包含某个元素的末尾,
//left初始的时候为-1
int left = -1;
//right指向可能包含某个元素的首部
int right =0;
while(right<nums.length){
//包含某个元素，则跳过这个元素
if(nums[right]==val) right++;
else{//当前元素不包含该元素
left++;
nums[left]=nums[right];
right++;
}
}
return left+1;
}
public static void main(String[] args) {
}
}
数组的全排列问题就是：
对于数组中的元素，进行所有的排列可能，其衍生版本可以为字符串的全排列
先确定一个位置，在这个位置的基础上进行接下来的操作；满足目标操作完成，进行回溯，将刚才的位置取消，重新确立一个新的位置
基本方法:使用递归加回溯的方法
具体操作:
- 定义一个方法，
permute(数组，起始位置start);其中数组为待排列的数组，可能在操作过程中，已经进行了部分排列，start为从当前这个位置以及之后没有进行排列，可以确定start的具体值- 确定完
start的值，就可以进行递归，不断的进行递归确定新的start的值，直到start的位置到达数组的末尾，- 接着进行回溯，回溯到上一个start的位置
注意事项:
- 在保存对象到数组或者
list的时候，需要new对象- 在
list中删除整数的时候有两种删除按照索引和按照值，若按照值删除最好在值前面加上（Object）
public void allpay(数组,int start){
if(start==数组的长度){
//新建对象，进行保存到链表中（注意一定要新建对象）
rs.add(new String(c));
}
//先固定到start处的元素（start处的元素可以改变）
for(int j=start;j<c.length;j++){
//确定start出的元素（start可以取从start之后的任意元素，遍历）
swap(c,j,start);
//确定start之后的元素（这是一种递归）
allpay(c,start+1);
//回溯（从最后的start的元素开始回溯）
swap(c,j,start);
}
}
//交换数组中i和j处的元素怒
public void swap(char[] c,int i,int j){
char temp=c[i];
c[i]=c[j];
c[j]=temp;
}
//保存结果
private ArrayList<ArrayList<Integer>> rs = new ArrayList<>();
private ArrayList<Integer> r = new ArrayList<>();
public void permute(int[] array,int start){
//r满了
if(start==array.length){
System.out.println(r);
//注意这里必须 new ArrayList
rs.add(new ArrayList<>(r));
//讲述组情况
}else {
//start表示定位到第几个元素
//i是可选的start的位置
//从前往后，逐次确地每个位置上可能出现的元素
//其中start是待确定的位置(start之前的位置已经确定）
//在每个start位置
for (int i = start; i < array.length; i++) {
swap(array, i, start);
r.add(array[start]);
permute(array, start + 1);
//注意这里删除的问题
//在ArrayList中有两个remove方法，其中一个是删除在某个索引位置处的元素，另一个是按照object value
//默认是按照索引删除，因此可能存在冲突，若按照目标值，加上(object)
r.remove((Object)array[start]);
swap(array, i, start);
}
}
}
public void swap(int[] array,int i,int j){
int temp = array[i];
array[i]=array[j];
array[j]=temp;
}
package AarrayProblem;
import java.util.ArrayList;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/1 0001 12:30
* 字符串的全排列
*/
public class StringAllpay {
ArrayList<String> rs = new ArrayList<>();
public void allpay(char[] c,int start){
if(start==c.length){
rs.add(new String(c));
}
//先固定到start处的元素（start处的元素可以改变）
for(int j=start;j<c.length;j++){
//确定start出的元素
swap(c,j,start);
//确定start之后的元素
allpay(c,start+1);
//回溯（从最后的start的元素开始回溯）
swap(c,j,start);
}
}
public void swap(char[] c,int i,int j){
char temp=c[i];
c[i]=c[j];
c[j]=temp;
}
public static void main(String[] args) {
String str="abc";
StringAllpay stringAllpay = new StringAllpay();
stringAllpay.allpay(str.toCharArray(),0);
System.out.println(stringAllpay.rs);
}
}
上面就是基本介绍，下面看看常见的题目
采用
回溯算法
是一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认 不是 一个解的话（或者至少不是 最后一个 解），回溯算法会通过在上一步进行一些变化抛弃该解，即 回溯 并且再次尝试。
如何确保按照顺序输出
package AarrayProblem;
import java.util.ArrayList;
import java.util.List;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/1 0001 16:15
* 给定一个 没有重复 数字的序列 返回其所有可能的全排列
*/
public class Problem46 {
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
//递归加回溯
public List<List<Integer>> permute(int[] nums) {
permuteAll(nums,0);
return result;
}
//回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解
//当发现已不满足求解条件时，就回溯返回，尝试别的路径。
//回溯法是一种优选搜索法，按优选条件向前搜索，以达到目标。
//但当探索到某一步时，发现原先选择并不优秀或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术成为
//回溯法，而满足回溯条件的状态点称为回溯点。
//许多复杂的，规模较大的问题都可以使用回溯法，有通用解题方法之称
public void permuteAll(int[] nums,int start){
if(start==nums.length){
result.add(new ArrayList<>(list));
}else{
for(int i=start;i<nums.length;i++){
//加上这一行就可以按照顺序输出，特别重要
Arrays.sort(nums,start,nums.length);
swap(nums,i,start);
//递归+回溯
list.add(nums[start]);
permuteAll(nums,start+1);
list.remove((Object)nums[start]);
swap(nums,i,start);
}
}
}
//交换元素
public void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
在上一题的基础上进行改进
关键是如何去重
- 当然，可以通过
set保存所有排列的组合进行保存上面的方法比较粗暴，·、,是否可以在某个阶段就确定一定会重复，那么我们就可以减小复杂度关键是，如何确定会出现重复进行回溯的过程中，进行交换时，就绪要判断是否需要进行交换，如果在待确定的位置start与待候选元素之间，存在于待候选元素相同的值，说明在这个值之前存在于这个值相等的排列，因此，不需要交换
package AarrayProblem;
import java.util.ArrayList;
import java.util.List;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/1 0001 16:48
* 返回所有不重复的全排列
*
*/
public class Problem47 {
//返回结果
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
dfs(nums,0);
return ans;
}
private void dfs(int[] nums,int cur) {
//当前已经排列完
if (cur == nums.length) {
//保存结果
List<Integer> line = new ArrayList<>();
for (int i : nums) {
line.add(i);
}
ans.add(line);
} else {
for (int i = cur;i < nums.length;i++) {
//在这一步判断是否可以交换
//cur是待固定的位置；i是待交换的位置
//若 在cur于i之间有等于i指向的对象 不用交换
//说明在i之前有等于i的元素，已经和cur交换过了，那么我们就不需要交换了
if (canSwap(nums,cur,i)) {
swap(nums,cur,i);
dfs(nums,cur + 1);
swap(nums,cur,i);
}
}
}
}
//判断是否能交换
private boolean canSwap(int nums[],int begin,int end) {
for (int i = begin;i < end;i++) {
if (nums[i] == nums[end]) {
return false;
}
}
return true;
}
private void swap(int nums[],int i,int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
int[] arr = {1,1,2};
Problem47 problem47 = new Problem47();
problem47.permuteUnique(arr);
System.out.println(problem47.ans);
}
}
- 可以使用暴力法，穷举所有的全排列，并将全排列进行存储，找到数组在全排列中的位置，就可以输出下一个
排列;但是这种方法是一种非常天真的方法，因为它要求我们找到所有可能的排列，这需要很长的时间，实施起来也非常复杂改进
在全排列的过程中，我们是如何进行排列的呢？
首先，对数组进行排序，确定每个位置的元素，确定完一个排列之后，进行回溯
·关键就是序列如何回溯，从形成序列的尾部进行回溯`** 对于本题目。我们观察到对于任何一个序列，么有可能更大的额序列的情况核实出现呢
** 当数组中序列是全部降序的时候，例如654321`，就是数组的后一个元素小于前一个元素的时候。这时候数组的下一个序列按理来说就没有了。
那么序列什么时候有下一个序列，以及系列是如何形成的呢？我们应该知道，序列按照从小到大形成的过程是
先确定前面的元素，也就是先固定一部分元素，动态变化后面的元素，当后面元素组合完成后（也就是后面全部是降序的时候也就组合完成了，前面固定部分锁对应的所有结果都搞出来了，此时前面固定的部分就需要动了，也就需要修改了）；**在本体中，如何发现固定的部分需要动了，就是当后一个元素大于前一个元素的时候的分解点的时候，因为后面若已经组合完成了，元素是降序的，找到分界线跟就是我们需要替换的元素，如何替换呢？从分界点后找到一个大于分界点前的元素进行元素替换，并对分界点后的元素怒进行排序`
解题思路
- 从数组的右侧向左开始遍历，找到nums[i]>nums[i-1]的情况
- 如果不存在这种nums[i]>nums[i-1]情况，for循环会遍历到0（也就是没有下一个排列），此时按照提议排成有序Arrays.sort()
- 如果存在，则将从下标i到nums.length(）d的部分排序，然后再排过序的这部分中遍历找到第一个大于nums[i-1]的数，并与nums[i-1]
package AarrayProblem;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/1 0001 00:25
* 数组的排列问题
*/
public class Problem31 {
/*
暴力法：在这种话方法中，我们找出由给定数组的元素形成的列表的每个可能的排列，
并找出比给定排列更大的排列
但是这个方法是一种非常天真的方法，因为它要求我们找出所有可能的排列，则需要很长的时间
*/
ArrayList<ArrayList<Integer>> rs = new ArrayList<>();
ArrayList<Integer> arrayList = new ArrayList<>();
//如何获取数组的排列
//我们可以先获得数组的全排列
//然后再数组的全排列中 获取当前排列所在的位置
public void nextPermutation(int[] nums) {
int[] newNum = nums.clone();
Arrays.sort(newNum);
//获取数组的全排列
allPermutation(newNum,0);
//将数组装换为ArrayList
ArrayList<Integer> arrayList = new ArrayList<>();
for(int i=0;i<nums.length;i++) arrayList.add(nums[i]);
//获取当前nums在全排列中的顺序
int index = rs.indexOf(arrayList);
System.out.println(index);
if(index==rs.size()-1) index=-1;
index++;
ArrayList<Integer> result = rs.get(index);
System.out.println(result);
}
//获取数组的全排列
public void allPermutation(int[] nums,int start){
//一次遍历完
if(arrayList.size()==nums.length){
rs.add(new ArrayList<>(arrayList));
}
for(int i=start;i<nums.length;i++){
swap(nums,start,i);//交换元素
arrayList.add(nums[start]);
allPermutation(nums,start+1);//交换完之后再进行全排列
arrayList.remove((Object)nums[start]);
swap(nums,start,i);
}
}
//交换两个数
public void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
/
//借助递归的思想：
//在暴力的方法之上进行改进：
//暴力递归与回溯
//回溯是在前一个的基础上进行回溯，从尾部进行回溯
//那么我们可以参考这种方式，对nums数组，从尾部进行回溯
//如发现 nums[i]>nums[i-1]则可以将从 i开始的数组进行排列，排列之后将i出的位置与i-1处的位置对调
//若从后往前遍历发现都是后一个比钱一个小，说明数据已经从大往小排列了，此时直接对nums进行排序即可
public void nextPermutation(int[] nums) {
//从后往前遍历
int i = nums.length-1;
while(i>0){
//后一个元素比前一个元素大
if(nums[i]>nums[i-1]){
//对i之后的元素进行排序，
Arrays.sort(nums,i,nums.length);
int t = i;
//在拍过虚的部分找到第一个大于nums[i-1]的数，
for(;t<nums.length;t++){
if(nums[t]>nums[i-1]) break;
}
//将i出的元素与i-1出的元素交换
int temp = nums[t];
nums[t]=nums[i-1];
nums[i-1]=temp;
return;
}
i--;
}
//在其中没有找到，说明已经全排列到最后了
Arrays.sort(nums);
}
public static void main(String[] args) {
int[] arr = {2,3,1};
Problem31 problem31 = new Problem31();
problem31.nextPermutation1(arr);
System.out.println(Arrays.toString(arr));
}
}
分析：在排列中的三种常见问题:全排列（没有顺序）、全排列（有顺序）、求排列的下一个排列、求全排列中的第k个排列
求第k个排列是有规律的：
我们可以知道，n个数据的全排列共有n!中组合，因此每确定第一个元素则有(n-1)!中排列，则确定一个元素之后，后面的元素
直接用回溯法做的话需要在回溯到第k个排列时终止就不会超时了, 但是效率依旧感人
可以用数学的方法来解, 因为数字都是从1开始的连续自然数, 排列出现的次序可以推
算出来, 对于n=4, k=15 找到k=15排列的过程:
1 + 对2,3,4的全排列 (3!个)
2 + 对1,3,4的全排列 (3!个) 3, 1 + 对2,4的全排列(2!个)
3 + 对1,2,4的全排列 (3!个)-------> 3, 2 + 对1,4的全排列(2!个)-------> 3, 2, 1 + 对4的全排列(1!个)-------> 3214
4 + 对1,2,3的全排列 (3!个) 3, 4 + 对1,2的全排列(2!个) 3, 2, 4 + 对1的全排列(1!个)
确定第一位:
k = 14(从0开始计数)
index = k / (n-1)! = 2, 说明第15个数的第一位是3
更新k
k = k - index*(n-1)! = 2
确定第二位:
k = 2
index = k / (n-2)! = 1, 说明第15个数的第二位是2
更新k
k = k - index*(n-2)! = 0
确定第三位:
k = 0
index = k / (n-3)! = 0, 说明第15个数的第三位是1
更新k
k = k - index*(n-3)! = 0
确定第四位:
k = 0
index = k / (n-4)! = 0, 说明第15个数的第四位是4
最终确定n=4时第15个数为3214
class Solution {
public String getPermutation(int n, int k) {
/**
直接用回溯法做的话需要在回溯到第k个排列时终止就不会超时了, 但是效率依旧感人
可以用数学的方法来解, 因为数字都是从1开始的连续自然数, 排列出现的次序可以推
算出来, 对于n=4, k=15 找到k=15排列的过程:
1 + 对2,3,4的全排列 (3!个)
2 + 对1,3,4的全排列 (3!个) 3, 1 + 对2,4的全排列(2!个)
3 + 对1,2,4的全排列 (3!个)-------> 3, 2 + 对1,4的全排列(2!个)-------> 3, 2, 1 + 对4的全排列(1!个)-------> 3214
4 + 对1,2,3的全排列 (3!个) 3, 4 + 对1,2的全排列(2!个) 3, 2, 4 + 对1的全排列(1!个)
确定第一位:
k = 14(从0开始计数)
index = k / (n-1)! = 2, 说明第15个数的第一位是3
更新k
k = k - index*(n-1)! = 2
确定第二位:
k = 2
index = k / (n-2)! = 1, 说明第15个数的第二位是2
更新k
k = k - index*(n-2)! = 0
确定第三位:
k = 0
index = k / (n-3)! = 0, 说明第15个数的第三位是1
更新k
k = k - index*(n-3)! = 0
确定第四位:
k = 0
index = k / (n-4)! = 0, 说明第15个数的第四位是4
最终确定n=4时第15个数为3214
**/
StringBuilder sb = new StringBuilder();
// 候选数字
List<Integer> candidates = new ArrayList<>();
// 分母的阶乘数
int[] factorials = new int[n+1];
factorials[0] = 1;
int fact = 1;
for(int i = 1; i <= n; ++i) {
candidates.add(i);
fact *= i;
factorials[i] = fact;
}
k -= 1;
for(int i = n-1; i >= 0; --i) {
// 计算候选数字的index
int index = k / factorials[i];
sb.append(candidates.remove(index));
k -= index*factorials[i];
}
return sb.toString();
}
}
采用回溯法
package AarrayProblem;
import java.util.ArrayList;
import java.util.List;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/2 0002 17:24
* 组合:
* 顺序无所谓，但是不能包含重复（按照组合的定义，[12]和[21]也算重复
*/
public class Combine {
public List<List<Integer>> combine(int n,int k){
List<List<Integer>> rs = new ArrayList<>();
List<Integer> r = new ArrayList<>();
permutate(n,k,1,rs,r);
return rs;
}
public void permutate(int n,int k,int start,List<List<Integer>> rs,List<Integer> r){
//到达树的底部
//和计算子集差不多，区别在于，更新res的地方是低daunt
if(r.size()==k){
rs.add(new ArrayList<>(r));
return;
}
//注意i从start开始递增
for(int i=start;i<=n;i++){
//左选择
r.add(i);
//回溯
permutate(n,k,i+1,rs,r);
//撤销选择
r.remove((Object)i);
}
}
public static void main(String[] args) {
Combine combine = new Combine();
System.out.println(combine.combine(3,2));
}
}
package AarrayProblem;
import java.util.ArrayList;
import java.util.List;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/2 0002 17:06
*
* 回溯算法
*
* result=[]
*
* def backtrac(路径，选择列表）
*
* if 满足结束条件:
* result.add(路径）
* return;
*
* for 选择 in 选择列表:
* 左选择
* backtrack(路径，选择列表）
* 撤销选择
*/
public class SubSet {
public List<List<Integer>> subSet(int[] nums){
//记录走过的路径
List<Integer> list = new ArrayList<>();
List<List<Integer>>rs = new ArrayList<>();
fun(nums,0,list,rs);
return rs;
}
//求子集
public void fun(int[] nums,int start,List<Integer> list , List<List<Integer>> rs){
//只要不是空寂
rs.add(new ArrayList<>(list));
//注意i从start开始递增
for(int i=start;i<nums.length;i++){
//左选择
list.add(nums[i]);
//回溯
fun(nums,i+1,list,rs);
//撤销选择
list.remove((Object)nums[i]);
}
}
public static void main(String[] args) {
int[] nums ={1,2,3};
SubSet subSet = new SubSet();
System.out.println(subSet.subSet(nums));
}
}
package AarrayProblem;
import java.util.ArrayList;
import java.util.List;
/**
* @Author Zhou jian
* @Date 2020 ${month} 2020/4/2 0002 17:35
* 全排列
*/
public class Permutate {
public List<List<Integer>> permutate(int[] nums){
List<List<Integer>> rs = new ArrayList<>();
List<Integer> r = new ArrayList<>();
fun(nums,rs,r);
return rs;
}
public void fun(int[] nums, List<List<Integer>> rs,List<Integer> r){
if(r.size()==nums.length){
rs.add(new ArrayList<>(r));
return;
}
//排列问题比较堆成，而组合问题树越靠近右接地那越少
//注意这里的i从0开始
//要是全排序则从start开始
//
for(int i=0;i<nums.length;i++){
//假如已经包含取出
if(r.contains(nums[i])) continue;
//若没有宝行则加入进r中
r.add(nums[i]);
fun(nums,rs,r);
r.remove((Object)nums[i]);
}
}
public static void main(String[] args) {
int[] nums = {1,2,3};
Permutate permutate = new Permutate();
System.out.println(permutate.permutate(nums));
}
}
全排列子集合组合的问题
都可以采用递推加回溯的方法解决定义一个list可存放中间结果，当list中的元素到大某个要求的值时，满足条件，此时可以进行回溯;将最近一次添加的元素从List中去除，再尝试求他的值不同的点是全排序，对于元素的顺序有要求；组合和子集合对元素的顺序没有要求一般全排序有n!个（若无重合的问题）,
采用回溯算法
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> rs = new ArrayList<>();
combine(candidates,0,target,new ArrayList<>(),rs,0);
return rs;
}
//采用回溯算法
//关键是：如何确保不包含重复组合
public void combine(int[] cadidates,int start,int target,List<Integer>r,List<List<Integer>> rs,int sum){
if(sum>target) return;
//假如sum为target将r放入到rs中
if(sum==target){
rs.add(new ArrayList<>(r));
if(sum>target) return;
}else{
//从中选取元素
for(int i=start;i<cadidates.length;i++){
//进行价值
r.add(cadidates[i]);
sum=sum+cadidates[i];
//进行回溯
combine(cadidates,i,target,r,rs,sum);
sum=sum-cadidates[i];
r.remove((Object)cadidates[i]);
}
}
}
}
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> rs = new ArrayList<>();
permutae(candidates, 0, target, new ArrayList<>(), rs,0);
return rs;
}
public void permutae(int[] candidates, int start, int target, List<Integer> r, List<List<Integer>> rs, int sum) {
if (sum > target) return;
System.out.println(r);
if (sum == target) {
rs.add(new ArrayList<>(r));
return;
} else {
for (int i = start; i < candidates.length; i++) {
//在这里进行裁剪
if(i>start&&candidates[i]==candidates[i-1]) continue;
r.add(candidates[i]);
sum = sum + candidates[i];
permutae(candidates, i + 1, target,r, rs, sum);
sum = sum - candidates[i];
r.remove((Object) candidates[i]);
}
}
}
}