wen 算法笔记1
笔记1
用两个栈实现队列
1、进栈时候进入第一个栈内
2、出栈时将栈1的内容再次压入栈2中，即正向
3、如果栈2没有元素，弹栈需要栈1进栈
4、如果栈2有元素，即上一次进栈元素没有全部弹栈，直接弹栈
package esay.jz9用两个栈实现队列;
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.isEmpty()) {
while (stack1.size() != 0) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
旋转数组的最小数字
/**
* 二分法实现
*
* @param array
* @return
*/
public static int minNumberInRotateArray(int[] array) {
if (array.length == 0) {
return 0;
}
int l = 0;
int r = array.length - 1;
while (l < r - 1) {
int mid = (l + r) >> 1;
if (array[l] < array[mid]) {
l = mid; //说明mid是在左边递减数列中
} else if (array[r] > array[mid]) {
r = mid; //说明mid是在右边递减数列中
} else {
int result = array[0];
for (int i = 0; i < array.length; i++) {
result = Math.min(result, array[i]);
}
return result;
}
}
return array[r];
}
二进制中1的个数
package esay.JZ15二进制中1的个数;
public class Solution {
public static void main(String[] args) {
System.out.println(new Solution().NumberOf1(10));
}
public int NumberOf1(int n) {
int res = 0;
for (int i = 0; i < 32; i++) {
if ((n & 1) == 1) {
res++;
}
n >>= 1;
}
return res;
}
}
打印从1到最大的n位数
package esay.JZ17打印从1到最大的n位数;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型 最大位数
* @return int整型一维数组
*/
public int[] printNumbers (int n) {
// write code here
int max = (int) Math.pow(10, n);
int[] result = new int[max -1];
for (int i = 1; i <= max - 1; i++) {
result[i - 1] = i;
}
return result;
}
}
删除链表的节点
package esay.JZ18删除链表的节点;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类
* @param val int整型
* @return ListNode类
*/
public ListNode deleteNode(ListNode head, int val) {
// write code here
ListNode p = head;
//判断是否删除的是头结点
if (p.val == val) {
head = p.next;
return head;
}
//如果不是遍历删除
while (p.next != null) {
if (p.next.val == val) {
p.next = p.next.next;
} else {
p = p.next;
}
}
return head;
}
}
class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
链表中倒数最后k个结点
1、将节点全部放入list集合中
2、将最后第length – k 个元素输出即可
package esay.JZ22链表中倒数最后k个结点;
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail(ListNode pHead, int k) {
// write code here
if (k == 0) {
return null;
}
List<ListNode> list = new ArrayList<>();
while (pHead != null) {
list.add(pHead);
pHead = pHead.next;
}
if (list.size() < k) {
return null;
}
return list.get(list.size() - k);
}
}
class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
反转链表
1、准备一个list
2、对链表遍历，每个元素都插入list的第一个位置即可实现反转
-
List -> add(index, element); // 插入特定位置
3、创建一个新的链表接收即可
package esay.JZ24反转链表;
import java.util.ArrayList;
import java.util.List;
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ListNode ReverseList(ListNode head) {
if (head == null) {
return null;
}
List<ListNode> reverse = new ArrayList<>();
while (head != null) {
reverse.add(0, head);
head = head.next;
}
ListNode temp = reverse.get(0);
ListNode result = temp;
for (int i = 1; i < reverse.size(); i++) {
temp.next = reverse.get(i);
temp = temp.next;
}
temp.next = null;
return result;
}
}
合并两个排序的链表
1、保证下一个元素不为空，即temp.next = list2; 不能使用temp = list2;
package esay.JZ25合并两个排序的链表;
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if (list1 == null || list2 == null) {
return list1 != null ? list1 : list2;
}
ListNode temp = new ListNode(-1);
ListNode result = temp;
while (list1 != null && list2 != null) {
if (list1.val >= list2.val) {
temp.next = list2;
list2 = list2.next;
} else {
temp.next = list1;
list1 = list1.next;
}
temp = temp.next;
}
if (list1 != null) {
temp.next = list1;
return result.next;
} else {
temp.next = list2;
return result.next;
}
}
public static void main(String[] args) {
ListNode temp = new ListNode(0);
ListNode result = temp;
temp.next = new ListNode(1);
temp = temp.next;
temp.next = null;
while (result != null) {
System.out.println(result.val);
result = result.next;
}
}
}
二叉树的镜像
1、递归进行
package esay.JZ27二叉树的镜像;
import java.util.*;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param pRoot TreeNode类
* @return TreeNode类
*/
public TreeNode Mirror(TreeNode pRoot) {
// write code here
if (pRoot == null) {
return null;
}
TreeNode pLeft = Mirror(pRoot.left);
TreeNode pRight = Mirror(pRoot.right);
pRoot.left = pRight;
pRoot.right = pLeft;
return pRoot;
}
}
对称的二叉树
1、左右不为空，且值相同
package esay.JZ28对称的二叉树;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
boolean isSymmetrical(TreeNode pRoot) {
return recursion(pRoot, pRoot);
}
public boolean recursion(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null || root1.val != root2.val) {
return false;
}
return recursion(root1.left, root2.right) && recursion(root1.right, root2.left);
}
}
顺时针打印矩阵
1、从外到内一层一层打印
package esay.JZ29顺时针打印矩阵;
import javax.management.MBeanRegistration;
import javax.swing.plaf.nimbus.AbstractRegionPainter;
import java.util.ArrayList;
public class Solution {
public static void main(String[] args) {
int[][] a = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
System.out.println(new Solution().printMatrix(a));
}
public ArrayList<Integer> printMatrix(int [][] matrix) {
if (matrix.length == 0) {
return null;
}
ArrayList<Integer> res = new ArrayList<>();
//左边界
int left = 0;
//右边界
int right = matrix[0].length - 1;
//上边界
int up = 0;
//下边界
int down = matrix.length - 1;
while (left <= right && up <= down) {
//左边界到右边界
for (int i = left; i <= right; i++) {
res.add(matrix[up][i]);
}
up++;
if (up > down) {
break;
}
for (int i = up; i <= down; i++) {
res.add(matrix[i][right]);
}
right--;
if (left > right) {
break;
}
for (int i = right; i >= left; i--) {
res.add(matrix[down][i]);
}
down--;
if (up > down) {
break;
}
for (int i = down; i >= up ; i--) {
res.add(matrix[i][left]);
}
left++;
if (left > right) {
break;
}
}
return res;
}
}
包含min函数的栈
1、保证弹栈一次之后，min函数还有最小值
2、即使push的node没有最小值小，也要将s2最小值再一次进栈
package esay.JZ30包含min函数的栈;
import java.util.Stack;
public class Solution {
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
public void push(int node) {
s1.push(node);
if (s2.isEmpty() || s2.peek() > node) {
s2.push(node);
} else {
s2.push(s2.peek());
}
}
public void pop() {
s1.pop();
s2.pop();
}
public int top() {
return s1.peek();
}
public int min() {
return s2.peek();
}
}
从上往下打印二叉树
广度遍历树
1、利用队列进行遍历，利用list进行结果打印
2、先将根节点进队
3、根节点添加到list
4、判断左右子节点是否为null，不为null也进队
5、根节点出队
6、队列为空结束
