LeetCode刷題的一天（1）

前言

因為某些已知原因，我又開始在LeetCode上 真·刷題 了，

簡單題·移除元素

確實是很簡單啊，但是我還是寫了一個小時，因為有些細節把控的不到位，寫的程序中也發生了不少有趣的思考，

題目

給你一個陣列 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并回傳移除后陣列的新長度，
不要使用額外的陣列空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入陣列，
元素的順序可以改變，你不需要考慮陣列中超出新長度后面的元素，

說明:

為什么回傳數值是整數，但輸出的答案是陣列呢?

請注意，輸入陣列是以「參考」方式傳遞的，這意味著在函式里修改輸入陣列對于呼叫者是可見的，

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

// nums 是以“參考”方式傳遞的，也就是說，不對實參作任何拷貝
int len = removeElement(nums, val);

// 在函式里修改輸入陣列對于呼叫者是可見的，
// 根據你的函式回傳的長度, 它會列印出陣列中 該長度范圍內 的所有元素，
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

輸入：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]，也會被視作正確答案，

示例 2：

輸入：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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-element
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，

思路

思路其實很直接，我不知道我是不是有講過這道題，很親切的感覺，

就是從前往后遍歷，遇到相同的就和“末尾”互換一下位置，使用雙指標的方式，
優化嘛，那就要交換的時候，把尾部的“target”消除掉（尾指標前移），

很直接的思路，

代碼實作

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();
        
        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--;
                }
            }
        }
        return sz;
    }
};

思考

在寫這題的時候，想了很多，為什么C++不支持[-1]檢索？為什么C++不能執行切片？為什么C++ STL沒有foreach的快速遍歷，而是非要去用迭代器？

在網上一波搜索無果后，我想了想，也是，這些操作，還有什么很高效的演算法去實作？那如果沒有，自己寫不就好了嘛，
果然，這些抱怨的源頭都是因為讀書少，

簡單題·搜索插入位置

這題我都不想說我做過了，
這不就是二分法，難不成還要我祭出“加權二分法”？

題目

給定一個排序陣列和一個目標值，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，
你可以假設陣列中無重復元素，

代碼實作

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

中等題·四數之和

這個啊，之前講N數和的時候講過了，但是寫起來居然這么麻煩，
代碼還可以再優化，比如說抽象成N數和的通用解法，但是寫的太累了，就沒去抽象了，

【C++】演算法集錦（8）：從兩數和問題拓展到一百數和問題

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(); it++) {	//指標一號
	//	if (*it == *(++it))	//如果和下一位重復，就跳過（那如果 3 3 6呢？）
		if(it!=nums.begin() + begin && *it==*(it-1))	//如果和上一位重復，就跳過
			continue;

		int temp_target = target - *it;
		for (vector<int>::iterator it2 = (it+1); it2 != nums.end(); it2++) {
			//這里就是不要和下一位重復咯
			if ((it2+1) != nums.end() && *it2 == *(it2+1))
				continue;

			//如果剛好碰上了，那就寫入
			if (temp_target == *it2) {
				ret.push_back({add1, add2, *it, temp_target});
			}

			//如果下一位明顯大于結果值
			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))	//如果和上一位重復，就跳過
			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(); it != (nums.end() - 3); it++){
		i++;
		if (it != nums.begin() && *it == *(it - 1))	//如果和上一位重復，就跳過
			continue;

		ThreeSum(nums, ret, target - *it, *it, i);
	}
	return ret;
}
};

困難題·跳躍游戲II

說困難吶，其實也不是很困難嘛，好吧，還是挺困難的，
貪心演算法，都講過的啦，

【C++】演算法集錦（14）：貪心演算法

代碼實作

class Solution {
public:
int jump(vector<int>& nums) {
    int maxPos = 0, n = nums.size(), end = 0, step = 0; /* maxPos:最遠到達距離；end:邊界*/
    for (int i = 0; i < n - 1; ++i) {
        if (maxPos >= i) {  //如果可以到達 i
            maxPos = max(maxPos, i + nums[i]);  //不斷調整當前可到達邊界
            if (i == end) { //到達邊界
                end = maxPos;   //更新邊界
                ++step; //計算步數
            }
        }
    }
    return step;
}
};

累死啦，休息休息，剛剛報名了LeetCode的雙周賽，十點半準備參加了，
一覺醒來，明早還有單周賽等著我，