[数据结构与算法]LeetCode 116~120

前言

本文隶属于专栏《LeetCode 刷题汇总》，该专栏为笔者原创，引用请注明来源，不足和错误之处请在评论区帮忙指出，谢谢！

本专栏目录结构请见LeetCode 刷题汇总

Github 配套工程

algorithm

正文

幕布

幕布链接

116. 填充每个节点的下一个右侧节点指针

题解

官方题解

递归 + ArrayList

package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode116.solution1;


import com.shockang.study.algorithm.java.leetcode.common.Node;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Shockang
 */
public class Solution {
	private List<Node> list = new ArrayList<>();

	public Node connect(Node root) {
		if (root == null) return null;
		helper(root, 0);
		return list.get(0);
	}

	private void helper(Node node, int level) {
		if (node == null) return;
		if (level < list.size()) {
			Node pre = list.get(level);
			pre.next = node;
			list.set(level, node);
		} else {
			list.add(node);
		}
		helper(node.left, level + 1);
		helper(node.right, level + 1);
	}
}

递归 + root.next

package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode116.solution2;

import com.shockang.study.algorithm.java.leetcode.common.Node;

/**
 * @author Shockang
 */
public class Solution {
	public Node connect(Node root) {
		if (root == null) {
			return root;
		}
		if (root.left != null) {
			root.left.next = root.right;
			root.right.next = root.next != null ? root.next.left : null;
			connect(root.left);
			connect(root.right);
		}
		return root;
	}
}

117. 填充每个节点的下一个右侧节点指针 II

题解

官方题解?

BFS

package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode117.solution1;

import com.shockang.study.algorithm.java.leetcode.common.Node;

/**
 * BFS
 *
 * @author Shockang
 */
public class Solution {
	public Node connect(Node root) {
		if (root == null) return root;
		//cur我们可以把它看做是每一层的链表
		Node cur = root;
		while (cur != null) {
			//遍历当前层的时候，为了方便操作在下一层前面添加一个哨兵（注意这里是访问当前层的节点，然后把下一层的节点串起来）
			Node dummy = new Node(0);
			//pre表示访下一层节点的前一个节点
			Node pre = dummy;
			//然后开始遍历当前层的链表
			while (cur != null) {
				if (cur.left != null) {
					//如果当前节点的左子节点不为空，就让pre节点的next指向他，也就是把它串起来
					pre.next = cur.left;
					//然后再更新pre
					pre = pre.next;
				}
				//同理参照左子树
				if (cur.right != null) {
					pre.next = cur.right;
					pre = pre.next;
				}
				//继续访问这一行的下一个节点
				cur = cur.next;
			}
			//把下一层串联成一个链表之后，让他赋值给cur，
			//后续继续循环，直到cur为空为止
			cur = dummy.next;
		}
		return root;
	}
}

118. 杨辉三角

题解

My concise solution in Java?

正斜杠对齐

package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode118.solution1;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Shockang
 */
public class Solution {
	public List<List<Integer>> generate(int numRows) {
		List<List<Integer>> res = new ArrayList();
		List<Integer> row = new ArrayList();
		for (int i = 0; i < numRows; i++) {
			for (int j = row.size() - 1; j >= 1; j--) {
				row.set(j, row.get(j) + row.get(j - 1));
			}
			row.add(1);
			res.add(new ArrayList<>(row));
		}
		return res;
	}
}

119. 杨辉三角 II

题解

Here is my brief O(k) solution

正斜杆对齐

package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode119.solution1;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Shockang
 */
public class Solution {
	public static List<Integer> getRow(int rowIndex) {
		List<Integer> ret = new ArrayList<>(rowIndex + 1);
		ret.add(1);
		for (int i = 1; i <= rowIndex; i++) {
			for (int j = i - 1; j >= 1; j--) {
				int tmp = ret.get(j - 1) + ret.get(j);
				ret.set(j, tmp);
			}
			ret.add(1);
		}
		return ret;
	}
}

120. 三角形最小路径和

题解

DP Solution for Triangle?

动态规划，↑

package com.shockang.study.algorithm.java.leetcode.leetcode101_200.leetcode120.solution1;

import java.util.List;

/**
 * @author Shockang
 */
public class Solution {
	public int minimumTotal(List<List<Integer>> triangle) {
		int n = triangle.size();
		int[] dp = new int[n + 1];
		for (int i = n - 1; i >= 0; i--) {
			for (int j = 0; j <= i; j++) {
				dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
			}
		}
		return dp[0];
	}
}