＜2.20＞Leetcode哈希、双指针

还可以用双指针的做法 我们要找等于9 排序后从两边开始左右指针 2 3 7 9 如果2+9>9那么9肯定不能要 去掉

左边也一样   2  3 5 6   2+6小于9 那么2肯定不能要 去掉

package Leetcode;
import java.util.*;public class 两数之和 {public int[] twoSum(int[] nums,int target) {暴力 时间复杂度O(n^2)for(int i = 0; i < nums.length;i++) {for (int j = i+1;j<nums.length;j++) {if (nums[i] + nums[j] == target) {return new int[] {i,j};}}}return null;}
}

package Leetcode;
import java.io.*;
import java.util.*;
/*输入
2 7 11 15
9
*/
public class 两数之和_ {public static void main(String[] args) throws IOException {// 创建BufferedReader用于从System.in读取输入BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));// 创建PrintWriter用于向System.out输出PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));// 读取一行，并使用split分割成字符串数组String[] s = bf.readLine().split(" ");// 创建一个整型数组来存储输入的整数int[] nums = new int[s.length];// 将字符串数组转换为整型数组for (int i = 0; i < nums.length; i++)nums[i] = Integer.parseInt(s[i]);int target = Integer.parseInt(bf.readLine());//暴力 时间复杂度O(n^2)for(int i = 0; i < nums.length;i++) {for (int j = i+1;j<nums.length;j++) {if (nums[i] + nums[j] == target) {pw.printf("[%d,%d]", i,j);bf.close();pw.close();return ;}}}bf.close();pw.close();}
}

package Leetcode;
import java.util.*;public class 两数之和 {public int[] twoSum(int[] nums,int target) {//哈希表 时间复杂度O(n)Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return null;}
}

import java.io.*;
import java.util.*;
/*输入
2 7 11 15
9
*/
public class 两数之和_ {public static void main(String[] args) throws IOException {// 创建BufferedReader用于从System.in读取输入BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));// 创建PrintWriter用于向System.out输出PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));// 读取一行，并使用split分割成字符串数组String[] s = bf.readLine().split(" ");// 创建一个整型数组来存储输入的整数int[] nums = new int[s.length];// 将字符串数组转换为整型数组for (int i = 0; i < nums.length; i++)nums[i] = Integer.parseInt(s[i]);int target = Integer.parseInt(bf.readLine());//哈希表 时间复杂度O(n)Map<Integer,Integer> hashTable = new HashMap<Integer,Integer>();for(int i= 0;i<nums.length;i++) {if(hashTable.containsKey(target - nums[i])) {pw.printf("[%d,%d]",hashTable.get(target-nums[i]),i);bf.close();pw.close();return ;}hashTable.put(nums[i],i);}bf.close();pw.close();}
}

 1.排序

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String,List<String>> map = new HashMap<String,List<String>>();for(String str : strs) {char[] array = str.toCharArray();//每个单词转化成一个chara数组Arrays.sort(array);//对这个char[]进行排序 array改变了 但是str还是原样String sortedWord = new String(array);//char数组转化成一个String类型map.computeIfAbsent(sortedWord, k -> new ArrayList<>()).add(str);//检查这个map里面是否有一个键是sortedWord 如果有就不创建键了 如果没有就创建一个这个键  最后将这个字符加在这个键下面}return new ArrayList<>(map.values());}
}

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<String, List<String>>();for (String str : strs) {char[] array = str.toCharArray();Arrays.sort(array);String key = new String(array);List<String> list = map.getOrDefault(key, new ArrayList<String>());list.add(str);map.put(key, list);}return new ArrayList<List<String>>(map.values());}
}
//List<String> list = map.getOrDefault(key, new ArrayList<String>());允许你获取指定键的值，如果这个键不存在，则返回一个默认值。但是，使用 getOrDefault 方法时需要注意，因为它返回的是默认值的一个副本，而不是实际存储在映射中的值。这意味着如果你修改了返回的列表，原始映射中的值不会被改变，除非你将修改后的列表再次放入映射中。

//时间复杂度：O(nklogk)，其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度。需要遍历n个字符串，对于每个字符串，需要O(klogk)的时间进行排序以及O(1)的时间更新哈希表，因此总时间复杂度是O(nklogk)import java.util.*;
import java.io.*;
import static java.lang.Math.*;
/*
eat tea tan ate nat bat*/
public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));String[] s = br.readLine().split(" ");List<String> l_s = Arrays.asList(s);Map<String,List<String>> map = new HashMap<String,List<String>>();for(String str : l_s) {char[] array = str.toCharArray();//每个单词转化成一个chara数组Arrays.sort(array);//对这个char[]进行排序 array改变了 但是str还是原样String sortedWord = new String(array);//char数组转化成一个String类型map.computeIfAbsent(sortedWord, k -> new ArrayList<>()).add(str);//检查这个map里面是否有一个键是sortedWord 如果有就不创建键了 如果没有就创建一个这个键  最后将这个字符加在这个键下面}pw.println(new ArrayList<>(map.values()));br.close();pw.close();}
}

import java.util.*;
import java.io.*;
import static java.lang.Math.*;
/*
eat tea tan ate nat bat*/
public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));String[] strs = br.readLine().split(" ");//字符串数组 里面每一个元素都是一个单词List<String>  l_s= Arrays.asList(strs);//一个List 里面每一个元素都是一个单词 将String[]转化成ListMap<String,List<String>> map = new HashMap<String,List<String>>();for(String str:strs){int[] counts = new int[26];//对于每一个单词计数int length = str.length();for(int i=0;i<length;i++){counts[str.charAt(i)-'a']++;//每个字符出现的次数++}//将每一个出现 次数大于0的字母和出现次数 按顺序拼接成字符串作为哈希表的键StringBuffer sb = new StringBuffer();//格式a2b3...for(int i=0;i<26;i++){if(counts[i]>0){sb.append((char)(i+'a'));sb.append(counts[i]);}}String key = sb.toString();List<String> list = map.getOrDefault(key,new ArrayList<String>());//如果什么都没有就返回一个ArrayListlist.add(str);//但是这个list不会更新位map的值 因为是副本map.put(key,list);//更细map}pw.println(new ArrayList<>(map.values()));br.close();pw.close();}
}

//排序时间复杂为nlogn
class Solution {public int longestConsecutive(int[] nums) {if(nums.length == 0) return 0;Arrays.sort(nums);//res表示=最长的长度(结果) len表示目前的长度 last表示在这个序列中上一个数字是int res = 1,c_len = 1,last = nums[0];for(int i = 1; i < nums.length; i++) {if (nums[i] == last) continue;else if (nums[i] == (1+last)){last = nums[i];c_len ++;}else{res = Math.max(res,c_len);//连不上了记录一下长度就行c_len = 1;last = nums[i];}}res = Math.max(res, c_len); // 临界条件 最后一段 要和现在比一下return res;}
}

import java.util.*;
import java.io.*;
import static java.lang.Math.*;
/*
100 4 200 1 3 2*/
public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));String[] nums_s = br.readLine().split(",");int[] nums = new int[nums_s.length];for (int i = 0; i < nums_s.length; i++) {nums[i] = Integer.parseInt(nums_s[i]);}
//        if(nums.length == 0) return 0;Arrays.sort(nums);//res表示=最长的长度(结果) len表示目前的长度 last表示在这个序列中上一个数字是int res = 1,c_len = 1,last = nums[0];for(int i = 1; i < nums.length; i++) {if (nums[i] == last) continue;else if (nums[i] == (1+last)){last = nums[i];c_len ++;}else{res = Math.max(res,c_len);//连不上了记录一下长度就行c_len = 1;last = nums[i];}}res = Math.max(res, c_len); // 临界条件 最后一段 要和现在比一下pw.println(res);br.close();pw.close();
//        return res;}
}

public int longestConsecutive(int[] nums) {if (nums.length == 0) return 0;int n = nums.length, max = 1;Set<Integer> set = new HashSet<>();for (int v : nums) set.add(v);for (int v : nums) {// 技巧：如果有比自己小一点的，那自己不查，让小的去查if (set.contains(v - 1)) continue;int r = v; // r: right 表示「以 v 开头，能连续到多少」while (set.contains(r + 1)) r++; // 逐个查看max = Math.max(max, r - v + 1); // 记录区间 [v, r] 长度}return max;
}

class Solution {public int longestConsecutive(int[] nums) {int ans = 0;Set<Integer> st = new HashSet<>();for (int num : nums) {st.add(num); // 把 nums 转成哈希集合}for (int x : st) { // 遍历哈希集合if (st.contains(x - 1)) {//x不是起点continue;}// x 是序列的起点int y = x + 1;while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中y++;}// 循环结束后，y-1 是最后一个在哈希集合中的数ans = Math.max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数}return ans;}
}

 

import java.util.*;
import java.io.*;
import static java.lang.Math.*;
/*
100 4 200 1 3 2*/
public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));String[] nums_s = br.readLine().split(",");int[] nums = new int[nums_s.length];for (int i = 0; i < nums_s.length; i++) {nums[i] = Integer.parseInt(nums_s[i]);}int l = 0, r = 1;for (;r<nums.length;r++) {if(nums[l] == 0 && nums[r] != 0){//交换两个数字int temp = nums[l];nums[l] = nums[r];nums[r] = temp;l++;//r会自动++}else if(nums[l] == 0 && nums[r] == 0)continue;else l++;}
//        pw.print(nums);//数组的话打印出来的是地址pw.println(Arrays.toString(nums));br.close();pw.close();}
}

这两种双指针的起点不一样

class Solution {public void moveZeroes(int[] nums) {int l = 0, r = 1;for (;r<nums.length;r++) {if(nums[l] == 0 && nums[r] != 0){//交换两个数字int temp = nums[l];nums[l] = nums[r];nums[r] = temp;l++;//r会自动++}else if(nums[l] == 0 && nums[r] == 0)continue;else l++;}}
}

impl Solution {pub fn move_zeroes(nums: &mut Vec<i32>) {let mut i0 = 0;for i in 0..nums.len() {if nums[i] != 0 {nums.swap(i, i0);i0 += 1;}}}
}

利用双指针的方法 面积与长度和较小的那个高度有关系  左指针向右移动 右指针向左移动

只考虑较小高度变大的情况 因为长度减小的同时 如果想让面积变大 只能让高度变高

public class Solution {public int maxArea(int[] height) {int l = 0, r = height.length - 1;int ans = 0;while (l < r) {int area = Math.min(height[l], height[r]) * (r - l);ans = Math.max(ans, area);if (height[l] <= height[r]) {++l;}else {--r;}}return ans;}
}

import java.util.*;
import java.io.*;
import static java.lang.Math.*;
/*
100 4 200 1 3 2*/
public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));String[] nums_s = br.readLine().split(",");int[] height = new int[nums_s.length];for (int i = 0; i < nums_s.length; i++) {height[i] = Integer.parseInt(nums_s[i]);}int l = 0, r = height.length - 1;int ans = 0;while (l < r) {int area = Math.min(height[l], height[r]) * (r - l);ans = Math.max(ans, area);if (height[l] <= height[r]) {//较小的边走++l;}else {--r;}}
//        return ans;pw.println(ans);br.close();pw.close();}
}

想想这个写法为什么错了？ 

class Solution {

    public int maxArea(int[] height) {

        int l = 0, r = height.length - 1;

        int min_hei = Integer.MAX_VALUE;

        int ans = 0;

        while (l < r) {

            min_hei = Math.min(height[l], height[r]);

            int len = r - l ;

            ans = Math.max(ans, len * min_hei);

            int deltal = (l + 1 < height.length) ? height[l + 1] - height[l] : 0;

            int deltar = (r - 1 >= 0) ? height[r - 1] - height[r] : 0;

            if (deltar <= 0 && deltal <= 0) {

                break; // 如果两边的高度差都不大于0，则无法扩展窗口

            }

            if (deltar > deltal) {

                r--;

            } else {

                l++;

            }

        }

        return ans;

    }

}

因为不能看哪个增加的多就去动哪个 这样没有遍历全部情况 更不能因为不增加了就不往后查了

这样的话如果来一个突变 那么就又有可能变得更大

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);//排序List<List<Integer>> ans = new ArrayList<List<Integer>>();//枚举nfor(int i = 0; i < nums.length; i++){//去重 如歌和上一次的数字一样 那我们就去下一个if(i>0 && nums[i] == nums[i-1]){//注意这里只能这样写 不能在上面i=1 否则会漏掉continue;}int target = -nums[i];//双指针//右端点int k = nums.length-1;//枚举j 左端点for(int j = i+1; j < k; j++){//需要与上一次枚举的数不同if(j>i+1 && nums[j] == nums[j-1]){continue;}while(j<k&&(nums[j]+nums[k]>target)){k--;}if(j==k)break;//说明没有这样的组合if(nums[j]+nums[k]==target){List<Integer> list = new ArrayList<Integer>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);ans.add(list);}}}return ans;}
}

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));String[] nums_s = br.readLine().split(",");int[] nums = new int[nums_s.length];for (int i = 0; i < nums_s.length; i++) {nums[i] = Integer.parseInt(nums_s[i]);}Arrays.sort(nums);//排序List<List<Integer>> ans = new ArrayList<List<Integer>>();//枚举nfor(int i = 0; i < nums.length; i++){//去重 如歌和上一次的数字一样 那我们就去下一个if(i>0 && nums[i] == nums[i-1]){//注意这里只能这样写 不能在上面i=1 否则会漏掉continue;}int target = -nums[i];//双指针//右端点int k = nums.length-1;//枚举j 左端点for(int j = i+1; j < k; j++){//需要与上一次枚举的数不同if(j>i+1 && nums[j] == nums[j-1]){continue;}while(j<k&&(nums[j]+nums[k]>target)){k--;}if(j==k)break;//说明没有这样的组合if(nums[j]+nums[k]==target){List<Integer> list = new ArrayList<Integer>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);ans.add(list);}}}pw.println(ans);br.close();pw.close();}
}

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));String[] nums_s = br.readLine().split(",");int[] height = new int[nums_s.length];for (int i = 0; i < nums_s.length; i++) {height[i] = Integer.parseInt(nums_s[i]);}int ans = 0;int len = height.length;if(len<3)pw.println("0");int[] left_max_arr = new int[len];int[] right_max_arr = new int[len];left_max_arr[0] = height[0];right_max_arr[len-1] = height[len-1];for(int i=1;i<len;i++){left_max_arr[i] = Math.max(left_max_arr[i-1],height[i]);}for(int i=len-2;i>=0;i--){right_max_arr[i] = Math.max(right_max_arr[i+1],height[i]);}for(int i=0;i<len;i++){ans += Math.min(left_max_arr[i],right_max_arr[i]) - height[i];}pw.println(ans);br.close();pw.close();}
}

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));String[] nums_s = br.readLine().split(",");int[] height = new int[nums_s.length];for (int i = 0; i < nums_s.length; i++) {height[i] = Integer.parseInt(nums_s[i]);}//找到一根比前面柱子高的柱子才可以积水Stack<Integer> st = new Stack<Integer>();int i = 0,ans = 0;while(i<height.length){while(!st.isEmpty() && height[i] > height[st.peek()]){//栈不为空 且现在这个柱子高于上一个柱子的高度int top = st.pop();if(st.empty())break;int dis = i - st.peek() + 1 - 2;//想一下int bounded_height = Math.min(height[i],height[st.peek()])-height[top];//这个水坑的两侧高度的最小值减去这个坑的石块ans += bounded_height * dis;}st.push(i++);}pw.println(ans);
//        return ans;br.close();pw.close();}
}

import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));String[] nums_s = br.readLine().split(",");int[] height = new int[nums_s.length];for (int i = 0; i < nums_s.length; i++) {height[i] = Integer.parseInt(nums_s[i]);}//双指针int l = 0 ,r = height.length-1;int l_mx = 0,r_mx = 0,ans = 0;while(l<r){if(height[l]<height[r]){//说明右可以给左兜底 左指针可以放心大胆的走if(height[l] > l_mx)l_mx = height[l];else ans += l_mx-height[l];l ++ ;}else{//说明左可以给右兜底 //右指针可以放心大胆的走if(height[r] > r_mx)r_mx = height[r];else ans += r_mx-height[r];r -- ;}}return ans;
//        pw.println(ans);br.close();pw.close();}
}