leetcode刷题指南
2018-10-24 本文已影响0人
暴躁的伊泽瑞尔
56. Merge Intervals
链接
https://leetcode.com/problems/merge-intervals/
#Array, #Sort, #Medium
思路
先排序，然后挨个看后一个点的begin是不是比当前hold的那个range的end要小，如果小的话就修改当前range的end，否则就开一个新的range。
代码
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> merge(List<Interval> intervals) {
intervals.sort((a, b) -> a.start - b.start);
if (intervals.size() < 2) {
return intervals;
}
List<Interval> res = new ArrayList<>();
res.add(new Interval(intervals.get(0).start, intervals.get(0).end));
int now = 0;
for (int i = 1; i < intervals.size(); i++) {
Interval cur = intervals.get(i);
Interval pre = res.get(now);
if (cur.start <= pre.end) {
res.get(now).end = Math.max(res.get(now).end, cur.end);
} else {
now++;
res.add(new Interval(intervals.get(i).start, intervals.get(i).end));
}
}
return res;
}
}
112. Path Sum
链接
https://leetcode.com/problems/path-sum/
#Tree, #Depth-first Search, #Easy
思路
极其简单，直接递归向下走即可。
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
} else {
if (root.left == null && root.right == null) {
return sum == root.val;
} else {
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
}
}
223. Rectangle Area
链接
https://leetcode.com/problems/rectangle-area/
#Math, #Medium
思路
求两个矩形一共的占地面积，实际上等于两个矩形分别的面积的和再减去重合部分。重合部分的话是需要矩形左下角两个点坐标里x, y里的最大值，和矩形右上角两个点坐标x, y里的最小值。
代码
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int x1 = A > E ? A : E;
int y1 = B > F ? B : F;
int x2 = C > G ? G : C;
int y2 = D > H ? H : D;
int total = (C - A) * (D - B) + (G - E) * (H - F);
if (x2 <= x1 || y2 <= y1) {
return total;
} else {
return total - (y2 - y1) * (x2 - x1);
}
}
273. Integer to English Words
链接
https://leetcode.com/problems/integer-to-english-words/
#Math, #String, #Hard
思路
三位取一个来算。思路很简单。
代码
public String numberToWords(int num) {
Map<Integer, String> map = new HashMap<>();
map.put(1, "One");
map.put(2, "Two");
map.put(3, "Three");
map.put(4, "Four");
map.put(5, "Five");
map.put(6, "Six");
map.put(7, "Seven");
map.put(8, "Eight");
map.put(9, "Nine");
map.put(10, "Ten");
map.put(11, "Eleven");
map.put(12, "Twelve");
map.put(13, "Thirteen");
map.put(14, "Fourteen");
map.put(15, "Fifteen");
map.put(16, "Sixteen");
map.put(17, "Seventeen");
map.put(18, "Eighteen");
map.put(19, "Nineteen");
map.put(20, "Twenty");
map.put(30, "Thirty");
map.put(40, "Forty");
map.put(50, "Fifty");
map.put(60, "Sixty");
map.put(70, "Seventy");
map.put(80, "Eighty");
map.put(90, "Ninety");
Map<Integer, String> due = new HashMap<>();
due.put(1, "Thousand");
due.put(2, "Million");
due.put(3, "Billion");
String res = "";
List<List<String>> list = new ArrayList<>();
if (0 == num) {
return "Zero";
}
int i = 0;
while (num != 0) {
List<String> l = new ArrayList<>();
int k = num % 1000;
num = num / 1000;
int hundred = k / 100;
if (hundred != 0) {
l.add(map.get(hundred));
l.add("Hundred");
k = k % 100;
}
if (k == 0) {
} else if (k <= 20) {
l.add(map.get(k));
} else {
int shi = k / 10;
if (shi != 0) {
l.add(map.get(shi * 10));
}
int ge = k % 10;
if (ge != 0) {
l.add(map.get(ge));
}
}
if (l.size() != 0 && i != 0) {
l.add(due.get(i));
}
i++;
list.add(0, l);
}
return list.stream().flatMap(e -> e.stream()).collect(Collectors.joining(" "));
}
590. N-ary Tree Postorder Traversal
链接
https://leetcode.com/problems/n-ary-tree-postorder-traversal/
#Tree, #Easy
思路
多叉树的后序遍历，和二叉树一个道理。
代码
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> postorder(Node root) {
List<Integer> arr = new ArrayList<>();
if (null == root) {
return arr;
}
if (root.children != null) {
root.children.forEach(e ->
arr.addAll(postorder(e))
);
}
arr.add(root.val);
return arr;
}
}
795. Number of Subarrays with Bounded Maximum
链接
https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/
#Array, #Medium
思路
小于上界的各线段的自由连续组合数，减去小于夏桀的各线段的自由组合连续组合数。
代码
public int numSubarrayBoundedMax(int[] A, int L, int R) {
for (int i = 0; i < A.length; i++) {
if (A[i] < L) {
A[i] = -1;
} else if (A[i] > R) {
A[i] = -2;
}
}
int total = 0;
boolean isLess = false;
boolean isGreat = true;
boolean isOK = false;
int lessCount = 0;
int okCount = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] == -1) {
if (isGreat) {
isGreat = false;
}
isOK = true;
okCount++;
if (isLess) {
lessCount++;
} else {
isLess = true;
lessCount = 1;
}
} else if (A[i] == -2) {
isGreat = true;
if (isOK) {
total += okCount * (okCount + 1) / 2;
isOK = false;
okCount = 0;
}
if (isLess) {
total -= lessCount * (lessCount + 1) / 2;
lessCount = 0;
isLess = false;
}
} else {
if (isGreat) {
isGreat = false;
isOK = true;
okCount = 1;
} else if (isOK) {
okCount++;
}
if (isLess) {
total -= lessCount * (lessCount + 1) / 2;
lessCount = 0;
isLess = false;
}
}
}
total += okCount * (okCount + 1) / 2;
total -= lessCount * (lessCount + 1) / 2;
return total;
}
848. Shifting Letters
链接
https://leetcode.com/problems/shifting-letters/
#String, #Medium
思路
这道题比较简单明了。每一位的shift要模26，因为是循环shifting。然后数组后面的shift size要依次向前加。
代码
public String shiftingLetters(String S, int[] shifts) {
for (int i = 0; i < shifts.length; i++) {
shifts[i] = shifts[i] % 26;
}
for (int i = 1; i < shifts.length; i++) {
for (int j = 0; j < i; j++) {
shifts[j] = shifts[j] + shifts[i];
}
}
String res = "";
for (int i = 0; i < shifts.length; i++) {
int shift = shifts[i];
char tc = S.charAt(i);
tc = (char) (tc + (shift % 26));
if (tc > 'z') {
tc = (char) (tc - 26);
}
res += tc;
}
return res;
}
849. Maximize Distance to Closest Person
链接
https://leetcode.com/problems/maximize-distance-to-closest-person/
#Array, #Easy
思路
找到两边的连续空位数，然后再找出中间的最长连续空位数。然后再对比一下，即可得到最大的离有人座位的最短距离。
代码
public int maxDistToClosest(int[] seats) {
int now = 0;
int maxi = 0;
boolean start = false;
int startCount = 0;
for (int i = 0; i < seats.length; i++) {
if (seats[i] != 1) {
now++;
maxi = maxi > now ? maxi : now;
} else {
if (!start) {
start = true;
startCount = now;
}
now = 0;
}
}
now = now > startCount ? now : startCount;
int a = (maxi + 1) / 2;
return a > now ? a : now;
}
851. Loud and Rich
链接
https://leetcode.com/problems/loud-and-rich/
#Depth-first Search, #Medium
思路
这道题需要找到不比自己穷的人里最低调（有个quiet值）的那个。最原始的想法是，存一个Map<Integer, Set<Integer>>的map，然后记录所有比自己有钱的人的全集。但是这样的话空间复杂度和时间复杂度都会增高。实际上给定一个单向无环图（也是一棵树），当我们想去看第i个人的对应解的时候，我们可以用深度优先搜索去遍历，对应着把下游结点也计算出来并且做缓存，下次再来拿的时候会节约时间。
代码
class Solution {
private int[] a = null;
public int[] loudAndRich(int[][] richer, int[] quiet) {
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int i = 0; i < richer.length; i++) {
Set<Integer> set = map.getOrDefault(richer[i][1], new HashSet<>());
set.add(richer[i][0]);
map.put(richer[i][1], set);
}
a = new int[quiet.length];
for (int i = 0; i < a.length; i++) {
a[i] = -1;
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < quiet.length; i++) {
list.add(findSmall(i, map, quiet));
}
return list.stream().mapToInt(Integer::valueOf).toArray();
}
private int findSmall(int index, Map<Integer, Set<Integer>> map, int[] quiet) {
if (a[index] != -1) {
return a[index];
} else {
Set<Integer> set = map.getOrDefault(index, new HashSet<>());
if (set.size() == 0) {
a[index] = index;
return index;
} else {
int kk = set.stream().map(e -> findSmall(e, map, quiet)).reduce((a, b) -> quiet[a] > quiet[b] ? b : a).get();
int val = quiet[kk] > quiet[index] ? index : kk;
a[index] = val;
return val;
}
}
}
}
850. Rectangle Area II
链接
https://leetcode.com/problems/rectangle-area-ii/
Segment Tree, #Hard, #TODO
思路
a. 集合方法
求多个集合的数量和，是可以用诡异的|A| + |B| - |A & B|方法求出。这道题也可以这么搞，但是时间复杂度为O(n*2^n)，无法接受。
b. Y轴扫描法
从Y轴下向上看，一共有很多个Y轴上的顶点值。把Y轴坐标值从小向大排序时，每一次突变的delta(Y)乘以这段范围内X轴上线段的长度即为这段内的面积。依次类推得到最终面积。
代码
// Y轴扫描法
class Solution {
public int rectangleArea(int[][] rectangles) {
int[][] ps = new int[rectangles.length * 2][4];
for (int i = 0; i < rectangles.length; i++) {
ps[i * 2][0] = rectangles[i][1];
ps[i * 2][1] = rectangles[i][0];
ps[i * 2][2] = rectangles[i][2];
ps[i * 2][3] = 1;
ps[i * 2 + 1][0] = rectangles[i][3];
ps[i * 2 + 1][1] = rectangles[i][0];
ps[i * 2 + 1][2] = rectangles[i][2];
ps[i * 2 + 1][3] = -1;
}
Arrays.sort(ps, Comparator.comparingInt(a -> a[0]));
List<int[]> curLevel = new ArrayList<>();
long res = 0;
int lastY = -1;
for (int i = 0; i < ps.length; i++) {
if (ps[i][0] != lastY && lastY != -1) {
if (curLevel.size() != 0) {
long len = 0;
curLevel.sort(Comparator.comparingInt(a -> a[0]));
int begin = curLevel.get(0)[0];
int end = curLevel.get(0)[1];
for (int ii = 1; ii < curLevel.size(); ii++) {
if (curLevel.get(ii)[0] <= end) {
end = Math.max(end, curLevel.get(ii)[1]);
} else {
len = len + end - begin;
begin = curLevel.get(ii)[0];
end = curLevel.get(ii)[1];
}
}
res = (res + (len - begin + end) * (ps[i][0] - lastY)) % 1_000_000_007;
}
}
handlingRange(curLevel, ps[i]);
lastY = ps[i][0];
}
return (int) res;
}
private void handlingRange(List<int[]> curLevel, int[] vector) {
if (vector[3] == 1) {
curLevel.add(new int[]{vector[1], vector[2]});
} else {
int index = -1;
for (int ii = 0; ii < curLevel.size(); ii++) {
if (curLevel.get(ii)[0] == vector[1] && curLevel.get(ii)[1] == vector[2]) {
index = ii;
break;
}
}
curLevel.remove(index);
}
}
}
