341. 扁平化嵌套列表迭代器
public class NestedIterator implements Iterator<Integer> {
List<Integer> list = new ArrayList<>();
int index = 0;
public NestedIterator(List<NestedInteger> nestedList) {
add(nestedList);
}
private void add(List<NestedInteger> nestedList) {
for (NestedInteger nestedInteger : nestedList) {
if (nestedInteger.isInteger()) {
list.add(nestedInteger.getInteger());
} else {
add(nestedInteger.getList());
}
}
}
@Override
public Integer next() {
return list.get(index++);
}
@Override
public boolean hasNext() {
return index < list.size();
}
}
342. 4的幂
class Solution {
public boolean isPowerOfFour(int n) {
if (n <= 0) {
return false;
}
while (n % 4 == 0) {
n /= 4;
}
return n == 1;
}
}
343. 整数拆分
根据均值不等式，正整数n拆分成相等的k个数相加时，乘积最大。
设这个数为x，那么k = n/x 。
求 y = x ^ (n/x) 的极大值，求得驻点为 x = e。观察知分成2 或者 3相加最优。
class Solution {
public int integerBreak(int n) {
if (n <= 3) {
return n - 1;
}
int r = n % 3;
int k = n / 3;
if (r == 0) {
return (int) Math.pow(3, k);
} else if (r == 1) {
return (int) Math.pow(3, k - 1) * 4;
} else {
return (int) Math.pow(3, k) * 2;
}
}
}
344. 反转字符串
class Solution {
public void reverseString(char[] s) {
int i = 0, j = s.length - 1;
while (i < j) {
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
}
345. 反转字符串中的元音字母
class Solution {
private boolean judge(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
public String reverseVowels(String s) {
char[] chars = s.toCharArray();
int i = 0, j = s.length() - 1;
while (i < j) {
while (i < chars.length && !judge(chars[i])) {
i++;
}
while (j > 0 && !judge(chars[j])) {
j--;
}
if (i < j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
i++;
j--;
}
}
return String.valueOf(chars);
}
}
347. 前 K 个高频元素
用大根堆，时间复杂度Onlogn:
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
Set<Integer> set = new HashSet<>();
for (int i : nums) {
set.add(i);
map.put(i, map.getOrDefault(i, 0) + 1);
}
Queue<Integer> q = new PriorityQueue<>((o1, o2) -> map.get(o2) - map.get(o1));
for (int i : set) {
q.offer(i);
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = q.poll();
}
return res;
}
}
用小根堆，时间复杂度Onlogk：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
Set<Integer> set = new HashSet<>();
for (int i : nums) {
set.add(i);
map.put(i, map.getOrDefault(i, 0) + 1);
}
Queue<Integer> q = new PriorityQueue<>((o1, o2) -> map.get(o1) - map.get(o2));
for (int i : set) {
q.offer(i);
if (q.size() > k) {
q.poll();
}
}
int[] res = new int[k];
for (int i = k - 1; i >= 0; i--) {
res[i] = q.poll();
}
return res;
}
}
349. 两个数组的交集
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
for (int i : nums1) {
set.add(i);
}
Set<Integer> res = new HashSet<>();
for (int i : nums2) {
if (set.contains(i)) {
res.add(i);
}
}
int[] arr = new int[res.size()];
int pos = 0;
for (int i : res) {
arr[pos++] = i;
}
return arr;
}
}
350. 两个数组的交集 II
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
for (int i : nums1) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
List<Integer> res = new ArrayList<>();
for (int i : nums2) {
if (map.containsKey(i) && map.get(i) > 0) {
res.add(i);
map.put(i, map.get(i) - 1);
}
}
return res.stream().mapToInt(Integer::valueOf).toArray();
}
}
354. 俄罗斯套娃信封问题
二维的最长上升子序列问题。先对第一维排序好之后，再对第二维求解最长上升子序列，稍微不同的是，还需要多判断一下第二维上升的同时第一维的数字不能相同。
class Solution {
private int lis(int[][] envelopes) {
int[] dp = new int[envelopes.length];
dp[0] = 1;
int res = 1;
for (int i = 1; i < envelopes.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (envelopes[j][0] != envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
public int maxEnvelopes(int[][] envelopes) {
if (envelopes.length == 0) {
return 0;
}
Arrays.sort(envelopes, (o1, o2) -> o1[0] - o2[0]);
return lis(envelopes);
}
}
355. 设计推特
难点在于获取关注列表的最新10条推文。
将推文设计成链表，就可以转化成这道题。23. 合并K个升序链表
class Twitter {
public static int timestamp = 0;
class User {
private int userId;
private Set<Integer> follows;
private Tweet head;
public User(int userId) {
this.userId = userId;
this.follows = new HashSet<>();
follows.add(userId);//关注自己
}
private void follow(Integer id) {
follows.add(id);
}
private void unFollow(Integer id) {
if (id != userId) {
follows.remove(id);
}
}
private void postTweet(int id) {
Tweet tweet = new Tweet(id, timestamp++);
tweet.next = head;
head = tweet;
}
}
class Tweet {
int tweetId;
int time;
Tweet next;
public Tweet(int tweetId, int time) {
this.tweetId = tweetId;
this.time = time;
}
}
Map<Integer, User> map;
/**
* Initialize your data structure here.
*/
public Twitter() {
map = new HashMap<>();
}
/**
* Compose a new tweet.
*/
public void postTweet(int userId, int tweetId) {
if (!map.containsKey(userId)) {
map.put(userId, new User(userId));
}
map.get(userId).postTweet(tweetId);
}
/**
* Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
*/
public List<Integer> getNewsFeed(int userId) {
if (!map.containsKey(userId)) {
return new ArrayList<>();
}
Set<Integer> follows = map.get(userId).follows;
Queue<Tweet> q = new PriorityQueue<>((o1, o2) -> o2.time - o1.time);
for (int i : follows) {
if (map.get(i).head != null) {
q.offer(map.get(i).head);
}
}
List<Integer> news = new ArrayList<>();
for (int i = 0; i < 10; i++) {
Tweet front = q.poll();
if (front == null) {
break;
}
if (front.next != null) {
q.offer(front.next);
}
news.add(front.tweetId);
}
return news;
}
/**
* Follower follows a followee. If the operation is invalid, it should be a no-op.
*/
public void follow(int followerId, int followeeId) {
if (!map.containsKey(followerId)) {
map.put(followerId, new User(followerId));
}
if (!map.containsKey(followeeId)) {
map.put(followeeId, new User(followeeId));
}
map.get(followerId).follow(followeeId);
}
/**
* Follower unfollows a followee. If the operation is invalid, it should be a no-op.
*/
public void unfollow(int followerId, int followeeId) {
if (!map.containsKey(followerId)) {
map.put(followerId, new User(followerId));
}
if (!map.containsKey(followeeId)) {
map.put(followeeId, new User(followeeId));
}
map.get(followerId).unFollow(followeeId);
}
}
357. 计算各个位数不同的数字个数
排列组合问题。
最高位不取0时，最高位有9种情况，后面每一位少一种情况，注意次高位有9种情况，因为最高位不能取0，次高位可以取。
最高位取0时，等于n-1时的答案。
class Solution {
public int countNumbersWithUniqueDigits(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
int sum = 9;
for (int j = 0; j < i - 1; j++) {
sum *= 9 - j;
}
dp[i] = dp[i - 1] + sum;
}
return dp[n];
}
}
365. 水壶问题
裴蜀定理：
说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
class Solution {
public boolean canMeasureWater(int x, int y, int z) {
if (x + y < z) {
return false;
}
if (x == 0 || y == 0) {
return z == 0 || x + y == z;
}
return z % gcd(x, y) == 0;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
367. 有效的完全平方数
class Solution {
public boolean isPerfectSquare(int num) {
int lo = 1, hi = 65536;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if ((long) mid * (long) mid < (long) num) {
lo = mid + 1;
} else if ((long) mid * (long) mid == (long) num) {
return true;
} else {
hi = mid - 1;
}
}
return false;
}
}
368. 最大整除子集
dp[i]代表以nums[i]为结尾的最大整除子集
边界:
dp[0]是只包含nums[0]的子集
转移方程：
对于求解dp[i]，j从遍历0到i-1，如果nums[i]可以整除nums[j]，此时如果把nums[i]加入到dp[j]中，一定是一个整除子集。遍历得到最大的整除子集赋给dp[i]。
在遍历i的过程中记录最大整除子集的编号，结果就是dp[maxIndex]。
class Solution {
public List<Integer> largestDivisibleSubset(int[] nums) {
if (nums.length == 0) {
return new ArrayList<>();
}
Arrays.sort(nums);
List<Integer>[] dp = new ArrayList[nums.length];
dp[0] = new ArrayList<>();
dp[0].add(nums[0]);
int max = 0, maxIndex = 0;
for (int i = 1; i < nums.length; i++) {
dp[i] = new ArrayList<>();
dp[i].add(nums[i]);
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[i].size() < dp[j].size() + 1) {
dp[i].clear();
dp[i].addAll(dp[j]);
dp[i].add(nums[i]);
}
}
if (dp[i].size() > max) {
max = dp[i].size();
maxIndex = i;
}
}
return dp[maxIndex];
}
}
改进：可以降维，dp[i]只记录以i为结尾的最大整除子集的大小。最后再重建出子集。
371. 两整数之和
return a+b;
372. 超级次方
class Solution {
//快速幂模板，求a^b%m
private long binaryPow(long a, long b, long m) {
long res = 1;
while (b > 0) {
if (b % 2 == 1) {
res = res * a % m;
}
a = a * a % m;
b >>= 1;
}
return res;
}
public int superPow(int a, int[] b) {
int m = 1337;
long res = 1;
for (int i : b) {
res = binaryPow(res, 10, m) * binaryPow(a, i, m) % m;
}
return (int) res;
}
}
373. 查找和最小的K对数字
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
Queue<List<Integer>> maxHeap = new PriorityQueue<>((o1, o2) -> -o1.get(0) - o1.get(1) + o2.get(0) + o2.get(1));
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
maxHeap.offer(Arrays.asList(nums1[i], nums2[j]));
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
}
List<List<Integer>> res = new ArrayList<>();
while (!maxHeap.isEmpty()) {
res.add(maxHeap.poll());
}
return res;
}
}
374. 猜数字大小
二分的原始问题。
public class Solution extends GuessGame {
public int guessNumber(int n) {
int lo = 1, hi = n;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (guess(mid) > 0) {
lo = mid + 1;
} else if (guess(mid) == 0) {
return mid;
} else {
hi = mid - 1;
}
}
return -1;
}
}
375. 猜数字大小 II
方法和5. 最长回文子串类似
dp[i][j]代表从i到j选一个数字，至少需要多少现金。
边界：
dp[i][i] = 0
转移方程：
dp[i][j] 等于 遍历k从i到j，某一轮猜的是数字k，最坏的情况需要Math.max(dp[i][k - 1], dp[k + 1][j]) + k 的现金。 dp[i][j]等于所有k情况的最小值。
区间的长度从2到n遍历，因为大的区间的dp值由更小的区间递推而来。
最后的答案就是dp[1][n]
class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n + 2][n + 2];
for (int L = 2; L <= n; L++) {
for (int i = 1; i <= n - L + 1; i++) {
int j = i + L - 1;
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k <= j; k++) {
dp[i][j] = Math.min(dp[i][j], Math.max(dp[i][k - 1], dp[k + 1][j]) + k);
}
}
}
return dp[1][n];
}
}
376. 摆动序列
动态规划
up[i]代表目前为止最长的以第 i个元素结尾的上升摆动序列的长度。
down[i]记录的是目前为止最长的以第 i个元素结尾的下降摆动序列的长度。
边界：
up[0] = down[0] = 1
转移方程：
如果当前数字比前一个数字大，up[i] = down[i - 1] + 1，down[i] = down[i - 1];
如果当前数字比前一个数字小，up[i] = up[i - 1] ， down[i] = up[i - 1] + 1;
如果当前数字等于前一个数字，up[i] = up[i - 1] ， down[i] = down[i - 1];
时间复杂度On,空间复杂度On。
class Solution {
public int wiggleMaxLength(int[] nums) {
int len = nums.length;
if (len < 2) {
return len;
}
int[] up = new int[len], down = new int[len];
up[0] = down[0] = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
up[i] = down[i - 1] + 1;
down[i] = down[i - 1];
} else if (nums[i] == nums[i - 1]) {
up[i] = up[i - 1];
down[i] = down[i - 1];
} else if (nums[i] < nums[i - 1]) {
up[i] = up[i - 1];
down[i] = up[i - 1] + 1;
}
}
return Math.max(up[len - 1], down[len - 1]);
}
}
优化，采用滚动数组的思想。时间复杂度On，空间复杂度O1。
class Solution {
public int wiggleMaxLength(int[] nums) {
int len = nums.length;
if (len < 2) {
return len;
}
int up = 1, down = 1;
for (int i = 1; i < len; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
}
377. 组合总和 Ⅳ
dfs回溯超时：
class Solution {
int res = 0;
private void dfs(int target, int[] nums) {
if (target == 0) {
res++;
return;
}
if (target < 0) {
return;
}
for (int i = 0; i < nums.length; i++) {
target -= nums[i];
dfs(target, nums);
target += nums[i];
}
}
public int combinationSum4(int[] nums, int target) {
dfs(target, nums);
return res;
}
}
动态规划：
dp[i]代表目标target为i时，组合的个数
边界：
dp[0] = 1
转移方程：
dp[i] = dp[i-nums[0]] + dp[i-nums[1]] + ... + dp[i-nums[n-1]]
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (i - num >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
378. 有序矩阵中第K小的元素
用最小堆实现n路归并。第k次归并的时候的元素就是第k小的元素。
class Solution {
public int kthSmallest(int[][] matrix, int k) {
Queue<List<Integer>> minHeap = new PriorityQueue<>((o1, o2) -> o1.get(0) - o2.get(0));
List<List<Integer>> list = new ArrayList<>();
for (int i = 0; i < matrix.length; i++) {
list.add(Arrays.stream(matrix[i]).boxed().collect(Collectors.toList()));
}
for (List<Integer> l : list) {
minHeap.offer(l);
}
for (int i = 0; i < k - 1; i++) {
List<Integer> l = minHeap.poll();
if (l.size() > 1) {
l.remove(0);
minHeap.offer(l);
}
}
return minHeap.poll().get(0);
}
}
380. 常数时间插入、删除和获取随机元素
哈希表可以实现常数时间插入和删除，但是不容易实现常数时间的获取随机元素。
动态数组可以实现常数时间的插入和获取随机元素，想要常数时间的删除动态数组，只能每次删数组中的最后一个元素。
因此可以用哈希表+动态数组来实现，哈希表记录每一个元素在数组中的位置，
这样要删除这个元素时，先获取它的位置，再把数组中的最后一个元素移到这个位置上，然后删最后一个元素即可。
class RandomizedSet {
Map<Integer, Integer> map;
List<Integer> list;
Random random;
public RandomizedSet() {
map = new HashMap<>();
list = new ArrayList<>();
random = new Random();
}
public boolean insert(int val) {
if (map.containsKey(val)) {
return false;
}
int size = list.size();
map.put(val, size);
list.add(val);
return true;
}
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
int index = map.get(val);
int lastElement = list.get(list.size() - 1);
map.put(lastElement, index);
list.set(index, lastElement);
list.remove(list.size() - 1);
map.remove(val);
return true;
}
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}
