輸入方式
必須引入的包java.util.*
- list轉陣列的方式：
int[] nums = list.stream().mapToInt(Integer::intValue).toArray();
- 或是通過String.split(" ")來分割
舉例
public static void main(String[] args) {
Solution solution = new Solution();
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
String[] data = https://www.cnblogs.com/kitorio/p/input.split(" ");
int[] nums = new int[data.length];
for (int i = 0; i < nums.length; i++) {
nums[i] = Integer.parseInt(data[i]);
}
int k = sc.nextInt();
System.out.println(solution.KEqualSumSubset(nums, k));
sc.close();
}
-
Stack的方法：
empty，peek(查看頂部但不移出),pop(移出頂部),push(壓入頂部) -
Queue的方法：
empty,offer,poll,``peek(查看但不移出)` -
Deque的方法：
offerFirst,offerLast等等
注意Queue和Deque的初始化方法是new LinkedList<>() -
Arrays的sort方法
Arrays.sort(arr,(a,b)->{return b - a;}) //自定義降序 Arrays.sort(arr,(a,b)->{return b[1] - a[1];}) //二維陣列優先讓第二列按照降序排列 -
HashSet的方法：
contains,removes,add,clear,size, -
Hashmap的方法：
put,get,removes,constainsKey,getOrDefault,putIfAbsent
迭代方法Set<Map.Entry<Integer,String>> sets=maps.entrySet(); for(Map.Entry<Integer,String> entry:sets){ System.out.println("key="+entry.getKey()+"value="https://www.cnblogs.com/kitorio/p/+entry.getValue()); }
分治
將一個復雜的問題分割成規模較小的相同問題，以便各個擊破，
1.最大二叉樹
給定一個不含重復元素的整數陣列 nums，以此陣列直接遞回構建的最大二叉樹，最大二叉樹定義如下：
- 二叉樹的根是陣列 nums 中的最大元素，
- 左子樹是通過陣列中最大值左邊部分遞回構造出的最大二叉樹，
- 右子樹是通過陣列中最大值右邊部分遞回構造出的最大二叉樹，
回傳有給定陣列nums 構建的最大二叉樹 (前序遍歷輸出)，
思路
遞回構建左子樹以及右子樹，每次都尋找所得陣列中的最大值，將左邊的部分劃分給左子樹，右邊劃分給右子樹，然后將最大值作為節點回傳，
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
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 {
public TreeNode constructMaximunBinaryTree(int[] nums){
return construct(nums,0,nums.length - 1);
}
public TreeNode construct(int[] nums,int left,int right){
if(left > right) return null;
int maxidx = left;
for(int i = left + 1;i <= right;i++){
if(nums[i] > nums[maxidx]){
maxidx = i;
}
}
TreeNode node = new TreeNode(nums[maxidx]);
node.left = construct(nums,left,maxidx - 1);
node.right = construct(nums,maxidx + 1,right);
return node;
}
}
public class Main {
public void PreOrderRecur(TreeNode root){
// if(root == null){
// System.out.print("null ");
// return;
// }
System.out.print(root.val + " ");
if(root.left == null && root.right == null){
return;
}
if(root.left != null){
PreOrderRecur(root.left);
}else{
System.out.print("null ");
}
if(root.right != null){
PreOrderRecur(root.right);
}else{
System.out.print("null ");
}
}
}
2.鏈表排序
思路
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 ListNode sortListNode(ListNode head) {
if(head == null || head.next == null) return head;
ListNode splienode = split(head);
head = sortListNode(head);
splienode = sortListNode(splienode);
return merge(head,splienode);
}
public ListNode split(ListNode head){
ListNode dummyhead = new ListNode(0,head);
ListNode fast = dummyhead,slow = dummyhead;
while(fast != null && fast.next !=null){
slow = slow.next;
fast = fast.next.next;
}
ListNode ans = slow.next;
slow.next = null; //截斷
return ans;
}
public ListNode merge(ListNode node1,ListNode node2){
ListNode dummyhead = new ListNode(0);
ListNode temp = dummyhead;
ListNode temp1 = node1,temp2 = node2;
while(temp1 != null && temp2 != null){
//將較小值加入到合并后的串列中
if(temp1.val <= temp2.val){
temp.next = temp1;
temp1 = temp1.next;
}else{
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if(temp1 != null){
temp.next = temp1;
}else if(temp2 != null){
temp.next = temp2;
}
return dummyhead.next;
}
}
3.尋找多數
給定一個大小為 n 的整型陣列 a，找到其中的多數元素，多數元素是指在陣列中出現次數大于 ? n/2 ? 的元素，
思路1（分治）
若數a是陣列nums的眾數，那么當nums分為兩部分時，a至少是一部分的眾數，那么就可以將陣列分為左右兩部分，求出左半部分的眾數a1以及右半部分的眾數a2，再對其進行比較
public class Problem2 {
public int majorityElement(int[] nums) {
return majorityElementRec(nums, 0, nums.length - 1);
}
public int majorityElementRec(int[] nums, int left, int right) {
// 特殊情況，不用尋找左右多數可以直接回傳
if (left == right) {
return nums[left];
}
// 將陣列分割為左右部分尋找其各自的多數
int mid = (right - left) / 2 + left;
int leftmajority = majorityElementRec(nums, left, mid);
int rightmajority = majorityElementRec(nums, mid + 1, right);
if (leftmajority == rightmajority) {
return leftmajority;
}
int leftcount = countInRange(nums, leftmajority, left, right);
int rightcount = countInRange(nums, rightmajority, left, right);
return leftcount > rightcount ? leftmajority : rightmajority;
}
// 回傳num在nums中的個數
public int countInRange(int[] nums, int num, int left, int right) {
int count = 0;
for (int i = left; i <= right; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
}
思路2（排序）
直接進行排序，因為當a是多數時，它一定會出現在陣列的 ? n/2 ?下標位置
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for(int i = 0;i < n;i++){
nums[i] = sc.nextInt();
}
Arrays.sort(nums);
System.out.print(nums[n/2]);
}
}
4.找到最大子序和
給定一個整數陣列 nums，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，
思路1（分治）
取m=?(l+r)/2?，對[l+m]和[m+1,r]分治求解，所需要維護的為下述四個量：
-
lSum 表示 l,r內以 l為左端點的最大子段和，lSum=Max(左子區間的lSum,左子區間的iSum+右子區間的lSum)
-
rSum 表示 l,r內以 r 為右端點的最大子段和，其值同上
-
mSum 表示 l,r內的最大子段和,mSum=Max(左子區間的mSum,右子區間的mSum,左子區間的rSum+右子區間的lSum)
-
iSum 表示l,r 的區間和
public class Problem3 {
// 便于維護每個狀態的這四個變數
public class Status {
public int lSum, rSum, mSum, iSum;
public Status(int lSum, int rSum, int mSum, int iSum) {
this.lSum = lSum;
this.rSum = rSum;
this.mSum = mSum;
this.iSum = iSum;
}
}
public int maxSubArray(int[] nums) {
return getInfo(nums, 0, nums.length - 1).mSum;
}
public Status getInfo(int[] nums, int l, int r) {
if (l == r) {
return new Status(nums[l], nums[l], nums[l], nums[l]);
}
int m = (r - l) / 2 + l;
Status lSub = getInfo(nums, l, m);
Status rSub = getInfo(nums, m + 1, r);
return pushUp(lSub, rSub);
}
// 合并
public Status pushUp(Status lSub, Status rSub) {
int iSum = lSub.iSum + rSub.iSum;
int lSum = Math.max(lSub.lSum, lSub.iSum + rSub.lSum);
int rSum = Math.max(rSub.rSum, lSub.rSum + rSub.iSum);
int mSum = Math.max(Math.max(lSub.mSum, rSub.mSum), lSub.rSum + rSub.lSum);
return new Status(lSum, rSum, mSum, iSum);
}
}
思路2（動態規劃）
可以得到動態規劃轉移方程\(f(i) = max(f(i - 1) + nums[i],nums[i])\) ，其中由于\(f(i)\)只和 \(f(i-1)\)有關，可以用一個變數pre去維護，
class Solution {
public int MaxSubArray(int[] nums){
int pre = 0;
int ans = nums[0];
for(int num : nums){
pre = Math.max(pre + num,num);
ans = Math.max(ans,pre);
}
return ans;
}
}
5.找到k個最小數
輸入整數陣列 arr，找出其中最小的 k 個數，
思路（分治/快速排序思想）
快排的劃分函式每次執行完后都會將陣列分為兩部分，小于分界值pivot的元素都會放在陣列左邊,而大于的則會放到陣列右邊，然后回傳分界值下標，而此處只需要處理劃分的其中一邊就可以了，
class Solution {
public int[] smallestK(int[] arr, int k) {
randomizedSelected(arr, 0, arr.length - 1, k);
int[] vec = new int[k];
for (int i = 0; i < k; ++i) {
vec[i] = arr[i];
}
return vec;
}
private void randomizedSelected(int[] arr, int l, int r, int k) {
if (l >= r) {
return;
}
int pos = randomizedPartition(arr, l, r);
int num = pos - l + 1;
if (k == num) {
return;
} else if (k < num) { //說明第k小的數在右側
randomizedSelected(arr, l, pos - 1, k);
} else { //說明在左側
randomizedSelected(arr, pos + 1, r, k - num);
}
}
// 基于隨機的劃分，使前k小的數在陣列左側
private int randomizedPartition(int[] nums, int l, int r) {
int i = new Random().nextInt(r - l + 1) + l;
swap(nums, r, i);
return partition(nums, l, r);
}
private int partition(int[] nums, int l, int r) {
int pivot = nums[r];
int i = l - 1;
for (int j = l; j <= r - 1; ++j) {
if (nums[j] <= pivot) {
i = i + 1;
swap(nums, i, j);
}
}
swap(nums, i + 1, r);
return i + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
6.尋找第k個最大元素
思路（分治/快排思想）
快排思想的劃分中，每一次劃分都使得左邊的元素小于等于a，而a右邊的元素都大于等于它，也就是每一次都能確認一個元素的最終位置，所以只需要某次劃分得到的a為倒數第k個下標的時候就能找到答案，
由此可以知道，我們只需要在劃分得到的a小于目標下標時劃分右區間，大于目標下標的時候劃分左區間，直到它等于目標下標即可，（引入隨機化是為了加速劃分的程序）
class Solution {
Random random = new Random();
public int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}
public int quickSelect(int[] a, int l, int r, int index) {
int q = randomPartition(a, l, r);
if (q == index) {
return a[q];
} else {
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}
}
public int randomPartition(int[] a, int l, int r) {
int i = random.nextInt(r - l + 1) + l;
swap(a, i, r);
return partition(a, l, r);
}
public int partition(int[] a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a, ++i, j);
}
}
swap(a, i + 1, r);
return i + 1;
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
7.找到k個最長重復字串
在一個字串 s 中找出 s 中的最長子串，且該字串的每一個字符出現次數都不少于 k，輸出該子串的長度，
思路
首先統計每個字符的出現次數，然后找到不滿足k次出現的字符作為劃分字符，然后逐步劃分統計長度
class Solution{
public int FindMaxSubString(String s,int k){
return divide(s,0,s.length() - 1,k);
}
public int divide(String s,int left,int right,int k){
int[] count = new int[26];
for(int i = left;i <= right;i++){
count[s.charAt(i) - 'a']++;
}
int splitchar= -1;
for(int i = 0;i < 26;i++){
if(count[i] > 0 && count[i] < k){
splitchar = i;
break;
}
}
if (splitchar == -1){
return right - left + 1;
}
int ans = 0;
int splitindex = left;
while(splitindex <= right){
//考慮到存在不滿足要求的字符放在left端的情況
while(splitindex <= right && (s.charAt(splitindex) - 'a') == splitchar){
splitindex++;
}
int start = splitindex;
while(splitindex <= right && (s.charAt(splitindex) - 'a') != splitchar){
splitindex++;
}
int length = divide(s,start,splitindex - 1,k);
ans = Math.max(ans,length);
}
return ans;
}
}
動態規劃
1.換硬幣
給定面值分別為2，5，7的硬幣，每種硬幣有無限個，給定一個N，求組成N最少需要的硬幣的數量，若無法組成則回傳-1.
思路
class Solution{
public int SwapCoins(int n) {
if(n <= 1 || n == 3) return -1;
if(n == 2) return 1;
int[] coins = {2,5,7};
int[] dp = new int[n + 1];
Arrays.fill(dp, n + 1);
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
dp[3] = 0;
for(int i = 4;i <= n;i++) {
for(int coin : coins) {
if(i >= coin && i - coin != 1 && i - coin != 3) {
dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
}
}
}
return dp[n];
}
}
進階版
給定不同面額的硬幣和一個總金額(面額、硬幣數、總金額均不超過 10)，寫出函式來計算可以湊成總金額的硬幣組合數，假設每一種面額的硬幣有無限個，
思路
其實思路是類似的，前一題是想要最少的硬幣數，所以對每一種硬幣都進行嘗試然后找到其中所需數量最少的那個，這一題因為要求的是組合數所以直接加上dp[i-coin]的數量就可以，
class Solution {
public int CoinsProblem(int sum, int[] coins) {
Arrays.sort(coins);
int[] dp = new int[sum + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= sum; i++) {
dp[i] += dp[i - coin];
}
}
return dp[sum];
}
}
2.走網格
m行n列的網格，從左上角（1，1）出發，每一步只能向下或者向右，問共有多少種方法可以走到右下角（m,n);
思路
對于最左邊的列以及最上面的行都只有一種方法
\(dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\)，而實際上每次都是依賴于\(dp[i - 1][j]\)或\(dp[i][j - 1]\)，所以可以將二維陣列優化為一維陣列
class Solution{
public int walkinggrids(int m,int n) {
int[] ans = new int[n];
Arrays.fill(ans, 1);
for(int i = 1;i < m;i++) {
for(int j = 1;j < n;j++) {
ans[j] += ans[j - 1];
}
}
return ans[n - 1];
}
}
進階版
m行n列的網格，從左上角出發，每一步只能向下或者向右，網格中有障礙物，障礙物用1表示，空位置用0表示，問共有多少種方法可以走到右下角（m,n);
思路
同上，但是遇到障礙物就置0，不用全部置1是因為在上一題，左上邊緣行列必然可行，而在此處不一定，
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[] ans = new int[n];
ans[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
for(int i = 0;i <m;i++){
for(int j = 0;j < n;j++){
if(obstacleGrid[i][j] == 1){
ans[j] = 0;
continue;
}
if(j >= 1 && obstacleGrid[i][j] == 0){
ans[j] += ans[j - 1];
}
}
}
return ans[n - 1];
}
}
3.爬樓梯
假設你正在爬樓梯，需要 n 階你才能到達樓頂，(n是正整數)每次你可以爬 1 或 2 個臺階，你有多少種不同的方法可以爬到樓頂呢？
思路
\(dp[i] = dp[i - 1] + dp[i - 2]\)
class Solution{
public int walkingstairs(int n) {
if(n <= 1) return 1;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i = 3;i <= n;i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
進階版：最小花費爬樓梯
給你一個整數陣列 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用，一旦你支付此費用，即可選擇向上爬一個或者兩個臺階，
你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯，
請你計算并回傳達到樓梯頂部的最低花費，
思路
class Solution {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 0;
for(int i = 2;i <= n;i++){
dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
}
4.背包問題
一個背包有一定的承重W，有N件物品，每件物品都有自己的價值，記錄在陣列V中，也都有自己的重量，記錄在陣列W中，每件物品只能選擇要裝入還是不裝入背包，要求在不超過背包承重的前提下，選出的物品總價值最大， 假設物品數量為4 背包承重為10 每個商品重量為7,3,4,5 價值為42,12,40,25
思路
\[dp[i][j] = \begin{cases} max(dp[i - 1][j - W[i]] + V[i],dp[i - 1][j])，如果放得下背包\\ dp[i - 1][j]，放不下背包 \end{cases} \]class Solution{
int[] W = {7,3,4,5};
int[] V = {42,12,40,25};
public int backetProblem(int n,int cap){
//列標代表容量 行標代表所選的物品
//該陣列存放的是當前選擇第i個物品時j承重的情況下所得到的最大價值
int[][] dp = new int[n][cap+1];
for(int i = 0;i < cap;i++){
if(i >= W[0]){
dp[0][i] = V[0];
}
}
for(int i = 1;i < n;i++){
for(int j = 1;j <= cap;j++){
if(j >= W[i]){
//放得下
dp[i][j] = Math.max(dp[i-1][j - W[i]] + V[i],dp[i-1][j]);//前者為選擇，后者為不選
}else{
//放不下
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n-1][cap];
}
}
5.最長回文子串
求一個字串中的最長的回文子串
思路
class Solution {
public String longsetPalindrome(String s) {
if (s.length() == 1)
return s;
// dp(i,j) = dp(i + 1,j - 1)
// dp[i][j] 代表s[i,j]是否為回文串
int len = s.length();
int maxlen = 1; // 最大回文串長度
int begin = 0; // 回文串起始位置
boolean[][] dp = new boolean[len][len];
// init dp 所有長度為1的子串都是回文串
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] chararray = s.toCharArray();
// 開始列舉子串長度
for (int L = 2; L <= len; L++) {
// 列舉左邊界
for (int i = 0; i < len; i++) {
// 右邊界可計算得出
int j = L + i - 1;
if (j >= len) // 以防越界
break;
if (chararray[i] != chararray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) { // 只有兩個字符
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && L > maxlen) {
maxlen = L;
begin = i;
}
}
}
return s.substring(begin, begin + maxlen);
}
}
6.最長公共子序列
給定兩個字串 text1 和 text2，回傳這兩個字串的最長 公共子序列 的長度，如果不存在 公共子序列 ，回傳 0
思路
從1開始防止越界
\[dp[i][j] = \begin{cases} dp[i - 1][j - 1] + 1,text_1[i - 1] = text_2[j - 1]\\ max(dp[i - 1][j],dp[i][j - 1]),text_1[i - 1] ≠ text_2[j - 1] \end{cases} \]
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length(), len2 = text2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
char c1 = text1.charAt(i - 1);
for (int j = 1; j <= len2; j++) {
char c2 = text2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[len1][len2];
}
}
7.打家劫舍
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警，
給定一個代表每個房屋存放金額的非負整數陣列，計算你 不觸動警報裝置的情況下 ，一夜之內能夠偷竊到的最高金額，
思路
\[dp[i] = max(dp[i - 1],dp[i - 2] + nums[i]) \]class Solution {
public int stolen(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];
}
}
進階版
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金，這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的，同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警
給定一個代表每個房屋存放金額的非負整數陣列，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額，
思路
同上題，但是要保證不能同時盜竊第一間房子和最后一間房子，
考慮分為兩種情況進行考慮，即分別對[0,n-1],[1,n]的房子進行考慮，也就是不偷第一件房子和不偷最后一間房子
class Solution {
public int rob(int[] nums) {
int length = nums.length;
if (length == 1) {
return nums[0];
} else if (length == 2) {
return Math.max(nums[0], nums[1]);
}
return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
}
public int robRange(int[] nums, int start, int end) {
int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
8.擺動序列
如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為 擺動序列 ，第一個差（如果存在的話）可能是正數或負數，僅有一個元素或者含兩個不等元素的序列也視作擺動序列，
- 例如， [1, 7, 4, 9, 2, 5] 是一個 擺動序列 ，因為差值 (6, -3, 5, -7, 3) 是正負交替出現的，
- 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最后一個差值為零， 子序列 可以通過從原始序列中洗掉一些（也可以不洗掉）元素來獲得，剩下的元素保持其原始順序，
給你一個整數陣列 nums ，回傳 nums 中作為 擺動序列 的 最長子序列的長度 ，
思路
可以分為上升擺動序列和下降擺動序列分別進行考慮
class Solution {
public int WiggleMaxLength(int[] nums) {
int n = nums.length;
if (n == 1)
return n;
int up = 1, down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = Math.max(down + 1, up);
} else if (nums[i] < nums[i - 1]) {
down = Math.max(up + 1, down);
}
}
return Math.max(up, down);
}
}
9.戳氣球
有 n 個氣球，編號為0 到 n - 1，每個氣球上都標有一個數字，這些數字存在陣列 nums 中，
現在要求你戳破所有的氣球，戳破第 i 個氣球，你可以獲得$ nums[i - 1]nums[i] nums[i + 1]$枚硬幣， 這里的 i - 1 和 i + 1 代表和 i 相鄰的兩個氣球的序號，如果 i - 1或 i + 1 超出了陣列的邊界，那么就當它是一個數字為 1 的氣球，
求所能獲得硬幣的最大數量
思路
可以觀察到戳氣球的操作會導致兩個氣球從不相鄰變成相鄰，因此倒過來看這些操作，就會變成每一次添加一個氣球
class Solution {
public int PokeBallon(int[] nums) {
int n = nums.length;
int[][] dp = new int[n + 2][n + 2];
int[] coins = new int[n + 2];
for (int i = 1; i <= n; i++) {
coins[i] = nums[i - 1];
}
coins[0] = coins[n + 1] = 1;
// 注意此處需要從下往上計算
// 因為所依賴的dp[k][j]在從上往下算的時候根本還沒參與計算
// i的變化程序可以視作氣球向左逐漸添加的程序
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 2; j <= n + 1; j++) {
for (int k = i + 1; k < j; k++) {
dp[i][j] = Math.max(dp[i][j], coins[i] * coins[k] * coins[j] + dp[i][k] + dp[k][j]);
}
}
}
return dp[0][n + 1];
}
}
貪心
一般來說都是做點排序，選擇當前看來最好的選擇，考慮的都是區域最優解
1.最長回文串
給定一個包含大寫字母和小寫字母的字串，找到通過這些字母構造成的最長的回文串，在構造程序中，請注意區分大小寫，比如 "Aa" 不能當做一個回文字串，解釋：第一個例子可以構成"dccaccd", 它的長度是 7，
- 字串的長度不會超過 1010
思路
先統計字串中所有字母的個數再進行選擇，只要大于1均可使用，等于1的只能使用一次，
class Solution {
public int longestPalindrome(String s) {
int ans = 0;
int[] hash = new int[52];
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c < 'a') {
hash[c - 'A']++;
} else {
hash[c - 'a' + 26]++;
}
}
Arrays.sort(hash);
for (int i = 51; i >= 0; i--) {
ans += hash[i] / 2 * 2;
if (hash[i] % 2 == 1 && ans % 2 == 0)
ans++;
}
return ans;
}
}
2.移掉K位數字
給你一個以字串表示的非負整數 num 和一個整數 k ，移除這個數中的 k 位數字，使得剩下的數字最小，請你以字串形式回傳這個最小的數字，
- 1 <= k <= num.length <= 1000
- num 僅由若干位數字（0 - 9）組成
- 除了 0 本身之外，num 不含任何前導零
思路
主要目的就是保證左邊的數都是最小的數，所以考慮用堆疊結構去進行維護（先進后出，每次都與左邊的資料比較把相對最小的留下來），但是記住堆疊結構存盤的資料輸出時是倒序的要轉換過來，
class Solution {
public String removeKNum(String num, int k) {
// 保證左邊的數都是最小的數
int length = num.length();
StringBuilder ans = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < length; i++) {
char digit = num.charAt(i);
while (!stack.isEmpty() && k > 0 && digit < stack.peek()) {
stack.pop();
k--;
}
stack.push(digit);
}
while (k-- > 0) {
stack.pop();
}
int n = stack.size();
ans.setLength(n);
for (int i = n - 1; i >= 0; i--) {
char digit = stack.pop();
ans.setCharAt(i, digit);
}
int i = 0;
while (ans.length() != 0 && ans.charAt(i) == '0') {
ans.deleteCharAt(i);
}
return ans.length() == 0 ? "0" : ans.toString();
}
}
3.盛最多的水
給你 n 個非負整數 a1，a2，...，an，每個數代表坐標中的一個點 (i, ai) ，在坐標內畫 n 條垂直線，垂直線 i 的兩個端點分別為 (i, ai) 和 (i, 0) ，找出其中的兩條線，使得它們與 x 軸共同構成的容器可以容納最多的水，
說明：你不能傾斜容器，
思路
用雙指標，在左右兩邊每次都取最長的那個柱子逐漸往中間縮，取計算程序中的最大值，
lass Solution{
public int MaxWater(int[] nums){
int ans = 0;
int left = 0;
int right = nums.length - 1;
while(left < right){
int v = Math.min(nums[left],nums[right]) * (right - left);
ans = Math.max(ans,v);
if(nums[left] > nums[right]){
right--;
}else{
left++;
}
}
return ans;
}
}
4.分發糖果
n 個孩子站成一排，給你一個整數陣列 ratings 表示每個孩子的評分， 你需要按照以下要求，給這些孩子分發糖果：
- 每個孩子至少分配到 1 個糖果，
- 相鄰的孩子中，評分高的孩子必須獲得更多的糖果，
請你給每個孩子分發糖果，計算并回傳需要準備的最少糖果數目 ，
思路
先從左到右遍歷一遍，處理應該比自己左邊的孩子多一顆糖果的情況
再從右到左遍歷一遍，處理右邊的孩子的情況
class Solution {
public int PartitionCandys(int[] ratings) {
int ans = 0;
int n = ratings.length;
int[] left = new int[n];
left[0] = 1;
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
} else {
left[i] = 1;
}
}
int right = 1;
ans += Math.max(left[n - 1], right);
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
right++;
} else {
right = 1;
}
ans += Math.max(left[i], right);
}
return ans;
}
}
5.跳躍游戲
給定一個非負整數陣列 nums ，你最初位于陣列的 第一個下標 ，
陣列中的每個元素代表你在該位置可以跳躍的最大長度
判斷你是否能夠到達最后一個下標，
思路
每次都取自己能跳到的最遠距離
class Solution {
public boolean JumpGame(int[] nums) {
int k = 0;
for (int i = 0; i < nums.length; i++) {
if (i > k)
return false;
k = Math.max(k, i + nums[i]);
}
return true;
}
}
進階版
在上面的基礎上回傳跳到最后一個下標時的最小跳躍次數，但是保證一定可以跳到最后的位置
思路
正向查找可以到達的最大位置（也可以反向查找離終點最遠的那個作為出發位置，這里不給出）
class Solution {
public int jump(int[] nums) {
int length = nums.length;
int end = 0;
int maxPosition = 0;
int steps = 0;
for (int i = 0; i < length - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
steps++;
}
}
return steps;
}
}
回溯
- 針對所給問題定義解空間
- 確定易于搜索的解空間結構
- 以深度優先搜索的方式搜索解空間，中間可以用剪枝函式避免無效搜索
1.括號生成
數字 n 代表生成括號的對數，請你設計一個函式，用于能夠生成所有可能的并且 有效的 括號組合，
有效括號組合需滿足：左括號必須以正確的順序閉合，
提示：
-
1 <= n <= 8
-
請按照括號生成的層數有大到小排序，如輸入3時，先生成((()))，最后再生成 ()()()
思路
class Solution {
// 1.(始終在左邊，同理右邊必須有）
// 2.出現）時，（的數量大于等于）
// 3.使用回溯法務必記住在遞回后將自己執行的操作撤回，如這里的deletecharat
List<String> ans = new ArrayList<>();
StringBuilder element = new StringBuilder();
public List<String> GenenrateParantheses(int n) {
back_tracking(0, 0, 0, n);
return ans;
}
public void back_tracking(int numsleft, int numsright, int index, int n) {
// numsleft:(的數量
// numsright:)的數量
// index:當前字串的字符數
// n:上限
if (index == 2 * n) {
ans.add(element.toString());
return;
}
if (numsleft < n) {
element.append("(");
back_tracking(numsleft + 1, numsright, index + 1, n);
element.deleteCharAt(element.length() - 1);
}
if (numsright < n && numsright < numsleft) {
element.append(")");
back_tracking(numsleft, numsright + 1, index + 1, n);
element.deleteCharAt(element.length() - 1);
}
}
}
2.組合問題
給定兩個整數 n 和 k，回傳范圍 [1, n] 中所有可能的 k 個數的組合，
你需要按順序回傳答案，
思路
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> element = new ArrayList<>();
public List<List<Integer>> Combine(int n, int k) {
back_tracking(n, k, 1);
return ans;
}
public void back_tracking(int n, int k, int startindex) {
if (element.size() == k) {
ans.add(new ArrayList<>(element)); // 拷貝
return;
}
// 剪枝版本
// 剪枝原理為如果還沒選中的長度為x，已選中的為y，若x+y<k則沒有繼續往下探查的必要
for (int i = startindex; i <= n - (k - element.size()) + 1; i++) {
element.add(i);
back_tracking(n, k, i + 1);
element.remove(element.size() - 1);
}
// 無剪枝版本
// for (int i = startindex; i <= n; i++) {
// element.add(i);
// back_tracking(n, k, i + 1);
// element.remove(element.size() - 1);
// }
}
}
進階：全排列
給定一個不含重復數字的陣列 nums ，回傳其 所有可能的全排列 ，你可以 按任意順序 回傳答案，
思路
在組合的基礎上建立一個 visited 陣列用以標記是否已經填入這個數字
class Solution {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> element = new ArrayList<Integer>();
public List<List<Integer>> permute(int[] nums) {
int[] visited = new int[nums.length];
backtracking(nums,visited);
return result;
}
public void backtracking(int[] nums,int[] visited){
if(element.size() == nums.length){
result.add(new ArrayList<Integer>(element));
return;
}
for(int i=0;i<nums.length;i++){
if(visited[i] == 1) continue;
element.add(nums[i]);
visited[i] = 1;
backtracking(nums,visited);
visited[i] = 0;
element.remove(element.size() - 1);
}
}
}
進階：全排列II
給定一個可包含重復數字的序列 nums ，按任意順序 回傳所有不重復的全排列，
思路
先排序，這樣相同數字就會被歸到一起，然后在全排列的基礎上判斷當前數字是否等于上一個數字并且是否被選擇
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> element = new ArrayList<Integer>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
int[] visited = new int[nums.length];
backtracking(nums,visited);
return ans;
}
public void backtracking(int[] nums,int[] visited){
if(element.size() == nums.length){
ans.add(new ArrayList<Integer>(element));
return;
}
for(int i=0;i<nums.length;i++){
if(visited[i] == 1 || (i > 0 && nums[i-1] == nums[i] && visited[i - 1] == 0)) continue;
element.add(nums[i]);
visited[i] = 1;
backtracking(nums,visited);
visited[i] = 0;
element.remove(element.size() - 1);
}
}
}
進階：組合總和
給你一個 無重復元素 的整數陣列 candidates 和一個目標整數 target ，找出 candidates 中可以使數字和為目標數 target 的 所有 不同組合 ，并以串列形式回傳，你可以按 任意順序 回傳這些組合，
candidates 中的 同一個 數字可以 無限制重復被選取 ，如果至少一個數字的被選數量不同，則兩種組合是不同的，
對于給定的輸入，保證和為 target 的不同組合數少于 150 個
思路
類似全排列，但是這里由于可以重復選擇，因此不需要visited陣列
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> element = new ArrayList<Integer>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
back_tracking(candidates,target,0);
return ans;
}
public void back_tracking(int[] nums,int diff,int begin){
if(diff == 0){
ans.add(new ArrayList<>(element));
return;
}
for(int i = begin;i < nums.length;i++){
if(diff < nums[i]) break; //剪枝，如果當前值大于差值就不必選擇了
element.add(nums[i]);
back_tracking(nums,diff - nums[i],i);
element.remove(element.size() - 1);
}
}
}
進階：優美的排列
假設有從 1 到 n 的 n 個整數，用這些整數構造一個陣列 perm（下標從 1 開始），只要滿足下述條件 之一 ，該陣列就是一個 優美的排列 ：
- perm[i] 能夠被 i 整除
- i 能夠被 perm[i] 整除
給你一個整數 n ，回傳可以構造的 優美排列 的 數量
思路
在排列的基礎上判斷當前數字是否可以被整除
class Solution {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> element = new ArrayList<Integer>();
int[] perm;
public int BeautyArrange(int n) {
perm = new int[n + 1];
boolean[] visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
perm[i] = i;
}
back_tracking(n, visited);
return ans.size();
}
public void back_tracking(int n, boolean[] visited) {
if (element.size() == n) {
ans.add(new ArrayList<>(element));
return;
}
for (int i = 1; i <= n; i++) {
if (visited[i]) {
continue;
} else {
int k = element.size() + 1;
if (perm[i] % k == 0 || k % perm[i] == 0) {
element.add(k);
visited[i] = true;
back_tracking(n, visited);
element.remove(element.size() - 1);
visited[i] = false;
}
}
}
}
}
3.找出所有子集的異或總和再求和
一個陣列的 異或總和 定義為陣列中所有元素按位 XOR 的結果；如果陣列為 空 ，則異或總和為 0 ，
例如，陣列 [2,5,6] 的 異或總和 為 2 XOR 5 XOR 6 = 1 ， 給你一個陣列 nums ，請你求出 nums 中每個 子集 的 異或總和 ，計算并回傳這些值相加之 和 ，
注意：在本題中，元素 相同 的不同子集應 多次 計數，
陣列 a 是陣列 b 的一個 子集 的前提條件是：從 b 洗掉幾個（也可能不洗掉）元素能夠得到 a ，
思路
分兩種情況回溯，分別是選擇當前數字ornot
class Solution {
Integer ans = 0;
public Integer SumXorSubset(int[] nums) {
back_tracking(nums, 0, 0);
return ans;
}
public void back_tracking(int[] nums, int val, int idx) {
if (idx == nums.length) {
ans += val;
return;
}
back_tracking(nums, val ^ nums[idx], idx + 1); // 選擇當前數字
back_tracking(nums, val, idx + 1); // 不選擇當前數字
}
}
4.分割回文串
給你一個字串 s，請你將 s 分割成一些子串，使每個子串都是 回文串 ，回傳 s 所有可能的分割方案，
回文串 是正著讀和反著讀都一樣的字串，
思路
先判斷該字串是不是回文串，如果是回文串再對其進行分割
class Solution {
boolean[][] isPalindrome;
List<List<String>> ans = new ArrayList<List<String>>();
List<String> element = new ArrayList<String>();
int n;
public List<List<String>> SplitPalindrome(String s) {
// 先判斷回文串在進行分割
n = s.length();
isPalindrome = new boolean[n][n];
for (int i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
for (int L = 2; L <= n; L++) {
for (int i = 0; i < n; i++) {
int j = L + i - 1;
if (j >= n)
break;
if (s.charAt(i) != s.charAt(j)) {
isPalindrome[i][j] = false;
} else {
if (j - i < 3) {
isPalindrome[i][j] = true;
} else {
isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
}
}
}
}
back_tracking(s, 0);
return ans;
}
public void back_tracking(String s, int start) {
if (start == s.length()) {
ans.add(new ArrayList<String>(element));
}
for (int i = start; i < n; i++) {
if (isPalindrome[start][i]) {
element.add(s.substring(start, i + 1));
back_tracking(s, i + 1);
element.remove(element.size() - 1);
}
}
}
}
5.電話號碼字母組合
給定一個僅包含數字 2-9 的字串，回傳所有它能表示的字母組合，答案按字母順序回傳，
給出數字到字母的映射如下（與電話按鍵相同），注意 1 不對應任何字母，
思路
class Solution {
List<String> ans = new ArrayList<>();
StringBuffer element = new StringBuffer();
String[] number = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public List<String> PhoneLetterCombination(String s) {
if (s.length() == 0)
return ans;
back_tracking(s, 0);
return ans;
}
public void back_tracking(String s, int index) {
if (index == s.length()) {
ans.add(element.toString());
return;
}
String digitletters = number[s.charAt(index) - '2'];
for (int i = 0; i < digitletters.length(); i++) {
element.append(digitletters.charAt(i));
back_tracking(s, index + 1);
element.deleteCharAt(element.length() - 1);
}
}
}
6.大禮包
在商店中， 有 n 件在售的物品，每件物品都有對應的價格，然而，也有一些大禮包，每個大禮包以優惠的價格捆綁銷售一組物品，
給你一個整數陣列 price 表示物品價格，其中 price[i] 是第 i 件物品的價格，另有一個整數陣列 needs 表示購物清單，其中 needs[i] 是需要購買第 i 件物品的數量，
還有一個陣列 special 表示大禮包，special[i] 的長度為 n + 1 ，其中 special[i][j] 表示第 i 個大禮包中內含第 j 件物品的數量，且 special[i][n] （也就是陣列中的最后一個整數）為第 i 個大禮包的價格，
回傳 確切 滿足購物清單所需花費的最低價格，你可以充分利用大禮包的優惠活動，你不能購買超出購物清單指定數量的物品，即使那樣會降低整體價格，任意大禮包可無限次購買，
思路
先過濾掉沒用的禮包，然后再對滿足條件的禮包回溯選擇，對符合要求的組合進行計算選擇最小的那個
class Solution {
int ans;
int[] buy;
public int BigPresent(int[] price, int[][] special, int[] need, int n) {
buy = new int[price.length];
for (int i = 0; i < price.length; i++) {
ans += price[i] * need[i];
}
// 過濾掉無用的大禮包
List<int[]> filterspecial = new ArrayList<int[]>();
for (int[] sp : special) {
int totalCount = 0, totalPrice = 0;
boolean isadd = true;
for (int i = 0; i < price.length; i++) {
if (sp[i] > need[i]) { // 禮包本身所含的東西已經大于了的話就沒有必要
isadd = false;
break;
}
totalCount += sp[i];
totalPrice += price[i] * sp[i];
}
if (isadd && totalCount > 0 && totalPrice > sp[price.length]) { // 如果夠優惠的話則可以選擇
filterspecial.add(sp);
}
}
if (filterspecial.size() == 0)
return ans;
back_tracking(price, filterspecial, need, 0, 0);
return ans;
}
public void back_tracking(int[] price, List<int[]> special, int[] need, int money, int idx) {
if (idx == special.size()) { // 遍歷完禮包后判斷是否值得
int extra = 0;
for (int i = 0; i < need.length; i++) {
extra += (need[i] - buy[i]) * price[i];
}
ans = Math.min(ans, money + extra);
return;
}
for (int i = idx; i <= special.size(); i++) {
int j = 0;
for (; j < need.length && i < special.size(); j++) { // 判斷該禮包是否可以選擇
if (buy[j] + special.get(i)[j] > need[j]) {
break;
}
}
if (j == need.length || i == special.size()) { // 已經確認可以購買或是已經遍歷完可以選擇的禮包
for (j = 0; j < need.length && i < special.size(); j++) { // 購買
buy[j] += special.get(i)[j];
}
if (i < special.size()) {
money += special.get(i)[need.length]; // 付錢
}
back_tracking(price, special, need, money, i); // 遞回
for (j = 0; j < need.length && i < special.size(); j++) {
buy[j] -= special.get(i)[j]; // 回溯退貨
}
if (i < special.size()) {
money -= special.get(i)[need.length]; // 回溯退款
}
}
}
}
}
7.分K個等和子串
Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.
思路
先找到目標值，如果不能整除k就沒有意義，再對目標值進行回溯選擇，這里相當于分配k個桶，然后將數字裝到桶中直到剛好裝滿，所有數字能夠全部裝完就是符合條件，
class Solution {
int n;
int target;
public boolean KEqualSumSubset(int[] nums, int k) {
int sum = 0;
n = nums.length;
for (int i = 0; i < n; i++) {
sum += nums[i];
}
if (sum % k != 0) // 如果不等于0說明沒辦法整除
return false;
// 降序排列，讓值大的先進行選擇，加快速度
Arrays.sort(nums);
int left = 0, right = nums.length - 1;
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
target = sum / k;
int[] subsets = new int[k];
return back_tracking(nums, subsets, 0, k);
}
public boolean back_tracking(int[] nums, int[] subsets, int index, int k) {
if (index == nums.length) {
return true;
}
for (int i = 0; i < k; i++) {
if (i > 0 && subsets[i] == subsets[i - 1]) // 剪枝：第一個數字可以直接放進去，而相同的子集效果相同可以跳過
continue;
if (subsets[i] + nums[index] > target)
continue;
subsets[i] += nums[index];
if (back_tracking(nums, subsets, index + 1, k))
return true;
subsets[i] -= nums[index];
}
return false;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/546911.html
標籤：Java
下一篇：學習筆記——Python基礎