＜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[]转化成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();
}
}