- 划分为k个相等的子集
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入：nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出：True
说明：有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
注意:
1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
思路：首先判断不可能的条件：
1.当数组中的数不能等分为K个非空子集 也就是数组中各元素和取余K不为0时，不可能
2.如果可以均分还要判断数组中最大的那个数是否大于各元素和取余K的值 如果大于很明显也不能均分
判断完毕后就要通过递归函数来开始划分K个相等的子集
思路就是建立长度为K的桶，每个桶中事先放入均分计算得到的元素值，然后每次向桶中放入新的元素时减去新元素的值，并判断相减之后的值是否大于数组由小到大排序后的第一个值也就是最小值，如果大于就说明可以继续放下一个数。再通过该递归函数判断下一个数可不可以放到该桶中（有可能由于下一个数过大而无法放入，那么这时就得向前挪移一个单元试试比他小的数可不可以放入桶中） 就这样依次递归下去 直到这个桶完全放满为止。然后再放下一个桶，直到所有的元素都放入了桶中，就说明可以把这个数组分成K个非空子集，其总和都相等。
源代码如下：
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
//因为题目限制条件不用担心溢出
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
}
if(sum % k != 0){
return false;
}
//求出子集的和
sum = sum / k;
//排序 小的放最前面大的放最后面
Arrays.sort(nums);
//如果子集的和小于数组最大的直接返回false
if(nums[nums.length - 1] > sum){
return false;
}
//建立一个长度为k的桶
int[] arr = new int[k];
//桶的每一个值都是子集的和
Arrays.fill(arr, sum);
//从数组最后一个数开始进行递归
return help(nums, nums.length - 1, arr, k);
}
boolean help(int[] nums, int cur, int[] arr, int k){
//已经遍历到了-1说明前面的所有数都正好可以放入桶里，那所有桶的值此时都为0，说明找到了结果，返回true
if(cur < 0){
return true;
}
//遍历k个桶
for(int i = 0; i < k; i++){
//如果正好能放下当前的数或者放下当前的数后，还有机会继续放前面的数（剪枝）
if(arr[i] == nums[cur] || (cur > 0 && arr[i] - nums[cur] >= nums[0])){
//放当前的数到桶i里
arr[i] -= nums[cur];
//开始放下一个数
if(help(nums, cur - 1, arr, k)){
return true;
}
//这个数不该放在桶i中
//从桶中拿回当前的数
arr[i] += nums[cur];
}
}
return false;
}
}
- 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
方法1：暴力解法 也就是我第一时间想到的解法，结果，emmmm 超时了
思路就是遍历每一种组成字符串的可能，然后将每一次遍历到的字符串进行反转再比较看是否相等。
特殊情况的字符串总长度为0和为1时，直接返回该字符串即可
源代码如下：
class Solution {
public:
string longestPalindrome(string s) {
int num[2000] = {0};
int q = 0;
string lastStr;
string finalStr;
if (s.length() == 0 || s.length() == 1) {
return s;
}
for (int i = 0; i < s.length()-1; i++) {
string str;
str += s[i];
for (int j = i+1; j < s.length(); j++) {
str += s[j];
//逆序
string rStr(str.rbegin(), str.rend());
if (str == rStr) {
num[q] = j - i + 1;
}
}
if (num[q] != 0) {
finalStr = s.substr(i, num[q]);
}
if (finalStr.length() > lastStr.length()) {
lastStr = finalStr;
}
q++;
}
if (lastStr.length() == 0) {
//substr 提取指定位置的str字符串
return s.substr(0,1);
}
return lastStr;
}
};
但上面这样做是超时的！虽然解法正确 所以就得用新的方法——动态规划
动态规划的思路比较巧妙
类似于中心扩散法，首先想想，作为回文串，他的首尾两个字符应该相等，那么再左右都向里压缩一个字符单位，那么如果压缩后剩余的字符单位数量大于1，则这两个字符单位也相等，然后继续左右压缩。如果压缩后剩余字符单位为1 那么该串必为回文串
所以动态规划的解题步骤：
1.定义一个二维数组bool dp[len-1][len-1]来记录遍历字符串所得的状态，dp[l][r]为true表示从l到r的子串为回文串，false表示不是回文串
2.初始化二维数组，单个字符为回文串，所以定义dp[i][i] = true
3.找到状态转移方程，dp[l][r] = (s[r]==s[l] && (r-l==1 || dp[l+1][r-1])) ? true : false
源代码如下:
class Solution {
public:
string longestPalindrome(string s) {
int len = s.length();
if (len == 0)
return s;
bool dp[len][len];
int start = 0, end = 0;
for (int i = 0; i < len; i++)
dp[i][i] = true;
for (int r = 1; r < len; r++)
for (int l = 0; l < r; l++)
if (s[r]==s[l] && (r-l==1 || dp[l+1][r-1])) {
dp[l][r] = true;
if (r-l > end-start) {
start = l; end = r;
}
continue;
}else
dp[l][r] = false;
return s.substr(start, end-start+1);
}
};
- 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
这道题其实很简单，是我一开始用惯性思维想复杂了...
思路就是通过动态规划先得出每一步之后现在位置上的和，这个和是之前走的位置上数字的所有和加上现在位置上的数字。
至于怎么判断下一步是走右边还是走下边，那么就得每走一步，都要判断该位置右边和下边的数哪个小，然后走小的那个。
那么边界问题怎么解决呢？一共有四种情况
首先一个就是如果现在的位置有左边界，那么上一个位置只能从上面来，
即为当i !- 0 j = 0 时 dp[i][j] = dp[i-1][j] + dp[i][j];
如果现在的位置有上边界，那么上一个位置只能从左边来，
即为当i = 0 j != 0 时 dp[i][j] = dp[i][j-1] + dp[i][j];
如果现在的位置既没有左边的边界，也没有上边的边界时，
即为当i !- 0 j != 0 时 dp[i][j] = dp[i][j] + math.min(dp[i-1][j], dp[i][j-1]);
最后一种情况显而易见，不做讨论
下面 源代码如下:
很简单 也容易理解
class Solution {
public int minPathSum(int[][] grid) {
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(i == 0 && j == 0) continue;
else if(i == 0) grid[i][j] = grid[i][j - 1] + grid[i][j];
else if(j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j];
else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
}
网友评论