698. 划分为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) <= 160 < nums[i] < 10000
使用dfs 注意剪枝 优化，避免访问不必要的节点
class Solution {
public:
bool dfs(vector<int>& nums,vector<bool>& flag,int subsum,int target,int k,int cnt,int start){
if(cnt == k) return true;
if(subsum == target) {
return dfs(nums,flag,0,target,k,cnt+1,0);
}
if(subsum < target){
for(int i =start;i<nums.size();i++) {
if (flag[i] == false) {
flag[i] = true;
if(dfs(nums, flag, subsum + nums[i], target, k, cnt, i + 1))
return true;
flag[i] = false;
}
}
}
return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = 0;
for(auto i:nums)
sum+=i;
if(sum%k != 0) return false;
int target = sum/k;
// 从大到小排序，可以减少很多不必要的组合，因为全是正数
sort(nums.begin(), nums.end(), greater<int>());
if(nums[0] > target) return false;
vector<bool> flag(nums.size(), false);
return dfs(nums,flag,0,target,k,0,0);
}
};
/* 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; } */
130. 被围绕的区域
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：
X X X X
X X X X
X X X X
X O X X
解释:
被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
所以只需要利用BFS找到所有与边界O相连的O即可，没有与边界O相连的全部置为X
class Solution {
public:
typedef pair<int,int> P;
void bfs(vector<vector<char>>& grid,int x,int y,int rows,int cols){
queue<P> mq;
mq.push(P(x,y));
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
while(!mq.empty()){
x = mq.front().first;
y = mq.front().second;
mq.pop();
for(int i=0;i<4;i++){
int newx = x+dx[i];
int newy = y+dy[i];
if(newx>=0 && newx<rows && newy>=0 && newy<cols && grid[newx][newy] == 'O'){
grid[newx][newy] = '-';
mq.push(P(newx,newy));
}
}
}
}
void solve(vector<vector<char>>& board) {
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if((i==0 || i==board.size()-1 || j==0 || j==board[0].size()-1) && board[i][j]=='O'){
bfs(board,i,j,board.size(),board[0].size());
board[i][j] = '-';
}
}
}
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if(board[i][j] == 'O')
board[i][j] = 'X';
else if(board[i][j] == '-')
board[i][j] = 'O';
}
}
}
};
137 只出现一次的数字II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
首先每一个整数都可以用32位的二进制进行表示，然后统计每个位上1的个数，然后找对k取余的位即可，k==3，然后将所有的1位组合起来即可，使用一个32位的数组存储对应位的1/0；
假如例子是 1 2 6 1 1 2 2 3 3 3, 3 个 1, 3 个 2, 3 个 3,1 个 6
1 0 0 1
2 0 1 0
6 1 1 0
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1
3 0 1 1
3 0 1 1
看最右边的一列 1001100111 有 6 个 1
再往前看一列 0110011111 有 7 个 1
再往前看一列 0010000 有 1 个 1
我们只需要把是 3 的倍数的对应列写 0，不是 3 的倍数的对应列写 1
也就是 1 1 0,也就是 6。
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> bits(32,0);
int ans = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < nums.size(); j++)
bits[i] += (nums[j]>>i) & 1;
ans |= (bits[i] % 3) << i;
}
return ans;
}
};
473
class Solution {
public:
bool makesquare(vector<int>& nums) {
int sum = 0;
if(nums.size()<4) return false;
for(auto i:nums)
sum+=i;
if(sum%4!=0) return false;
int target = sum/4;
sort(nums.begin(),nums.end(),greater<int>());
if(nums[0] > target) return false;
vector<bool> flag(nums.size(),false);
vector<int> sums(4,0);
return dfs2(nums,sums,target,0);
// return dfs(nums,flag,target,0,0,0);
}
bool dfs2(vector<int>& nums,vector<int>& sums,int target,int start){
// 搜索完了即火柴全部放入桶中，成功
if(start == nums.size()) return true;
// 尝试把火柴放入4个桶中
for(int j=0;j<4;j++){
if(sums[j] + nums[start] <= target){
// 这里有一个非常重要的剪枝过程，即前一个桶和当前桶火柴数一致时，可以直接跳过，因为对于1根火柴来讲，两个桶如果当前大小一样，再放入时是没有区别的，而前面那个桶放入失败，则如果重新放入也肯定失败，故可以直接跳过，实测效率可以提高几十倍
if(j==0 || sums[j] != sums[j-1]){
//在当前桶放入火柴 并开始下一轮递归 开始放入下一根火柴
sums[j] += nums[start];
if(dfs2(nums,sums,target,start+1))
return true;
// 放入失败，取出火彩并尝试下一个桶
sums[j] -= nums[start];
}
}
}
// 四个桶都不能放火柴时既需要回溯，体现在上述过程中的取出操作
return false;
}
bool dfs(vector<int>& nums,vector<bool>& flag,int target,int start,int subsum,int cnt){
if(cnt==4) return true;
if(subsum == target) return dfs(nums,flag,target,0,0,cnt+1);
if(subsum<target){
for(int i=start;i<nums.size();i++){
if(flag[i] == false)
{
flag[i] = true;
if(dfs(nums,flag,target,i+1,subsum+nums[i],cnt))
return true;
flag[i] = false;
}
}
}
return false;
}
};
class Solution {
public:
vector<vector<int>> res;
set<vector<int>> ans;
vector<vector<int>> findSubsequences(vector<int>& nums) {
if(nums.size() <= 1) return res;
vector<int> tmp;
vector<bool> used(nums.size(),false);
// sort(nums.begin(),nums.end());
dfs(nums,used,tmp,0);
return vector<vector<int>>(ans.begin(),ans.end());
}
void dfs(vector<int>& nums,vector<bool>& used,vector<int>& tmp,int start){
if(tmp.size()>=2){
ans.insert(tmp);
// res.push_back(tmp);
}
if(start == nums.size()) return;
for(int i=start;i<nums.size();i++){
if((tmp.empty() || tmp.back()<=nums[i])){
// if(used[i] == false && (tmp.empty() || tmp.back()<=nums[i])){
// used[i] = true;
tmp.push_back(nums[i]);
dfs(nums,used,tmp,i+1);
tmp.pop_back();
// used[i] = false;
}
}
}
};
515. 在每个树行中找最大值
您需要在二叉树的每一行中找到最大的值。
广度优先遍历BFS 深度优先遍历DFS
class Solution {
public:
// 广度优先遍历 借用队列实现
vector<int> largestValues(TreeNode* root) {
vector<int> res;
if(!root) return res;
queue<TreeNode*> mq;
mq.push(root);
while(!mq.empty()){
int size = mq.size();
int max_val = mq.front()->val;
for(int i=0;i<size;i++){
TreeNode* cur = mq.front();
mq.pop();
max_val = max(cur->val,max_val);
if(cur->left) mq.push(cur->left);
if(cur->right) mq.push(cur->right);
}
res.push_back(max_val);
}
return res;
}
// 深度优先遍历， 递归实现 递归时传递当前节点的深度，即可对于树的每一层进行操作
vector<int> res;
void dfs(TreeNode* root,int dep){
if(dep == res.size())
res.push_back(root->val);
else
res[dep] = max(root->val,res[dep]);
if(root->left) dfs(root->left,dep+1);
if(root->right) dfs(root->right,dep+1);
}
vector<int> largestValues(TreeNode* root) {
if(!root) return res;
dfs(root,0);
return res;
}
};
98. 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
解法
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {
public:
// 使用递归 回溯法
bool isOk(TreeNode* root,long long min , long long max){
if(!root) return true;
if(root->val <= min || root->val >= max) return false;
return isOk(root->left,min,root->val) && isOk(root->right,root->val,max);
}
bool isValidBST(TreeNode* root) {
return isOk(root,LONG_LONG_MIN,LONG_LONG_MAX);
}
// 中序遍历，左根右，确保中序遍历为升序 既满足二叉搜索树
TreeNode* pre = nullptr;
bool isValidBST(TreeNode* root) {
if(!root) return true;
if(!isValidBST(root->left)) return false;
if(pre && pre->val >= root->val) return false;
pre = root;
if(!isValidBST(root->right)) return false;
return true;
}
};
109. 有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
// 递归构建 快慢指针找链表中点，即为搜索树的根节点
TreeNode* sortedListToBST(ListNode* head) {
if (head == nullptr) return nullptr;
if (head->next == nullptr) return new TreeNode(head->val);
ListNode* pre=head, *slow=head, *fast=head;
while(fast && fast->next){
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = nullptr;
TreeNode* root = new TreeNode(slow->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(slow->next);
return root;
}
京公网安备 11010502036488号