/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.limit = capacity || 2
  this.storage = {}
  this.keyList = []
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  if (this.storage.hasOwnProperty(key)) {
    let index = this.keyList.findIndex(k => k === key)
    this.keyList.splice(index, 1)
    this.keyList.push(key)
    return this.storage[key]
  } else {
    return -1
  }
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  // 判断容量
  if (this.keyList.length >= this.limit && !this.storage.hasOwnProperty(key)) {
    this.deleteLRU()
  }
  
  // 存储数据
  this.updateKeyList(key)
  this.storage[key] = value
};

LRUCache.prototype.deleteLRU = function () {
  delete this.storage[this.keyList.shift()]
}

LRUCache.prototype.updateKeyList = function (key) {
  if (this.storage.hasOwnProperty(key)) {
    var index = this.keyList.findIndex(k => key === k)
    this.keyList.splice(index, 1)
  }
  this.keyList.push(key)
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    if(numbers.length===0)
        return [];
    var left = 0,right = numbers.length-1;
    while(right>left){
        if(numbers[right]+numbers[left]>target)
            right--;
        else if(numbers[right]+numbers[left]<target)
            left++;
        else return [left+1,right+1];
    }
    return [];
};

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var number=[];
    var left = 0;
    var right = nums.length - 1 ;
    while(left < right ) {
        if(nums[left] + nums[right] === target) {
            return [left+1, right+1]
        } else if(nums[left] + nums[right] > target ) {
            right--;
        } else {
            left++;
        }
    } 
};

/**
 * @param {string} s
 * @return {number}
 */
var titleToNumber = function(s) {
    if (!s) {
        return 0
    }
    let list = s.split('')
    list = list.map((alpha, index) => (parseInt(alpha, 36) - 9) * Math.pow(26, list.length - index - 1))
    return list.reduce((acc, cur) => (acc + cur), 0)
}

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
    if (nums.every(n => !n)) {
        return '0'
    }
    return nums.sort((a, b) => {
        return Number('' + b + a) - Number('' + a + b)
    }).join('')
};

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  let dp = []
  if(!nums.length) {
      return 0
  }
  nums.forEach((n, i) => {
    dp[i] = Math.max((dp[i-2] || 0) + n, (dp[i-1] || 0))
  })
  return dp[nums.length - 1]
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
  if (!head) {
    return head
  }
  let array = listNodeToArray(head)
  array = array.filter(i => (i !== val))
  return arrayToListNode(array)
};


function listNodeToArray (head) {
  let array = []
  while (head) {
    array.push(head.val)
    head = head.next
  }
  return array
}

function  arrayToListNode(array) {
  if(!array || !array.length) {
    return null
  }
  
  let node
  let head = new ListNode(array[0])
  let pnode = head  //pnode变量用来保存前一个节点
  
  for(let i = 1; i < array.length; i++) {
    node = new ListNode(array[i])
    pnode.next = node   //将前一个节点的next指向当前节点
    pnode = node   //将node赋值给pnode
  }
  
  return head
}

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
  if (!head) {
    return head
  }
  let slow = new ListNode()
  let result = slow
  while (head) {
    if (head.val !== val) {
      slow.next = head
      slow = slow.next
    } else if (!head.next) {
      slow.next = null
    }
    head = head.next
  }
  return result.next
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  var nodeList = []
  if (!head) {
    return head
  }
  while (head.next) {
    nodeList.push(head)
    head = head.next
  }
  nodeList.push(head)
  nodeList.forEach((node, index) => {
    if (nodeList[index - 1]) {
      node.next = nodeList[index - 1]
    } else {
      node.next = null
    }
  })
  return nodeList[nodeList.length - 1]
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  if (!head) {
    return head
  }
  let parentNode = null
  while (head) {
    let current = new ListNode(head.val)
    current.next = parentNode
    if (head.next) {
      let next = new ListNode(head.next.val)
      next.next = current
    } else {
      let next = null
      return current
    }
    parentNode = current
    head = head.next
  }
  return head
};

/**
 * @param {number} s
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(s, nums) {
  var left = 0;
  var right = -1; // right 的起始位置很重要，这里选择-1 [left, right]这个区间刚开始是没有值的
  var tmpSum = 0;
  var minLength;

  // 循环停止的条件是左指针小于长度
  while (left < nums.length - 1) {
    if(tmpSum < s) {
      // 这里要注意边界的处理，当右指针移动到最后一个元素的时候结束
      if(right >= nums.length -1) {
        return minLength || 0;
      }
      right ++;
      // 这里tmpSum的计算也很巧妙，直接用累加的方式，节省计算量
      tmpSum = tmpSum + nums[right]
    } else {
      var tmp = right - left + 1;
      if(minLength) {
        if(tmp < minLength) {
          minLength = tmp;
        }
      } else {
        minLength = tmp;
      }
      // 左边指针移动减少sum的值
      tmpSum = tmpSum - nums[left];
      left ++;
    } 
  }
  if(!minLength) {
    return 0;
  }
  return minLength;
};

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
    if(num==0)
        return num;
    if(num%9==0)
        return 9;
    else return num%9;
};