首页 > 编程学习 > LeetCode Exercise Track—Day 1 | 704. Binary Search | 27. Remove Element |

文章目录

  • Basics of Array Theory
  • LeetCode 704. Binary Search
  • LeetCode 27. Remove Element


Basics of Array Theory

  • Array index start from 0
  • Array is a data collection stored in the contiguous memory space
  • Because the array’s memory space is contiguous, we must modify the other element address when deleting or adding elements
  • We can’t delete array elements, only overwritten

LeetCode 704. Binary Search

Question Link

Solution:

class Solution {// avoid looping when tartget less than nums[0] and bigger than nums[nums.length - 1]if(target < nums[0] || target > nums[nums.length-1])return -1;public int search(int[] nums, int target) {int left = 0;int right = nums.length-1;// left-closed and right-closed intervalwhile(left <= right) {int middle = (left + right) >> 1;if(nums[middle] > target)right = middle - 1;else if(nums[middle] < target)left = middle + 1;else    return middle;}return -1;}
}

Thoughts:

  • Avoid looping when target less than nums[0] and bigger than nums[nums.length - 1]
  • Two greater than signs >> means move one place to the right. >> 1 means divide by 2.
  • Two less than signs << means move one place to the left. << 1 means multiple 2.
  • The prerequisite of using binary search is an ordered distinct array.
  • We have to follow the loop invariant principle. It means we should do our boundary operation according to the interval’s definition.
  • We define target in a left-closed and right-closed interval,that is[left, right].
  • We use left <= right in the while loop. Because left == right makes sense.

LeetCode 27. Remove Element

Question Link

Solution:

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];slow++;}}return slow;}
}

Thoughts:

  • I adopt the Two Pointers Method. Complete the work of 2 for loop under 1 for loop through a slow and a fast point.
  • The principle of solving this two-pointer question is clarifying the definition of these two pointers.
  • Fast Point: find elements of the new array that doesn’t contain the target val.
  • Slow Point: update new array index.


本文链接:https://www.ngui.cc/article/show-747565.html
Copyright © 2010-2022 ngui.cc 版权所有 |关于我们| 联系方式| 豫B2-20100000