題號為LeetCode劍指Offer題庫中的題號，網址：https://leetcode-cn.com/problem-list/xb9nqhhg/
從上到下列印二叉樹 32-III
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
List<Integer> list = new ArrayList<>();
if(root == null){
return ans;
}
deque.add(root);
while((list = pollAll(deque)) != null){
if(ans.size() % 2 != 0){
Collections.reverse(list);
}
ans.add(list);
}
return ans;
}
public List<Integer> pollAll(Deque<TreeNode> deque){
TreeNode tr;
List<Integer> list = new ArrayList<>();
int n = deque.size();
if(n==0)
return null;
for (int i = 0 ; i < n ; i++){
tr = deque.poll();
list.add(tr.val);
if(tr.left!=null){
deque.add(tr.left);
}
if(tr.right!=null){
deque.add(tr.right);
}
}
return list;
}
}
只需要稍稍注意加上反轉條件，與32-2相同流程，
二叉搜索樹的后序遍歷序列 33
二叉搜索樹：左子樹中所有節點的值 << 根節點的值；右子樹中所有節點的值 >> 根節點的值；其左、右子樹也分別為二叉搜索樹，
class Solution {
public boolean verifyPostorder(int[] postorder) {
return recur(0,postorder.length-1, postorder);
}
public boolean recur(int i , int j, int[] postorder){
if(i>=j) return true;
int p = i;
while(postorder[p]<postorder[j]) p++;
int m = p;
while(postorder[p]>postorder[j]) p++;
return p==j && recur(i,m-1,postorder) && recur(m,j-1,postorder);
}
}
這個思路在于，判斷整數序列是否符合后序遍歷特點，<左子樹>，<右子樹>，<根節點>，符合之后，對子樹進行判斷，寫一個遞回，
二叉樹中和為某一值的路徑 34
class Solution {
Deque<Integer> list = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
dfs(root,target);
return res;
}
public void dfs(TreeNode root, int target) {
if(root == null)
return ;
list.offerLast(root.val);
target = target - root.val;
if(target==0 && root.left==null && root.right==null)
res.add(new LinkedList<Integer> (list));
dfs(root.left,target);
dfs(root.right,target);
list.pollLast();
}
}
本題需要對二叉樹的路徑進行遞回，判斷每個葉子節點是否滿足和為target，
注意：這里有一個小細節，list為Deque是為了方便遍歷，而Deque->List<Integer> 則是利用了 LinkedList的構造方法，可以將Collection物件直接構造為List，
二叉搜索樹與雙向鏈表 36
class Solution {
Node head,pre;
public Node treeToDoublyList(Node root) {
if(root == null)
return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
public void dfs(Node cur) {
if(cur == null)
return ;
dfs(cur.left);
if(pre != null)
pre.right = cur;
else head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}
二叉搜索樹的中序遍歷即為按從小到大排序，需要注意的是節點的指標更換方式，
序列化二叉樹 37
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null) return "[]";
Deque<TreeNode> deque = new LinkedList<>() {{add(root);}};
StringBuilder ans = new StringBuilder("[");
while( deque.size() !=0 ) {
TreeNode temp = deque.poll();
if(temp != null){
ans.append(temp.val+",");
deque.add(temp.left);
deque.add(temp.right);
}
else{
ans.append("null,");
}
}
ans.deleteCharAt(ans.length()-1);
ans.append("]");
return ans.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("[]")) return null;
String[] vals = data.substring(1,data.length()-1).split(",");
TreeNode node = new TreeNode(Integer.parseInt(vals[0]));
Deque<TreeNode> deque = new LinkedList<>() {{add(node);}};
int i = 1;
while( i < vals.length ) {
TreeNode temp = deque.poll();
if(!vals[i].equals("null")){
temp.left = new TreeNode(Integer.parseInt(vals[i]));
deque.add(temp.left);
}
i++;
if(!vals[i].equals("null")){
temp.right = new TreeNode(Integer.parseInt(vals[i]));
deque.add(temp.right);
}
i++;
}
return node;
}
}
本題的思路在于建立佇列對二叉樹結構進行BFS，實際演算法思路并不復雜，主要在于理清演算法流程，
字串的排列 38 （全排列題型）
class Solution {
List<String> res = new LinkedList<>();
char[] c ;
public String[] permutation(String s) {
c = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if( x == c.length -1 ){
res.add(String.valueOf(c));
return;
}
HashSet<Character> set = new HashSet<>();
for(int i = x ; i < c.length ; i++) {
if(set.contains(c[i])) continue;
set.add(c[i]);
swap(i,x);
dfs(x+1);
swap(i,x);
}
}
void swap(int a, int b) {
char temp = c[a];
c[a] = c[b];
c[b] = temp;
return ;
}
}
這道題是回溯法的典型應用，利用深搜進行一個字串的全排列組合，同時注意每個字符位置的剪枝（遇到重復的元素直接跳過），
陣列中出現次數超過一半的數字 39（求眾數）
本題有多種思路，排序，利用map進行計數，以及摩爾計數法，
摩爾計數法實際上可以理解為假設共有n個不同的數字，即有n方勢力，每兩方可以對拼消耗，無論如何消耗，最終剩下來的肯定是最大的一方勢力，（在存在眾數的情況下）
1：HashMap 時間復雜度O(N)，空間復雜度O(N)
class Solution {
public int majorityElement(int[] nums) {
int len = nums.length/2;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i : nums){
if(map.containsKey(i)){
int count = map.get(i);
map.put(i,count+1);
}
else{
map.put(i,1);
}
}
for(Integer o : map.keySet()){
if(map.get(o) > len)
return o;
}
return 0;
}
}
2：摩爾投票法
class Solution {
public int majorityElement(int[] nums) {
int votes=0,x=0;
for(int i : nums) {
if(votes ==0) {
votes++;
x = i;
continue;
}
if(i == x) votes++;
else votes--;
}
return x;
}
}
思路都較為簡單，理解即可，
最小的k個數 40 （TOP K）
多種思路：排序，維護大根堆的前k個元素，快排變形
1：排序思路
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] ans = new int[k];
if(k==0) return ans;
Arrays.sort(arr);
for(int i= 0 ; i < k ; i++){
ans[i] = arr[i];
}
return ans;
}
}
2：利用大根堆
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int[k];
if(k==0) return res;
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer o1, Integer o2){
return o2 - o1;
}
});
for(int i = 0 ; i < k ; i++){
queue.offer(arr[i]);
}
for(int j = k ; j < arr.length ; j++){
if(arr[j] < queue.peek()){
queue.poll();
queue.offer(arr[j]);
}
}
for(int i = 0 ; i < k ; i++){
res[i] = queue.poll();
}
return res;
}
}
這里要注意，java默認的是小根堆，所以需要重寫compare方法，維護前K個元素即可，
return o1-o2(升序) return o2-o1(降序)
3： 快排變形
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(k==0 || arr.length==0) return new int[0];
return quickSearch(arr,0,arr.length-1,k-1);
}
public int[] quickSearch(int[] num,int l,int r,int k){
int j = partition(num,l,r);
if(j==k){
return Arrays.copyOf(num,j+1);
}
return j > k ? quickSearch(num,l,j-1,k) : quickSearch(num,j+1,r,k); //j本身是沒用的可以跳過
}
public int partition(int[] nums,int l,int r){
int tmp = nums[l];
int i=l,j=r+1;
while(true){
while(++i<r && nums[i]<tmp) ;
while(--j>l && nums[j]>tmp) ;
if(i>=j) break;
int t = nums[i];
nums[i]=nums[j];
nums[j]=t;
}
nums[l] = nums[j];
nums[j] = tmp;
return j;
}
}
這里相較于快排只是缺少最終對整體的遞回，主要在于判斷每次快排第一個元素在陣列中的位置，并放到相應位置，
資料流中的中位數 41
class MedianFinder {
Queue<Integer> A,B;
/** initialize your data structure here. */
public MedianFinder() {
A = new PriorityQueue<>();
B = new PriorityQueue<>((x,y) -> (y-x));
}
public void addNum(int num) {
if(A.size()!=B.size()){
A.add(num);
B.add(A.poll());
}
else{
B.add(num);
A.add(B.poll());
}
}
public double findMedian() {
return A.size()>B.size() ? A.peek() : (A.peek()+B.peek())/2.0;
}
}
代碼不長，主要利用2個堆：一個大根堆一個小根堆，對元素進行大小分割，小元素在大根堆里，大元素在小根堆里，
試想一下，這樣的話，堆頂就是中位數了，具體實作思想是：A，B兩個堆，A=B=0或其他數時，向B添加元素，出B堆頂元素到A，保證去A的元素為較小一方；當A!=B時，A加元素，出A堆頂元素到B，保證去B的元素較大，從A=B=1時開始就會一直保持A較小一方，B較大一方，需要自己理解一下，
連續子陣列的最大和 42
該題利用動態規劃(N)和暴力求解(N^2)均可
動態規劃：
class Solution {
public int maxSubArray(int[] nums) {
int max,pre=nums[0];
max = pre;
for(int i = 1 ; i < nums.length ; i++) {
pre = nums[i] > (pre+nums[i]) ? nums[i] : (pre+nums[i]);
max = max > pre ? max : pre;
}
return max;
}
}
因為是連續子陣列，pre代表當前i為最后一位，對應的連續子陣列最大值，需要體會一下狀態轉移程序，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/311922.html
標籤：Java