5.27号刷题

发表于 | 分类于 | 0 comments

第一题 15. 3Sum

算法

自己的

先将整个数组进行排序，然后在数组中找下一个，然后再找最后一个。自己的方法与别人的整个思路大致相似，但是由于没利用数组已经是sort过这个条件，导致复杂度是O(n^3)相当慢

  • 重点，当一个Array是排序过的时候，找寻合适的数字的时候可以考虑从双向查找，尾到头同时头到尾。这样时间复杂度会减少很多 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    public class threeSum15 {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if (nums.length < 3) return result;
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 2; i++) {
                for (int j = i + 1; j < nums.length - 1; j++) {
                    if (nums[j] > 0 && nums[j] > -nums[i]) break;
                    int target = - nums[i] - nums[j];
                    if (nums[j] > target) break;
                    int position = find(nums, target);
                    if (position > 0 && position != j && position != i) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[position]));
                    }
                    while(nums[j] == nums[j+1] && j < nums.length - 2) j++;
                }
                while(nums[i] == nums[i+1] && i < nums.length - 3) i++;
                if (nums[i] > 0) break;
            }
            return result;
        }
        public int find(int[] nums, int target) {
            for (int i = nums.length - 1; i >= 0; i--) {
                if (nums[i] == target) return i;
                if (nums[i] < target) break;
            }
            return -1;
        }
    }
别人的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class threeSum15 {
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums.length < 3) return result;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (i == 0 || (i > 0 && nums[i-1] != nums[i])) {
                if (nums[i] > 0) break;
                int low = i + 1, high = nums.length - 1;
                int sum = 0 - nums[i];
                while (low < high) {
                    if (nums[low] + nums[high] == sum) {
                        result.add(Arrays.asList(nums[i], nums[low], nums[high]));
                        while (low < high && nums[low] == nums[low + 1]) low++;
                        while (low < high && nums[high] == nums[high - 1]) high--;
                        low++;
                        high--;
                    } else if (nums[low] + nums[high] > sum) {
                        high--;
                    } else {
                        low++;
                    }
                }
            }
        }
        return result;
    }
}

学到的东西

  • 对一个数组进行排序 Arrays.sort即可
  • 对于List>可以多个一次性用Arrays.asList进行添加

第二题 16. 3Sum Closest

算法

思路与前一题相似，都是排序之后再通过两个指针的推进，查看是否接近于理想的target值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length < 3) return 0;
        Arrays.sort(nums);
        int sum = nums[0] + nums[1] + nums[2], previous = sum;
        for (int i = 0; i < nums.length - 2; i++) {
            int low = i + 1, high = nums.length - 1;
            while (low < high) {
                int tempSum = nums[i] + nums[low] + nums[high];
                if (Math.abs(sum - target) > Math.abs(tempSum - target)) sum = tempSum;
                
                if (tempSum > target) high--;
                else if (tempSum < target) low++;
                else return target;
            }
            while (i < nums.length - 3 && nums[i] == nums[i+1]) i++;
        }
        return sum;
        
    }
}

第三题 259. 3Sum Smaller

算法

自己的O(n^3)

！！！！记住sort之后的一定要考虑是否能用两个指针减少计算的数量级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class threeSumSmaller259 {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums.length < 3) return 0;
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    int tempSum = nums[i] + nums[j] + nums[k];
                    if (tempSum < target) sum++;
                    else break;
                }
            }
        }
        return sum;
    }
}

参考O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class threeSumSmaller259 {
    public int threeSumSmaller2(int[] nums, int target) {
        if (nums.length < 3) return 0;
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int low = i + 1, high = nums.length - 1;
            while(low < high) {
                int tempSum = nums[i] + nums[low] + nums[high];
                if (tempSum < target) {
                    sum += high - low + 1;
                    low++;
                } else {
                    high--;
                }
            }
        }
        return sum;
    }
}

第四题 128. Longest Consecutive Sequence

算法

这道题的主要算法是用一个Hashmap将已经出现的数字存下来，key: 对应的是数字，value: 连续的长度。如果是没有出现的，例如n，查看其左边n-1和n+1是否存在。如果存在，获得value即已经有的连续的长度，然后计算出现在新的长度。

比较关键的一步是每次结束的时候，put(n+value_left, value_new),和put(n+value_right, value_new)更新新的边界值.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class longestConsecutive128 {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int maxSec = 0;
        for (int num : nums) {
            if (!map.containsKey(num)) {
                int left = map.containsKey(num - 1) ? map.get(num - 1) : 0;
                int right = map.containsKey(num + 1) ? map.get(num + 1) : 0;
                int sum = left + right + 1;
                maxSec = Math.max(maxSec, sum);
                map.put(num, sum);
                map.put(num - left, sum);
                map.put(num + right, sum);
            }
        }
        return maxSec;
    }
}

第五题 162. Find Peak Element

算法

算法一

从后面向前推进，如果是peak就进行输出。复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class findPeakElement162 {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length <= 1) return 0;
        if (nums.length == 2) {
            if (nums[0] > nums[1]) return 0;
            else return 1;
        }
        for (int i = 1; i < nums.length - 1; i++) {
            if (i == 1 && nums[i-1] > nums[i]) return i - 1;
            if (i == nums.length - 2 && nums[i] < nums[i+1]) return i + 1;
            if (nums[i] > nums[i-1] && nums[i] > nums[i+1]) return i;
        }
        return -1;
    }
}

算法二

二分查找和回溯，将时间复杂度降为O(n)
利用的原理是：

  • If num[i-1] < num[i] > num[i+1], then num[i] is peak
  • If num[i-1] < num[i] < num[i+1], then num[i+1…n-1] must contains a peak
  • If num[i-1] > num[i] > num[i+1], then num[0…i-1] must contains a peak
  • If num[i-1] > num[i] < num[i+1], then both sides have peak
    (n is num.length)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class findPeakElement162 {
    public int findPeakElement2(int[] nums) {
        return helpFunction(nums, 0, nums.length - 1);
    }
    public int helpFunction(int[] nums, int begin, int end) {
        int mid = begin + (end - begin) / 2;
        if (begin == end) {
            return begin;
        } else if (begin + 1 == end) {
            if (nums[begin] > nums[end]) return begin;
            else return end;
        }
        if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
            return mid;
        } else if (nums[mid + 1] > nums[mid]) {
            return helpFunction(nums, mid, end);
        } else if (nums[mid - 1] > nums[mid]) {
            return helpFunction(nums, begin, mid);
        }
        return -1;
    }
}