解题方法：
-
快慢指针推进程序降低复杂度 - HashMap,优先队列，双端队列辅助
统计计算 - 快排思想完成
对半查找，无需进行构造搜索树 - 使用kmp算法进行
子串查找 - 遇到字母统计使用hash思想进行统计
- 遇到数字可以使用
异或运算
思维
首先请放弃你那种暴力法，即动不动就上双重循环的思维方式。
然后更多的使用切分和线性的方式去做数组或者链表的题，在动态规划中更是这样。
例题一
解题方法：使用快慢指针+Map进行辅助统计计算
总结一句话：连续不重复字串最长
题目内容
LeetCode 第 03 题：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1
输入："abcabcbb"
输出：3
解释：因为无重复字符的最长子串是"abc"，其长度为3。
解题思路：
使用快慢指针（slow,fast）的方式,当fast前进一步就向Map中进行put一个元素，当遇到Map中包含这个元素时，就进行删除。
怎么删除呢？
使用Map获取相同字符的位置然后加一，并且更新slow指针
怎么计算长度呢？
快慢指针位置相减加一
下面的解题方法有两种：
1.使用指针一个一个删除这种方式显然是很多次是多余
2.使用Map进行跳跃，那就可以省去了很多次的删除过程
public class ContinuousNonRepetitionString {
public static void main(String[] args) {
String[] data = {"d","e","a","d","c","a","q"};
System.out.println(new ContinuousNonRepetitionString().length(data));
System.out.println(new ContinuousNonRepetitionString().lengthStep(data));
}
/**
* 使用Map快速跳转慢指针的方法
* @param nums
* @return
*/
private int length(String[] nums){
int i = 0;
int j = 0;
Map<String,Integer> temp = new HashMap<>();
int max = 0;
for(;j<nums.length;j++){
if(temp.containsKey(nums[j])){
i = temp.get(nums[j])+1;
}
temp.put(nums[j],j);
max=Math.max(max,j-i+1);
}
return max;
}
/**
* 使用循环删除的方式，更新慢指针
* @param nums
* @return
*/
private int lengthStep(String[] nums){
int i = 0;
int j = 0;
Set<String> temp = new HashSet<>();
int max = 0;
for(;j<nums.length;j++){
while (temp.contains(nums[j])){
temp.remove(nums[i]);
i++;
}
temp.add(nums[j]);
max=Math.max(max,j-i+1);
}
return max;
}
}
例题二
解题方法：使用快排的思想进行查找，并不是把全部的元素排序
总结一句话： 找中位数
题目：
LeetCode 第 04 题：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m+n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例1
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例2
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
解题思路
换一种思路想：
首先将两个数组合并
然后找第k大的元素，当我们使用快速排序的时候，每排序一轮后，中间的那个元素就就是第k大元素，所以我们可以通过比较k值得大小决定向左还是向右继续比较，另一边就不需要管了。这样就降低的时间复杂度
此题有两种情况：
1.数组是奇数，中位数为 第k大的元素 k=nums.length/2 ,排序后的坐标为k-1
2.数组是偶数，中位数为 第k大和第k+1大的平均值
public class MedianQuickMethod {
public static void main(String[] args) {
int[] nums = {1,3,5,7,9,11,13,15};//1,3,5,7,9,15,13,11
//15,3,5,7,9,1,13,11
//15,13,11,7,9,1,3,5
System.out.println(new MedianQuickMethod().findMedian(nums));
}
private double findMedian(int[] nums){
int k = nums.length/2;
if((nums.length)%2 == 0){
double k1= quick(nums,0,nums.length-1,k);
double k2= quick(nums,0,nums.length-1,k+1);
return (k1+k2)/2f;
}else {
return quick(nums,0,nums.length-1,k+1);
}
}
private double quick(int[] nums,int low,int he,int k){
int pivot = (int) (Math.random()*(he-low+1)+low);
// int pivot = low;
swap(nums,pivot,he);
int finishPos = low;
System.out.println("p:"+nums[he]);
for(int i=low;i<nums.length;i++){
if(nums[i]>nums[he]){
swap(nums,i,finishPos);
finishPos++;
}
}
swap(nums,he,finishPos);
System.out.println(Arrays.toString(nums));
//第几个
int tempk = finishPos-low+1;
System.out.println("第k大："+tempk + "要求：" + k);
if(tempk==k)
return nums[finishPos];
else if(tempk<k)
return quick(nums,finishPos+1,he,k-tempk);
else
return quick(nums,low,finishPos-1,k);
}
private void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
网友评论