目录
- 一、寻找重复数
- 二、最小栈
- 三、Z 字形变换
- 四、二叉树展开为链表
- 五、提莫攻击
- 六、用队列实现栈
- 七、数青蛙
- 八、重排链表
- 九、螺旋矩阵
- 十、螺旋矩阵Ⅱ
一、寻找重复数
寻找重复数
我们将数组逻辑转化为一个链表，下标为 i 是值域，指针域就是nums[ i ]。由于会有重复的nums[ i ]，所以这样的链表一定是有环的，使用快慢指针即可。
慢指针 slow 和快指针 fast ，慢指针每次走一步，快指针每次走两步，根据「Floyd 判圈算法」两个指针在有环的情况下一定会相遇，此时我们再将 slow 放置起点 0，两个指针每次同时移动一步，相遇的点就是答案。
时间复杂度：O（N） 空间复杂度：O（1）
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
}while(slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
二、最小栈
最小栈 
我们使用两个栈，一个stack正常存数据，一个minStack存入最小值顺序。 push 方法，只需要放入stack，minstack放入时，如果有数据必须时比当前栈顶元素小才能进。 pop方法：出stack栈的元素，并且当前元素与minstack元素相同，minstack也出元素。 top：返回stack栈顶元素 getMin：返回minstack栈顶元素
时间复杂度：O（1） 空间复杂度：O（N）
class MinStack {
Stack<Integer> stack ;
Stack<Integer> minStack ;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if(minStack.empty()){
minStack.push(val);
}else if(minStack.peek() >= val){
minStack.push(val);
}
}
public void pop() {
int val = stack.pop();
if(!minStack.empty()){
if(val == minStack.peek()){
minStack.pop();
}
}
}
public int top() {
return stack.peek();
}
public int getMin() {
if(minStack.empty()){
return –1;
}
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
三、Z 字形变换
Z 字形变换 模拟 ，观察案例可以看出每一个字母的下一个对应的下标差值其实是固定的 2 * numRows – 2，我们只需要确定每一行的开头元素即可。第一行和最后一行的起始元素都是一个，很好确认，中间行的开始元素是两个一个 i ,另一个是公差减去i 。遍历即可。
时间复杂度：O（N） 空间复杂度：O（1）
class Solution {
public String convert(String s, int numRows) {
int len = s.length();
int d = 2 * numRows – 2; //公差d
StringBuffer ret = new StringBuffer();
if(numRows == 1) return s;
//第一行
for(int i = 0; i < len; i += d) {
ret.append(s.charAt(i));
}
//中间行
for(int i = 1; i < numRows – 1; i++) {
for(int j = i, k = d – i; j < len || k < len; j += d, k += d) {
if(j < len) ret.append(s.charAt(j));
if(k < len) ret.append(s.charAt(k));
}
}
//最后一行
for(int i = numRows – 1; i < len; i += d) {
ret.append(s.charAt(i));
}
return ret.toString();
}
}
四、二叉树展开为链表
二叉树展开为链表 我们遍历二叉树，当 当前节点 有左子树的时候，我们就将当前节点的右子树拼接到左子树的最右节点的右节点，比如第一个例子，就将5拼接在4的right节点。 然后将左子树放入当前节点的右节点， 左节点置空。 往当前节点右节点循环遍历即可。
时间复杂度：O（N） 空间复杂度：O（1） 
五、提莫攻击
提莫攻击 
模拟，我们只需要遍历timeSeries数组，看当前的元素加上中毒时间会不会超出下一个元素所在时间节点即可。超出就只加两个元素之间的时间，没超出就加上中毒时间。
时间复杂度：O（N） 空间复杂度：O（1）
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int ret = duration;
for(int i = 0; i < timeSeries.length – 1; i++) {
if( (timeSeries[i] + duration – 1) < timeSeries[i+1]) {
ret += duration;
} else {
ret = ret + (timeSeries[i+1] – timeSeries[i]);
}
}
return ret;
}
}
六、用队列实现栈
用队列实现栈
我们只需要一直保持有一个空队列即可，出栈操作的时候，将非空队列元素移入空队列，最后一个元素进行poll或者peek操作。
时间复杂度：O（N） 空间复杂度：O（N）
class MyStack {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();;
}
public void push(int x) {
if(queue1.isEmpty()) {
queue2.offer(x);
} else {
queue1.offer(x);
}
}
public int pop() {
if(empty()) { //栈为空
return –1;
} else if(!queue1.isEmpty()) { //队列1有元素
int size = queue1.size();
for(int i = 0; i < size – 1; i++) {
queue2.offer( queue1.poll() );
}
return queue1.poll();
} else { //队列2有元素
int size = queue2.size();
for(int i = 0; i < size – 1; i++) {
queue1.offer( queue2.poll() );
}
return queue2.poll();
}
}
public int top() {
if(empty()) { //栈为空
return –1;
} else if(!queue1.isEmpty()) { //队列1有元素
int size = queue1.size();
for(int i = 0; i < size – 1; i++) {
queue2.offer( queue1.poll() );
}
int ret = queue1.poll();
queue2.offer(ret);
return ret;
} else { //队列2有元素
int size = queue2.size();
for(int i = 0; i < size – 1; i++) {
queue1.offer( queue2.poll() );
}
int ret = queue2.poll();
queue1.offer(ret);
return ret;
}
}
public boolean empty() {
return queue1.isEmpty() && queue2.isEmpty();
}
}
/**
* 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();
*/
七、数青蛙
数青蛙 
我们遍历字符串，将叫声croak按照顺序存储在一个数组中。 当遍历到一个字符的时候：有以下情况：
- 正常情况：将对应数组下标元素加1
- 错误情况：字符出现次数超出已有的青蛙，比数组前一个元素大
- 没叫完：当遍历完后，数组中元素没全变0
时间复杂度：O（N） 空间复杂度：O（1）
class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
int[] hash = new int[5];
int ret = 0;
for(int i = 0; i < croakOfFrogs.length(); i++) {
if('c' == croakOfFrogs.charAt(i)) {
hash[0]++;
ret = Math.max(ret, hash[0]);
} else if ('r' == croakOfFrogs.charAt(i)) {
if(++hash[1] > hash[0]) {
return –1;
}
ret = Math.max(ret, hash[1]);
} else if ('o' == croakOfFrogs.charAt(i)) {
if(++hash[2] > hash[1]) {
return –1;
}
ret = Math.max(ret, hash[2]);
} else if ('a' == croakOfFrogs.charAt(i)) {
if(++hash[3] > hash[2]) {
return –1;
}
ret = Math.max(ret, hash[3]);
} else {
for(int j = 0; j < 4; j++) {
hash[j]—;
if(hash[j] < 0) return –1;
}
}
}
//查看结果
for(int j = 0; j < 4; j++) {
if(hash[j] != 0) return –1;
}
return ret;
}
}
八、重排链表
重排链表
三步：
- 快慢双指针，找中间节点
- 头插逆置后半段节点
- 合并两段链表 引入一个哨兵节点，可以减少边界情况讨论。
时间复杂度：O（N） 空间复杂度：O（1）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
ListNode slow = head;
ListNode fast = head;
//快慢双指针，找中间节点
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//头插逆置后半段节点
ListNode head2 = null;
ListNode cur = slow.next;
slow.next = null;
while(cur != null) {
ListNode next = cur.next;
cur.next = head2;
head2 = cur;
cur = next;
}
//合并两段链表
ListNode newHead = head;
ListNode cur1 = head;
ListNode cur2 = head2;
while(cur1 != null && cur2 != null) {
ListNode next1 = cur1.next;
ListNode next2 = cur2.next;
cur1.next = cur2;
cur2.next = next1;
cur1 = next1;
cur2 = next2;
}
}
}
九、螺旋矩阵
螺旋矩阵 
我们模拟顺时针走的过程，当超出边界的时候 或者 是已经访问的元素的时候，就让他进入下一个步骤的起点。 当所有元素全部访问完就可以了。 时间复杂度：O（M*N） 空间复杂度：O（1）
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ret = new ArrayList<>();
//记录当前走的方向 0-右 1-下 2-左 3-上
int flag = 0;
int len = matrix.length * matrix[0].length;
int i = 0;
int j = 0;
while(len != 0) {
//向右
while( matrix[i][j] != –101 && 0 == flag) {
ret.add(matrix[i][j]);
matrix[i][j] = –101;
j++;
len—;
//超出界限
if(j == matrix[0].length || matrix[i][j] == –101){
j—;
break;
}
}
//向下
while( matrix[i][j] != –101 && 1 == flag) {
ret.add(matrix[i][j]);
matrix[i][j] = –101;
i++;
len—;
//超出界限
if(i == matrix.length || matrix[i][j] == –101) {
i—;
break;
}
}
//向左
while( matrix[i][j] != –101 && 2 == flag) {
ret.add(matrix[i][j]);
matrix[i][j] = –101;
j—;
len—;
//超出界限
if(j == –1 || matrix[i][j] == –101) {
j++;
break;
}
}
//向上
while(matrix[i][j] != –101 && 3 == flag) {
ret.add(matrix[i][j]);
matrix[i][j] = –101;
i—;
len—;
//超出界限
if(i == –1 || matrix[i][j] == –101) {
i++;
break;
}
}
//下一步
if(flag == 0) {
if(matrix[i][j] == –101) {
i++;
}
flag++;
} else if(flag == 1) {
if(matrix[i][j] == –101) {
j—;
}
flag++;
}else if(flag == 2) {
if(matrix[i][j] == –101) {
i—;
}
flag++;
}else {
if(matrix[i][j] == –101) {
j++;
}
flag = 0;
}
}
return ret;
}
}
十、螺旋矩阵Ⅱ
螺旋矩阵Ⅱ 
我们跟上面还是一样的思路，但是我们先将每一步要如何走用数组写出来，当开始走的时候，先去看下一步是不是没有 超出数组边界 或者 没有遍历过。如果不满足条件，就走下一个方向。 时间复杂度：O（N*N） 空间复杂度：O（1）
class Solution {
public int[][] generateMatrix(int n) {
int[][] ret = new int[n][n];
int len = n*n;
//使用数组来表示顺时针执行 右下左上
int[][] tep = new int[][]{{0,1},{1,0},{0,–1},{–1,0}};
int row = 0, column = 0;
//表示当前执行 0-右 1-下 2-左 3-上
int flag = 0;
for(int i = 1; i <= len; i++) {
ret[row][column] = i;
int nextRow = row + tep[flag][0];
int nextColumn = column + tep[flag][1];
if (nextRow < 0 || nextRow >= n
|| nextColumn < 0 || nextColumn >= n
|| ret[nextRow][nextColumn] != 0) {
flag = (flag + 1) % 4; // 顺时针旋转至下一个方向
}
row += tep[flag][0];
column += tep[flag][1];
}
return ret;
}
}
