剑指offer 09 用两个栈实现队列
class CQueue {
// stack 的声明必须是公共的，否则后续方法无法调用
Stack<Integer> stack1;
Stack<Integer> stack2;
//CQueue 就是为了新建对象
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
//当stack2时空，先判断stack1是否空，是 -> 返回-1
// 否 -> 开始转移
if(stack2.isEmpty()){
if(stack1.isEmpty()){
return -1;
}
while(!stack1.isEmpty()){
int temp = stack1.pop();
stack2.push(temp);
}
}
return stack2.pop();
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
剑指offer 30 包含min函数的栈
最小栈
class MinStack {
Stack<Integer> stack1;
Stack<Integer> stack2;
/** initialize your data structure here. */
public MinStack() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
// 要 >=, 例如，push进的两个2都为最小，stack2若不同步，则在后续min操作会输出错误结果
if(stack2.isEmpty()||stack2.peek() >= x){
stack2.push(x);
}
}
//如果stack1 顶端pop的恰好是最小值，stack2 要同步
public void pop() {
// stack1.pop(); 这里无序加，因为在下面判断中，stack1已经删除顶端了
// 必须用equals
if(stack2.peek().equals(stack1.pop())){
stack2.pop();
}
}
public int top() {
int top = stack1.peek();
return top;
}
public int min() {
return stack2.peek();
}
}
/**
* 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.min();
*/
剑指offer 31 栈的压入，弹出序列
这是第一次自己的想法做出的中等难度的题，希望越来越好了 :)
栈的压入，弹出序列
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
if(pushed.length != popped.length) return false;
Stack<Integer> stack1 = new Stack<>();
// 把pushed每一个元素都push进stack1中，过程中如果遇到poped首个元素，则pop掉
// 对照最后stack1是否为空且j指针完全遍历
int j = 0;
for(int i: pushed){
stack1.push(i);
while(stack1.peek().equals(popped[j])){
stack1.pop();
j++;
//勿忘break
if(stack1.isEmpty()) break;
}
}
if(stack1.isEmpty() && j == popped.length) return true;
return false;
}
}
剑指offer 58-i 翻转单词顺序
String.trim(); 去除前后的空格
对于.equals 和 == 之间区别的讨论
String和StringBuilder和StringBuffer之间的区别
class Solution {
public String reverseWords(String s) {
String[] words = s.split(" ");
StringBuilder ans = new StringBuilder();
for(int i = words.length-1; i>=0; i--){
//要用equals
if(!words[i].equals("")){
ans.append(words[i]);
ans.append(" ");
}
}
return ans.toString().trim();
}
}
剑指offer 59-i 滑动窗口最大值
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null) return new int[0];
if(nums.length == 0 || k == 1) return nums;
int[] ans = new int[nums.length - k + 1];
//取前k个最大值
int curMax = Integer.MIN_VALUE;
for(int i=0; i<k; i++){
if(curMax < nums[i]) curMax = nums[i];
}
ans[0] = curMax;
for(int i=k; i < nums.length; i++){
/*如果取走的是最大值
0 1 2 3 4 5 6 7 <- i index
[1,3,4,2,1,9,4,10] k=3 len=8
| |
| ans[i-k+1] = ans[1] 第一次移动
nums[i-k] = nums[0]
*/
if(curMax == nums[i-k]){
curMax = nums[i-k+1];
//重新在窗口中找最大值
for(int j=i-k+1; j<=i; j++){
curMax = Math.max(curMax,nums[j]);
}
}
if(curMax < nums[i]) curMax = nums[i];
ans[i-k+1] = curMax;
}
return ans;
}
}
