class MyStack:

def __init__(self):
    self.Que_1 = []
    self.Que_2 = []

def push(self, x: int) -> None:
    # Push element x onto stack. 
    self.Que_1.append(x)

def pop(self) -> int:
    # Removes the element on top of the stack and returns that element.
    while len(self.Que_1)>1:
        self.Que_2.append(self.Que_1.pop(0))
    res = self.Que_1.pop(0)
    self.Que_1, self.Que_2 = self.Que_2, self.Que_1
    self.Que_2.clear()
    return res

def top(self) -> int:
    # Get the top element.
    while len(self.Que_1)>1:
        self.Que_2.append(self.Que_1.pop(0))
    res = self.Que_1[0]
    self.Que_2.append(self.Que_1.pop(0))
    self.Que_1, self.Que_2 = self.Que_2, self.Que_1
    self.Que_2.clear()
    return res

def empty(self) -> bool:
    return not self.Que_1

入栈操作（push）：O(1)
出栈操作（pop）：平均情况下接近O(1)，最坏情况下O(n)
获取栈顶元素（top）：平均情况下接近O(1)，最坏情况下O(n)
判空操作（empty）：O(1)

思路分析

1. 遍历链表统计长度：首先遍历链表，统计链表的长度。这是为了确定每个部分的长度以及可能存在的剩余节点数。
2. 计算分割数量和长度：根据给定的分割数量k和链表长度，计算出每个部分的平均长度（即链表长度除以分割数量），以及前面多余的部分的长度（即链表长度对分割数量取余）。
3. 分割链表：再次遍历链表，根据计算出的长度将链表分割成k个部分，并将每个部分的尾节点的next指针置为空。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        if not head:
            return [None for _ in range(k)]

        length = 0
        node = head
        while node:
            length += 1
            node = node.next

        # 计算每段的长度以及多出的部分
        avg_len, extra_len = length//k, length%k 

        # 再次遍历链表，根据 avg_len 和 extra_len 将链表分割成 k 个部分
        # 并将每个部分的尾节点的 next 指针置为空。
        res = []
        cur = head
        pre = None

        for _ in range(k):
            res.append(cur)
            for _ in range(avg_len+(1 if extra_len > 0 else 0)):
                pre = cur
                cur = cur.next
            if pre:
                pre.next = None
            extra_len -= 1
        return res

复杂度分析

• 时间复杂度：O(n)，其中n是链表的长度，需要遍历链表两次。
• 空间复杂度：O(1)

参考力扣725.分隔链表，k恒定为3即可。

利用差值存入栈中可以保证O（1）的空间复杂度

class MinStack {
    Deque<Integer> stack;
    Deque<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
    }

    public void push(int x) {
        stack.offerLast(x);
        if(minStack.isEmpty() || x <= minStack.peekLast()) {
            minStack.offerLast(x);
        }
    }

    public void pop() {
        int i = stack.pollLast();
        if(i == minStack.peekLast()) {
            minStack.pollLast();
        }
    }

    public int top() {
        return stack.peekLast();
    }

    public int getMin() {
        return minStack.peekLast();
    }
}

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

时间复杂度O（1）,空间复杂度O（n）

class Solution {
    public int[] spiralArray(int[][] array) {
        if(array==null||array.length==0){
            return new int[0];
        }
        int m = array.length;
        int n = array[0].length;
        int[] res = new int[m*n];
        int up = 0;//上边界
        int down = m-1;//下边界
        int left = 0;//左边界
        int right = n-1;//右边界
        int index = 0;
        while(up<=down||left<=right){
            //往右走
            for(int i=left;i<=right;i++){
                res[index++] = array[up][i];
            }
            up++;
            if(up>down){
                break;
            }
            //往下走
            for(int i=up;i<=down;i++){
                res[index++] = array[i][right];
            }
            right--;
            if(right<left){
                break;
            }
            //往左走
            for(int i = right;i>=left;i--){
                res[index++] = array[down][i];
            }
            down--;
            if(down<up){
                break;
            }
            //往上走
            for(int i = down;i>=up;i--){
                res[index++] = array[i][left];
            }
            left++;
            if(left>right){
                break;
            }
        }
        return res;
    }
}
思路：定义左边界、有边界、上边界和下边界，然后可以向右走、向下走、
向左走和向上走，同时创建一个res数组用来保存访问到的数组元素
时间复杂度：O(mn)
空间复杂度：O(1)

class Solution {
public int jewelleryValue(int[][] frame) {
int m = frame.length;
int n = frame[0].length;

    int[][] dp = new int[m][n];
    dp[0][0] = frame[0][0];
    for(int j=1; j<n; j++){
        dp[0][j] = dp[0][j-1] + frame[0][j];
    }
    for(int i=1; i<m; i++){
        dp[i][0] = dp[i-1][0] + frame[i][0];
    }

    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + frame[i][j];
        }
    }

    return dp[m-1][n-1];
}

}

时间：O(mn)
空间：O(mn)

暴力法：
class Solution {
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        //暴力法
        if(plants==null||plants.length==0){
            return false;
        }
        int m = plants.length;
        int n = plants[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(plants[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }
}
时间复杂度：O(n2)
空间复杂度：O(1)

最优解：
class Solution {
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        if(plants==null||plants.length<=0){
            return false;
        }
        int i = plants.length-1;
        int j = 0;
        while(i>=0&&j<plants[0].length){
            if(plants[i][j]==target){
                return true;
            }
            if(plants[i][j]<target){
                j++;
            }else{
                i--;
            }
        }
        return false;
    }
}
时间复杂度：O(m+n)
空间复杂度：O(1)

数学+迭代法：
class Solution {
    public int iceBreakingGame(int num, int target) {
        int x = 0;
        for (int i = 2; i <= num; i++) {
            x = (x + target) % i;
        }
        return x;
    }
}

链表法，模拟删除，但是后面会超时：
class Solution {
    public int iceBreakingGame(int num, int target) {
        Node pre = new Node();
        Node cur = pre;
        //构造环形数组
        for(int i=0;i<num;i++){
            cur.next = new Node(i,null);
            cur = cur.next;
        }
        cur.next = pre.next;//现在cur指向的是最后一个元素
        cur = cur.next;//此时cur指向第一个元素
        while(cur.next!=cur){
            int count = 1;
            while(count<target){
                cur = cur.next;//往后走一步
                count++;
            }
            //把cur所指向的节点删除
            cur.val = cur.next.val;
            cur.next = cur.next.next;
        }
        return cur.val;
    }
}
class Node{
    int val;
    Node next;
    public Node(){

    }
    public Node(int val,Node next){
        this.val = val;
        this.next = next;
    }
}

class Solution {
    public int fib(int n) {
        final int MOD = 1000000007;
        if(n<=1){
            return n;
        }
        int first = 0;
        int second = 1;
        for(int i=2;i<=n;i++){
            int temp = first+second;
            first = second;
            second = temp%MOD;
        }
        return second;
    }
}
时间复杂度：O(n)
空间复杂度：O(1)
需要注意题意里的取模部分，给我恶心坏了

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        if(dungeon==null||dungeon.length<=0||dungeon[0].length<=0){
            return 0;
        }
        int m = dungeon.length;
        int n = dungeon[0].length;
        //dp[i][j]表示从i,j位置到终点所需要的最少血量
        int[][] dp = new int[m][n];
        //初始值
        //如果dungeon[m-1][m-1]是正值，说明这里会加血，所以初始值不需要设置
        //如果是负值的话，说明这里会减血，所以需要设置初始值
        dp[m-1][n-1] = Math.max(-dungeon[m-1][n-1],0);
        //设置最后一行的值
        for(int i = n-2;i>=0;i--){
            int needMin = dp[m-1][i+1]-dungeon[m-1][i];
            dp[m-1][i] = Math.max(needMin,0);
        }
        //设置最后一列的值
        for(int i=m-2;i>=0;i--){
            int needMin = dp[i+1][n-1]-dungeon[i][n-1];
            dp[i][n-1] = Math.max(needMin,0);
        }

        for(int i=m-2;i>=0;i--){
            for(int j = n-2;j>=0;j--){
                int needMin = Math.min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];
                dp[i][j] = Math.max(0,needMin);
            }
        }
        return dp[0][0]+1;
    }
}
思路：由于这个题在往后便利过程中会涉及到加血，
所以i,j位置的值可能是和后面的值有关系，不像之前的题那样，
i，j位置的值只与左或者上的值有关，所以这个题可以从后往前推，
如果从后往前推，之前的动归思想都是从开始位置到当前位置的xxx，
而这里的dp[i][j]表示的就是从当前位置到最后所需要的血量。
这时候前一位置的血量要根据右边和下边的值来判断，
所需要的最小血量needMin = Math.min(dp[i+1][j],dp[i][j+1]),
dp[i][j] = Math.max(needMin-dungeon[i][j],0)

这个题我最开始的时候陷入了一个误区：要凑出来面值为amount，而且同时
硬币数量还得最少，那就从最大面值的硬币开始分配，这样最后结果就会是
最小的面值，这种想法本身没问题，但是可能会出现这种情况：一直用最大面值
硬币匹配导致最后剩下的amount值不足以匹配剩余的硬币，所以这种是有问题的
class Solution {
    public int coinChange(int[] coins, int amount) {
        //dp[i]表示组成金额i所需要的最少的硬币数量
        //前面凑出来的i的最小的硬币数量可以用来凑后面的i的硬币数量
        //由于后面的i的硬币数量需要依赖前面的i的硬币数量，所以后面的i
        //能凑出来的话dp[i]值一定是小于amount+1的，否则就返回-1
        int[] dp = new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for(int i=1;i<amount+1;i++){
            for(int j=0;j<coins.length;j++){
                //防止越界，因为i表示金额值，coins[j]表示第j枚硬币的金额值，i不应该小于coins[j]
                if(coins[j]<=i){
                    dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }
}
思路：数组dp[i]表示凑出来面值为i时需要的最少的硬币数量；如果面值为i
的时候前面的都凑不出来，那i的面值肯定也凑不出来，就返回-1；
否则就动态计算需要的面值，dp[i] = Math.min(dp[i],dp[i-coins[j]]+1)，最后返回结果。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(coins.size() <= 0){
            return 0;
        }

        int Max = amount + 1;
        // 定义 dp[i] 为组成金额 i 所需最少的硬币数量
        // 初始值设置为需要 amount + 1 的硬币，这是最大值了
        vector<int> dp(amount + 1, Max); 

        dp[0] = 0;
        for(int i = 1; i <= amount; ++i){
            for(int j = 0; j < coins.size(); ++j){
                if(coins[j] <= i){
                    dp[i] = min(dp[i], dp[i-coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;

    int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0];
    for(int j=1; j<n; j++){
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    for(int i=1; i<m; i++){
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }

    for(int i=1; i<m; i++){
        for(int j=1; j<n; j++){
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

}

时间：O(mn)
空间：O(mn)

/*一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 */
class Solution {
    public int takeAttendance(int[] records) {
        int left = 0 , right = records.length - 1;
        while(left < right){
            int mid = (right - left)/2 + left;
            if(records[mid] == mid){
                left = mid + 1;
            }
            else{
                right = mid;
            }    
        }

        if(records[left] == left){
                left = left + 1;
        }
        return left;
    }
}

思路：模拟顺时针打印矩阵，需要注意边界情况

“`c++
class Solution {
public:
vector spiralArray(vector>& array) {
if (array.empty()) return {};
int m = array.size(), n = array[0].size();
vector ans(m*n, 0);
int idx = 0;
int l = 0, r = n-1, t = 0, b = m-1;
while (true) {
// top row: t, j = [l -> r]
for (int j=l; j<=r; j++) { ans[idx++] = array[t][j]; } // top row is over. if (++t > b) break;
// right col: i = [t -> b], r
for (int i=t; i<=b; i++) { ans[idx++] = array[i][r]; } // right col is over. if (--r < l) break; // bottom row: b, j = [r -> l]
for (int j=r; j>=l; j–) {
ans[idx++] = array[b][j];
}
// bottom row is over.
if (–b < t) break; // left col: i = [b -> l], l
for (int i=b; i>=t; i–) {
ans[idx++] = array[i][l];
}
// left col is over.
if (++l > r) break;
}
return ans;
}
};
“`

class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int[][] dp = new int[dungeon.length][dungeon[0].length];
dp[dungeon.length-1][dungeon[0].length-1] = 1 + Math.max(0, – dungeon[dungeon.length-1][dungeon[0].length-1]);
for(int i = dungeon.length – 2; i >= 0; i–){
dp[i][dungeon[0].length – 1] = Math.max(1,dp[i + 1][dungeon[0].length – 1] – dungeon[i][dungeon[0].length – 1]);
}
for(int j = dungeon[0].length – 2; j >= 0; j–){
dp[dungeon.length – 1][j] = Math.max(1, dp[dungeon.length – 1][j + 1] – dungeon[dungeon.length – 1][j]);
}

    for(int i = dungeon.length - 2; i >= 0; i--){
        for(int j = dungeon[0].length - 2; j >= 0; j--){
            dp[i][j] = Math.max(1,Math.min(dp[i+1][j],dp[i][j+1]) - dungeon[i][j]);
        }
    }
    return dp[0][0];
}

}
//dp
//空间复杂度On2
//时间复杂度On2

class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
int i = 0, j = 0, k = 0;
dp[0] = 1;
int current = 1;
while(current < n){
int min = Math.min(dp[i] * 2,Math.min(dp[j] * 3,dp[k] * 5));
dp[current++] = min;
if(min dp[i] * 2) i++;
if(min dp[j] * 3) j++;
if(min dp[k] * 5) k++;
}
return dp[n-1];

}

}
//时间复杂度On 空间复杂度On

class Solution {
    public int[] spiralArray(int[][] array) {
        if(array==null || array.length==0 || array[0].length ==0) return new int[0];

        //记录可移动的列数的范围
        int l=0;
        int r=array[0].length-1;
        // 记录可移动的行数的范围
        int t = 0;
        int b=array.length-1;

        //用于保存结果的数组
        int[] res = new int[(r+1) * (b+1)];
        int index=0;

        while(true){
            //→
            for(int i=t,j=l;j<=r;j++) res[index++]=array[i][j];
            if(++t>b) break; //下次→只能从++b行开始了

            // ↓
            for(int i=t,j=r;i<=b;i++) res[index++]=array[i][j];
            if(l>--r) break; //下次↓只能从--r列开始了

            //←
            for(int i=b,j=r;j>=l;j--) res[index++]=array[i][j];
            if(t>--b) break;//下次→只能从--b行开始了

            //↑
            for(int i=b,j=l;i>=t;i--)  res[index++]=array[i][j];
            if(++l>r) break;//下次↑只能从++l列开始了
        }

        return res;
    }
}

时间复杂度：O(nm)
额外空间复杂度：O(nm)

class Solution {
    public int fib(int n) {
        // 特殊情况
        if( n <= 1){
            return n;
        }

        // int[] dp = new int[n+1];

        // dp[0]=0;
        // dp[1]=1;
        int a =0;
        int b=1;
        int c=0;

        // if(n==0) return b;
        // if(n==1) return 1;

        for(int i=2;i<=n;i++){
            c=(a+b)%1000000007;
            a=b;
            b=c;
        }

        return c;
    }
}

• 哈希表的方法

class Solution {
    public int findRepeatDocument(int[] documents) {

        Map<Integer, Integer> countMap = new HashMap<>();

        for (int document : documents) {
            countMap.put(document, countMap.getOrDefault(document, 0) + 1);

            if(countMap.get(document)>1) return document;
        }

        return -1;
    }
}

时间复杂度o(n),空间复杂度o(n)

• 文件id的范围是0-(n-1)，利用这一点,可以采用坐标法

class Solution {
    public int findRepeatDocument(int[] documents) {

        for(int i=0;i<documents.length;i++){
            while(documents[i]!=i){
                if(documents[i]==documents[documents[i]]) return documents[i];

                int k = documents[documents[i]];
                documents[documents[i]]=documents[i];
                documents[i]=k;
            }
        }

        return -1;
    }
}

时间复杂度：O(n)
额外空间复杂度：O(1)

 /*请实现两个函数，分别用来序列化和反序列化二叉树。 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "";
        }
        //StringBuilder 的特性:利用append拼接八大类型的任一种类型，此时选择以字符串类型进行拼接
        StringBuilder build = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()){
           TreeNode t = queue.poll();
            if(t != null){
                queue.add(t.left);
                queue.add(t.right);
                build.append(t.val + ",");
            }
            else{
                build.append("null,");
            }

        }
        return build.toString();

    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() <= 0){
            return null;
        }
        String[] s = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        //将字符串的第一位先定义好，并入队列
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            //构建左子树
            if(!s[i].equals("null")){
                TreeNode left = new TreeNode(Integer.parseInt(s[i]));
                t.left = left;
                queue.add(left);
            }
            i++;
            //构建右子树
            if(!s[i].equals("null")){
                TreeNode right = new TreeNode(Integer.parseInt(s[i]));
                t.right = right;
                queue.add(right);
            }
            i++;
        }
        return root;

    }
}
时间：On，空间：On

class Solution {
public int findRepeatDocument(int[] documents) {
int cur = 0;
while(cur < documents.length){
if(documents[cur] cur){
cur++;
continue;
}
if(documents[documents[cur]] documents[cur])
return documents[cur];
int temp = documents[documents[cur]];
documents[documents[cur]] = documents[cur];
documents[cur] = temp;
}
return -1;
}
}
//时间复杂度On
//空间复杂度O1

class Solution {
    public int iceBreakingGame(int num, int target) {
        return f(num,target);

    }

    // 返回值为最后留下的元素的号码
    public int f(int num,int target){
        // 退出递归的条件
        if(num==1) return 0;

        // 关系：长度为num的序列删除了一个后成为长度为 num -1的序列

        int x = f(num-1,target);

         return (target + x) % num;
    }
}

时间复杂度：O(num)

空间复杂度：O(num)

class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();

        int[][] dp = new int[n1+1][n2+1];


        // 初始化
        for(int i = 0; i <= n1; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n2; j++){
            dp[0][j] = j;
        }

        for(int i = 1; i <= n1; i++){
            for(int j = 1; j <= n2; j++){
                if(word1.charAt(i-1) != word2.charAt(j-1)){
                    dp[i][j] =Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]) + 1;
                }
                else{
                    dp[i][j]=dp[i-1][j-1];
                }

            }
        }

        return dp[n1][n2];
    }
}