739 每日溫度
根據每日 氣溫 列表，請重新生成一個列表，對應位置的輸出是需要再等待多久溫度才會升高超過該日的天數(shù)。如果之后都不會升高，請在該位置用 0 來代替。
// 思路1 直接遍歷統(tǒng)計
public int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
for(int i=0;i<T.length;i++){
int j = 0;
for(j=i+1;j<T.length&&T[j] <= T[i];j++);
if(j == T.length){
res[i] = 0;
}else{
res[i] = j - i;
}
}
return res;
}
647 回文子串
給定一個字符串，你的任務是計算這個字符串中有多少個回文子串。
具有不同開始位置或結束位置的子串，即使是由相同的字符組成，也會被計為是不同的子串。
public int countSubstrings(String s) {
if(s == null || s.length() == 0){
return 0;
}
boolean[][] dp = new boolean[s.length()][s.length()];
int sum = 0;
for(int i=0;i<s.length();i++){
dp[i][i] = true;
}
sum += s.length();
// i 表示字符串的長度
for(int i=1;i<s.length();i++){
for(int j=0;j<s.length()-i;j++){
if(i == 1){
if(s.charAt(j) == s.charAt(j+1)){
dp[j][j+i] = true;
sum++;
}else{
dp[j][j+i] = false;
}
}else{
dp[j][j+i] = (s.charAt(j) == s.charAt(j+i)) && dp[j+1][j+i-1];
if(dp[j][j+i]){
sum++;
}
}
}
}
return sum;
}
621 任務調度器
給定一個用字符數(shù)組表示的 CPU 需要執(zhí)行的任務列表。其中包含使用大寫的 A - Z 字母表示的26 種不同種類的任務。任務可以以任意順序執(zhí)行，并且每個任務都可以在 1 個單位時間內執(zhí)行完。CPU 在任何一個單位時間內都可以執(zhí)行一個任務，或者在待命狀態(tài)。
然而，兩個相同種類的任務之間必須有長度為 n 的冷卻時間，因此至少有連續(xù) n 個單位時間內 CPU 在執(zhí)行不同的任務，或者在待命狀態(tài)。
你需要計算完成所有任務所需要的最短時間。
示例 ：
輸入：tasks = ["A","A","A","B","B","B"], n = 2
輸出：8
解釋：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
在本示例中，兩個相同類型任務之間必須間隔長度為 n = 2 的冷卻時間，而執(zhí)行一個任務只需要一個單位時間，所以中間出現(xiàn)了（待命）狀態(tài)。
采用模擬的方式實現(xiàn)，每次都是從最高的任務開始執(zhí)行，然后進行遞減，如果為0 ，遞減夠次數(shù)
public int leastInterval(char[] tasks, int n) {
// 算法的思想是每次都進行排序，且每一次都是從最大進行遞減進行模擬
// 任務只有26中使用基數(shù)排序
int[] map = new int[26];
for(char c:tasks){
map[c-'A']++;
}
// 從小到大的排序
Arrays.sort(map);
int time = 0;
while(map[25]>0){
int i = 0;
while(i<=n){
if(map[25] <= 0){
break;
}
if(i<26 && map[25-i] > 0){
map[25-i]--;
}
time++;
i++;
}
Arrays.sort(map);
}
return time;
}
// 方法2 ，采用優(yōu)先隊列不進行排隊，同時采用list保存每次修改的值，然后再添加進去，不能只維護一個list,在此上進行增刪。
public int leastInterval(char[] tasks, int n) {
// 算法的思想是每次都進行排序，且每一次都是從最大進行遞減進行模擬
// 任務只有26中使用基數(shù)排序
// 使用優(yōu)先隊列維持排序的狀態(tài)
int[] map = new int[26];
for(char c:tasks){
map[c-'A']++;
}
PriorityQueue<Integer> queue = new PriorityQueue<>(26,Collections.reverseOrder());
for(int x:map){
if(x > 0)
queue.offer(x);
}
int time = 0;
while(!queue.isEmpty()){
int i = 0;
LinkedList<Integer> list = new LinkedList<>();
while(i <= n){
if(!queue.isEmpty() && queue.peek() > 1){
int t = queue.poll();
list.add(t-1);
}else if(!queue.isEmpty()){
queue.poll();
}
time++;
if(queue.isEmpty() && list.size() == 0){
break;
}
i++;
}
for(int x:list){
queue.offer(x);
}
}
return time;
}
617 合并二叉樹
給定兩個二叉樹，想象當你將它們中的一個覆蓋到另一個上時，兩個二叉樹的一些節(jié)點便會重疊。
你需要將他們合并為一個新的二叉樹。合并的規(guī)則是如果兩個節(jié)點重疊，那么將他們的值相加作為節(jié)點合并后的新值，否則不為 NULL 的節(jié)點將直接作為新二叉樹的節(jié)點。
// 合并二叉樹，采用先序遍歷
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if(t1 == null){
return t2;
}else if(t2 == null){
return t1;
}
t1.val = t1.val + t2.val;
t1.left = mergeTrees(t1.left,t2.left);
t1.right = mergeTrees(t1.right,t2.right);
return t1;
}
581 最短無序連續(xù)子數(shù)組
給定一個整數(shù)數(shù)組，你需要尋找一個連續(xù)的子數(shù)組，如果對這個子數(shù)組進行升序排序，那么整個數(shù)組都會變?yōu)樯蚺判颉?/p>
你找到的子數(shù)組應是最短的，請輸出它的長度。
示例 1:
輸入: [2, 6, 4, 8, 10, 9, 15]
輸出: 5
解釋: 你只需要對 [6, 4, 8, 10, 9] 進行升序排序，那么整個表都會變?yōu)樯蚺判颉?/p>
找到逆序中最小的數(shù)，逆序中最大的數(shù)，
然后從左遍歷找打第一個大于最小數(shù)的值
從右向左遍歷找打第一個小于最大數(shù)的值
public int findUnsortedSubarray(int[] nums) {
if(nums == null || nums.length < 2){
return 0;
}
// 最短無序子數(shù)組，從左到右，從右到左遍歷尋找第一個無序節(jié)點
boolean flag = false;
int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;
for(int i=1;i<nums.length;i++){
if(nums[i] < nums[i-1]) flag = true;
if(flag) min = Math.min(min,nums[i]);
}
flag = false;
for(int i=nums.length-2;i>=0;i--){
if(nums[i] > nums[i+1]) flag = true;
if(flag) max = Math.max(max,nums[i]);
}
int l,r;
for(l=0;l<nums.length;l++){
if(nums[l]>min){
break;
}
}
for(r=nums.length-1;r>=0;r--){
if(nums[r]<max){
break;
}
}
return r-l<0?0:r-l+1;
}
560 和為k的子數(shù)組
求連續(xù)子數(shù)組和，可以使用hashmap 存儲連續(xù)求和的次數(shù)，然后每次進行校驗。
給定一個整數(shù)數(shù)組和一個整數(shù) k，你需要找到該數(shù)組中和為 k 的連續(xù)的子數(shù)組的個數(shù)。
示例 1 :
輸入:nums = [1,1,1], k = 2
輸出: 2 , [1,1] 與 [1,1] 為兩種不同的情況。
public int subarraySum(int[] nums, int k) {
// 使用hashmap 統(tǒng)計和為k的數(shù)組個數(shù)
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int sum = 0;
int count = 0;
for(int i=0;i<nums.length;i++){
sum += nums[i];
if(map.containsKey(sum-k)){
count += map.get(sum-k);
}
map.put(sum,map.getOrDefault(sum,0)+1);
}
return count;
}
543 二叉樹的直徑
給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值。這條路徑可能穿過也可能不穿過根結點。
示例 :
給定二叉樹
1
/ \
2 3
/ \
4 5
返回 3, 它的長度是路徑 [4,2,1,3] 或者 [5,2,1,3]。
class NodeCount{
int val;
int mixVal;
int maxVal;
public NodeCount(int val,int mixVal,int maxVal){
this.val = val;
this.mixVal = mixVal;
this.maxVal = maxVal;
}
}
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
NodeCount res = diameterOfBinaryTreeCore(root);
return res.maxVal-1;
}
public NodeCount diameterOfBinaryTreeCore(TreeNode root){
if(root == null){
return new NodeCount(0,0,0);
}
NodeCount left = diameterOfBinaryTreeCore(root.left);
NodeCount right = diameterOfBinaryTreeCore(root.right);
int mixVal = left.val + right.val + 1;
int val = Math.max(left.val,right.val)+1;
int maxVal = Math.max(val,mixVal);
NodeCount node = new NodeCount(val,mixVal,Math.max(maxVal,Math.max(left.maxVal,right.maxVal)));
return node;
}
// 直接記錄長度即可
// 這里只需要返回 單節(jié)點的長度，總長度采用外變量進行更新
int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
depthTree(root);
return ans-1;
}
public int depthTree(TreeNode root){
if(root == null){
return 0;
}
int L = depthTree(root.left);
int R = depthTree(root.right);
ans = Math.max(ans,L+R+1);
return Math.max(L,R)+1;
}
538. 把二叉樹轉換為累加樹
int curValue = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null){
return root;
}
root.right = convertBST(root.right);
curValue += root.val;
root.val = curValue;
root.left = convertBST(root.left);
return root;
}
494. 目標和
給定一個非負整數(shù)數(shù)組，a1, a2, ..., an, 和一個目標數(shù)，S?，F(xiàn)在你有兩個符號 + 和 -。對于數(shù)組中的任意一個整數(shù)，你都可以從 + 或 -中選擇一個符號添加在前面。
返回可以使最終數(shù)組和為目標數(shù) S 的所有添加符號的方法數(shù)。
示例 1:
輸入: nums: [1, 1, 1, 1, 1], S: 3
輸出: 5
// 首先的思路是回溯深搜
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
if(nums == null || nums.length == 0){
return 0;
}
dfs(nums,S,0);
return count;
}
public void dfs(int[] nums,int S, int cur){
if(cur == nums.length){
if(S == 0){
count ++;
}
return;
}else{
// 要么加
dfs(nums,S-nums[cur],cur+1);
// 要么減
dfs(nums,S+nums[cur],cur+1);
}
}
// 采用動態(tài)規(guī)劃的思想，每次求前i項和為j的次數(shù)
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
if(nums == null || nums.length == 0){
return 0;
}
// 分別表示前 i 項 和 為 j
int[][] dp = new int[nums.length][2001];
// 這里加1000 是怕出現(xiàn)負數(shù)
dp[0][nums[0] + 1000] = 1;
dp[0][-nums[0]+1000] += 1;
for(int i=1;i<nums.length;i++){
for(int j=-1000;j<=1000;j++){
// 說明存在前i-1項和
if(dp[i-1][j+1000] > 0){
dp[i][j-nums[i]+1000] += dp[i-1][j+1000];
dp[i][j+nums[i]+1000] += dp[i-1][j+1000];
}
}
}
return S > 1000 ? 0 : dp[nums.length - 1][S + 1000];
}
461. 漢明距離
兩個整數(shù)之間的漢明距離指的是這兩個數(shù)字對應二進制位不同的位置的數(shù)目。
給出兩個整數(shù) x 和 y，計算它們之間的漢明距離。
注意：
0 ≤ x, y < 231.
示例:
輸入: x = 1, y = 4
輸出: 2
思路：異或相同為0，不同為1
// 漢明距離，異或相同為0，不同為1
public int hammingDistance(int x, int y) {
int res = x ^ y;
int count = 0;
for(int i=0;i<32;i++){
if(((res>>i)&1) == 1){
count++;
}
}
return count;
}
448.找到所有數(shù)組中消失的數(shù)
給定一個范圍在 1 ≤ a[i] ≤ n ( n = 數(shù)組大小 ) 的 整型數(shù)組，數(shù)組中的元素一些出現(xiàn)了兩次，另一些只出現(xiàn)一次。
找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字。
您能在不使用額外空間且時間復雜度為O(n)的情況下完成這個任務嗎? 你可以假定返回的數(shù)組不算在額外空間內。
示例:
輸入:
[4,3,2,7,8,2,3,1]
輸出:
[5,6]
public List<Integer> findDisappearedNumbers(int[] nums) {
int[] copy = new int[nums.length+1];
for(int x:nums){
copy[x%(nums.length+1)] = 1;
}
List<Integer> res = new ArrayList<>();
for(int i=1;i<copy.length;i++){
if(copy[i] != 1){
res.add(i);
}
}
return res;
}
// 原數(shù)組取反標記，已經訪問過
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
// 思路任然采用原地標記的思路，將原數(shù)值，取反，來表示已經訪問過，沒變?yōu)樨摂?shù)說明沒訪問過
for(int i=0;i<nums.length;i++){
int val = Math.abs(nums[i])-1;
if(nums[val] > 0){
nums[val] = -nums[val];
}
}
for(int i=0;i<nums.length;i++){
if(nums[i] > 0){
res.add(i+1);
}
}
return res;
}
438. 找到字符串中的異位符
給定一個字符串 s 和一個非空字符串 p，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引。
字符串只包含小寫英文字母，并且字符串 s 和 p 的長度都不超過 20100。
說明：
字母異位詞指字母相同，但排列不同的字符串。
不考慮答案輸出的順序。
示例 1:
輸入:
s: "cbaebabacd" p: "abc"
輸出:
[0, 6]
// 思路是采用字符數(shù)組統(tǒng)計的方式判斷字符串是否相同
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int len = p.length();
for(int i=0;i<s.length()-len+1;i++){
String sub = s.substring(i,i+len);
if(check(sub,p)){
res.add(i);
}
}
return res;
}
// 如果只有字符的字符串可以使用hash來判斷是否相同
public boolean check(String s, String t){
int[] z = new int[26];
for(char x:s.toCharArray()){
z[(x-'a')] ++;
}
for(char x:t.toCharArray()){
z[(x-'a')] --;
}
for(int x:z){
if(x != 0){
return false;
}
}
return true;
}
// 使用滑動窗口找尋字符異位詞
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int len = p.length();
int[] needs = new int[26];
int[] windows = new int[26];
// 先統(tǒng)計p的字符數(shù)
for(char c:p.toCharArray()){
needs[c-'a']++;
}
int left = 0,right = 0,total = len;
while(right < s.length()){
char ch = s.charAt(right);
if(needs[ch-'a'] > 0){
windows[ch-'a']++;
if(windows[ch-'a']<=needs[ch-'a']){
total--;
}
}
while(total == 0){
if(right-left+1 == len){
res.add(left);
}
char c = s.charAt(left);
if(needs[c-'a'] > 0){
windows[c-'a'] --;
if(windows[c-'a'] < needs[c-'a']){
total++;
}
}
left++;
}
right++;
}
return res;
}
437. 路徑總和3
給定一個二叉樹，它的每個結點都存放著一個整數(shù)值。
找出路徑和等于給定數(shù)值的路徑總數(shù)。
路徑不需要從根節(jié)點開始，也不需要在葉子節(jié)點結束，但是路徑方向必須是向下的（只能從父節(jié)點到子節(jié)點）。
二叉樹不超過1000個節(jié)點，且節(jié)點數(shù)值范圍是 [-1000000,1000000] 的整數(shù)。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
// 先序遍歷尋找路徑和為sum的次數(shù)
int count = 0;
public int pathSum(TreeNode root, int sum) {
if(root == null){
return 0;
}
preOrder(root,sum);
pathSum(root.left,sum);
pathSum(root.right,sum);
return count;
}
public void preOrder(TreeNode root,int sum){
if(root == null){
return;
}
sum -= root.val;
if(sum == 0){
count++;
}
preOrder(root.left,sum);
preOrder(root.right,sum);
}
// 每一個節(jié)點進行統(tǒng)計返回
public int pathSum(TreeNode root, int sum) {
if (root == null){
return 0;
}
return paths(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
}
private int paths(TreeNode root,int sum) {
if (root == null){
return 0;
}
int res = 0;
if (root.val == sum){
res ++;
}
res += paths(root.left,sum - root.val);
res += paths(root.right,sum - root.val);
return res;
}
416 分割等和子集
// 實際上可以轉化為，子集中是否存在是二分之一的子集
// 采用枚舉的方法進行dfs搜索
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0){
return false;
}
int sum = 0;
for(int x:nums){
sum += x;
}
if(sum % 2 == 1){
return false;
}
// 使用背包問題的動態(tài)規(guī)劃進行求解
boolean[][] dp = new boolean[nums.length][sum/2+1];
int target = sum/2;
if(nums[0] <= target){
dp[0][nums[0]] = true;
}
for(int i=1;i<nums.length;i++){
for(int j=0;j<=target;j++){
dp[i][j] = dp[i-1][j];
if(nums[i] == j){
dp[i][j] = true;
continue;
}
if(nums[i]<j){
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
}
}
}
return dp[nums.length-1][target];
}
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0){
return false;
}
int sum = 0;
for(int x:nums){
sum += x;
}
if(sum % 2 == 1){
return false;
}
// 使用背包問題的動態(tài)規(guī)劃進行求解
boolean[][] dp = new boolean[nums.length][sum/2+1];
int target = sum/2;
if(nums[0] <= target){
dp[0][nums[0]] = true;
}
for(int i=1;i<nums.length;i++){
for(int j=0;j<=target;j++){
dp[i][j] = dp[i-1][j];
if(nums[i]<=j){
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
}
}
if(dp[i][target]){
return true;
}
}
return dp[nums.length-1][target];
}
45. 跳躍游戲2
給定一個非負整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置。
數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置。
示例:
輸入: [2,3,1,1,4]
輸出: 2
思路是使用最大位置記錄最大，當?shù)竭_最大位置時更新遍歷過程中的最大位置。
public int jump(int[] nums) {
int step = 0;
int maxPosition = nums[0];
int curMaxPosition = 0;
for(int i=1;i<nums.length;i++){
curMaxPosition = Math.max(curMaxPosition,i+nums[i]);
if(i == maxPosition || i == nums.length -1){
maxPosition = curMaxPosition;
step++;
}
}
return step;
}
406. 根據身高重建隊列
假設有打亂順序的一群人站成一個隊列。 每個人由一個整數(shù)對(h, k)表示，其中h是這個人的身高，k是排在這個人前面且身高大于或等于h的人數(shù)。 編寫一個算法來重建這個隊列。
注意：
總人數(shù)少于1100人。
示例
輸入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
輸出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
public int[][] reconstructQueue(int[][] people) {
// 思路是先將所有人，按照從高到底，從前到后進行排序，這是因為最小的表明前2位置它一定是前2
// 先讓個高進行插入
Arrays.sort(people,(o1,o2)->(o1[0] == o2[0])?o1[1] - o2[1]:o2[0]-o1[0]);
List<int[]> res = new ArrayList<>();
for(int[] i:people){
res.add(i[1],i);
}
// 將list 轉換為 int[]數(shù)組使用toArray
return res.toArray(new int[res.size()][2]);
}
394. 字符串解碼
這里字符串的存儲必須使用StringBuilder 否則String 使用字符常量池會有65535限制。
字符串的解碼， 使用字符棧 和 數(shù)值棧， 使用stringBuilder
在遇見 [ 時入棧， 在遇見 ] 只計算當前res重算的次數(shù)，不入棧
res = new StringBuilder(strStack.pop() + sb.toString());
其次不用考慮棧是否為空，括號一定是成對的。
public String decodeString(String s) {
// 使用數(shù)值棧 和 字符串棧來解析字符串
char[] ss = s.toCharArray();
Stack<Integer> numStack = new Stack<>();
Stack<String> strStack = new Stack<>();
int tmpNum = 0;
StringBuilder res = new StringBuilder();
for(char c : ss){
if(c>='0' && c<='9'){
tmpNum = tmpNum * 10 + (c - '0');
}else if(c == '['){
numStack.push(tmpNum);
strStack.push(res.toString());
res = new StringBuilder();
tmpNum = 0;
}else if(c == ']'){
int x = numStack.pop();
StringBuilder sb = new StringBuilder();
while(x-->0){
sb.append(res);
}
res = new StringBuilder(strStack.pop() + sb.toString());
}else {
res.append(c);
}
}
return res.toString();
}
347. 前k個高頻元素
給定一個非空的整數(shù)數(shù)組，返回其中出現(xiàn)頻率前 k 高的元素。
示例 1:
輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]
// 使用堆排序構建前k個高頻元素
public int[] topKFrequent(int[] nums, int k) {
// 統(tǒng)計前k個高頻元素，可以采用hashmap 進行統(tǒng)計，然后放入優(yōu)先隊列
HashMap<Integer,Integer> map = new HashMap<>();
for(int x:nums){
map.put(x,map.getOrDefault(x,0)+1);
}
PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->(map.get(o1) - map.get(o2)));
for(int x:map.keySet()){
queue.offer(x);
if(queue.size()>k){
queue.poll();
}
}
int[] res = new int[k];
for(int i=k-1;i>=0;i--){
res[i] = queue.poll();
}
return res;
}
// 使用堆排序構建前k個高頻元素
public int[] topKFrequent(int[] nums, int k) {
// 統(tǒng)計前k個高頻元素，可以采用hashmap 進行統(tǒng)計，然后放入優(yōu)先隊列
HashMap<Integer,Integer> map = new HashMap<>();
for(int x:nums){
map.put(x,map.getOrDefault(x,0)+1);
}
// 使用桶排序獲取前k大，將數(shù)字的次數(shù)作為插入的下標,使用數(shù)組鏈表數(shù)組結構解決hash沖突
ArrayList<Integer>[] list = new ArrayList[nums.length+1];
for(int x:map.keySet()){
int index = map.get(x);
if(list[index] == null){
list[index] = new ArrayList<>();
}
list[index].add(x);
}
List<Integer> res = new ArrayList<>();
for(int i = list.length - 1;i >= 0 && res.size() < k;i--){
if(list[i] == null) continue;
res.addAll(list[i]);
}
int[] result = new int[k];
for(int i=0;i<k;i++){
result[i] = res.get(i);
}
return result;
}
338. 比特幣計數(shù)
// 統(tǒng)計數(shù)中1的.
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for(int i=1;i<=num;i++){
ans[i] = ans[i&(i-1)] + 1;
}
return ans;
}
337. 打家劫舍3
在上次打劫完一條街道之后和一圈房屋后，小偷又發(fā)現(xiàn)了一個新的可行竊的地區(qū)。這個地區(qū)只有一個入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。
計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。
示例 1:
輸入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
public int rob(TreeNode root) {
return Solution(root).val;
}
public TreeNode Solution(TreeNode root){
if(root == null){
TreeNode newNode = new TreeNode(0);
return Solution(newNode);
}
if(root.left == null && root.right == null){
root.left = new TreeNode(0);
root.right = new TreeNode(0);
return root;
}
root.left = Solution(root.left);
root.right = Solution(root.right);
root.val = Math.max(root.left.val + root.right.val, root.val + root.left.left.val + root.left.right.val + root.right.left.val + root.right.right.val);
return root;
}
public int rob(TreeNode root) {
// 爺爺 + 孫子 和 爸爸 比大小
if(root == null){
return 0;
}
int[] res = robCore(root);
return Math.max(res[0],res[1]);
}
// 狀態(tài)轉換機，每一個節(jié)點都有偷或者不偷兩種
public int[] robCore(TreeNode root){
if(root == null){
return new int[2];
}
int[] res = new int[2];
int[] left = robCore(root.left);
int[] right = robCore(root.right);
res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
res[1] = left[0] + right[0] + root.val;
return res;
}
322. 零錢兌換
給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)。如果沒有任何一種硬幣組合能組成總金額，返回 -1。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
思路是動態(tài)規(guī)劃，找找到amount錢的最少次數(shù)，就依次找出從1~amount的最少次數(shù)。
dp[i] = dp[i-coins[j]] + 1
public int coinChange(int[] coins, int amount) {
// 零錢兌換，就動態(tài)規(guī)劃，找到兌換i的最少錢數(shù)
// dp[i] = min 遍歷 dp[i-coins[j]] + 1
if(coins == null || coins.length == 0){
return -1;
}
int[] dp = new int[amount+1];
for(int i=1;i<=amount;i++){
// 這里最小的找錢次數(shù)是 amount + 1, 不要亂改
int min = amount+1;
for(int j=0;j<coins.length;j++){
if(coins[j]<=i)
min = Math.min(min,dp[i-coins[j]]+1);
}
dp[i] = min;
}
if (dp[amount] == amount+1){
return -1;
}
return dp[amount];
}
309.最佳買賣股票時機含冷凍期
給定一個整數(shù)數(shù)組，其中第 i 個元素代表了第 i 天的股票價格 。?
設計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。
示例:
輸入: [1,2,3,0,2]
輸出: 3
public int maxProfit(int[] prices) {
if(prices == null || prices.length < 2){
return 0;
}
// 使用狀態(tài)機進行計算
int[][] dp = new int[prices.length][3];
// 0 代表不持股 1 代表持股 2 代表 冷凍期
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for(int i=1;i < prices.length;i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2] - prices[i]);
dp[i][2] = dp[i-1][0];
}
return Math.max(dp[prices.length-1][0],Math.max(dp[prices.length-1][1],dp[prices.length-1][2]));
}
大數(shù)乘法
public String multiply(String num1, String num2){
int[] result = new int[num1.length() + num2.length()];
int[] n1 = new int[num1.length()];
int[] n2 = new int[num2.length()];
for(int i=0;i<num1.length();i++){
n1[i] = num1.charAt(i) - '0';
}
for(int j=0;j<num2.length();j++){
n2[j] = num2.charAt(j) - '0';
}
for(int i=0;i<num1.length();i++){
for(int j=0;j<num2.length();j++){
result[i+j] = n1[i] * n2[j];
}
}
// 進行進位
for(int i=result.length-1;i>0;i--){
result[i-1] += result[i] / 10;
result[i] = result[i] % 10;
}
// 轉String
String res = "";
for(int i=0;i<result.length;i++){
res += result[i] + "";
}
return res;
}
287. 尋找重復的數(shù)
給定一個包含 n + 1 個整數(shù)的數(shù)組 nums，其數(shù)字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數(shù)。假設只有一個重復的整數(shù)，找出這個重復的數(shù)。
示例 1:
輸入: [1,3,4,2,2]
輸出: 2
public int findDuplicate(int[] nums) {
// 使用本地相反數(shù)進行標注
for(int x: nums){
int index = Math.abs(x);
if(nums[index] < 0){
return index;
}else{
nums[index] = -nums[index];
}
}
return -1;
}
283 移動0
給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。
示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
public void moveZeroes(int[] nums) {
// 創(chuàng)建一個新的index作為防止下標
int index = 0;
for(int x : nums){
if(x != 0)
nums[index++] = x;
}
while(index < nums.length){
nums[index++] = 0;
}
}
279 完全平方數(shù)
給定正整數(shù) n，找到若干個完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n。你需要讓組成和的完全平方數(shù)的個數(shù)最少。
示例 1:
輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4.
public int numSquares(int n) {
int sqareLen = (int)(Math.sqrt(n));
int[] numSqare = new int[sqareLen];
for(int i=1;i<=sqareLen;i++){
numSqare[i-1] = i * i;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=n;i++){
int count = n+1;
for(int j=0;j < sqareLen && numSqare[j]<= i;j++){
count = Math.min(count,dp[i-numSqare[j]]+1);
}
dp[i] = count;
}
return dp[n];
}
240. 搜索二維矩陣
編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標值 target。該矩陣具有以下特性：
每行的元素從左到右升序排列。
每列的元素從上到下升序排列。
示例:
現(xiàn)有矩陣 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
// 思路搜索從左下角開始
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int i = m-1,j = 0;
while(i >=0 && i < m && j >=0 && j < n){
if(matrix[i][j] == target){
return true;
}else if(matrix[i][j] < target){
j++;
}else{
i--;
}
}
return false;
}
239.滑動窗口的最大值
給定一個數(shù)組 nums，有一個大小為 k 的滑動窗口從數(shù)組的最左側移動到數(shù)組的最右側。你只可以看到在滑動窗口內的 k 個數(shù)字。滑動窗口每次只向右移動一位。
返回滑動窗口中的最大值。
public int[] maxSlidingWindow(int[] nums, int k) {
// 創(chuàng)建維持一個最大數(shù)值
int[] res = new int[nums.length-k+1];
for(int i=0;i<nums.length-k+1;i++){
int max = Integer.MIN_VALUE;
if(i > 0 && nums[i-1] != res[i-1] && nums[i+k-1] < res[i-1]){
res[i] = res[i-1];
}else{
for(int j=i;j<i+k;j++){
max = Math.max(max,nums[j]);
}
res[i] = max;
}
}
return res;
}
O(n) 的時間復雜度
public int[] maxSlidingWindow(int[] nums, int k) {
// 創(chuàng)建維持一個最大數(shù)值
// 維持left 最大數(shù)組 // 維持一個右最大數(shù)組
int n = nums.length;
if(n * k == 0){
return new int[0];
}
if(k == 1){
return nums;
}
int[] left = new int[n];
left[0] = nums[0];
int[] right = new int[n];
right[n-1] = nums[n-1];
for(int i = 1;i<n;i++){
if(i % k == 0){
left[i] = nums[i];
}else{
left[i] = Math.max(left[i-1],nums[i]);
}
int j = n - i - 1;
if((j+1)%k == 0){
right[j] = nums[j];
}else{
right[j] = Math.max(right[j+1],nums[j]);
}
}
int[] output = new int[n-k+1];
for (int i = 0; i < n - k + 1; i++)
output[i] = Math.max(left[i + k - 1], right[i]);
return output;
}
238.除自身以外數(shù)組的乘積
給你一個長度為 n 的整數(shù)數(shù)組 nums，其中 n > 1，返回輸出數(shù)組 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積。
示例:
輸入: [1,2,3,4]
輸出: [24,12,8,6]
public int[] productExceptSelf(int[] nums) {
int[] tmp = new int[nums.length];
tmp[0] = 1;
for(int i=1;i<nums.length;i++){
tmp[i] = tmp[i-1] * nums[i-1];
}
int[] tmp2 = new int[nums.length];
tmp2[nums.length-1] = 1;
for(int i=nums.length-2;i>=0;i--){
tmp2[i] = tmp2[i+1] * nums[i+1];
}
for(int i=0;i<nums.length;i++){
tmp[i] = tmp[i] * tmp2[i];
}
return tmp;
}
234. 回文鏈表
請判斷一個鏈表是否為回文鏈表。
示例 1:
輸入: 1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
public boolean isPalindrome(ListNode head) {
Stack<Integer> stack = new Stack<>();
ListNode p = head;
while(p != null){
stack.push(p.val);
p = p.next;
}
p = head;
while(!stack.empty()){
int val = stack.pop();
if(val != p.val){
return false;
}
p = p.next;
}
return true;
}
// 采用回溯法進行判斷
ListNode first = null;
public boolean isPalindrome(ListNode head) {
first = head;
return isPalindromeCore(head);
}
public boolean isPalindromeCore(ListNode node){
if(node == null){
return true;
}
if(!isPalindromeCore(node.next)) return false;
if(first.val != node.val) return false;
first = first.next;
return true;
}
226. 翻轉二叉樹
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
221. 最大正方形
在一個由 0 和 1 組成的二維矩陣內，找到只包含 1 的最大正方形，并返回其面積。
示例:
輸入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
輸出: 4
public int maximalSquare(char[][] matrix) {
int res = 0;
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return res;
}
int[][] dp = new int[matrix.length][matrix[0].length];
for(int i=0;i<matrix.length;i++){
if(matrix[i][0] == '1') res = 1;
dp[i][0] = matrix[i][0] - '0';
}
for(int i=0;i<matrix[0].length;i++){
if(matrix[0][i] == '1') res = 1;
dp[0][i] = matrix[0][i] - '0';
}
for(int i=1;i<matrix.length;i++){
for(int j=1;j<matrix[0].length;j++){
if(matrix[i][j] == '1'){
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
res = Math.max(res,dp[i][j]);
}
}
}
return res * res;
}
215. 數(shù)組中第K大元素
在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。
示例 1:
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int x:nums){
queue.offer(x);
if(queue.size() > k){
queue.poll();
}
}
return queue.poll();
}
208. 字典樹
實現(xiàn)一個 Trie (前綴樹)，包含 insert, search, 和 startsWith 這三個操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
class Trie {
class TrieNode{
TrieNode[] links;
boolean isEnd;
final int R = 26;
public TrieNode(){
links = new TrieNode[R];
}
// 是否包含
public boolean containsKey(char ch){
return links[ch - 'a'] != null;
}
// put
public void put(char ch,TrieNode node){
links[ch-'a'] = node;
}
// get
public TrieNode get(char ch){
return links[ch - 'a'];
}
public void setEnd(){
isEnd = true;
}
public boolean isEnd(){
return isEnd;
}
}
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c: word.toCharArray()){
if(!node.containsKey(c)){
node.put(c,new TrieNode());
}
node = node.get(c);
}
node.setEnd();
}
private TrieNode searchPrifix(String word){
TrieNode node = root;
for(char c:word.toCharArray()){
if(node.containsKey(c)){
node = node.get(c);
}else{
return null;
}
}
return node;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = searchPrifix(word);
return node != null && node.isEnd();
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = searchPrifix(prefix);
return node != null;
}
}
/**
* 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);
*/
207. 課程表
你這個學期必須選修 numCourse 門課程，記為 0 到 numCourse-1 。
在選修某些課程之前需要一些先修課程。 例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們：[0,1]
給定課程總量以及它們的先決條件，請你判斷是否可能完成所有課程的學習？
示例 1:
輸入: 2, [[1,0]]
輸出: true
解釋: 總共有 2 門課程。學習課程 1 之前，你需要完成課程 0。所以這是可能的。
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] coursesCount = new int[numCourses];
for(int[] item:prerequisites){
coursesCount[item[1]]++;
}
Stack<Integer> stack = new Stack<>();
for(int i=0;i<coursesCount.length;i++){
if(coursesCount[i] == 0)
stack.push(i);
}
while(!stack.empty()){
int x = stack.pop();
for(int[] item: prerequisites){
if(item[0] == x){
coursesCount[item[1]]--;
if(coursesCount[item[1]] == 0){
stack.push(item[1]);
}
}
}
}
for(int x:coursesCount){
if(x != 0){
return false;
}
}
return stack.empty();
}
206.翻轉鏈表
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
ListNode pre = null;
ListNode p = head;
while(p != null){
ListNode next = p.next;
p.next = pre;
pre = p;
p = next;
}
return pre;
}
遞歸的翻轉二茬鏈表
public ListNode reverseList(ListNode head) {
if(head.next == null){
return head;
}
ListNode node = reverseList(head.next);
head.next.next = head;
head.next = null;
return node;
}
236. 二叉樹最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left != null && right != null){
return root;
}else if(root == p || root == q){
return root;
}
return left == null ? right:left;
}
200. 島嶼的數(shù)量
給你一個由 '1'（陸地）和 '0'（水）組成的的二維網格，請你計算網格中島嶼的數(shù)量。
島嶼總是被水包圍，并且每座島嶼只能由水平方向或豎直方向上相鄰的陸地連接形成。
此外，你可以假設該網格的四條邊均被水包圍。
示例 1:
輸入:
11110
11010
11000
00000
輸出: 1
// 標注即可
boolean[][] vis;
char[][] grid;
int m,n;
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0){
return 0;
}
this.grid = grid;
m = grid.length;
n = grid[0].length;
vis = new boolean[m][n];
int count = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j] == '1' && !vis[i][j]){
dfs(i,j);
count++;
}
}
}
return count;
}
public void dfs(int x,int y){
if(x < 0 || x >=m || y < 0 || y >= n || grid[x][y] != '1' ||vis[x][y]){
return;
}else{
vis[x][y] = true;
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x,y+1);
}
}
198. 打家劫舍
你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
示例 1:
輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
public int rob(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
if(nums.length <2){
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length;i++){
dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);
}
return dp[nums.length-1];
}
169.多數(shù)元素
給定一個大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素。
你可以假設數(shù)組是非空的，并且給定的數(shù)組總是存在多數(shù)元素。
示例 1:
輸入: [3,2,3]
輸出: 3
示例 2:
輸入: [2,2,1,1,1,2,2]
輸出: 2
// 多數(shù)元素，元素個數(shù)大于n/2 的可以，統(tǒng)計一個變量進行計數(shù)
public int majorityElement(int[] nums) {
int count = 1;
int element = nums[0];
for(int i=1;i<nums.length;i++){
if(nums[i] == element){
count++;
}else{
count--;
if(count == 0){
element = nums[i];
count = 1;
}
}
}
return element;
}
160. 找出鏈表的相交節(jié)點
思路使用交叉遍歷的方法
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA,q = headB;
while(p != q){
p = p == null ? headB:p.next;
q = q == null ? headA:q.next;
}
return p;
}
155. 最小棧
設計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內檢索到最小元素的棧。
push(x) —— 將元素 x 推入棧中。
pop() —— 刪除棧頂?shù)脑亍?br>
top() —— 獲取棧頂元素。
getMin() —— 檢索棧中的最小元素。
使用雙棧實現(xiàn)最小棧
class MinStack {
// 使用雙棧實現(xiàn)最小棧
Stack<Integer> stack;
Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if(minStack.empty()){
minStack.push(x);
}else{
int y = minStack.peek();
if(x < y){
minStack.push(x);
}else{
minStack.push(y);
}
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
152. 乘積最大子數(shù)組
給你一個整數(shù)數(shù)組 nums ，請你找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組中至少包含一個數(shù)字），并返回該子數(shù)組所對應的乘積。
示例 1:
輸入: [2,3,-2,4]
輸出: 6
curMax * x 和 x 比較大小，curMin * x 和 比最小
public int maxProduct(int[] nums) {
// 維護最大和最小值
int max = Integer.MIN_VALUE;
int curMax = 1;
int curMin = 1;
for(int x:nums){
if(x < 0){
int tmp = curMax;
curMax = curMin;
curMin = tmp;
}
curMax = Math.max(x,curMax * x);
curMin = Math.min(x,curMin*x);
max = Math.max(max,curMax);
}
return max;
}
139.單詞拆分
使用回溯加記憶完成單詞的拆分
給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現(xiàn)的單詞。
說明：
拆分時可以重復使用字典中的單詞。
你可以假設字典中沒有重復的單詞。
示例 1：
輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因為 "leetcode" 可以被拆分成 "leet code"。
// 使用回溯算法進行嘗試
public boolean wordBreak(String s, List<String> wordDict) {
return wordBreak(s,wordDict,0,new Boolean[s.length()]);
}
// 使用回溯算法進行嘗試
public boolean wordBreak(String s, List<String> wordDict,int cur,Boolean[] memo) {
if(s.equals("") || s.length() == 0){
return true;
}else if(memo[cur] != null) {
return memo[cur];
}else {
for(int j=0;j < wordDict.size();j++){
String start = wordDict.get(j);
if(s.startsWith(start)){
boolean res = wordBreak(s.substring(start.length()), wordDict,cur + start.length()-1,memo);
if(res) {
return memo[cur] = true;
}
}
}
}
return memo[cur] = false;
}
// 使用動態(tài)規(guī)劃進行單詞的拆分
// 使用動態(tài)規(guī)劃
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for(int i=1;i<=s.length();i++){
for(int j=0;j<i;j++){
if(dp[j] && set.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
柱形圖中最大矩形面積
給定 n 個非負整數(shù)，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積.
// 最大的矩形面積是，當前的寬度乘以最小的高度
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
int minHeight = Integer.MAX_VALUE;;
for(int i=0;i<heights.length;i++){
minHeight = Integer.MAX_VALUE;
for(int j=i;j<heights.length;j++){
minHeight = Math.min(minHeight,heights[j]);
maxArea = Math.max(maxArea,minHeight * (j-i+1));
}
}
return maxArea;
}
// 柱形圖最大矩形面積，是最矮柱子盡可能兩邊延伸
// 最矮柱子左邊最大面積
// 最矮柱子右邊最大面積
// 采用分治的思想，找到最小的柱子
public int largestRectangleArea(int[] heights) {
return largestRectangleArea(heights,0,heights.length-1);
}
public int largestRectangleArea(int[] heights, int left, int right){
if(right < left){
return 0;
}
int minHeight = left;
for(int i=left + 1;i<=right;i++){
if(heights[i] < heights[minHeight]){
minHeight = i;
}
}
int area = heights[minHeight] * (right - left + 1);
int leftArea = largestRectangleArea(heights,left,minHeight-1);
int rightArea = largestRectangleArea(heights,minHeight+1,right);
return Math.max(area,Math.max(leftArea,rightArea));
}
79. 單詞搜索
給定一個二維網格和一個單詞，找出該單詞是否存在于網格中。
單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。
存在一個情況進入還需要退出的情況下必須進行回溯，否則可以直接dfs
boolean[][] vis;
public boolean exist(char[][] board, String word) {
if(board == null || board.length == 0 || board[0].length == 0){
return false;
}
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(board[i][j] == word.charAt(0)){
vis = new boolean[board.length][board[0].length];
vis[i][j] = true;
boolean flag = dfs(board,word.substring(1),i,j);
if(flag){
return true;
}
}
}
}
return false;
}
int[][] next = {{0,1},{0,-1},{1,0},{-1,0}};
public boolean dfs(char[][] board,String word, int x, int y){
if(word == null || word.length() == 0){
return true;
}else{
for(int i=0;i<4;i++){
int xx = x + next[i][0];
int yy = y + next[i][1];
if(xx >= 0 && xx < board.length && yy >= 0 && yy < board[0].length && board[xx][yy] == word.charAt(0) && !vis[xx][yy]){
vis[xx][yy] = true;
boolean flag = dfs(board,word.substring(1),xx,yy);
if(flag) return true;
vis[xx][yy] = false;
}
}
}
return false;
}
