Leetcode 975 Odd Even Jump

思路：

1. 从后往前递推
2. 分配两个数组，odd和even数组，odd【i】表示在nums【i】上奇数此跳是否能够成功，同理even数组，初始时odd【len-1】=even【len-1】= true
3. 第奇数跳要求找到A【j】>=A【i】的最小A【j】，偶数此跳要求找到找到A【j】<=A【i】的最大A【i】
4. 最后统计出odd【i】中为true的个数

初始代码(c++) 超时

class Solution {
public:
	int oddEvenJumps(vector<int>& A) {
		bool* odd = new bool[A.size()];//奇数
		bool* even = new bool[A.size()];//偶数
		for (int i = 0; i < A.size(); i++) {
			odd[i] = even[i] = false;
		}
		odd[A.size() - 1] = even[A.size() - 1] = true;
		for (int i = A.size() - 2; i >= 0; i--) {
			//奇数跳要求A[i] <= A[j]
			//cout << i << endl;
			//char m; cin >> m;
			int firstodd = i;
			bool flag = true;
			for (int start = firstodd + 1; start < A.size(); start++) {
				if (flag) {
					if (A[start] >= A[i]) {
						firstodd = start;
						flag = false;
					}
				}
				else {
					if (A[start] >= A[i]&&A[start]<A[firstodd]) {
						firstodd = start;
					}
				}
			}
			if (firstodd > i&&even[firstodd] == true) {
				odd[i] = true;
			}
			int firsteven = i;
			flag = true;
			for (int start = firsteven + 1; start < A.size(); start++) {
				if (flag) {
					if (A[start] <= A[i]) {
						firsteven = start;
						flag = false;
					}
				}
				else {
					if (A[start] <= A[i] && A[start]>A[firsteven]) {
						firsteven = start;
					}
				}
			}
			if (firsteven > i&&odd[firsteven] == true) {
				even[i] = true;
			}
		}
		int res = 0;
		for (int i = 0; i < A.size(); i++) {
			if (odd[i])
				res++;
		}
		return res;
	}

评论区优化思路：

增加了map数据结构，利用map的low_bound和upper_bound函数

low_bound(v): Returns an iterator pointing to the first element in the container whose key is not considered to go before k (i.e., either it is equivalent or goes after). 不小于k,找不到否则返回map::end()

uppeer_bound(v): Returns an iterator pointing to the first element in the container whose key is considered to go after k. 大于，找不到返回map::end()

代码如下：

class Solution {
public:
	int oddEvenJumps(vector<int>& A) {
		int len = A.size();
		bool* odd = new bool[len]();//奇数
		bool* even = new bool[len]();//偶数
        //()代表初始化
		odd[len - 1] = even[len - 1] = true;
		map<int, int> dict;
		dict[A[len - 1]] = len - 1;
		for (int i = len - 2; i >= 0; i--) {
			//奇数跳要求A[i] <= A[j]
			int v = A[i];
			if (dict.find(v) != dict.end()) {
				odd[i] = even[dict[v]];
				even[i] = odd[dict[v]];
			}
			else {
				auto ite1 = dict.lower_bound(v);
				auto ite2 = dict.upper_bound(v);
				if (ite1 != dict.end()) {
					odd[i] = even[ite1->second];
				}
                //找到大于等于的第一个
				if (ite2 != dict.begin()) {
					ite2--;
					even[i] = odd[ite2->second];
				}
                //找到第一个大于的，前一个就是小于等于的，若果没有找到，就是end前的第一个元素
			}
			dict[v] = i;
		}
			
		int res = 0;
		for (int i = 0; i < A.size(); i++) {
			if (odd[i])
				res++;
		}
        delete[] odd;
        delete[] even;
		return res;
	}
};

ps：这题和栈有什么关系，可能也有栈的解法吧，下回来补