The article directories

    • preface
    • Simple problem · Remove elements
      • The title
      • Train of thought
      • Code implementation
      • thinking
    • Simple problem · Search for insertion position
      • The title
      • Code implementation
    • Medium problem · Sum of four numbers
    • Difficult questions · Jumping Games II
      • Code implementation

preface

For some known reason, I have started to brush up on LeetCode again.

Simple problem · Remove elements

It is indeed very simple, but I still wrote for an hour, because some details are not in place, and many interesting thoughts occurred in the process of writing.

The title

Given an array of nums and a value of val, you remove all elements equal to val in place and return the new length of the array. Instead of using extra array space, you must only use O(1) extra space and modify the input array in place. The order of elements can be changed. You don’t need to worry about the element after the new length in the array.

Description:

Why is the return value an integer, but the output answer is an array?

Note that the input array is passed “by reference,” which means that modifying the input array in a function is visible to the caller.

You can imagine the internal operation as follows:

// Nums is passed by reference. That is, no copies of the arguments are made
int len = removeElement(nums, val);

// Modifying the input array in a function is visible to the caller.
// Depending on the length returned by your function, it prints out all elements in the array within that length.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
Copy the code

Example 1:

Enter: nums = [3.2.2.3], val = 3Output:2, nums = [2.2The function should return the new length2And the first two elements in NUMS are2. You don't need to worry about the element after the new length in the array. For example, the function returns a new length of2, while nums = [2.2.3.3] or nums = [2.2.0.0] will also be taken as the correct answer.Copy the code

Example 2:

Enter: nums = [0.1.2.2.3.0.4.2], val = 2Output:5, nums = [0.1.4.0.3The function should return the new length5And the first five elements in NUMS are0.1.3.0.4. Notice that these five elements can be in any order. You don't need to worry about the element after the new length in the array.Copy the code

Tip:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
Copy the code

Source: LeetCode link: leetcode-cn.com/problems/re… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Train of thought

The idea is actually very direct, I don’t know if I have talked about this problem, very cordial feeling.

It is the way to traverse from front to back, encounter the same and “end” swap positions, using a double pointer. For optimization, remove the tail “target” when swapping.

Very straightforward.

Code implementation

class Solution {
public:
    void change(int& a, int& b) {
        int c = a;
        a = b;
        b = c;
    }

    int removeElement(vector<int>& nums, int val) {
        int sz = nums.size(a);for (int i = 0; i <= (sz- 1); i++) {
            if (nums[i] == val) {
                while (sz- 1> =0 && nums[sz- 1] == val) {
                    sz--;
                }
                if (sz - 1 > i) {
                    change(nums[i], nums[sz - 1]); sz--; }}}returnsz; }};Copy the code

thinking

I thought a lot when I wrote this. Why does C++ not support [-1] retrieval? Why can’t C++ perform slicing? Why doesn’t the C++ STL use iterators instead of foreach’s fast traversal?

After a wave of fruitless search on the Internet, I thought, also, these operations, what is a very efficient algorithm to achieve? Well, if not, just write it yourself. Sure enough, the source of these complaints is lack of reading.

Simple problem · Search for insertion position

I don’t even want to say I did that. If this isn’t a dichotomy, do I have to come up with a weighted dichotomy?

The title

Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order. You can assume that there are no duplicate elements in the array.

Code implementation

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for(int i=0; i<nums.size(a); i++) {if(nums[i]>=target)
            {
                returni; }}return nums.size();
    }
};
Copy the code

Medium problem · Sum of four numbers

Well, we did this before when we talked about sums of N numbers, but it’s so hard to write. The code could have been further optimized, such as abstracting into a general solution for sums of N numbers, but I was too tired to abstract.

【C++】 algorithm collection (8) : expand from two sum problems to one hundred sum problems

class Solution {
public:
    void TwoSum(vector<int>& nums, vector<vector<int>>& ret, int target, int add1, int add2, int begin) {

	for (vector<int>::iterator it = nums.begin() + begin; it ! = --nums.end(a); it++) {// pointer number one
	// if (*it == *(++it))
		if(it! =nums.begin() + begin && *it==*(it- 1))	// If it is the same as the previous digit, skip it
			continue;

		int temp_target = target - *it;
		for (vector<int>::iterator it2 = (it+1); it2 ! = nums.end(a); it2++) {// Don't repeat yourself with the next one
			if ((it2+1) != nums.end() && *it2 == *(it2+1))
				continue;

			// If it happens, write
			if (temp_target == *it2) {
				ret.push_back({add1, add2, *it, temp_target});
			}

			// If the next bit is significantly greater than the result value
			if ((it2+1) != nums.end() && *(it2+1) > temp_target)
				break; }}}void ThreeSum(vector<int>& nums, vector<vector<int>>& ret, int target, int add, int begin) {
	int i = 0;
	for (vector<int>::iterator it = nums.begin() + begin; it ! = (nums.end() - 2); it++) {
		i++;
		if(it ! = nums.begin() + begin && *it == *(it - 1))	// If it is the same as the previous digit, skip it
			continue;
		TwoSum(nums, ret, target - *it, add, *it, (begin + i));
	}
}

vector<vector<int>> fourSum(vector<int>& nums, int target) {
	vector<vector<int>> ret;

	if (nums.size()"4)
		return ret;

	sort(nums.begin(), nums.end());

	int i = 0;
	for (vector<int>::iterator it = nums.begin(a); it ! = (nums.end() - 3); it++){
		i++;
		if(it ! = nums.begin() && *it == *(it - 1))	// If it is the same as the previous digit, skip it
			continue;

		ThreeSum(nums, ret, target - *it, *it, i);
	}
	returnret; }};Copy the code

Difficult questions · Jumping Games II

It’s hard. It’s not so hard. Well, it’s hard. Greedy algorithms, that’s all there is to it.

【C++】 algorithm collection (14) : greedy algorithm

Code implementation

class Solution {
public:
int jump(vector<int>& nums) {
    int maxPos = 0, n = nums.size(), end = 0, step = 0; /* maxPos: maximum reach distance; The end: * / border
    for (int i = 0; i < n - 1; ++i) {
        if (maxPos >= i) {  // If you can reach I
            maxPos = max(maxPos, i + nums[i]);  // Constantly adjust the current reachable boundary
            if (i == end) { // Reach the boundary
                end = maxPos;   // Update boundaries
                ++step; // Count the steps}}}returnstep; }};Copy the code

I am exhausted and have a rest. I just signed up for LeetCode biweekly contest and am ready to participate at 10:30. I wake up in the morning and I have a weekly game.