文章目录
- 引言
- 复习
- Java实现——LRU缓存
- 对照实现
- Java实现——搜索插入位置
- java实现
- 知识补充
- 新作
- 搜索二维矩阵
- 个人实现
- 参考实现
- 总结
引言
- 以后都要向使用Java刷算法进行过滤了，所以今天主要是复习为主，复习两道之前做过的题目，然后做两道新的题目。
- 今天继续加油吧！
复习
Java实现——LRU缓存
- 第一次学习链接
- 第二次学习链接
- 题目链接
对照实现
- 如果要使用Java实现，得学这些一下，对照着实现！Java的语法是知道的，但是忽然间写这个，还是有点不习惯的！
知识补充
Map接口具有哪些具体的实现对象？有什么区别？
-
HashMap
- 基于哈希表实现，允许null的键
- 插入时间复杂度是O（1），适用于需要快速访问元素时的操作
- 非线程安全
-
LinkedHashMap
- 继承HashMap，底层是用双向链表维护节点
- 时间复杂度是O（1），适用于需要按照插入顺序或者访问顺序遍历元素使用。
-
TreeMap
- 基于红黑树实现，按key的自然顺序或者提供的比较器进行排序，线程不安全
- O（log N），按照键的顺序访问元素使用
-
ConcurrentHashMap
- 线程安全，使用分段锁机制提高并发性能
- 多线程环境下，比Hashtable好用
Java中如何表示空指针
- null不是None
- 有啥区别？
好吧，东西太多了，记混了，以后就用Java和python了，类的声明方法也是的，用的太多了，就混了
使用HashMap实现的相关方法
- 如何插入对应的值？
// 创建一个HashMap
HashMap<Integer, String> hashMap = new HashMap<>();
// 插入键值对
hashMap.put(1, "Value1");
hashMap.put(2, "Value2");
hashMap.put(3, "Value3");
- 如何删除对应的值？
// 删除键值对
String removedValue = hashMap.remove(2);
- 如何判定对应的值是否存在？
// 判定键是否存在
boolean containsKey2 = hashMap.containsKey(2);
boolean containsKey4 = hashMap.containsKey(4);
具体实现
class LRUCache {
class Node{
int key,val;
Node right,left;
public Node(int _key,int _val){
key = _key;
val = _val;
right = null; // how to represent nulll pointer in Java
left = null;
}
}
Map<Integer,Node> dict;
Node L,R;
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
this.L = new Node(-1,-1);
this.R = new Node(-1,-1);
dict = new HashMap<>();
L.right = R;
R.left = L;
}
public void remove(Node temp){
// remove the temp from the list
temp.left.right = temp.right;
temp.right.left = temp.left;
}
public void insert(Node temp){
// insert the temp to the first
temp.right = L.right;
temp.left = L;
L.right.left = temp;
L.right = temp;
}
public int get(int key) {
// judge whether the key exists
if(!dict.containsKey(key)) return -1;
// refresh the key and return the value
Node temp = dict.get(key);
remove(temp);
insert(temp);
return temp.val;
}
public void put(int key, int value) {
// judge whether the key-value exists
if(dict.containsKey(key)){
// update the key-value
Node temp = dict.get(key);
temp.val = value;
remove(temp);
insert(temp);
return ;
}
// insert the key-value into cache
Node temp = new Node(key,value);
dict.put(key,temp);
insert(temp);
// judge whether the cache is full
if(dict.size() > capacity){
Node toRemove = R.left;
// remove(R.left);
remove(toRemove);
// dict.remove(R.left.key);
dict.remove(toRemove.key);
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
最后这里真的是蠢死了，我没有发现他居然是已经删除了节点，R.left已经发生了变化，弄了半天！
总结
- 以后都用Java了，一方面是复习语法特性，另外一方面，Java的语法写起来，确实比C++好用太多了，还是用Java吧！
Java实现——搜索插入位置
- 这道题做了一遍，这一次单纯是使用java重新刷一下
- 第一次学习链接
- 单纯就是一个二分搜索的模版题
java实现
如何对Java中的数组，获取长度
- 使用length，不是方法
具体实现
class Solution {
public int searchInsert(int[] nums, int target) {
int l = 0,r = nums.length - 1,mid = 0;
while(l <= r){
mid = (l + r) >> 1;
if(nums[mid] < target) l = mid + 1;
else if(nums[mid] > target) r = mid - 1;
else return mid;
}
return l;
}
}
知识补充
C++中vector，对应Java中的什么？
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Integer> a = new ArrayList();
a.add(1);
a.add(2);
a.add(3);
a.add(4);
a.add(5);
System.out.println(a.get(3));
System.out.println(a.size());
for(int x : a)
System.out.println(x);
System.out.println("Hello world!"
);
}
}
其他实现
C++中的priority_queue对应Java中的什么？
import java.util.PriorityQueue;
import java.util.Comparator;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.add(1);
pq.add(2);
pq.add(3);
while(!pq.isEmpty()){
System.out.println(pq.poll());
}
}
}
- 这里是判定是否为空是isEmpty，不是empty两个方法
- poll是会返回队列头的元素，然后在弹出，和pop不一样
新作
搜索二维矩阵
题目链接
注意
- 矩阵从左到右是严格递增的，所以不存在相等的情况
- 每一行开头的元素都是大于上一行最后一个元素
- 返回在列表中能否找到对应的元素
个人实现
- 这道题就是一个两次二分查找，现在第一行进行二分查找，然后在在当前行中进行二分查找，不过我可能对Java中的二维数组操作不是很习惯！
具体实现代码如下
class Solution {
public boolean searchMatrix(int[][] mat, int tar) {
// find the line
int m = mat.length,n = mat[0].length;
int up = 0 , down = mat.length - 1,midRow = 0;
while(up < down){
midRow = (up + down ) >> 1;
if(mat[midRow][0] < tar) up = midRow + 1;
else if(mat[midRow][0] > tar) down = midRow - 1;
else return true;
}
// judge the mid condition
if(up - 1 >= 0 && mat[up - 1][n - 1] >= tar && mat[up -1][0] <= tar ) up --;
else if (up + 1 < m - 1 && mat[up + 1][n - 1] >= tar && mat[up + 1][0] <= tar ) up ++;
// find the col
int l = 0,r = mat[0].length - 1,midCol = 0;
while(l <= r){
midCol = (l + r) >>1 ;
if(mat[up][midCol] > tar) r = midCol - 1;
else if(mat[up][midCol] < tar) l = midCol + 1;
else return true;
}
if(mat[up][midCol] == tar) return true;
return false;
}
}
写是写完了，但是有点小问题
- 第一个判定索引那里，会出现异常情况，这里还是看一下其他的怎么求的吧！
- 这里是将整个二维矩阵逐行进行拼接，将二维矩阵转成一维矩阵，然后根据一维有序数组，使用二分查找目标值。
- 这里专门提到了二分模板，这里也贴一下，自己老是对边界值有误解
参考实现
二分查找的模板
- 有x找到x，否则找到一个最接近x，并且比x大的数字
- l == r的时候退出循环
- l是最终的目标值，返回的是最接近x并且第一个比x大的数字
int l = 1,r = n;
while(l < r){
int mid = (l + r) >>1;
if(a[mid] >= x) r = mid;
else l = mid + 1;
}
- 有x找到x，否则找到第一个最接近x，并且比x小的数字
- 具体条件同上
int l = 1,r = n;
while(l < r){
int mid = (l + r) >>1;
if(a[mid] <= x) l = mid;
else r = mid - 1;
}
- 这里背诵的话，基本上是通过的返回条件的要求确定，返回的第一个大于他的数字，就是符号就是大于等于，小于即使小于等于。
左加大，右减小
数组坐标转换
- 行数 = index / 一行多少个元素
- 列数 = index % 一行多少个元素
参考实现代码
class Solution {
public boolean searchMatrix(int[][] mat, int tar) {
// jedge the edge condition
if(mat.length == 0 || mat[0].length == 0) return false;
// convert the idx
int m = mat.length,n = mat[0].length;
int l = 0,r = m * n -1;
while(l < r){
int mid = (l +r) >> 1;
if(mat[mid / n][mid % n] >= tar) r = mid;
else l = mid + 1;
}
return mat[l / n][l % n] == tar;
}
}
- 这个模板还是挺好记的，继续加油吧！
总结
- 今天搞得太晚了，已经一点钟了，再不睡，明天又没有精神，不行的！今天主要是加班搞定了MySQL中的索引，明天早上在起来 背背对应的八股，应该就够了。
- 后续再看需要什么，在补充什么，加油，尽快把简历还有项目弄完！
