53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组
是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
/**
* @author XiSoil
* @date 2024/04/15 16:00
*执行分布用时1ms,击败的100.00%Java用户
*消耗内存分布55.54MB,击败的94.78%Java用户
**/
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int currentSum = nums[0];
for (int i = 1; i < nums.length; i++) {
currentSum = Math.max(nums[i], currentSum + nums[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
动态规划秒了
706. 设计哈希映射
不使用任何内建的哈希表库设计一个哈希映射（HashMap）。
实现 MyHashMap 类：
MyHashMap() 用空映射初始化对象
void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。
示例：
输入：
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
输出：
[null, null, null, 1, -1, null, 1, null, -1]
解释：
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1); // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(3); // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2); // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2); // 返回 -1（未找到），myHashMap 现在为 [[1,1]]
提示：
0 <= key, value <= 10^6
最多调用 10^4 次 put、get 和 remove 方法
/**
* @author XiSoil
* @date 2024/04/15 15:24
*执行分布用时139ms,击败的6.95%Java用户
*消耗内存分布56.88MB,击败的5.00%Java用户
**/
class MyHashMap {
int size = 65023;
int length = 1701031;
Integer[][] MAP;
//第一个值用来存储keys,第二个值用来存储对应的values
public int hash(int index){
return index % size;
}
public MyHashMap() {
MAP = new Integer[length][2];//最多进行10000次put操作,所以最多10000个key
}
public void put(int key, int value) {
int index = hash(key);
while(MAP[index][0] !=null){
if (MAP[index][0] == key) {
MAP[index][1] = value;
return;
}else {
index = (index+1) % size;
}
}
MAP[index][0] = key;
MAP[index][1] = value;
}
public int get(int key) {
int index = hash(key);
if (MAP[index][0] == null)
return -1;
//下标相等、且键也要相等才能判断为指向同一个key-value对
if (MAP[index][0] == key)
return MAP[index][1];
else {
index = (index + 1) % size;
while (index != hash(key)) {
if (MAP[index][0] == null){
index = (index+1)%size;
}else if (MAP[index][0] == key) {
return MAP[index][1];
}
else {
index = (index + 1) % size;
}
}
return -1;
}
}
public void remove(int key) {
int index = hash(key);
if (MAP[index][0] == null)
return;
if (MAP[index][0] == key) {
MAP[index][0] = null;
MAP[index][1] = null;
} else {
index = (index + 1) % size;
while (index != hash(key)) {
if (MAP[index][0] == null){
index = (index+1)%size;
}else if (MAP[index][0] == key) {
MAP[index][0] = null;
MAP[index][1] = null;
return;
}else {
index = (index + 1) % size;
}
}
}
}
}
HashMap求解，空间和时间的开销都比较大
/**
* @author XiSoil
* @date 2024/04/15 15:51
*执行分布用时18ms,击败的73.99%Java用户
*消耗内存分布46.81MB,击败的61.39%Java用户
**/
class MyHashMap {
private class Pair {
private int key;
private int value;
public Pair(int key, int value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
// public void setKey(int key){
// this.key = key;
// }
}
private final int BASE = 769;
private LinkedList[] data;
public int hash(int key) {
return key % BASE;
}
public MyHashMap() {
data = new LinkedList[BASE];
for (int i = 0; i < BASE; i++) {
data[i] = new LinkedList<>();
}
//初始化一个新的链表数组,并将每个链表都初始化为空链表
}
public void put(int key, int value) {
int index = hash(key);
//获取data[index]链表的迭代器
Iterator<Pair> iterator = data[index].iterator();
//遍历链表,如果存在key相同的Pair,则更新value,否则添加新的Pair
while (iterator.hasNext()) {
Pair pair = iterator.next();
if (pair.getKey() == key) {
pair.setValue(value);
return;
}
}
//data[index].addLast(new Pair(key, value));
data[index].offerLast(new Pair(key, value));
}
public int get(int key) {
int index = hash(key);
Iterator<Pair> iterator = data[index].iterator();
while (iterator.hasNext()) {
Pair pair = iterator.next();
if (pair.getKey() == key) {
return pair.getValue();
}
}
return -1;
}
public void remove(int key){
int index = hash(key);
Iterator<Pair> iterator = data[index].iterator();
while(iterator.hasNext()){
Pair pair = iterator.next();
if(pair.getKey() == key){
data[index].remove(pair);
return;
}
}
}
}
HashMap结合LinkList节省了空间
2216. 美化数组的最少删除数
给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：
nums.length 为偶数
对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立
注意，空数组同样认为是美丽数组。
你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。
返回使 nums 变为美丽数组所需删除的 最少 元素数目。
public int minDeletion(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
if (len == 1) {
return 1;
}
int count = 0;
int right = 0;
int left = 1;
for (; left < len; ) {
if (nums[right] == nums[left]){
left++;
count++;
}else {
right = left+1;
left = right+1;
}
}
if ((len-count)%2 == 1)
count++;
return count;
}
双指针+贪心
标签：三则,index,MAP,int,nums,value,key,LeetCode From： https://www.cnblogs.com/xxaxf/p/18137151