一、LeetCode

剑指offer

03.数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findRepeatNumber(int[] nums) {
if(nums==null||nums.length==0) return -1;
//1.暴力遍历 超出时间限制
for(int i=0;i<nums.length-1;i++)
for(int j=i+1;j<nums.length;j++){
if(nums[i]==nums[j]) return nums[i];
}
// return -1;
//2.利用set集合的不可重复
Set<Integer> set = new HashSet<Integer>();
for(int i=0;i<nums.length;i++){
if(!set.add(nums[i])) return nums[i];
}
return -1;
//3.hash表 map<key,value>

}

04.剪绳子

推论一: 将绳子 以相等的长度等分为多段 ,得到的乘积最大。

推论二: 尽可能将绳子以长度 33 等分为多段时,乘积最大。

1
2
3
4
5
6
7
public int cuttingRope(int n) {
if(n <= 3) return n - 1;
int a = n / 3, b = n % 3;
if(b == 0) return (int)Math.pow(3, a);
if(b == 1) return (int)Math.pow(3, a - 1) * 4;
return (int)Math.pow(3, a) * 2;
}

15.二进制中1的个数

请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

1
2
3
4
5
6
7
8
9
10
public int hammingWeight(int n) {
if(n==0) return 0;
int res = 0;
while(n!=0){
res += n & 1;
//位右移运算
n>>>=1;
}
return res;
}

26.树的子结构

1
2
3
4
5
6
7
8
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A!=null&&B!=null)&&(recur(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B));
}
boolean recur(TreeNode A,TreeNode B){
if(B==null) return true;
if(A==null||A.val!=B.val) return false;
return recur(A.left,B.left)&&recur(A.right,B.right);
}

27.二叉树的镜像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public TreeNode mirrorTree(TreeNode root) {
//1.递归
if(root==null) return root;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirrorTree(root.left);
mirrorTree(root.right);
// return root;
//2.迭代(利用栈)
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
if (node.left!=null) stack.push(node.left);
if (node.right!=null) stack.push(node.right);
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
return root;
}

28.对称二叉树

简洁且优雅

1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean isSymmetric(TreeNode root) {
return root==null ? true : recur(root.left,root.right);
}
public boolean recur(TreeNode L,TreeNode R){
if(L==null&&R==null) return true;
if(L==null||R==null || R.val!=L.val) return false;
return recur(L.left,R.right)&&recur(L.right,R.left);
}
}

30.包含min函数的栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MinStack {
Stack<Integer> A,B;
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
public void push(int x) {
A.add(x);
if(B.empty()||B.peek()>=x) B.add(x);
}
public void pop() {
if(A.pop().equals(B.peek())) B.pop();
}
public int top() {
return A.peek();
}
public int min() {
return B.peek();
}
}

31.栈的压入、弹出序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
//辅助栈,判断栈顶元素是否与弹出元素相等
Stack<Integer> stack = new Stack<>();
int i = 0;
for(int num : pushed){
stack.push(num);
while(!stack.isEmpty() && stack.peek() == popped[i]){
stack.pop();
i++;
}
}
return stack.isEmpty();
}
}

32-1.二叉树层序遍历

借助队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] levelOrder(TreeNode root) {
if(root==null) return new int[0];
Queue<TreeNode> queue = new LinkedList<>(){{ add(root); }};
ArrayList<Integer> list = new ArrayList<>();
while(!queue.isEmpty()){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
}
int[] res = new int [list.size()];
for(int i=0;i<list.size();i++){
res[i] = list.get(i);
}
return res;
}

39.数组中出现次数超过一半的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int majorityElement(int[] nums) {
//1.hashmap记录 //用hashmap保存,key是数字的值,value是数字出现的次数
HashMap<Integer,Integer> map = new HashMap<>();
int len = nums.length;
for(int i=0;i<len;i++){
if(map.containsKey(nums[i])){
map.put(nums[i],map.get(nums[i])+1);
}else{
map.put(nums[i],1);
}
}
int result = 0;
for(Integer key:map.keySet()){
if(map.get(key) > len/2){
result = key;
break;
}
}
return result;
}

42.连续子数组的最大和

1
2
3
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
1
2
3
4
5
6
7
8
9
10
public int maxSubArray(int[] nums) {
int max = 0;
int[] dp = new int[nums.length];
dp[0] = nums[0];
for(int i=1;i<nums.length-1;i++){
dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
max = Math.max(dp[i],max);
}
return max;
}

52.两个链表的第一个公共节点

1
2
3
4
5
6
7
8
9
10
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode l1 = headA;
ListNode l2 = headB;
while(l1!=l2){
l1 = l1 == null ? headB : l1.next;
l2 = l2 == null ? headA : l2.next;
}
return l1;
}

54.二叉搜索树的第K大节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
//类变量设置
int res,k;
public int kthLargest(TreeNode root, int k) {
this.k = k;
dfs(root);
return res;
}

public void dfs(TreeNode root){
if(root==null) return;
dfs(root.right);
if(k==0) return;
if(--k==0) res = root.val;
dfs(root.left);
}
}

55-1.二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
//1.递归
// public int maxDepth(TreeNode root) {
// if(root==null) return 0;
// return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
// }
//层序遍历
public int maxDepth(TreeNode root) {
if(root == null) return 0;
List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
int res = 0;
while(!queue.isEmpty()) {
tmp = new LinkedList<>();
for(TreeNode node : queue) {
if(node.left != null) tmp.add(node.left);
if(node.right != null) tmp.add(node.right);
}
queue = tmp;
res++;
}
return res;
}
}

55-2平衡二叉树

如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

1
2
3
4
5
6
7
8
9
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

private int depth(TreeNode root) {
if (root == null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}

57.和为s的两个数字

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while(i < j) {
int s = nums[i] + nums[j];
if(s < target) i++;
else if(s > target) j--;
else return new int[] { nums[i], nums[j] };
}
return new int[0];
}
}

other

1.两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int[] twoSum(int[] nums, int target) {
//1.暴力解法
// for(int i=0;i<nums.length-1;i++)
// for(int j=i+1;j<nums.length;j++){
// if(nums[i]+nums[j]==target){
// return new int[]{i,j};
// }
// }
// return new int[0];
//2.hashcode
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for(int i=0;i<nums.length-1;i++){
if(hashtable.containsKey(target-nums[i])) return new int[]{hashtable.get(target-nums[i]),i};
hashtable.put(nums[i],i);
}
return new int [0];
}

2.最小路径和

动态规划

给定一个包含非负整数的 *m* x *n* 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
if(m<=0||n<=0){
return 0;
}
int[][] dp = new int [m][n];
dp[0][0] = grid[0][0];
//初始化第一列
for(int i=1;i<m;i++){
dp[i][0] = dp[i-1][0] + grid[i][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++)
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];
}

3.LRU算法

哈希表+双向链表

二、牛客刷题

1.反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode ReverseList(ListNode head) {
if(head==null) return head;
//头插法
ListNode cur = head;
ListNode pre = null;
ListNode next = null;
while(cur != null){
//先保存链表的下一个节点
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}

三、常见排序算法

如何写算法程序

1.由简单到复杂 验证一步走一步 多打印中间结果

2.先局部后整体 没思路实现细分

3.先粗糙,后精细 变量更名,语句合并,边界处理

image-20210529134120465

1.选择排序

选择最小的放到最前面,重复此过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void main(String[] args) {
int[] arr = {9,8,7,6,5,4,3,2,1};
for (int i=0;i<arr.length-1;i++){
int min = i;
for (int j=i+1;j<arr.length;j++){
min = arr[j]<arr[min] ? j : min;
}
swap(arr,i,min);
}
print(arr);
}
static void swap(int[] arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

static void print(int[] arr){
for (int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
}

2.冒泡排序

1
2
3
4
5
6
for(int i=1;i<nums.length;i++)
for(int j=0;j<nums.length-i;j++){
if(nums[j]>nums[j+1]){
swap(nums,j,j+1);
}
}

3.插入排序

1
2
3
4
5
6
for (int i=1;i<arr.length;i++)
for (int j=i;j>0;j--){
if (arr[j]<arr[j-1]){
swap(arr,j,j-1);
}
}

4.希尔排序

改进的插入排序

5.归并排序

6.快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class QuickSort {
public static void main(String[] args){
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i<j) {
//先看右边,依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边,依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
}

四、算法思想

1.动态规划

image-20210621210633115

问题描述

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

1
2
3
4
5
6
7
8
9
举例:
输入:
arr = [
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 13111 的总和最小。
步骤一、定义数组元素的含义

由于我们的目的是从左上角到右下角,最小路径和是多少,那我们就定义 dp[i] [j]的含义为:**当机器人从左上角走到(i, j) 这个位置时,最下的路径和是 dp[i] [j]**。那么,dp[m-1] [n-1] 就是我们要的答案了。

注意,这个网格相当于一个二维数组,数组是从下标为 0 开始算起的,所以 由下角的位置是 (m-1, n - 1),所以 dp[m-1] [n-1] 就是我们要走的答案。

步骤二:找出关系数组元素间的关系式

想象以下,机器人要怎么样才能到达 (i, j) 这个位置?由于机器人可以向下走或者向右走,所以有两种方式到达

一种是从 (i-1, j) 这个位置走一步到达

一种是从(i, j - 1) 这个位置走一步到达

不过这次不是计算所有可能路径,而是计算哪一个路径和是最小的,那么我们要从这两种方式中,选择一种,使得dp[i] [j] 的值是最小的,显然有

1
dp[i] [j] = min(dp[i-1][j],dp[i][j-1]) + arr[i][j];// arr[i][j] 表示网格种的值
步骤三、找出初始值

显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的,相当于计算机图中的最上面一行和左边一列。因此初始值如下:

dp[0] [j] = arr[0] [j] + dp[0] [j-1]; // 相当于最上面一行,机器人只能一直往左走

dp[i] [0] = arr[i] [0] + dp[i] [0]; // 相当于最左面一列,机器人只能一直往下走

———————————————————————-分割线———————————————————————————

例:题目:有三种硬币,面值2.5.7,买一本书需要27元,如何用最少的硬币整好付清。

1、确定状态
简单的说,就是解动态规划时需要开一个数组,数组的每个元素f[i]或者f[i][j]代表什么,类似解数学题中,xyz代表什么一样,具体分为下面两个步骤:
——-研究最优策略的最后一步
——-化为子问题
2、转移方程
根据子问题定义直接得到
3、初始条件和边界情况
初始条件一般都是a[0]、a[1]这种,多看看
边界条件主要是看数组的边界,数组是否越界
4、计算顺序
利用之前的计算结果

打家劫舍
1
2
3
4
5
6
7
8
9
10
11
12
public int rob(int[] nums) {
if(nums==null&&nums.length==0) return 0;
int length = nums.length;
if(length==1) return nums[0];
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i=2;i<length;i++){
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[length-1];
}
不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int uniquePaths(int m, int n) {
if(m==0&&n==0) return 0;
int[][] dp = new int[m][n];
//边界为第一行和第一列
for(int i=0;i<m;i++){
dp[i][0] = 1;
}
for(int j=0;j<n;j++){
dp[0][j] = 1;
}
for(int i=1;i<m;++i){
for(int j=1;j<n;++j){
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}

2.链表

2.1 单链表

单链表中的每个结点不仅包含值,还包含链接到下一个结点的引用字段

可以在 O(1) 时间复杂度中将新结点插入到链表中,这非常高效。

在我们的第一步中,我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next,但是,我们必须从头结点遍历链表,以找出 prev,它的平均时间是 O(N),其中 N 是链表的长度。因此,删除结点的时间复杂度将是 O(N)

双指针

我们提到了两种使用双指针技巧的情景:

  1. 两个指针从不同位置出发:一个从始端开始,另一个从末端开始;
  2. 两个指针以不同速度移动:一个指针快一些,另一个指针慢一些。(快慢指针)

一个安全的选择是每次移动慢指针一步,而移动快指针两步。每一次迭代,快速指针将额外移动一步。如果环的长度为 M,经过 M 次迭代后,快指针肯定会多绕环一周,并赶上慢指针。

在对链表进行操作时,一种常用的技巧是添加一个哑节点(dummy node),它的 \textit{next}next 指针指向链表的头节点。这样一来,我们就不需要对头节点进行特殊的判断了。

判断链表是否有环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
//1.快慢指针
if(head==null||head.next==null) return false;
// ListNode first = head;
// ListNode second = head;
// while(first!=null&&second!=null){
// first = first.next;
// second = second.next==null ? null : second.next.next;
// if(first==second) return true;
// }
//2.哈希表
ListNode node = head;
Set<ListNode> set = new HashSet();
while(node!=null){
if(set.contains(node)) return true;
set.add(node);
node = node.next;
}
return false;
}
}
相交链表

方法一:哈希表

方法二:双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
删除链表的倒数第N个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//1.栈
ListNode dummy = new ListNode(0,head);
Stack<ListNode> stack = new Stack<ListNode>();
ListNode cur = dummy;
while(cur!=null){
stack.push(cur);
cur = cur.next;
}
for(int i=0;i<n;++i){
stack.pop();
}
ListNode pre = stack.peek();
pre.next = pre.next.next;
ListNode result = dummy.next;
return result;
//2.双指针
ListNode dummy = new ListNode(0, head);
ListNode first = head;
ListNode second = dummy;
for (int i = 0; i < n; ++i) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
ListNode ans = dummy.next;
return ans;
}
}
移除链表元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while(cur.next!=null){
if(cur.next.val==val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return dummy.next;
}
}
奇偶链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode oddEvenList(ListNode head) {
if(head==null) return head;
ListNode evenHead = head.next;
ListNode odd = head;
ListNode even = evenHead;
while(even!=null&&even.next!=null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
回文链表

将值复制到数组中后用双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
// 将链表的值复制到数组中
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// 使用双指针判断是否回文
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
合并两个有序链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0,l1);
ListNode node = dummy;
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
node.next = l1;
l1 = l1.next;
}else{
node.next = l2;
l2 = l2.next;
}
node = node.next;
}
node.next = l1==null ? l2 : l1;
return dummy.next;
}
旋转链表

闭合为环,移动之后,再将环断开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) {
return head;
}
int n = 1;
ListNode iter = head;
while (iter.next != null) {
iter = iter.next;
n++;
}
int add = n - k % n;
if (add == n) {
return head;
}
//接环
iter.next = head;
while (add-- > 0) {
iter = iter.next;
}
ListNode ret = iter.next;
//断环
iter.next = null;
return ret;
}
}

2.2二叉树

前序遍历

递归

1
2
3
4
5
6
7
8
9
10
11
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
preOrder(root,res);
return res;
}
public void preOrder(TreeNode root,List<Integer> res){
if(root==null) return;
res.add(root.val);
preOrder(root.left,res);
preOrder(root.right,res);
}

层序遍历(广度优先搜索) 借助队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}

Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for (int i = 1; i <= currentLevelSize; ++i) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
ret.add(level);
}

return ret;
}

递归解决树问题

自顶向下 先序遍历

自底向上 后序遍历

五、java常规代码题

1.实现死锁及解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class MustDeadLock implements Runnable{
int flag = 1;
static Object o1 = new Object();
static Object o2 = new Object();

public static void main(String[] args) {
MustDeadLock r1 = new MustDeadLock();
MustDeadLock r2 = new MustDeadLock();
r1.flag = 1;
r2.flag = 0;
Thread t1 = new Thread(r1);
Thread t2 = new Thread(r2);
t1.start();
t2.start();
}
@Override
public void run() {
System.out.println("flag="+flag);
if (flag == 1){
synchronized (o1){
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (o2){
System.out.println("线程1成功拿到两把锁!");
}
}
}
if (flag == 0){
synchronized (o2){
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized (o1){
System.out.println("线程2成功拿到两把锁!");
}
}
}
}
}

解决办法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
static Object lock = new Object();

public static void transferMoney(Account from, Account to, int amount) {
class Helper {

public void transfer() {
if (from.balance - amount < 0) {
System.out.println("余额不足,转账失败。");
return;
}
from.balance -= amount;
to.balance = to.balance + amount;
System.out.println("成功转账" + amount + "元");
}
}
int fromHash = System.identityHashCode(from);
int toHash = System.identityHashCode(to);
if (fromHash < toHash) {
synchronized (from) {
synchronized (to) {
new Helper().transfer();
}
}
}
else if (fromHash > toHash) {
synchronized (to) {
synchronized (from) {
new Helper().transfer();
}
}
}else {
synchronized (lock) {
synchronized (to) {
synchronized (from) {
new Helper().transfer();
}
}
}
}

2.两个线程交替打印数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class TwoThreadPrintNum implements  Runnable{
private boolean runNow;
private Object lock;
private int num;
public TwoThreadPrintNum(boolean runNow,Object lock,int num){
this.runNow = runNow;
this.lock = lock;
this.num = num;
}
@Override
public void run() {
synchronized (lock){
while(num<=100){
if (runNow){
runNow = false;
}else {
try {
lock.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println(num);
num += 2;
lock.notify();
}
}
}
public static void main(String[] args) {
Object lock = new Object();
Thread t1 = new Thread(new TwoThreadPrintNum(true,lock,1));
Thread t2 = new Thread(new TwoThreadPrintNum(false,lock,2));
t2.start();
t1.start();
}
}