Category: LeetCode

Posted 2022-05-06Updated 2022-05-05LeetCode / Medium / 复习4 minutes read (About 538 words)

673. Number of Longest Increasing Subsequence

Question

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Solution

本题还有贪心算法+前缀和+二分查找的算法。

本题是300. Longest Increasing Subsequence的拓展。
同样采用动态规划，数组dp[i]记录到i为止最长递增数列长度。
可以用一个新的数组cnt[i]记录到i为止可以组成的最长递增数列的数量。

对于每个新位置i，cnt[i]的最小值为i。
遍历i之前的所有位置j。如果nums[j] < nums[i]，则i可以比dp[j]组成更长的递增数列，其长度为dp[j]+1。
如果dp[i] < dp[j]+1。则可以更新dp[i]。同时，cnt[i]可以从cnt[j]继承其计数。
如果dp[i] == dp[j]+1。则之前已经更新过dp[i]。说明有新的组合同样可以组成更长的递增数列。此时将cnt[j]加入当前的cnt[i]。

遍历完成i以内的所有j后，如果dp[i]大于当前的最长递增数列长度，则更新max。
同时更新长度的总数count为cnt[i]。
如果dp[i]等于max，则将cnt[i]加入计数count。
最后返回count。

Code

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        int max = 0;
        int count = 0;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            cnt[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];    //如果后面的数字大于前面的，且可以组成更长的数列，则继承之前的计数。
                    }
                    else if(dp[j] + 1 == dp[i]){    //如果之前已经更新过dp[i]，则有新的组合长度一直，加和之前的计数。
                        cnt[i] += cnt[j];
                    }
                }
            }
            if(dp[i] > max){    //如果当前的长度大于之前的最大值，则更新。
                max = dp[i];
                count = cnt[i];  //同时将之前计算的计数记录。
            }
            else if(dp[i] == max){  //如果有同样达到最大值的情况，则加和计数。
                count += cnt[i];
            }
        }
        return count;
    }
}

Posted 2022-05-05Updated 2022-05-05LeetCode / Easy2 minutes read (About 366 words)

225. Implement Stack using Queues

Question

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.

int pop() Removes the element on the top of the stack and returns it.

int top() Returns the element on the top of the stack.

boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.

Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Solution

用两个队列实现栈。一个队列存放压入的元素。

push()

将当前元素加入到第一个队列。

top() & pop()

当需要挤出或者查看栈顶时，第一个队列只保留一个元素，其余元素加入第二个队列。最后一个元素就是栈顶。当第一个队列为空时，交换第一个队列与第二个队列。

empty()

返回两个队列是否均为空。

Code

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    public MyStack() {
        q1 = new LinkedList<Integer>();
        q2 = new LinkedList<Integer>();
        
    }
    
    public void push(int x) {
        q1.add(x);
    }
    
    public int pop() {
        move();
        return q1.poll();
    }
    
    public int top() {
        move();
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
    
    private void move(){
        if(q1.isEmpty()){
            Queue<Integer> temp = q1;
            q1 = q2;
            q2 = temp;
        }
        while(q1.size() != 1){
            q2.add(q1.poll());
        }
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Posted 2022-05-05Updated 2022-05-05LeetCode / Medium / 复习2 minutes read (About 260 words)

973. K Closest Points to Origin

Question

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Solution

此题可以采用快速排序的思想。可以在O(n)时间复杂度里完成排序。

Solution 2

优先级队列，根据每个点距离的平方排序。时间复杂度O(nlogk)。

Code

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int[] point : points){
            pq.add(point);
        }
        for(int i = 0; i < k; i++){
            ret[i] = pq.poll();
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Solution 3

直接排序。时间复杂度为O(nlogn)。

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] ret = new int[k][2];
        Arrays.sort(points, (a, b) -> squaredDistance(a) - squaredDistance(b));
        for(int i = 0; i < k; i++){
            ret[i] = points[i];
        }
        return ret;
    }
    
    private int squaredDistance(int[] point){
        int x = point[0], y = point[1];
        return x * x + y * y;
    }
}

Posted 2022-05-05Updated 2022-05-04LeetCode / Mediuma minute read (About 203 words)

451. Sort Characters By Frequency

Question

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Solution

哈希表记录字符出现的频率。然后将其添加到优先队列中。
最后根据优先级队列的顺序，加入每个字符对应的哈希表中记录的字符数。
理论上也可以用数组记录频率，但是问题中字符较复杂故未采用。

Code

class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        PriorityQueue<Character> pq = new PriorityQueue<>((a,b) -> map.get(b) - map.get(a));
        StringBuffer sb = new StringBuffer();
        for(char c : s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0)+1);
        }
        for(char c : map.keySet()){
            pq.add(c);
        }
        while(!pq.isEmpty()){
            char c = pq.poll();
            for(int i = 0; i < map.get(c); i++){
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

Posted 2022-05-05Updated 2022-06-21LeetCode / Mediuma minute read (About 149 words)

215. Kth Largest Element in an Array

Problem

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Solution

直接排序数组，返回倒数第k个值。

Code

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Solution 2

采用优先级队列，将所有元素加入队列，采用倒序比较器。
挤出前k-1个值，然后返回第k个值。

Code

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int num : nums){
            pq.add(num);
        }
        for(int i = 0; i < k-1; i++){
            pq.poll();
        }
        return pq.peek();
    }
}

Posted 2022-05-05Updated 2022-05-04LeetCode / Medium / 复习a minute read (About 202 words)

130. Surrounded Regions

Question

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Solution

首先对所有在边缘上的“O”进行BFS或DFS搜索，将和边缘连续的“O”改为“#”或任意其他字符。

然后遍历整个board，如果是“O”则改为“X”，如果是“#”则恢复为“O”。

Code

class Solution {
    public void solve(char[][] board) {
        for(int i = 0; i <board.length; i++){
            for(int j = 0; j <board[0].length; j++){
                boolean isEdge = (i == 0 || j == 0 || i == board.length-1 || j == board[0].length-1);
                if(isEdge && board[i][j] == 'O'){
                    bfs(board, i, j);
                }
            }
        }
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == '#') board[i][j] = 'O';
                else if(board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }

    private void bfs(char[][] board, int x, int y){
        int m = board.length;
        int n = board[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        int size = 1;
        while(!q.isEmpty()){
            for(int k = 0; k < size; k++){
                int[] curr = q.poll();
                int i = curr[0], j = curr[1];
                if( i<0 || j<0 || i>m-1 || j>n-1 || board[i][j] == 'X' || board[i][j] == '#' ) continue;
                board[i][j] = '#';
                q.add(new int[]{i+1,j});
                q.add(new int[]{i-1,j});
                q.add(new int[]{i,j+1});
                q.add(new int[]{i,j-1});
            }
            size = q.size();
        }
    }
}

Posted 2022-05-05Updated 2022-05-04LeetCode / Medium3 minutes read (About 401 words)

384. Shuffle an Array

Question

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

Solution(int[] nums) Initializes the object with the integer array nums.

int[] reset() Resets the array to its original configuration and returns it.

int[] shuffle() Returns a random shuffling of the array.

Solution

Fisher-Yates洗牌算法。将数组分为两组部分，一组为已打乱的部分，一组为未打乱的部分。每次从未打乱部分中取一个元素，随机和一个未打乱部分的元素（包括自身）交换，则该位置变为已打乱的部分。

Code

class Solution {
    int[] data;
    int[] shuffle;
    Random r;
    public Solution(int[] nums) {
        data = nums;
        shuffle = new int[nums.length];
        r = new Random();
        for(int i = 0; i < data.length; i++){
            shuffle[i] = nums[i];
        }
    }
    
    public int[] reset() {
        return data;
    }
    
    public int[] shuffle() {
        for(int i = data.length-1 ; i >= 0; i--){
            swap(i, r.nextInt(i+1));
        }
        return shuffle;
    }
    
    private void swap(int i, int j){
        int temp = shuffle[i];
        shuffle[i] = shuffle[j];
        shuffle[j] = temp;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

Solution 2

将静态数组转换为动态数组，每次随机取动态数组里的一个index。
将其按顺序填入result数组，并删除动态数组这个位置。
最后返回result。

Code

class Solution {
    int[] data;
    Random r;
    public Solution(int[] nums) {
        data = nums;
        r = new Random();
    }
    
    public int[] reset() {
        return data;
    }
    
    public int[] shuffle() {
        ArrayList<Integer> bin = new ArrayList<>();
        for(int i = 0; i < data.length; i++){
            bin.add(data[i]);
        }
        
        int[] ret = new int[data.length];
        for(int i = 0 ; i < data.length; i++){
            int random = r.nextInt(bin.size());
            ret[i] = bin.get(random);
            bin.remove(random);
        }
        return ret;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

Posted 2022-05-05Updated 2022-05-04LeetCode / Hard4 minutes read (About 589 words)

297. Serialize and Deserialize Binary Tree

Question

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Solution

编码过程

编码时采用BFS搜索，将二叉树按层级组成字符串。
当当前节点不等于null时，添加当前节点的值和一个符号。
然后将其左右子节点加入队列。
当当前节点为null时，添加一个非数字字符和一个符号。

解码过程

解码时同样采用BFS搜索，按层级恢复二叉树。
首先将字符串根据符号进行分割，变为字符串数组。
如果第一个字符表示为null，返回null。

否则将第一个数字组成根节点并加入队列。创建一个指针i记录位置。
当队列不为空，且指针i未越界时，根据指针i上的字符串创建当前节点的左子节点。
将指针右移，如果没有越界则创建当前节点的右子节点，然后将指针右移。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder data = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(curr == null) data.append("n,");
            else {
                data.append(curr.val + ",");
                q.add(curr.left);
                q.add(curr.right);
            }
        }
        return data.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] values = data.split(",");
        if(values[0].equals("n")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;     
        while(!q.isEmpty() && i < values.length){
            TreeNode curr = q.poll();
            curr.left = values[i].equals("n") ? null : new TreeNode(Integer.parseInt(values[i]));
            if(i++ < values.length) curr.right = values[i].equals("n") ? null : new TreeNode(Integer.parseInt(values[i]));
            if(curr.left != null) q.add(curr.left);
            if(curr.right != null) q.add(curr.right);
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

Posted 2022-05-05Updated 2022-05-04LeetCode / Medium / 复习3 minutes read (About 384 words)

201. Bitwise AND of Numbers Range

Question

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Solution

进行按位和运算时，只要两个位不都是1就会为0。从left到right之间，如果left和right的前x位是一样的，那么两者之间必定有一个数字
在x位上为1，后面的位上为0。因此和这个数字进行按位和运算必定为0。
因此，我们只要保留前面两者相同的位的信息即可，后面均为0。

当left与right不相等时，将两者同时右移，并计算移动的总数。
当两者相等时，向左移动计算的总数的位数。就保留了其相同的前缀。

Code

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int count = 0;
        
        while(left != right){
            left >>= 1;
            right >>= 1;
            count++;
        }
        return left << count;
    }
}

Solution 2

利用一串只有一个1的32位数字作为掩码，获得两个数字单独的位信息。
32位整数的第一位是符号位。因此我们的掩码从第1位开始直到第31位。
当对left和right进行该位的掩码操作后，如果两者相同，则掩码右移一位。
并将答案和当前位进行位或运算。（相当于保存当前位的位信息。）

如果不同，或者掩码变为0，则返回结果。

Code

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int mask = 1 << 30;
        int ans = 0;
        
        while(mask > 0 && (mask & left) == (mask & right)){
            ans |= (mask & left);
            mask >>= 1;
        }
        return ans;
    }
}

Posted 2022-05-04Updated 2022-05-04LeetCode / Medium2 minutes read (About 358 words)

1679. Max Number of K-Sum Pairs

Question

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Solution

两种思路，第一种，哈希表统计总数，然后逐个排除。
每次从数组中取一个数，先查询寻找的target是否在哈希表内。
如果表内存在target，则将target的计数减一，对数加一。

如果target不在表内，则将当前的数字加入表内。
最后返回结果。时间复杂度为O(n)。

Code

class Solution {
    public int maxOperations(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for(int num : nums){
            int target = k - num;
            if(map.containsKey(target) && map.get(target) > 0){
                map.put(target, map.get(target)-1);
                count++;
            }
            else{
                map.put(num, map.getOrDefault(num, 0)+1);
            }
        }
        return count;
    }
}

Solution 2

第二种思路，先排序。
然后双指针放在首尾。
当两者的和等于目标值时增加计数器，并移动两个指针。
当两者的和大于目标值时，右侧指针左移。
当两者的和小于目标值时，左侧指针右移。
最后返回结果。由于有排序存在，因此时间复杂度为O(nlogn) + O(n)。

Code

class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int left = 0, right = nums.length-1, count = 0;

        while(left < right){
            if(nums[left] + nums[right] == k){
                count++;
                left++;
                right--;
            }
            else if(nums[left] + nums[right] > k){
                right--;
            }
            else{
                left++;
            }
        }
        return count;
    }
}

Posted 2022-05-04Updated 2022-05-04LeetCode / Medium2 minutes read (About 268 words)

841. Keys and Rooms

Question

There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Solution

BFS，创建一个数组记录房间是否被访问。（用DFS搜素亦可。）

如果钥匙对应的房间已经访问过则跳过。
如果未访问过则记录为已访问并加入队列。

最后遍历一次访问状态，如果有没访问过的房间则返回false。反之返回true。

Code

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int[] visited = new int[rooms.size()];
        visited[0] = 1;
        Queue<List<Integer>> q = new LinkedList<>();
        q.add(rooms.get(0));
        
        while(!q.isEmpty()){
            List<Integer> keys = q.poll();
            for(int key : keys){
                if(visited[key] == 1) continue;
                visited[key] = 1;
                q.add(rooms.get(key));
            }
        }
        
        for(int i=1; i<rooms.size(); i++){
            if(visited[i] == 0) return false;
        }
        return true;
    }
}

Posted 2022-05-04Updated 2022-05-04LeetCode / Medium / 复习a minute read (About 158 words)

1557. Minimum Number of Vertices to Reach All Nodes

Question

Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [from i, to] represents a directed edge from node from i to node to i .

Find the smallest set of vertices from which all nodes in the graph are reachable. It’s guaranteed that a unique solution exists.

Notice that you can return the vertices in any order.

Answer

由于是有向无环图（Directed acyclic graph），因此直接计算图内的入度为0的节点即可。
每条路径都需要从入度为0的点开始。

Code

class Solution {
    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        List<Integer> ret = new ArrayList<>();
        int[] inDegrees = new int[n];
        for(List<Integer> edge : edges){
            inDegrees[edge.get(1)]++;
        }
        for(int i = 0; i < n; i++){
            if(inDegrees[i] == 0) ret.add(i);
        }
        return ret;
    }
}

Posted 2022-05-04Updated 2022-05-04LeetCode / Easy / 复习a minute read (About 220 words)

997. Find the Town Judge

Question

In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

The town judge trusts nobody.

Everybody (except for the town judge) trusts the town judge.

There is exactly one person that satisfies properties 1 and 2.

You are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi.

Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Solution

题目可以转换为计算各个顶点的入度和出度。

遍历每条边，并计算边上两个顶点的出度和入度。
如果某个节点的入度为n-1，出度为0，则符合有法官的条件。
否则没有法官，返回-1。

Code

class Solution {
    public int findJudge(int n, int[][] trust) {
        int[] inDegrees = new int[n];
        int[] outDegrees = new int[n];
        
        for(int[] edge : trust){
            outDegrees[edge[0]-1]++;
            inDegrees[edge[1]-1]++;
        }
        for(int i = 0; i < n; i++){
            if(outDegrees[i] == 0 && inDegrees[i] == n-1) return i+1;
        }
        return -1;
    }
}

Posted 2022-05-04Updated 2022-05-04LeetCode / Hard2 minutes read (About 331 words)

72. Edit Distance

Question

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character

Delete a character

Replace a character

Solution

本题和583. Delete Operation for Two Strings大同小异。

动态规划，两个字符串的分别以长宽组成一个矩阵，记录该位置得编辑距离。
将初始的编辑距离dp[i][0]一行和dp[0][j]一列按照对应的位置i和j填写。

双重遍历矩阵的坐标。
当两个字符相等时，编辑距离等于对角线方向的状态的编辑距离（即两个字符都没有取得上一个状态）。
当两个字符不相等时，编辑距离等于左边，上边（少取一个字符的状态）以及对角线方向（两个字符都不取的状态）的编辑距离中得最小值再加上1。

Code

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        char[] bin1 = word1.toCharArray();
        char[] bin2 = word2.toCharArray();
        int[][] dp = new int[m+1][n+1];
        
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n; j++){
            dp[0][j] = j;
        }
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(bin1[i-1] == bin2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(dp[i-1][j-1] + 1, Math.min(dp[i-1][j], dp[i][j-1]) + 1);
                }
            }
        }
        return dp[m][n];
    }
}

Posted 2022-05-04Updated 2022-05-04LeetCode / Medium3 minutes read (About 499 words)

343. Integer Break

Question

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Solution

动态规划，用数组dp[]记录最大乘积。
在n < 4之前为特例，由于必须拆分，因此乘积小于自身。但由于之后的数字要用到拆分的特性，因此这三个数字要特殊设置为自身。
在此之后，每个数字可以拆分成两个数的加和，然后乘积等于对应两个数的乘积。
（dp[4]可以不设置计算得出，但是指定值的话可以加快速度。）

Code

class Solution {
    public int integerBreak(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
  
        for(int i = 4; i <= n; i++){
            for(int j = 1; j <= (i/2)+1; j++){
                int k = i - j;
                dp[i] = Math.max(dp[i], dp[j] * dp[k]);
            }
        }
        return dp[n];
    }
}

Solution 2

数学方法，当两数之和大于4时，拆分成两个更小的加和可以得到更大的乘积。
而当等于4时，可以拆分为两个2相乘。
因此，最终有意义的拆分结果只会有2和3。

拆分规则：

最优： 3 。把数字 n 可能拆为多个因子 3 ，余数可能为 0,1,2 三种情况。

次优： 2 。若余数为 2 ；则保留，不再拆为 1+1 。

最差： 1 。若余数为 1 ；则应把一份 3+1 替换为 2 + 22+2，因为 2 * 2 > 3 * 1

Code

class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        }
        else if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        }
        else {
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

Solution 3

同样，我们可以将之前的结论用在动态规划上，j只取2或3，将时间复杂度从O(n^2)降低到O(n)。

Code

class Solution {
    public int integerBreak(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
  
        for(int i = 4; i <= n; i++){
            for(int j = 2; j <= 3; j++){
                int k = i - j;
                dp[i] = Math.max(dp[i], dp[j] * dp[k]);
            }
        }
        return dp[n];
    }
}

Question

Solution

Code

Question

Solution

push()

top() & pop()

empty()

Code

Question

Solution

Solution 2

Code

Solution 3

Question

Solution

Code

Problem

Solution

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

编码过程

解码过程

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Solution 2

Code

Question

Solution

Code

Question

Answer

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

Code

Solution 2

Code

Solution 3

Code

Recents

Archives

Links