＜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 puteIfAbsent(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 puteIfAbsent(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[]转化成List Map<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>());//如果什么都没有就返回一个ArrayList list.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>>(); //枚举n for(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>>(); //枚举n for(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(); } }