# 算法

**Repository Path**: dapeng15042435737/algorithm

## Basic Information

- **Project Name**: 算法
- **Description**: 自己平时利用空闲时间做的算法练习。
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-10-28
- **Last Updated**: 2021-11-30

## Categories & Tags

**Categories**: Uncategorized

**Tags**: 算法, JavaScript

## README

# 算法

#### 介绍
自己平时利用空闲时间做的算法练习。

### twoSum 提交说明

 **题目** 

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

 **例：** 

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

 **算法思路：** 

这道题适合使用Map数据结构进行哈希查找，Map中存储值和索引的键值对，用9减去当前的值取得的结果在Map中进行哈希查找，如果找到证明匹配成功，
如果找不到，把当前值和索引放入Map中，继续对下一个值进行判断，以此类推直到匹配成功为止。

**代码实现：** 


```javascript
const twoSum = (nums, target) => {
    let result = [];
    //用Map来定义一个哈希表
    let m = new Map();
    let i = 0;
    for(;i<(nums.length-1);i++){
        let a = target - nums[i];
        if(m.has(a)){
            result.push(i);
            result.push(m.get(a));
            return result;
        }else{
            //如果差值不在哈希表中，则把当前的值和索引值放入Map中
            m.set(nums[i],i);
        }
    }
}
```


### pulsone 提交说明


 **题目** 

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

 **例：** 

输入：digits =  [1,2,3]; 输出：[1,2,4]
输入：digits =  [4,3,2,1];输出：[4,3,2,2]
输入：digits = [9];输出：[1,0]
输入：digits = [9,9,9,9];输出：[1,0,0,0,0]
输入：digits = [9,9,8,9];输出：[9,9,9,0]
输入：digits = [6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3];输出：[6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,4];

 **题目分析：** 

如果数组中的最后一个元素是9的话，数组的最后一个元素需要变成0，并且让前一个元素继续加一。
如果数组中的最后一个元素不是9的话，数组的最后一个元素直接加一就可以

 **算法思路：** 

从后向前循环比较数组中的元素是否是9，如果是9的话，就把当前这个元素pop出数组，同时向新数组放入0，如果不是9的话，就停止循环，直接把当前的数组加一。
循环结束后，digits数组就只剩下除了9以外并且已经加完一的元素了，接下来把digits数组和新数组合并就可以了。合并后的数组内容就是加一之后的结果。

 **代码实现：** 


```javascript
/**
 * @param {number[]} digits 
 * @return {number[]}
 **/
var plusOne = function(digits) {
    let digits2=[];
    while(digits.length-1>=0){   
        if(digits[digits.length-1]==9){
            digits.pop();
            digits2.push(0);
        }else{
            digits[digits.length-1]++;
            break;
        }
    }
    if(digits.length==0){
        digits=[1,...digits2];
    }else{
        digits=[...digits,...digits2];
    }
    return digits;
};
```

### 二进制求和(addBinary) 提交说明


 **题目** 

给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。。

 **例：** 

输入: a = "11", b = "1"
输出: "100"

输入: a = "1010", b = "1011"
输出: "10101"

 **题目分析：** 

输入的两个二进制字符串的长度可能不一样，下面这个算法只能实现int范围内的运算。

parseInt(a,2) + parseInt(b,2)).toString(2)


 **算法思路：** 

初始进位值变量为0，根据两个二进制字符串中最长字符串的长度，从最低位开始比较两个字符串的位值和进位值，

111情况时， 当前位置设为1，进位值设置位1
110情况时， 当前位置设为0，进位值设置位1
100情况时， 当前位置设为1，进位值设置位0
000情况时， 当前位置设为0，进位值设置位0

依次类推，循环比较全长度两个字符串的位值和进位变量，进位值初始是0，短字符串如果比较完毕的话，使用0参与运算。


```javascript
/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    let array_a = a.split('');
    let array_b = b.split('');
    let len = array_a.length>=array_b.length?array_a.length:array_b.length;
    let carry = 0, array_c = [], i = 1, c = [];
    let a1 = parseInt('0',2);
    let b1 = parseInt('0',2);
    for(i=1;i<=len;i++){
        a1 = parseInt(array_a[array_a.length-i],2)||parseInt('0',2);
        b1 = parseInt(array_b[array_b.length-i],2)||parseInt('0',2);
        c = (a1+b1+parseInt(carry,2)).toString(2).split('');
        carry = c.length>1?1:0;
        array_c.push(c[carry]);
    }
    if(carry){
        array_c.push(carry.toString());
    }
    return array_c.reverse().join('');
};
```

###  Sqrt(x) 提交说明


 **题目** 

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

 **例：** 

输入：x = 4
输出：2

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

 **算法思路：** 

从0开始循环，每循环一次都用当前的数进行平方运算，把平方运算结果和输入进行比较，
如果平方结果大于输入，则证明它的平方根是上一次的循环数，退出循环，返回上一个循环数
如果平方结果小于输入，需要对当前数加1，然后继续执行循环。
如果平方结果等于输入，则证明它的平方根是当前数，退出循环，返回当前数。

```javascript
/**
 * @param {number} x
 * @return {number}
 */
 var mySqrt = function(x) {
    let i = 0, j = 0;
    while(i<=x){
        j = i*i;
        if(j==x){
            break;
        }else if(j>x){
            i--;
            break;
        }
        i++;
    }
    return i;
};
```

###   删除排序链表中的重复元素(deleteDuplicates) 提交说明


 **题目** 

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。

 **例：** 

输入：1 -> 1 -> 2
输出：1 -> 2

输入：1 -> 1 -> 2 -> 3 -> 3
输出：1 -> 2 -> 3

 **算法思路：** 

准备两个循环，主循环进行链表的整体遍历，次循环进行剩余节点的遍历，
次循环要保证找到剩余节点中下一个不重复的节点，主循环负责把次循环
找到的不重复节点和上一个不重复节点进行连接，并开启下一个次循环的
遍历，直到所有的节点都遍历完成，遍历完的链表就是不重复的链表。


```javascript
var deleteDuplicates = function(head) {
    let head1 = head;
    let head2 = null;
    while((head1 != null) && (head1.next != null)){
        head2 = head1;
        while(head2.next != null){
            if(head2.val == head2.next.val){
                head2 = head2.next;
            }else{
                break;
            }
        }
        head1.next = head2.next;
        head1 = head1.next;
    }
    return head;
};
```

###   合并两个有序数组(merge) 提交说明


 **题目** 

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。


 **例：** 

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

nums1=[1,2,3,4,4,5,6,7,7,8,0,0,0] m=10 
nums2=[3,5,7] n=3
输出 =[1,2,3,3,4,4,5,5,6,7,7,7,8]

nums1 = [0,0,3,0,0,0,0,0,0] m=3
nums2 = [-1,1,1,1,2,3] n=6
输出 =[-1,0,0,1,1,1,2,3,3]

 **算法思路：** 

循环取得nums2的元素，使用折半查找方法找到它在nums1的位置。

```javascript
/**
 * @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) {
    if(nums1[0] == 0 && m == 0){
        let j = 0;
        while(j != n){
            nums1[j] = nums2[j];
            j++;
        }
        return;
    }
    let i = 0;
    while(i != n){
        find(nums1,m,nums2[i]);
        i++;
        m++;
    }
    nums1.splice(m,n);
};


const find = (num1, len, a) => {
    let low = 0;
    let hight = len - 1;
    let mid = 1;
    let found = false;
    if(a<num1[low]){
        mid = 0;
    }else if(a>num1[hight]){
        mid = hight+1;
    }else{
        if(hight > 1){
            while((hight-low) != 1){
                mid = Math.round((hight-low)/2) + low;
                if(a>num1[mid]){
                    low = mid;
                }else if(a<num1[mid]){
                    hight = mid;
                }else{
                    found = true;
                    break;
                }
            }
            if(!found){
                if(mid == low){
                    mid++;
                }
            }
        }
    }
    num1.splice(mid,0,a);
    return;
}
```


###   二叉树的中序遍历(inorderTraversal) 提交说明


 **题目** 

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

 **算法思路：** 

从根节点开始，做如下迭代处理。
先左，在中，后右。

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let ret = [];
    if(root != null){
        inorder(root,ret);
    }
    return ret;
};

const inorder = (node, ret) => {
    if(node != null){
        inorder(node.left, ret);
        ret.push(node.val);
        inorder(node.right, ret);
    }
    return;
}
```



###   相同的树(isSameTree) 提交说明


 **题目** 

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。


 **算法思路：** 

对两个树同时进行迭代进行中序遍历，
迭代过程中如果发生结构不一样或者值不一样的情况，立刻停止迭代，返回false.

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    return (inorder(p,q));
};

const inorder = (node1, node2) => {
    if(node1 != null && node2 != null){
        if(!inorder(node1.left, node2.left)){
            return false;
        }
        if(node1.val != node2.val){
            return false;
        }
        if(!inorder(node1.right, node2.right)){
            return false;
        }
    }else if(node1 == null && node2 != null){
        return false;
    }else if(node1 != null && node2 == null){
        return false;
    }
    return true;
}
```


###   对称二叉树(isSymmetric) 提交说明


 **题目** 

给定一个二叉树，检查它是否是镜像对称的。


 **算法思路：** 

对二叉树的左右子树进行递归，每次递归判断左子树和右子树的值是否相等。
如果相等则继续递归，否则直接返回failed
举例：节点1的左子树必须和节点2的右子树相等

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
 var isSymmetric = function(root) {
    return ismirror(root,root);
};

const ismirror = (node1,node2) => {
    if(node1 == null && node2 == null){
        return true;
    }
    if(node1 == null || node2 == null){
        return false;
    }
    if((node1.val == node2.val) &&
        ismirror(node1.left,node2.right) &&
        ismirror(node1.right,node2.left)){
        return true;
    }
    return false;
}
```


###   二叉树的最大深度(maxDepth) 提交说明


 **题目** 

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

 **算法思路：** 

通过递归左右子树方式来找出最大深度，当有子树的时候就把深度加1，
判断左右子树的深度，取大的那一个子树的深度值。

```javascript
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
 var maxDepth = function(root) {
    let depth = 0;
    if(root == null){
        return depth;
    }
    let left = maxDepth(root.left);
    let right = maxDepth(root.right);
    depth = left>=right?left:right; 
    return 1 + depth
};
```

https://github.com/youngyangyang04/leetcode-master