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. 整數(shù)拆分
根據(jù)均值不等式，正整數(shù)n拆分成相等的k個數(shù)相加時，乘積最大。
設(shè)這個數(shù)為x，那么k = n/x 。
求 y = x ^ (n/x) 的極大值，求得駐點為 x = e。觀察知分成2 或者 3相加最優(yōu)。
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. 反轉(zhuǎn)字符串
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. 反轉(zhuǎn)字符串中的元音字母
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. 兩個數(shù)組的交集
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. 兩個數(shù)組的交集 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. 俄羅斯套娃信封問題
二維的最長上升子序列問題。先對第一維排序好之后，再對第二維求解最長上升子序列，稍微不同的是，還需要多判斷一下第二維上升的同時第一維的數(shù)字不能相同。
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. 設(shè)計推特
難點在于獲取關(guān)注列表的最新10條推文。
將推文設(shè)計成鏈表，就可以轉(zhuǎn)化成這道題。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);//關(guān)注自己
}
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. 計算各個位數(shù)不同的數(shù)字個數(shù)
排列組合問題。
最高位不取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. 水壺問題
裴蜀定理：
說明了對任何整數(shù)a、b和它們的最大公約數(shù)d，關(guān)于未知數(shù)x和y的線性不定方程（稱為裴蜀等式）：若a,b是整數(shù),且gcd(a,b)=d，那么對于任意的整數(shù)x,y,ax+by都一定是d的倍數(shù)，特別地，一定存在整數(shù)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. 有效的完全平方數(shù)
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]為結(jié)尾的最大整除子集
邊界:
dp[0]是只包含nums[0]的子集
轉(zhuǎn)移方程：
對于求解dp[i]，j從遍歷0到i-1，如果nums[i]可以整除nums[j]，此時如果把nums[i]加入到dp[j]中，一定是一個整除子集。遍歷得到最大的整除子集賦給dp[i]。
在遍歷i的過程中記錄最大整除子集的編號，結(jié)果就是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為結(jié)尾的最大整除子集的大小。最后再重建出子集。
371. 兩整數(shù)之和
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對數(shù)字
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. 猜數(shù)字大小
二分的原始問題。
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. 猜數(shù)字大小 II
方法和5. 最長回文子串類似
dp[i][j]代表從i到j選一個數(shù)字，至少需要多少現(xiàn)金。
邊界：
dp[i][i] = 0
轉(zhuǎn)移方程：
dp[i][j] 等于 遍歷k從i到j，某一輪猜的是數(shù)字k，最壞的情況需要Math.max(dp[i][k - 1], dp[k + 1][j]) + k 的現(xiàn)金。 dp[i][j]等于所有k情況的最小值。
區(qū)間的長度從2到n遍歷，因為大的區(qū)間的dp值由更小的區(qū)間遞推而來。
最后的答案就是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. 擺動序列
動態(tài)規(guī)劃
up[i]代表目前為止最長的以第 i個元素結(jié)尾的上升擺動序列的長度。
down[i]記錄的是目前為止最長的以第 i個元素結(jié)尾的下降擺動序列的長度。
邊界：
up[0] = down[0] = 1
轉(zhuǎn)移方程：
如果當前數(shù)字比前一個數(shù)字大，up[i] = down[i - 1] + 1，down[i] = down[i - 1];
如果當前數(shù)字比前一個數(shù)字小，up[i] = up[i - 1] ， down[i] = up[i - 1] + 1;
如果當前數(shù)字等于前一個數(shù)字，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]);
}
}
優(yōu)化，采用滾動數(shù)組的思想。時間復雜度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;
}
}
動態(tài)規(guī)劃：
dp[i]代表目標target為i時，組合的個數(shù)
邊界：
dp[0] = 1
轉(zhuǎn)移方程：
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小的元素
用最小堆實現(xiàn)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. 常數(shù)時間插入、刪除和獲取隨機元素
哈希表可以實現(xiàn)常數(shù)時間插入和刪除，但是不容易實現(xiàn)常數(shù)時間的獲取隨機元素。
動態(tài)數(shù)組可以實現(xiàn)常數(shù)時間的插入和獲取隨機元素，想要常數(shù)時間的刪除動態(tài)數(shù)組，只能每次刪數(shù)組中的最后一個元素。
因此可以用哈希表+動態(tài)數(shù)組來實現(xiàn)，哈希表記錄每一個元素在數(shù)組中的位置，
這樣要刪除這個元素時，先獲取它的位置，再把數(shù)組中的最后一個元素移到這個位置上，然后刪最后一個元素即可。
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()));
}
}
