刷题LeetCode第一天

数组

LeetCode 704

1. 看到题目的第一想法

   首先想到有序数组，又要查找目标值肯定要使用二分法查询。但是不太清除区间的取法。
   while(left<right) ?
   OR
   while(left<=right) ?

里面if(nums[mid]>target){
right=mid-1;//right=mid?
}
这些条件判断不是很清楚

2. 看完之后的想法
   首先确定是取左闭右闭还是左闭右开，一般从这两个方面进行考虑。
   如果是左闭右闭，举个例子[1,1]这个区间是合法的，说明left，right可以取相等的值，所以我们取
   while(left<=right){
   …
   if(nums[mid]>target){
   right=mid-1;
   //如果是right=mid，nums[mid] == nums[right],而nums[right]是大于target
   //的，所以没意义，只能向前走一个mid-1.
   }
   }
   完整的[left,right]代码

class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while(left<=right){
            int mid=left+((right-left)>>1);
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

与此对应的[left,right)区间说明right的值取不到
while(left<right)
if(nums[mid]>target){
	right=mid;//因为这里mid取不到，所以实际上还是取得前一个的值
}
完整的[left,right)代码
1
2
3
4
5
6

	class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while(left<right){
            int mid=left+((right-left)>>1);
            if(nums[mid]>target){
                right=mid;
            }else if(nums[mid]<target){
                left=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3. 遇到的困难
   区间的确定，闭区间和开区间的理解

LeetCode 27

1. 看到题目的第一想法
   想到有一层循环从头遍历到尾，内层循环也是遍历，不过遍历的时候查找有没有等于目标值target的数，如果有的话，把后面的数往前放，因为放的动作是循环放的，所以我又加了一层循环。运行超时。

class Solution {
    public int removeElement(int[] nums, int val) {
        int i,j=0;
        for(i=0;i<nums.length;i++){
            for(j=0;j<nums.length;j++){
                if(nums[j]==val){
                    do{
                        nums[j+1]=nums[j];
                    }while(j<nums.length);
                    break;
                }
            }
        }
        return j;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

然后我又换了一种方式将判断卸载另一个循环的外面，但是这次出错，因为我没有考虑到后面是不是还有元素和val的值相同，就全部前移，所以答案肯定是错的

int i=0,j=0;
for(i=0;i<nums.length;i++){
    if(nums[i]==val){
        for(j=i+1;j<nums.length;j++){
            nums[j-1]=nums[j];
        }
    }
}
return j;
1
2
3
4
5
6
7
8
9

之后，我设置了一个变量size，表示删除后数组的长度，判断如果相等，那么size就要做size–操作。并且这时的i也要做i–操作，因为相等了i后面的位置都向前了，所以i也要向前移动，不做i–操作的话，最后会剩下一个值没有删掉。
比如：
输入：
[0,1,2,2,3,0,4,2]
2
输出：
[0,1,2,3,0,4]
预期结果：
[0,1,4,0,3]

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for(int i=0;i<size;i++){
            if(nums[i]==val){
                for(int j=i+1;j<size;j++){
                    nums[j-1]=nums[j];
                }
                i--;
                size--;
            }
            
        }
        return size;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 看了题解后的想法
   使用双指针写法，定义两个快慢指针，逆向思维，快指针只需要把不等于val的值给慢指针即可，最后返回慢指针的下标，就是所有元素之和，因为是从0 开始的。

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow=0;
        for(int fast=0;fast<nums.length;fast++){
            if(nums[fast]!=val){
                nums[slow++]=nums[fast];
            }
        }
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11

3. 遇到的困难
   逆向思维，存储不等于val的值，不太容易想到

今日学习的文章链接

• LeetCode 704 https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md
• LeetCode 27
  https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.md