衝刺大廠每日演算法&面試題,動態規劃21天——第十八天

語言: CN / TW / HK

highlight: a11y-dark theme: mk-cute


「這是我參與11月更文挑戰的第16天,活動詳情檢視:2021最後一次更文挑戰

導讀

在這裡插入圖片描述

肥友們為了更好的去幫助新同學適應演算法和麵試題,最近我們開始進行專項突擊一步一步來。我們先來搞一下讓大家最頭疼的一類演算法題,動態規劃我們將進行為時21天的養成計劃。還在等什麼快來一起肥學進行動態規劃21天挑戰吧!!

21天動態規劃入門

給你一個整數陣列 nums ,找到其中最長嚴格遞增子序列的長度。

子序列是由陣列派生而來的序列,刪除(或不刪除)陣列中的元素而不改變其餘元素的順序。例如,[3,6,2,7] 是陣列 [0,3,1,6,2,2,7] 的子序列。

```java 示例 1:

輸入:nums = [10,9,2,5,3,7,101,18] 輸出:4 解釋:最長遞增子序列是 [2,3,7,101],因此長度為 4 。 ```

```java 示例 2:

輸入:nums = [0,1,0,3,2,3] 輸出:4 ```

```java 示例 3:

輸入:nums = [7,7,7,7,7,7,7] 輸出:1 ```

```java class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int[] dp = new int[nums.length]; dp[0] = 1; int maxans = 1; for (int i = 1; i < nums.length; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } maxans = Math.max(maxans, dp[i]); } return maxans; } }

```

面試題

繼續介紹二叉樹的面試題: 構建二叉樹節點 ```java package tree;

public class node { public int val; public node left;//左孩子 public node right;//右孩子 public node() {

}
public node(int val,node left,node right) {
    this.val=val;
    this.left=left;
    this.right=right;
}
public node(int val, node left) {
    super();
    this.val = val;
    this.left = left;
}

}

```

```java public class kTierNums { //求第k層節點的個數 public int kNums(node root,int k) { if(root==null||k<1)return 0; if(k==1)return 1; int leftNum=kNums(root.left,k-1); int rightNum=kNums(root.right,k-1); return leftNum+rightNum; }

} ``` 問:怎麼判斷是否為平衡二叉樹

我先來說一下什麼是平衡二叉樹

平衡二叉樹(Balanced Binary Tree)又被稱為AVL樹(有別於AVL演算法),且具有以下性質:它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1,並且左右兩個子樹都是一棵平衡二叉樹。這個方案很好的解決了二叉查詢樹退化成連結串列的問題,把插入,查詢,刪除的時間複雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉會使插入和刪除犧牲掉O(logN)左右的時間,不過相對二叉查詢樹來說,時間上穩定了很多。

```java package tree;

public class AVL { //判斷是不是平衡二叉樹 public int BalancedTree(node root) { if(root==null)return 0; int left=BalancedTree(root.left); int right=BalancedTree(root.right); if(left==-1||right==-1||Math.abs(left-right)>1) { return -1; } return Math.max(left, right)+1; } public boolean isBalanced(node root) { return BalancedTree(root)!=1; } }

```