leetcode233 数字1的个数

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
思路详见袁厨公众号 

  1. class Solution {
  2.     public int countDigitOne(int n) {
  3.         //高位
  4.         int high =n;
  5.         //低位
  6.         int low = 0;
  7.         //位数（个十百千万...）
  8.         int num = 1;
  9.         //当前位数上的数值
  10.         int curr = 0;
  11.         //计数
  12.         int count = 0;
  13.         while(high!=0){
  14.             curr = high % 10;
  15.             high /=10;
  16.             if(curr == 0) count +=high*num;
  17.             else if(curr == 1) count +=high*num+1+low;
  18.             else count+=(high+1)*num;
  19.             low += curr*num;
  20.             num *= 10;
  21.         }
  22.         return count;
  23.     }
  24. }

leetcode146 LRU 缓存机制

  1.     class LRUCache {
  3.         class DLinkedNode{
  4.             int key;
  5.             int value;
  6.             // 前驱结点
  7.             DLinkedNode prev;
  8.             // 后驱结点
  9.             DLinkedNode next;
  10.             public DLinkedNode(int key, int value){
  11.                 this.value = value;
  12.                 this.key = key;
  13.             }
  14.             public DLinkedNode(){};
  15.         }
  17.         // 双向链表头结点
  18.         private DLinkedNode head;
  19.         // 双向链表尾结点
  20.         private DLinkedNode tail;
  21.         // 当前存储量
  22.         private int size;
  23.         // 最大容量
  24.         private int capacity;
  25.         private Map<Integer, DLinkedNode> map = new HashMap<>();
  27.         public LRUCache(int capacity) {
  28.             this.capacity = capacity;
  29.             this.size = 0;
  30.             head = new DLinkedNode();
  31.             tail = new DLinkedNode();
  32.             head.next = tail;
  33.             tail.prev = head;
  34.         }
  36.         public int get(int key) {
  37.             DLinkedNode node = map.get(key);
  38.             if(node==null){
  39.                 return -1;
  40.             }
  41.             // 移动到头
  42.             removeToHead(node);
  43.             return node.value;
  44.         }
  46.         public void put(int key, int value) {
  47.             DLinkedNode node = map.get(key);
  48.             if(node!=null){
  49.                 node.value = value;
  50.                 removeToHead(node);
  51.             }else{
  52.                 node = new DLinkedNode(key,value);
  53.                 if(this.size>=capacity){
  54.                     map.remove(tail.prev.key);
  55.                     removeNode(tail.prev);
  56.                 }else{
  57.                     size++;
  58.                 }
  59.                 addNode(node);
  60.                 map.put(key, node);
  61.             }
  62.         }
  64.         // 移动结点到链表头部方法
  65.         public void removeToHead(DLinkedNode node){
  66.             removeNode(node);
  67.             node.prev = head;
  68.             node.next = head.next;
  69.             head.next.prev = node;
  70.             head.next = node;
  71.         }
  73.         // 移除结点方法
  74.         public void removeNode(DLinkedNode node){
  75.             node.prev.next = node.next;
  76.             node.next.prev = node.prev;
  77.         }
  79.         // 增加结点
  80.         public void addNode(DLinkedNode node){
  81.             node.next = head.next;
  82.             node.prev = head;
  83.             head.next.prev = node;
  84.             head.next = node;
  85.         }
  86.     }