LeetCode 341-380

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()));
    }
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,468评论 5 473
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,620评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,427评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,160评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,197评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,334评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,775评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,444评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,628评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,459评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,508评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,210评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,767评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,850评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,076评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,627评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,196评论 2 341

推荐阅读更多精彩内容