算法刷题日志

从左下角开始找，比目标要小的就往右走，比目标要大的就往上走，等于就返回true

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int n = matrix.length-1;int m = 0;while(m<matrix[0].length&&n>=0){if(matrix[n][m]<target){m++;}else if(matrix[n][m]>target){n--;}else{return true;}}return false;}
}

class Solution {public void rotate(int[] nums, int k) {k=k%nums.length;reverse(nums,0,nums.length-1);reverse(nums,0,k-1);reverse(nums,k,nums.length-1);}public void reverse(int[]nums,int l ,int r){while(l<r){int tmp = nums[l];nums[l]=nums[r];nums[r]=tmp;l++;r--;}}
}

class Solution {public int compareVersion(String version1, String version2) {String[] ss1 = version1.split("\\.");String[]  ss2 = version2.split("\\.");int n =ss1.length;int m = ss2.length;int  i=0,j=0;while(i<n||j<m){int a=0,b=0;if(i<n)a=Integer.parseInt(ss1[i++]);if(j<m)b=Integer.parseInt(ss2[j++]);if(a!=b)return a>b?1:-1;}return 0;}
}

先判断合法不合法，合法就添加进队列，然后递归的方式去判断

class Solution {//画图理解public List<String> restoreIpAddresses(String s) {//定义表示一个字符长度的变量int len = s.length();//定义一个返回结果的集合List<String> res = new ArrayList<>();//如果当前字符长度大于12或者小于4都不满足if(len > 12 || len <4){return res;}//定义一个保存路径上的变量Deque<String> path = new ArrayDeque<>();//深度优先搜索dfs(s,len, 0, 4, path, res);//返回结果return res;}
//residue 是需要截取多少段public void dfs(String s, int len, int begin, int residue, Deque<String> path, List<String> res){//如果字符串已经遍历到最后了，并且已经切分为4段了，//就把当前路径上的元素加入到返回的结果集中if(begin == len){if(residue ==0){res.add(String.join(".", path));}return;}//begin表示遍历字符串从哪里开始for(int i = begin; i < begin+3; i++){//如果超出字符串的长度，就直接退出//begin，每次选择都是从之前选择的元素的下一个元素开始，if(i >= len){break;}//如果剩余元素大于ip最多能容纳的个数，就剪枝。if(len -i > residue * 3){continue;}//判断当前截取字符是否是小于0或者大于255//这里的begin和i，代表的是，这时候截取了几个字符//begin从哪里开始，i到哪里结束if(judgeIpSegment(s, begin, i)){//保留当前截取字符String currentIpSegment = s.substring(begin, i+1);//将当前路径上的元素加入到路径队列中path.addLast(currentIpSegment);//递归下一层dfs(s, len, i+1,residue -1, path, res);//剪枝path.removeLast();}}}private boolean judgeIpSegment(String s, int left, int right){//定义一个表示整个字符的长度int len = right - left +1;//如果截取的大于等于2的字符的开头为0，就直接falseif(len > 1 && s.charAt(left) == '0'){return false;}//定义返回结果的集合int res = 0;//拼接字符while(left <= right){//res*10 是为了将先加的字符默认比后面的字符大10倍，也就是位数是从小到大res = res * 10 + s.charAt(left) - '0';left++;}return res >= 0 && res <= 255;}
}

学习了灵神的题解，使用双向列表，加一个dummy的哨兵节点来处理，先初始化定义一个node节点。
然后定义好容量，和哈希表，用来记住key值，以便更换value。

class LRUCache {private static class Node{int key,value;Node pre,next;Node(int k,int v){key=k;value=v;}}private final int capacity;private final Node dummy = new Node(0,0);private final  Map<Integer,Node> keyNode = new HashMap<>();public LRUCache(int capacity) {this.capacity=capacity;dummy.pre=dummy;dummy.next=dummy;}public int get(int key) {Node node = getNode(key);return node!=null?node.value:-1;}public void put(int key, int value) {Node node = getNode(key);if(node!=null){node.value=value;return;}node =new Node(key,value);keyNode.put(key,node);pushFront(node);if(keyNode.size()>capacity){Node backNode = dummy.pre;keyNode.remove(backNode.key);remove(backNode);}   }private Node getNode(int key){if(!keyNode.containsKey(key)){return null;}Node node = keyNode.get(key);remove(node);pushFront(node);return node;}private void remove(Node x){x.pre.next = x.next;x.next.pre = x.pre;}private void pushFront(Node x){x.pre=dummy;x.next=dummy.next;x.pre.next=x;x.next.pre=x;}}/*** 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);*/