1 ： 160. 相交链表 - 力扣（LeetCode）
题意：给定两个链表，让你返回这两个链表相交的起始节点，没有就返回null；
思路：我们让 pa 指向 A 链表的头节点，pb 指向 B 链表的头节点，然后每次都移动一个单位长度，假如 pa 移动到 A 链表的尾节点时，就让他指向 B 链表的头节点，同理，当 pb 指向 B 链表的尾节点时，就让它指向 A 链表的头节点。
我们仔细想一下，如果这两个链表后面相交的话，那么 pa 跑完一遍 A 链表，再从 B 链表的头节点跑到两个链表相交的起始节点 和 pb 跑完一遍 B 链表，再从 A 链表的头节点跑到两个链表相交的起始节点，这二者所走过的单位距离一定是相等的。
那么如果这两个链表不相交呢？会不会死循环呢？答案是不会的，他们会在两个链表长度的最大=小公倍数那里同时指向null，退出循环。
时间复杂度O(n);
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pa = headA;
ListNode pb = headB;
if(pa == null || pb == null) return null;
while(pa != pb){
pa = pa == null ? headB : pa.next;
pb = pb == null ? headA : pb.next;
}
return pa;
}
}2:1. 两数之和 - 力扣（LeetCode）
题意：给定一个数组，和一个目标数target，让你找到两个数，使他们加起来等于target，并输出这两个数的下标，保证有解。
思路：我们遍历数组，对于每个数 num1，用 target - num1，表示出我们要找的数num2，然后如果这个数不在 HashMap 里我们就把这个数和它的下标存进去，否则我们就取出这个数的下标 break 这是个在线做法。
那么我们为什么不一开始就存入每个数的下标呢（离线）？因为数组里面会有重复的数
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> mp = new HashMap<>();
int x = -1, y = -1;
for(int i = 0; i < nums.length; i ++){
int num1 = nums[i];
int num2 = target - num1;
if(mp.containsKey(num2)){
x = i;
y = mp.get(num2);
break;
}
mp.put(nums[i], i);
}
return new int[]{x, y};
}
}3: 236. 二叉树的最近公共祖先 - 力扣（LeetCode）
题意：很简单，给定一个二叉树，再给定两个节点p, q，求这两个节点的公共祖先
思路：当一个节点的左子树 lson 中有 p 或 q 节点，我们就设其为 true，右子树 rson 同理，当然如果该节点本身就是 p 或 q， 我们设其为 true，所以最后如果这个节点是最近公共祖先，他要满足的条件就是 ：
lson && rson || ((root.val == p.val && (lson || rson)) || (root.val == q.val && (lson || rson)))详情见代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
static TreeNode ans = null;
private boolean dfs(TreeNode root, TreeNode p, TreeNode q){
if(root == null) return false;
boolean lson = dfs(root.left, p, q);
boolean rson = dfs(root.right, p, q);
if(lson && rson || ((root.val == p.val && (lson || rson)) || (root.val == q.val && (lson || rson)))){
ans = root;
}
return lson || rson || root.val == p.val || root.val == q.val;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root, p, q);
return ans;
}
}补充：当然这是二叉树的情况，如果是多叉树呢？
我们要用倍增法和 dp 的思想，预处理；
#include <iostream>
#include <vector>
#define int long long
using namespace std;
const int N = 5e5 + 10;
vector<vector<int>> e(N);
vector<vector<int>> p(N, vector<int>(21, 0));
vector<int> d(N, 0); // 深度
void dfs(int u, int fa)
{
p[u][0] = fa;
d[u] = d[fa] + 1;
for(int i = 1; (1 << i) <= d[u]; i ++)
{
p[u][i] = p[p[u][i - 1]][i - 1];
}
for(auto v : e[u])
{
if(v != fa) dfs(v, u);
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n, m, s;
cin >> n >> m >> s;
for(int i = 0; i < n - 1; i ++)
{
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(s, 0);
while(m --)
{
int a, b;
cin >> a >> b;
if(d[a] > d[b]) swap(a, b);
for(int i = 20; i >= 0; i --)
{
if(d[b] - (1 << i) >= d[a])
{
b = p[b][i];
}
}
if(a == b) cout << a << '\n';
else
{
for(int i = 20; i >= 0; i --)
{
if(p[a][i] != p[b][i])
{
a = p[a][i];
b = p[b][i];
}
}
cout << p[a][0] << '\n';
}
}
return 0;
}4:234. 回文链表 - 力扣（LeetCode）
题意：给定一个链表，判断是否为回文链表；
思路：把链表中的 val 复制到一个数组中，然后用双指针判断即可
/**
* 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 boolean isPalindrome(ListNode head) {
List<Integer> vec = new ArrayList<>();
while(head != null){
vec.add(head.val);
head = head.next;
}
boolean f = true;
int j = vec.size() - 1;
int i = 0;
while(i < j){
if(!vec.get(i).equals(vec.get(j))){
f = false;
break;
}
i ++;
j --;
}
return f;
}
}5：739. 每日温度 - 力扣（LeetCode）
题意：给定一串数组，对于其中每个数，判断后面比它大且离他最近的那个数离它有多远。
思路：单调栈板子题
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int len = temperatures.length;
int[] ans = new int[len];
Stack<Integer> stack = new Stack<>();
for(int i = len - 1; i >= 0; i --){
while(!stack.isEmpty() && temperatures[stack.peek()] <= temperatures[i]) stack.pop();
if(stack.isEmpty()) ans[i] = 0;
else{
int pos = stack.peek();
ans[i] = pos - i;
}
stack.push(i);
}
return ans;
}
}6:226. 翻转二叉树 - 力扣（LeetCode）
题意：给你一个二叉树，反转二叉树
思路：递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private TreeNode dfs(TreeNode root){
if(root == null){
return null;
}
TreeNode tmp = root.right;
root.right = root.left;
root.left = tmp;
dfs(root.left);
dfs(root.right);
return root;
}
public TreeNode invertTree(TreeNode root) {
dfs(root);
return root;
}
}7:221. 最大正方形 - 力扣（LeetCode）
题意：给定一个 0 1 矩阵，让你算出矩阵中只包含 1 的正方形；
思路：考虑dp，dp[i][j]表示，以 i, j 坐标为右下角的正方型的最大边长，具体状态转移见代码
class Solution {
public int maximalSquare(char[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
int [][] dp = new int[rows + 1][cols + 1];
int maxsize = 0;
for(int i = 0; i < rows; i ++){
for(int j = 0; j < cols; j ++){
if(matrix[i][j] == '1'){
if((i == 0 || j == 0)){
dp[i][j] = 1;
}else{
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
}
maxsize = Math.max(maxsize, dp[i][j]);
}
}
return maxsize * maxsize;
}
}8：215. 数组中的第K个最大元素 - 力扣（LeetCode）
题意：给定一串数组，让你求出第K大的元素是什么。
思路：最简单的方法就是直接暴力排序，但是时间复杂度是O（nlogn），但我们可以用快速排序（分治）的思想，每次选个轴点，然后经过一轮分类后，这个轴点左边的元素都是小于它的，右边的元素都是大于它的，所以这个轴点的下标 j 就是排名第 j 的元素，然后如果这个排名 j 比我们要的排名高，那就继续排序左边的区间，否则就排序右边的区间。
class Solution {
private int quick_sort(int[] nums, int l, int r, int q){
if(l == r) return nums[q];
int x = nums[(l + r) / 2];
int i = l - 1, j = r + 1;
while(i < j){
do i ++; while(nums[i] < x);
do j --; while(nums[j] > x);
if(i < j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
if(q <= j) return quick_sort(nums, l, j, q);
else return quick_sort(nums, j + 1, r, q);
}
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
return quick_sort(nums, 0, n - 1, n - k);
}
}9：208. 实现 Trie (前缀树) - 力扣（LeetCode）
题意：实现字典树的增，查功能
思路：板子
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
this.children = new Trie[26];
this.isEnd = false;
}
public void insert(String word) {
Trie node = this;
for(char c : word.toCharArray()){
int idx = c - 'a';
if(node.children[idx] == null){
node.children[idx] = new Trie();
}
node = node.children[idx];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie f = checkPrefix(word);
return f != null && f.isEnd;
}
public boolean startsWith(String prefix) {
return checkPrefix(prefix) != null;
}
public Trie checkPrefix(String word){
Trie node = this;
for(char c : word.toCharArray()){
int idx = c - 'a';
if(node.children[idx] == null) return null;
node = node.children[idx];
}
return node;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/10：207. 课程表 - 力扣（LeetCode）
题意：给定num节课，以及几对先修课程的关系，如果一门课程有先修课程，那么必须要先学完先修课程，才能学这门课程，让你判断有没有可能学完所以课程。
思路：我们可以通过题目给的样例看出来，如果不满足情况，那么就意味有自相矛盾的地方，这在图论中就意味着有环存在，我们可以通过简单的拓扑排序判断有无环
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer> []e = new ArrayList[numCourses];
for(int i = 0; i < numCourses; i ++){
e[i] = new ArrayList<>();
}
int[] ind = new int[numCourses];
int cnt = 0;
Queue<Integer> q = new LinkedList<>();
for(int[] info : prerequisites){
int u = info[1];
int v = info[0];
e[u].add(v);
ind[v] ++;
}
for(int i = 0; i < numCourses; i ++){
if(ind[i] == 0){
q.add(i);
}
}
while(!q.isEmpty()){
cnt ++;
int t = q.poll();
for(int v : e[t]){
ind[v] --;
if(ind[v] == 0){
q.add(v);
}
}
}
return cnt == numCourses;
}
}