必须引入的包java.util.*
int[] nums = list.stream().mapToInt(Integer::intValue).toArray();
public static void main(String[] args) {
Solution solution = new Solution();
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
String[] data = input.split(" ");
int[] nums = new int[data.length];
for (int i = 0; i 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> sets=maps.entrySet();
for(Map.Entry entry:sets){
System.out.println("key="+entry.getKey()+"value="+entry.getValue());
}
将一个复杂的问题分割成规模较小的相同问题，以便各个击破。
给定一个不含重复元素的整数数组 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 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 ");
}
}
}
思路
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 给定一个大小为 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 思路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 给定一个整数数组 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;
}
}
输入整数数组 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 = r) {
return;
}
int pos = randomizedPartition(arr, l, r);
int num = pos - l + 1;
if (k == num) {
return;
} else if (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 在一个字符串 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 0 && count[i] 给定面值分别为2，5，7的硬币，每种硬币有无限个，给定一个N，求组成N最少需要的硬币的数量，若无法组成则返回-1.
思路
class Solution{
public int SwapCoins(int n) {
if(n = 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 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行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 = 1 && obstacleGrid[i][j] == 0){
ans[j] += ans[j - 1];
}
}
}
return ans[n - 1];
}
}
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。(n是正整数)每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
思路
(dp[i] = dp[i - 1] + dp[i - 2])
class Solution{
public int walkingstairs(int n) {
if(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 一个背包有一定的承重W，有N件物品，每件物品都有自己的价值，记录在数组V中，也都有自己的重量，记录在数组W中，每件物品只能选择要装入还是不装入背包，要求在不超过背包承重的前提下，选出的物品总价值最大。 假设物品数量为4 背包承重为10 每个商品重量为7,3,4,5 价值为42,12,40,25
思路
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 = W[0]){
dp[0][i] = V[0];
}
}
for(int i = 1;i = 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];
}
}
求一个字符串中的最长的回文子串
思路
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) // 以防越界
break;
if (chararray[i] != chararray[j]) {
dp[i][j] = false;
} else {
if (j - i maxlen) {
maxlen = L;
begin = i;
}
}
}
return s.substring(begin, begin + maxlen);
}
}
给定两个字符串 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 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
思路
[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 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
思路
同上题，但是要保证不能同时盗窃第一间房子和最后一间房子。
考虑分为两种情况进行考虑，即分别对[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 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
给你一个整数数组 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 nums[i - 1]) {
up = Math.max(down + 1, up);
} else if (nums[i] 有 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 = 0; i--) {
for (int j = i + 2; j 一般来说都是做点排序，选择当前看来最好的选择，考虑的都是局部最优解
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。解释：第一个例子可以构成"dccaccd", 它的长度是 7。
思路
先统计字符串中所有字母的个数再进行选择，只要大于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 = 0; i--) {
ans += hash[i] / 2 * 2;
if (hash[i] % 2 == 1 && ans % 2 == 0)
ans++;
}
return ans;
}
}
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
思路
主要目的就是保证左边的数都是最小的数，所以考虑用栈结构去进行维护（先进后出，每次都与左边的数据比较把相对最小的留下来）。但是记住栈结构存储的数据输出时是倒序的要转换过来。
class Solution {
public String removeKNum(String num, int k) {
// 保证左边的数都是最小的数
int length = num.length();
StringBuilder ans = new StringBuilder();
Stack stack = new Stack();
for (int i = 0; i 0 && digit 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();
}
}
给你 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 nums[right]){
right--;
}else{
left++;
}
}
return ans;
}
}
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求，给这些孩子分发糖果：
请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目 。
思路
先从左到右遍历一遍，处理应该比自己左边的孩子多一颗糖果的情况
再从右到左遍历一遍，处理右边的孩子的情况
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 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;
}
}
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度
判断你是否能够到达最后一个下标。
思路
每次都取自己能跳到的最远距离
class Solution {
public boolean JumpGame(int[] nums) {
int k = 0;
for (int i = 0; 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 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
提示：
1
请按照括号生成的层数有大到小排序，如输入3时，先生成((()))，最后再生成 ()()()
思路
class Solution {
// 1.(始终在左边，同理右边必须有）
// 2.出现）时，（的数量大于等于）
// 3.使用回溯法务必记住在递归后将自己执行的操作撤回，如这里的deletecharat
List ans = new ArrayList();
StringBuilder element = new StringBuilder();
public List 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 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你需要按顺序返回答案。
思路
class Solution {
List> ans = new ArrayList();
List element = new ArrayList();
public List> 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
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
思路
在组合的基础上建立一个 visited 数组用以标记是否已经填入这个数字
class Solution {
List> result = new ArrayList>();
List element = new ArrayList();
public List> 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(element));
return;
}
for(int i=0;i
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
思路
先排序，这样相同数字就会被归到一起，然后在全排列的基础上判断当前数字是否等于上一个数字并且是否被选择
class Solution {
List> ans = new ArrayList>();
List element = new ArrayList();
public List> 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(element));
return;
}
for(int i=0;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> ans = new ArrayList>();
List element = new ArrayList();
public List> 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
假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
给你一个整数 n ，返回可以构造的 优美排列 的 数量
思路
在排列的基础上判断当前数字是否可以被整除
class Solution {
List> ans = new ArrayList>();
List element = new ArrayList();
int[] perm;
public int BeautyArrange(int n) {
perm = new int[n + 1];
boolean[] visited = new boolean[n + 1];
for (int i = 1; i (element));
return;
}
for (int i = 1; i
一个数组的 异或总和 定义为数组中所有元素按位 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); // 不选择当前数字
}
}
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
思路
先判断该字符串是不是回文串，如果是回文串再对其进行分割
class Solution {
boolean[][] isPalindrome;
List> ans = new ArrayList>();
List element = new ArrayList();
int n;
public List> SplitPalindrome(String s) {
// 先判断回文串在进行分割
n = s.length();
isPalindrome = new boolean[n][n];
for (int i = 0; i = n)
break;
if (s.charAt(i) != s.charAt(j)) {
isPalindrome[i][j] = false;
} else {
if (j - i (element));
}
for (int i = start; i
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案按字母顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
思路
class Solution {
List ans = new ArrayList();
StringBuffer element = new StringBuffer();
String[] number = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
public List 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 在商店中， 有 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 filterspecial = new ArrayList();
for (int[] sp : special) {
int totalCount = 0, totalPrice = 0;
boolean isadd = true;
for (int i = 0; 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 special, int[] need, int money, int idx) {
if (idx == special.size()) { // 遍历完礼包后判断是否值得
int extra = 0;
for (int i = 0; i need[j]) {
break;
}
}
if (j == need.length || i == special.size()) { // 已经确认可以购买或是已经遍历完可以选择的礼包
for (j = 0; j 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 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;
}
}
登录查看全部
参与评论
手机查看
返回顶部