代码随想录算法训练营第十三天|n皇后&数独老经典了-创新互联

Leecode 90. 子集 II

链接：https://leetcode.cn/problems/subsets-ii/

创新互联公司是一家专注于做网站、成都做网站与策划设计,中原网站建设哪家好?创新互联公司做网站,专注于网站建设十年,网设计领域的专业建站公司;建站业务涵盖:中原等地区。中原做网站价格咨询:028-86922220

那么这道题和上一道题有什么区别呢？

没什么区别，就是仅仅多了重复元素而已，那怎么搞？

实际上[1,4,4]和[4,1,4]是同一个子集，所以就还要去重

不急，在递归的下面加上这句话

while(i+1< nums.size() && vec[vec.size()-1] == nums[i+1]

在pop元素之前，如果我们发现要pop的元素和下一个push进来的元素一毛一样，那么我们就让i++

class Solution {public:
    vector>ans;
    vectorvec;
    void recursion(vector& nums,int k,int step)
    {// 元素收集满了，记录当前vec然后return
        if(vec.size() == k)
        {ans.push_back(vec);
            return;
        }
        for(int i = step;ivec.push_back(nums[i]);
            recursion(nums,k,i + 1); // 是取搜下一个元素了
            while(i+1< nums.size() && vec[vec.size()-1] == nums[i+1]) i++; // 那么就跳过重复的数据呗
            vec.pop_back();
        }
    }
    vector>subsetsWithDup(vector& nums) 
    {sort(nums.begin(),nums.end());
        for(int i = 1; i< nums.size() ;i++) 
        {vec.clear();
            recursion(nums,i,0); 
        }
        //vector>res (ans.begin(),ans.end());
        ans.push_back({});
        ans.push_back(nums);
        return ans;
    }
};

Leecode 491. 递增子序列

链接：https://leetcode.cn/problems/increasing-subsequences/description/

注意，这个题目比较特别

因为要求输出递增序列，因此是不可以排序的，而我们之前推崇的办法

while(i + 1< nums.size() && nums[i+1] == vec[vec.size()-1]) i++;

也仅仅在排好序的数组上管用

所以我们需要重新思考去重的方式——set

同时因为题目要求递增，所以需要在push之前判断当前元素是不是比vector中的最后一个元素大

class Solution {public:
    set>ans;
    vectorvec;
    void recursion(vector& nums,int k,int step)
    {if(vec.size() == k)
        {ans.insert(vec);
            return;
        }
        for(int i=step;iif(!vec.empty() && nums[i] >= vec[vec.size()-1] || vec.empty()) // 如果满足递增，再把元素给push进来
            {vec.push_back(nums[i]);
                recursion(nums,k,i + 1);
                //while(i + 1< nums.size() && nums[i+1] == vec[vec.size()-1]) i++; // 不能排序这个办法基本上就死了，所以需要set
                vec.pop_back();
            }
        }
    }
    vector>findSubsequences(vector& nums) {//sort(nums.begin(),nums.end()); // 注意这个题目是不允许排序的
        for(int i=2;i<=nums.size();i++)
        {vec.clear();
            recursion(nums,i,0);
        }
        vector>res(ans.begin(),ans.end());
        return res;
    }
};

Leecode 46. 全排列

链接：https://leetcode.cn/problems/permutations/

确实是需要used数组了，记录当前哪些元素用过哪些元素没有用过

值得注意的一点是：used中的索引值需要是当前元素在nums中的索引而不能是当前元素的值，因为当前元素可能是负值···

class Solution {public:
    // 想返回全排列最好的办法就是用数组记重了
    vector>res;
    vectorvec;
    int used[100];
    void recurison(vector& nums)
    {if(vec.size() == nums.size()) 
        {res.push_back(vec);
            return;
        }
        for(int i = 0;iif(!used[i]) // 最好是记录索引而不是值，因为值有可能是负的
            {vec.push_back(nums[i]);
                used[i] = 1;
                recurison(nums);
                used[i] = 0;
                vec.pop_back();
            }
        }
    }
    vector>permute(vector& nums) {recurison(nums);
        return res;
    }
};

Leecode 47. 全排列 II

链接：https://leetcode.cn/problems/permutations-ii/

加个set去重咯，没有新意~

class Solution {public:
    set>ans;
    vectorvec;
    int used[100];
    void recurison(vector& nums)
    {if(vec.size() == nums.size()) 
        {ans.insert(vec);
            return;
        }
        for(int i = 0;iif(!used[i]) // 最好是记录索引而不是值，因为值有可能是负的
            {vec.push_back(nums[i]);
                used[i] = 1;
                recurison(nums);
                used[i] = 0;
                vec.pop_back();
            }
        }
    }
    vector>permuteUnique(vector& nums) {recurison(nums);
        vector>res(ans.begin(),ans.end());
        return res;
    }
};

Leecode 332. 重新安排行程

链接：https://leetcode.cn/problems/reconstruct-itinerary/

孙哥讲的真很好，很细

class Solution {unordered_map>targets;
    bool backtracking(int ticketNum, vector& result) {if (result.size() == ticketNum + 1) {return true;
        }
        for (pair& target : targets[result[result.size() - 1]]) 
        {if (target.second >0 ) 
            {// 记录到达机场是否飞过了
                result.push_back(target.first);
                target.second--;
                if (backtracking(ticketNum, result)) return true;
                result.pop_back();
                target.second++;
            }
        }
        return false;
    }
    public:
        vectorfindItinerary(vector>& tickets) 
        {targets.clear();
            vectorresult;
            for (const vector& vec : tickets) 
            {targets[vec[0]][vec[1]]++; // 记录映射关系
            }
            result.push_back("JFK"); // 起始机场
            backtracking(tickets.size(), result);
            return result;
        }
};

Leecode 51. N 皇后

链接：https://leetcode.cn/problems/n-queens/

经典练手题

// 区区n皇后是困难？？？
class Solution {public:
    vector>res;
    // 首先我们枚举行，从左到右，看行上的哪个元素可以放置Q
    bool check(int n,int row,int column,vector&test)
    {// [row,column]
        // 若是在row这行有元素，我们就直接return false
        for(int i=0;iif(test[i][column] == 'Q') return false;
            if(row - i >= 0 && column + iif(test[row - i][column + i] == 'Q') return false;}
            if(row - i >= 0 && column - i >=0) {if(test[row - i][column - i] == 'Q') return false;}
        }
        return true;c    
    }
    void recursion(int n,int step,vector&test) // 直接修改test数组
    {// 如果当前枚举的行数已经超过了n，那么我们直接就记录当前答案然后return
        if(step >n-1) 
        {res.push_back(test);
            return;
        }
        for(int i=0;iif(check(n,step,i,test)) // 如果当前位置是合法的
            {test[step][i] = 'Q';
                recursion(n,step + 1,test);
                test[step][i] = '.';
            }
        }
    }
    vector>solveNQueens(int n) // 此处的n给的是棋盘的大小 
    {// 首先需要初始化数组，答案是用三维数组装填的
        vectortest(n , string(n,'.')); // 刚开始我们将数组全部都用'.'装填之
        recursion(n,0,test);
        return res;
    }
};

Leecode 37. 解数独

经典练手题2，主要看细不细

首先我们考虑如何递归的问题：按理说是9*9的方格逐个位置搜索，那用for循环枚举位置不是有点多余？因为移动挺有规律的，所以我们这里就没有用两层for循环去枚举位置（加上枚举数字就有三层循环了），我们只要枚举当前位置需要填入的值就OK了

至于行数和列数，一般都是递归到当前行的下一列，只有当前行所有列全都遍历完毕才会去下一行，根据这个规律就能得到下一次递归的位置在哪

还有一个需要注意的点：数独数组本来就是有值的，并且我们在填充数独的过程中是不可以改变原来数独中的值的，因此我们在递归的过程中发现当前位置若是有值，就直接递归到下一层。并且，从此处回溯是不合理的，所以在递归操作的后面直接加上return避免此处回溯进入到后面的for循环，同时也提高了效率

除此之外，我设计了一个check函数，用来判断在当前位置填入num是否合法——还是为了提高效率，开始的时候我们就得到了不完全的数独数组，为了避免重复值出现在“同一行”，“同一列”，“同一个3 * 3矩阵”中，我们还要定义三个数组用来记录“当前行”，“当前列”，“当前的3 * 3矩阵中哪些数字被使用过

最后还有一个需要注意的点：数独填充完毕后是要return的，但是真的return回来所有被填充的数字又会变成’.'，所以在填充完毕后，我们定义标志位flag为1，并且在回溯的时候加上判断——只有在标志位不为1的时候才回溯，这样我们return回来的数组就是完整的

class Solution {public:
    int rows[10][10];
    int cols[10][10];
    int cell[10][10][10];
    int flag = 0;
    // 首先先遍历一遍数独，将其中都是1的位置全都置为1，表示这个元素已经被使用过了
bool check(int row, int col, vector>& board, int num)
{// 若是行中列中包括cell中都没有出现过这个元素，那么return true
	if (rows[row][num]) return false;
	if (cols[col][num]) return false;
	if (cell[row/3][col/3][num]) return false;
	return true;
}
void recursion(vector>& board, int row, int col)
{if (flag) return;
	if (col == 9)        {col = 0; row += 1; }
	if (row == 9 && col == 0) // 已经将数组填充完毕
	{flag = 1;
		return;
	}
	if (board[row][col]!='.') {recursion(board, row, col + 1); return; } // 如果当前有元素，直接跳过，并且不允许回溯，直接return

	// 你觉得需要用for循环枚举位置吗，是不是所有顺序都是固定的
	for (int num = 1; num<= 9; num++) // num是当前准备填充的元素
	{if (check(row, col, board, num))
		{	board[row][col] = num + '0';
			rows[row][num] = 1; // 第row行的num已经用过了
			cols[col][num] = 1; // 第col列的num已经用过了
			cell[row/3][col/3][num] = 1;

			recursion(board, row, col + 1);

			if (flag) return;
			board[row][col] = '.';
			rows[row][num] = 0; // 第row行的num没用过
			cols[col][num] = 0; // 第col列的num没用过
			cell[row/3][col/3][num] = 0;
		}
	}

}
void solveSudoku(vector>& board)
{memset(rows, 0, sizeof(rows));
	memset(cols, 0, sizeof(cols));
	memset(cell, 0, sizeof(cell));
	for (int i = 0; i<9; i++)
		for (int j = 0; j<9; j++)
		{	if (board[i][j] != '.')
			{		int num = board[i][j] - '0';
				rows[i][num] = 1; // 第i行的num已经用过了
				cols[j][num] = 1; // 第j列的num已经用过了;
				cell[i/3][j/3][num] = 1;
			}
		}
	recursion(board, 0, 0);
}
};

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

名称栏目：代码随想录算法训练营第十三天|n皇后&数独老经典了-创新互联
当前网址：http://cqcxhl.com/article/jjede.html