题目

1. 实现 pow(x,n)
2. Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
3. 给出若干闭合区间，合并所有重叠的部分

实现代码

• 首先找到小于n的最大的二进制数，这个最大二进制数就是实现对数复杂度的关键
• myPow(x,index / 2)*myPow(x,index / 2) * myPow(x,n-index);中myPow(x,index / 2)*myPow(x,index / 2) = myPow(x,index)应该知道这里使用乘法相当于myPow(x,n)之间n值直接相加
• 使用递归的方法，直到n的值变成0、1、-1.

public class Solution {
    /** @param x: the base number* @param n: the power number* @return: the result*/public double myPow(double x, int n) {// write your code hereif (n == 0) return 1;if (n == 1) return x;int index = getMaxTwo(n);return myPow(x,index / 2)*myPow(x,index / 2) * myPow(x,n-index);}public int getMaxTwo(int n){int index = 1;if (n / 2 > 0){index *= 2;}return index;}
}

• 这里忘记考虑负数的情况

public class Solution {
    /** @param x: the base number* @param n: the power number* @return: the result*/public double myPow(double x, int n) {// write your code hereif (n == 0) return 1;if (n == 1) return x;if (n == -1) return 1/x;int index = getMaxTwo(n);return myPow(x,index / 2)*myPow(x,index / 2) * myPow(x,n-index);}public int getMaxTwo(int n){int index = 1;if (n / 2 != 0){index *= 2;}return n > 0 ? index : - index;}
}

• 在实际使用中，对于-Integer.MIN_VALUE这个值是不准确的，所以将其单独列出

switch (n) {case 0:return 1;case 1:return x;case -1:return 1/x;case Integer.MIN_VALUE:return 0;}

• 首先暴力解决，时间复杂度过高（AC但时间较多），

public class Solution {
    /*** @param nums: the given array* @param k: the given number* @return: whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k*/public boolean containsNearbyDuplicate(int[] nums, int k) {// Write your code hereint length = nums.length;for (int i = 0; i < length ;i ++ ){for(int j = i + 1; j <= Math.min(length-1,i + k); j ++){if (nums[i] == nums[j])return true;}} return false;}
}

• 使用HashMap记录出现值的位置，判断是否在k以内（结果是内存爆炸）

public class Solution {
    /*** @param nums: the given array* @param k: the given number* @return: whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k*/public boolean containsNearbyDuplicate(int[] nums, int k) {// Write your code hereint length = nums.length;Map<Integer,Integer> map = new HashMap<Integer,Integer>();for (int i = 0; i < length ;i ++ ){if (map.get(nums[i]) == null){map.put(nums[i],i);} else {if (i - map.get(nums[i]) <= k){return true;}map.put(nums[i],i);}} return false;}
}

• 增加了超过K值以后删除，结果发现Map和Set性能无明显区别

public class Solution {
    /*** @param nums: the given array* @param k: the given number* @return: whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k*/public boolean containsNearbyDuplicate(int[] nums, int k) {// Write your code hereint length = nums.length;Map<Integer,Integer> map = new HashMap<Integer,Integer>();for (int i = 0; i < length ;i ++ ){if (map.get(nums[i]) == null){map.put(nums[i],i);if (i > k)map.remove(nums[i - k]);} else {if (i - map.get(nums[i]) <= k){return true;}map.put(nums[i],i);}} return false;}
}public boolean containsNearbyDuplicate(int[] nums, int k) {// Write your code hereint length = nums.length;Set<Integer> map = new HashSet<Integer>();for (int i = 0; i < length ;i ++ ){if (!map.contains(nums[i])){map.add(nums[i]);if (i >= k)map.remove(nums[i - k]);} else {return true;}} return false;}

• 排序之后直接遍历一次即可：

/*** Definition of Interval:* public classs Interval {* int start, end;* Interval(int start, int end) {* this.start = start;* this.end = end;* }* }*/public class Solution {
    /*** @param intervals: interval list.* @return: A new interval list.*/public List<Interval> merge(List<Interval> intervals) {// write your code hereCollections.sort(intervals, new IntervalComparator()); List<Interval> result = new ArrayList<>();Interval lastInterval = null;for (Interval interval : intervals){if (lastInterval == null || interval.start > lastInterval.end){lastInterval = interval;result.add(interval);} else {lastInterval.end = Math.max(lastInterval.end,interval.end);}} return result;}private class IntervalComparator implements Comparator<Interval> {
    public int compare(Interval a, Interval b) {return a.start - b.start;}}
}

git 地址： https://github.com/Outliwer/LintCode_Result