# algorithm-log

**Repository Path**: bishugui/algorithm-log

## Basic Information

- **Project Name**: algorithm-log
- **Description**: 刷题
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-03-23
- **Last Updated**: 2024-01-29

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# algorithm-log

刷题

1. 一刷：可参考解法，AC为主
2. 二刷：如若一刷非独立实现，则重写；已独立实现则优化
3. 三刷：巩固、变更语言
4. java代码目录：/src/
5. c++代码目录：/cpp/

> 文件命名规则：<题号>-<题目名>.java
## 参考

1. [刷题笔记 | LeetCode Cookbook](https://books.halfrost.com/leetcode/)
2. [代码随想录](https://programmercarl.com/)

# 记录

记录按首刷时间升序

| 题目                       | 分类 | 难度 | 代码文件名             | 首刷时间/语言/是否参考   | 备注 |
| -------------------------- | ---- | ---- | ---------------------- | ------------------------ | ---- |
| 1.两数之和                 | 数组 | 简单 | /TwoSum.java           | 2022/04/03 23:32,java,否 |      |
| 26. 删除有序数组中的重复项 | 数组 | 简单 | /RemoveDuplicates.java | 2022/04/04 15:36,java,否 |      |
| 27. 移除元素               | 数组 | 简单 | /RemoveElement.java    | 2022/04/05 11:44,java,否 |      |
| 35. 搜索插入位置           | 数组 | 简单 | /SearchInsert.java     | 2022/04/06 23:37,java,否 |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |
|                            |      |      |                        |                          |      |



## 1. 两数之和

[题目链接](https://leetcode-cn.com/problems/two-sum/) 数组 简单 

给定一个整数数组 `nums` 和一个整数目标值 `target`，请你在该数组中找出 **和为目标值** *`target`* 的那 **两个** 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

**示例 1：**

```
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
```

**示例 2：**

```
输入：nums = [3,2,4], target = 6
输出：[1,2]
```

**示例 3：**

```
输入：nums = [3,3], target = 6
输出：[0,1]
```

提示：

* 2 <= nums.length <= 10^4

* -10^9 <= nums[i] <= 10^9

* -10^9 <= target <= 10^9

* 只会存在一个有效答案

  

**解法1：**思路：暴力，双for循环遍历,O(n^2) -> 去除多余遍历 O(nlogn)

提交时间：2022/04/03 23:32

执行用时：49 ms, 在所有 Java 提交中击败了38.57%的用户
内存消耗：41.1 MB, 在所有 Java 提交中击败了71.07%的用户

```java
public int[] twoSum(int[] nums, int target) {
    int len = nums.length;
    int[] result = new int[2];

    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            if (j == i) {
                continue;
            }
            if (nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
                break;
            }
        }
    }
    return result;
}
```

**优化：**思路：使用HashMap,保存<target-nums[i],i>,保存前检测是否存在，存在则说明找到了,O(n)；[由于Hash检测的时间复杂度为O(1)]

```java
public int[] twoSum(int[] nums, int target) {
    int len = nums.length;
    int[] result = new int[2];

    HashMap<Integer,Integer> map = new HashMap<>();

    for (int i = 0; i < len; i++) {
        //检测存在
        if(map.containsKey(nums[i])){
            result[0] = map.get(nums[i]);
            result[1] = i;
            break;
        }
        //map中不存在则保存
        map.put(target-nums[i], i);
    }
    return result;
}
```

提交时间：2022/04/04 10:08

执行用时：1 ms, 在所有 Java 提交中击败了99.42%的用户

内存消耗：41.1 MB, 在所有 Java 提交中击败了71.54%的用户

## 26. 删除有序数组中的重复项

[题目链接](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/) 数组 简单

给你一个 **升序排列** 的数组 nums ，请你[ **原地**](http://baike.baidu.com/item/原地算法) 删除重复出现的元素，使每个元素 **只出现一次** ，返回删除后数组的新长度。元素的 **相对顺序** 应该保持 **一致** 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 [**原地** ](https://baike.baidu.com/item/原地算法)**修改输入数组** 并在使用 O(1) 额外空间的条件下完成。

**判题标准:**

系统会用下面的代码来测试你的题解:

```
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}
```

如果所有断言都通过，那么您的题解将被 **通过**。

```
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

实例2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：
0 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按 升序 排列
```

**解题**

```java
public int removeDuplicates(int[] nums) {
    int i=0,j;
    if(nums.length <= 1){
        return nums.length;
    }
    for(j = 1;j < nums.length;j++){
        //检测下一个是否与nums[i]不同
        while(nums[j] == nums[i]){
            j++;
            if(j >= nums.length){
                break;
            }
        }
        if(j >= nums.length){
            break;
        }
        i++;
        nums[i] = nums[j];
    }

    return i+1;
}
```

提交时间：2022/04/04 15:36

执行用时：1 ms, 在所有 Java 提交中击败了30.87%的用户

内存消耗：43.2 MB, 在所有 Java 提交中击败了9.13%的用户

**优化一：**快慢双下标

特别注意：直接访问成员变量(j < nums.length)会增加耗时，需要改写成int len = nums.length;j<len;

**以HotSpot VM为例，答案是在数组对象的对象头里有一个_length字段，记录数组长度。arraylength字节码的实现只要去读那个_length字段即可，但是依然会增加耗时**

```java
public int removeDuplicates(int[] nums) {
    int i=0,j,len = nums.length;
    if(len <= 1){
        return len;
    }
    for(j = 1;j < len;j++){
        //检测下一个是否与nums[i]不同
        if(nums[j] == nums[i]){
            continue;
        }
        nums[++i] = nums[j];
    }

    return i+1;
}
```

提交时间：2022/04/04 15:52

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：42.6 MB, 在所有 Java 提交中击败了69.02%的用户



## 27. 移除元素

[题目链接](https://leetcode-cn.com/problems/remove-element/) 数组 简单

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

```java
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
```

示例一：

```java
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
```

示例二：

```java
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
```

提示：

- `0 <= nums.length <= 100`
- `0 <= nums[i] <= 50`
- `0 <= val <= 100`

**解题：**

提交一：指定结果下标，与数组下标形成快慢双下标

```java
public int removeElement(int[] nums, int val) {
    int len = nums.length;
    if(len == 0){
        return 0;
    }
    int resultLen = 0;
    for(int i = 0;i < len;i++){
        //如果相等则跳过
        if(nums[i] == val){
            continue;
        }
        //让结果元素末尾等于当前元素
        nums[resultLen++] = nums[i];
    }
    return resultLen;
}
```

提交时间：2022/04/05 11:44

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：39.7 MB, 在所有 Java 提交中击败了60.90%的用户



## 35. 搜索插入位置

[题目链接](https://leetcode-cn.com/problems/search-insert-position/) 数组 简单

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

```
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
```

提示

* 1 <= nums.length <= 10^4
* -10^4 <= nums[i] <= 10^4
* nums 为 无重复元素 的 升序 排列数组
* -10^4 <= target <= 10^4

**解答：**二分查找+条件判断

```java
public static int searchInsert(int[] nums, int target) {
    int left = 0,right = nums.length-1,temp = 0;
    if(target <= nums[0]){
        return 0;
    }
    if(target > nums[right]){
        return right + 1;
    }
    while(left < right){
        temp = (left + right) / 2;
        if(nums[temp] == target){
            return temp;
        }
        if(target < nums[temp]){
            //右浮标向左移
            right = temp - 1;
        }else{
            //左浮标向右移
            left = temp + 1;
        }
    }
    if(target <= nums[left]){
        return left;
    }
    return left + 1;
}
```