算法练习LeetCode初级算法之设计问题

时间:2023-02-09 09:10:28
  • 打乱数组

不断的让第一个与后面随机选择的数交换

class Solution {

private int[] nums;

private int[] initnums;

public Solution(int[] nums) {

this.nums=nums;

this.initnums=Arrays.copyOf(nums, nums.length);//这里必须要复制,要指明对象

}

/** Resets the array to its original configuration and return it. */

public int[] reset() {

return initnums;//这里返回上面的复制

}

/** Returns a random shuffling of the array. */

public int[] shuffle() {

Random random=new Random();

for (int i = 0; i <nums.length/2; i++) {

swap(nums, 0, random.nextInt(nums.length));

}

return nums;

}

private void swap(int[] nums,int i,int j) {

int temp=nums[i];

nums[i]=nums[j];

nums[j]=temp;

}

}

  • 最小栈

  • 自己写的有点慢,勉强通过

    class MinStack {

    /** initialize your data structure here. */

    Stack<Integer> stack;

    public MinStack() {

    stack=new Stack<>();

    }

    public void push(int x) {

    stack.push(x);

    }

    public void pop() {

    if (!stack.isEmpty()) {

    stack.pop();

    }

    }

    public int top() {

    return stack.peek();//这里和我之前理解的不太一样,之前是取栈顶顺便就删除了

    }

    public int getMin() {

    Stack<Integer> stack2=new Stack<>();

    stack2.addAll(0, stack);

    Collections.sort(stack2);

    return stack2.get(0);

    }

    }

  • 双栈法挺快

    class MinStack {

    /** initialize your data structure here. */

    Stack<Integer> stack,minStack;

    public MinStack() {

    stack=new Stack<>();

    minStack=new Stack<>();

    }

    public void push(int x) {

    stack.push(x);

    if (minStack.isEmpty()) {

    minStack.push(x);

    }else if (x<=minStack.peek()) {//此处若没有等号

    minStack.push(x);

    }

    }

    public void pop() {

    if (stack.peek().equals(minStack.peek())) {//这里可能会提示栈为空的异常

    stack.pop();

    minStack.pop();

    }else {

    stack.pop();

    }

    }

    public int top() {

    return stack.peek();

    }

    public int getMin() {

    return minStack.peek();

    }

    }