# leetcode

**Repository Path**: jiuqi0822/leetcode

## Basic Information

- **Project Name**: leetcode
- **Description**: 记录自己刷题的过程
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2021-07-05
- **Last Updated**: 2021-07-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# leetcode

## 介绍

记录自己刷题的过程

## 题

### T704二分查找

#### 问题

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

**示例 1:**

```
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
```

**示例 2:**

```
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
```

**提示：**

1. 你可以假设 `nums` 中的所有元素是不重复的。
2. `n` 将在 `[1, 10000]`之间。
3. `nums` 的每个元素都将在 `[-9999, 9999]`之间。

#### 解题思路

不推荐使用<font color='red'>暴解法</font>

从`nums`值可得数值是依次变大的，首先把nums全部分成`左边`和`右边`两部分，定义`left=0`，`right=nums.length-1`，定义一个变量`mid`，它的值是每次循环可变的，对比的值每次都是中间的值，-即`mid = left + (right - left) / 2` 意思就是如果依次没有得到和`target`相等的值，就会得到这个值要么在左边，要么在右边，要是对比得知`小于target`，`left`就会变成`mid +1`，这里的加一减一都是为了和刚才中间的值再次比较，过滤掉了。

#### 代码

`暴解法`

```java
class Solution {
    public int search(int[] nums, int target) {
        boolean flag = false;
        int t = 0;
        int f = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                t = i;
                flag = true;
            }
        }
        return flag ? t : f;
    }
}
```



```java
public class T704 {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 3, 5, 8, 9, 12};
        int target = 0;
        Solution solution = new Solution();
        System.out.println(solution.search(nums, target));
    }
}

class Solution {
    public int search(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            //每次循环都要重新赋值mid
            int mid = left + ((right - left) / 2);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }
}
```







### T283 移动零

#### 问题

给定一个数组 `nums`，编写一个函数将所有 `0` 移动到数组的末尾，同时保持非零元素的相对顺序。

**示例:**

```
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
```

**说明**:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

#### 解题思路1

##### 不使用双指针的解题思路

首先根据示例得知，<font color='red'>非零</font>的数值依旧按照原来的顺序排序，只是索引值发生了变换，所以可以根据判断每一个值是否不等于零即<font color='red'>!=0</font>来为<font color='red'>非零</font>的数值重新分配索引<font color='red'>(index++) 1.2.3...n</font>，最后变量<font color='red'>index</font>得出<font color='red'>零</font>的个数，在数组后面添加即可。

![移动零](README.assets/移动零.gif)

#### 代码

```java
public class T283 {
    public static void main(String[] args) {
        int[] nums = {0, 1, 2, 0, 12};
        new Solution5().moveZeroes(nums);
    }
}
class Solution5 {
    public void moveZeroes(int[] nums) {
        System.out.println("原数组:"+Arrays.toString(nums));
        //计算数组的长度,并设置了索引值index从0开始
        int n = nums.length, index = 0;
        //对数组的每一个值进行遍历判断
        for (int i = 0; i < n; i++) {
            //!=0赋值
            if (nums[i] != 0) {
                //index从0开始,非零赋值,而且index每次都会自增1,所以非零的数值索引从0依次赋值
                nums[index++] = nums[i];
            }
        }
        //在数组后面直接添加0
        //n - index 即为0出现的次数
        for (int i = index; i < n; i++) {
            nums[i] = 0;
        }
        System.out.println("操作后的数组"+Arrays.toString(nums));
    }
}
```

#### 截图思路2

##### 使用双指针的解题思路

可以设置两个索引，右索引<font color='red'>负责遍历判断</font>每一个数值，索引每次自增1，<font color='red'>左</font>索引在前<font color='red'>右</font>索引遍历判断<font color='red'>！= 0</font>的基础上进行<font color='red'>两个索引数值的替换</font>，符合<font color='red'>！= 0</font>的条件索引自增1。这样就能得出这样的一个现象：左索引左边都是<font color='red'>非零</font>，右索引左边到左索引中间的数值都是<font color='red'>零</font>。

#### 代码

```java
public class T283 {
    public static void main(String[] args) {
        int[] nums = {0, 1, 2, 0, 12};
        new Solution5().moveZeroes(nums);
    }
}
class Solution5 {
    public void moveZeroes(int[] nums) {
        System.out.println("原数组:"+Arrays.toString(nums));
        //计算nums数组的长度,定义left和right两个索引并赋初值为0
        int n = nums.length, left = 0, right = 0;
        while (right<n) {
            if (nums[right] != 0) {
                //交换值  若nums[0] != 0 因为left和right初值都为0,所以也可进行交换
                //第一个值不为0时也可交换,因为索引值都是0
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                //左索引 只有达到 所遍历的数值 不为0时 才会自增1
                left++;
            }
            //右索引每次循环都会自增1
            right++;
        }
        System.out.println("操作后的数组"+Arrays.toString(nums));
    }
}
```



#### 运行截图

两次方法运行的结果都是一样的

![image-20210708131909388](README.assets/image-20210708131909388.png)





### T35搜索插入位置

### T189旋转数组

### T167两数之和 II - 输入有序数组

### T344反转字符串

### T557反转字符串中的单词 III