力扣 (LeetCode)-合并两个有序数组,字典,散列表

function Dictionary() {
 var items = {};
}

this.has = function(key) {
 return key in items;
);

// 将value设为items对象的key属性的值
this.set = function(key, value) { 
 items[key] = value; 
};

this.delete= function(key) { 
 if (this.has(key)) { 
 delete items[key]; 
 return true; 
 } 
 return false; 
};

this.get = function(key) { 
// 通过查找key值
 return this.has(key) ? items[key] : undefined; 
};

this.values = function() { 
 var values = []; 
 
 for (var k in items) { //遍历items对象的所有属性值
     if (this.has(k)) { 
     // 使用has函数来验证key确实存在
         values.push(items[k]); //将它的值加入values数组
     } 
 } 

 return values; 
};

this.keys = function() { 
 return Object.keys(items); 
};

this.getItems = function() { 
 return items; 
}

var dictionary = new Dictionary(); 
dictionary.set('da1', 'da1@email.com'); 
dictionary.set('da2', 'da2@email.com'); 
dictionary.set('da3', 'da3@email.com');

console.log(dictionary.has('da1'));
console.log(dictionary.size());
console.log(dictionary.keys()); 
console.log(dictionary.values()); 
console.log(dictionary.get('da2'));

dictionary.delete('da1');

// 使用数组来表示我们的数据结构
function HashTable() { 
 var table = []; 
}

// HashTable类中的一个私有方法
var loseloseHashCode = function (key) { 
// 给定一个key参数，我们就能根据组成key的每个字符的ASCII码值的和得到一个数字
// 需要一个变量来存储这个总和
 var hash = 0; 
 
 for (var i = 0; i < key.length; i++) { //遍历key 
 hash += key.charCodeAt(i); 
 //使用JavaScript的String类中的charCodeAt方法 
 } 

 return hash % 37; 
 //为了得到比较小的数值，我们会使用hash值和一个任意数做除法的余数
};

this.put = function(key, value) { 

 var position = loseloseHashCode(key); 
 //根据所创建的散列函数计算出它在表中的位置
 
 console.log(position + ' - ' + key); 
 table[position] = value; 
 //将value参数添加到用散列函数计算出的对应的位置上

};

this.get = function (key) { 
// 使用所创建的散列函数来求出给定key所对应的位置
// 根据这个位置从数组table中获得这个值
 return table[loseloseHashCode(key)]; 
};

this.remove = function(key) { 
// 求出元素的位置
 table[loseloseHashCode(key)] = undefined; 
};

// 实现print的方法
this.print = function() { 

 for (var i = 0; i < table.length; ++i) { //遍历数组中的所有元素 
     if (table[i] !== undefined) { //当某个位置上有值的时候
         console.log(i + ": " + table[i]);//输出位置和对应的值
     } 
 } 
};

// 在HashTable类内部定义
var ValuePair = function(key, value){ 
 this.key = key; 
 this.value = value; 
 this.toString = function() { 
 return '[' + this.key + ' - ' + this.value + ']';
 } 
};

this.put = function(key, value){ 

 var position = loseloseHashCode(key); 
 
 if (table[position] == undefined) { //将验证要加入新元素的位置是否已经被占据 
 table[position] = new LinkedList(); 
 // 会在这个位置上初始化一个LinkedList类的实例
 } 
 table[position].append(new ValuePair(key, value)); 
 //实现的append方法向LinkedList实例中添加一个ValuePair实例（键和值）
};

this.get = function(key) { 

 var position = loseloseHashCode(key); 
 
 if (table[position] !== undefined){ 
 //确定在特定的位置上是否有元素存在 
 //遍历链表来寻找键/值
 var current = table[position].getHead(); //获取链表表头的引用 
 while(current.next){ //从链表的头部遍历到尾部
 // Node链表包含next指针和element属性
 if (current.element.key === key){ 
 //current.element.key来获得Node链表的key属性
 
 return current.element.value; 
 //如果key值相同，就返回Node的值
 } 
 current = current.next; //如果不相同，就继续遍历链表，访问下一个节点
 } 
 //检查元素在链表第一个或最后一个节点的情况
 if (current.element.key === key){
 return current.element.value; 
 } 
 } 
 return undefined;  
};

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let len1 = m - 1;
    let len2 = n - 1;
    let len = m + n - 1;
    while(len1 >= 0 && len2 >= 0) {
        // 注意--符号在后面，表示先进行计算再减1，这种缩写缩短了代码
        nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
    }
    function arrayCopy(src, srcIndex, dest, destIndex, length) {
        dest.splice(destIndex, length, ...src.slice(srcIndex, srcIndex + length));
    }
    // 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为len2+1
    arrayCopy(nums2, 0, nums1, 0, len2 + 1);
};

var merge = function (nums1, m, nums2, n) {
  // 设置一个指针，指针初始化指向nums1的末尾（根据#62，应该是index为 m+n-1 的位置，因为nums1的长度有可能更长）
  // 然后不断左移指针更新元素
  let current = m + n - 1;

  while (current >= 0) {
    // 没必要继续了
    if (n === 0) return;

    // 为了方便大家理解，这里代码有点赘余
    if (m < 1) {
      nums1[current--] = nums2[--n];
      continue;
    }

    if (n < 1) {
      nums1[current--] = nums1[--m];
      continue;
    }
    // 取大的填充 nums1的末尾
    // 然后更新 m 或者 n
    if (nums1[m - 1] > nums2[n - 1]) {
      nums1[current--] = nums1[--m];
    } else {
      nums1[current--] = nums2[--n];
    }
  }
};