2020-3-23

102.二叉树的层次遍历

✒解题思路：

1. 固定套路

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if (root == null) {
			return result;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			List<Integer> list = new ArrayList<>();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				list.add(node.val);
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
			result.add(list);
		}
		return result;
	}
}

107.二叉树的层次遍历II

✒解题思路：

1. 在层次遍历的基础上对数组翻转

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
		List<List<Integer>> result = new LinkedList<List<Integer>>();
		if (root == null) {
			return result;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
			List<Integer> list = new ArrayList<>();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				list.add(node.val);
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
			((LinkedList<List<Integer>>) result).addFirst(list);
		}
		return result;
    }
}

103.二叉树的锯齿形层次遍历

✒解题思路：

1. 层次遍历时设置变量flag，每次翻转

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if (root == null) {
			return result;
		}
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		boolean flag = true;
		while (!queue.isEmpty()) {
			int size = queue.size();
			List<Integer> list = new ArrayList<>();
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				list.add(node.val);
				if (node.left != null) {
					queue.add(node.left);
				}
				if (node.right != null) {
					queue.add(node.right);
				}
			}
			flag = !flag;
			if (flag) {
				Collections.reverse(list);
			}
			result.add(list);
		}
		return result;
    }
}

876.链表的中间节点

✒解题思路：

1. 快慢指针

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
	public ListNode middleNode(ListNode head) {
		ListNode result = head;
		if (result == null||result.next==null) {
			return result;
		}
		ListNode fast = head.next.next;
		while (fast != null && fast.next != null) {
			result = result.next;
			fast = fast.next.next;
		}
		return result.next;
	}
}

392.判断子序列

✒解题思路：

1. 暴力

2. DP

   $$if(s.charAt(i-1)==t.charAt(j-1)) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = dp[i][j-1]; }$$

//暴力法
class Solution {
	public boolean isSubsequence(String s, String t) {
		int lenS = s.length();
		int lenT = t.length();
		int result = 0;
		int pre = 0;
		for (int i = 0; i < lenS; i++) {
			for (int j = pre; j < lenT; j++) {
				if (s.charAt(i) == t.charAt(j)) {
					result++;
					pre = j + 1;
					break;
				}
			}
		}
		return result == lenS;
	}
}
//DP
class Solution {
    	public boolean isSubsequence(String s, String t) {
		int lenS = s.length();
		int lenT = t.length();
        if (lenS==0){
			return true;
		}
		boolean[][] dp = new boolean[lenS + 1][lenT + 1];
		for (int i = 0; i < lenT; i++) {
			dp[0][i] = true;
		}
		for (int i = 1; i <= lenS; i++) {
			for (int j = 1; j <= lenT; j++) {
				if (s.charAt(i - 1) == t.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1];
				} else {
					dp[i][j] = dp[i][j - 1];
				}
			}
		}
		return dp[lenS][lenT];
	}
}

08.01.三步问题

✒解题思路：

1. DP $$dp[i] = dp[i-1]+dp[i-2]+dp[i-3];$$

class Solution {
	public int waysToStep(int n) {
		if (n == 0 || n == 1) {
			return 1;
		}
		if (n == 2) {
			return 2;
		}
		if (n == 3) {
			return 4;
		}
		int a = 1;
		int b = 2;
		int c = 4;
		int result = 0;
		for (int i = 4; i <= n; i++) {
			result = ((a% 1000000007 + b% 1000000007)% 1000000007 + c% 1000000007) % 1000000007;
			a = b;
			b = c;
			c = result;
		}
		return result;
	}
}

17.16.按摩师

✒解题思路：

1. DP $$dp[i] = max(dp[i-1],dp[i-2]+nums[i]);$$

class Solution {
	public int massage(int[] nums) {
		int len = nums.length;
		if (len < 1) {
			return 0;
		}
		if (len < 2) {
			return nums[0];
		}
		int[] dp = new int[len];
		dp[0] = nums[0];
		dp[1] = Math.max(nums[0], nums[1]);
		for (int i = 2; i < len; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
		}
		return dp[len - 1];
	}
}

16.17.连续数列

✒解题思路：

1. sum存储当前子列和，max存储最大子列和

class Solution {
	public int maxSubArray(int[] nums) {
		if (nums.length == 0) {
			return 0;
		}
		int sum = 0;
		int result = nums[0];
		for (int i = 0; i < nums.length; i++) {
			if (sum + nums[i] < nums[i]) {
				sum = nums[i];
			} else {
				sum += nums[i];
			}
			if (sum > result) {
				result = sum;
			}
		}
		return result;
	}
}