讨论/建议反馈/题目[1095. 山脉数组中查找目标值 ]测试用例问题/
题目[1095. 山脉数组中查找目标值 ]测试用例问题

[1095. 山脉数组中查找目标值]测试用例问题

  • 截图了一张,同样的测试用例,提交前自测没问题,提交后报错,检查代码了应该是没有问题的;

43645.png

提交的代码:

/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface MountainArray {
 *     public int get(int index) {}
 *     public int length() {}
 * }
 */
 
class Solution {
 	private static HashMap<Integer, Integer> CACHE = new HashMap<Integer, Integer>();
	private static MountainArray M;

	public int findInMountainArray(int target, MountainArray mountainArr) {
		M = mountainArr;
		int len = mountainArr.length();
		int left = 0, right = len - 1, mid;
		while (left < right) {
			mid = (left + right) >> 1;
			if (getFromCache(mid) < getFromCache(mid + 1)) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		mid = left;
		if (getFromCache(mid) == target) {
			return mid;
		}
		// 先查左半边,再查右半边
		int index = bingarySearch(0, mid - 1, target, true);
		if (index != -1) {
			return index;
		}
		index = bingarySearch(mid + 1, len - 1, target, false);
		return index == -1 ? -1 : index;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月29日 下午8:41:02 
	 * @param: @param left
	 * @param: @param right
	 * @param: @param target
	 * @param: @param f
	 * @param: @return
	 * @return: int
	 * @Description: 二分查找
	 *
	 */
	private int bingarySearch(int left, int right, int target, boolean f) {
		while (left < right) {
			int mid = (left + right) >> 1;
			int midVal = getFromCache(mid);
			if (f ? midVal < target : midVal > target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return getFromCache(left) == target ? left : -1;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月29日 下午8:40:50 
	 * @param: @param index
	 * @param: @return
	 * @return: int
	 * @Description: 缓存获取过的值
	 *
	 */
	private static int getFromCache(int index) {
		Integer val = CACHE.get(index);
		if (val == null) {
			val = M.get(index);
			CACHE.put(index, val);
		}
		return val;
	}
}
展开讨论
1