重庆名威建设工程咨询有限公司网站,做俄罗斯外贸网站,公司管理软件用什么好,网站建设业务流程图目录
1. 冒泡排序法排序 ★
2. 有效的数独 ★★
3. 不同的二叉搜索树 II ★★
附录
二叉搜索树 1. 冒泡排序法排序
输入n#xff08;1≤n≤10#xff09;个整数#xff0c;用冒泡排序法对其从小到大排序#xff0c;共进行n-1趟#xff0c;要求输出每一趟的排序情…
目录
1. 冒泡排序法排序 ★
2. 有效的数独 ★★
3. 不同的二叉搜索树 II ★★
附录
二叉搜索树 1. 冒泡排序法排序
输入n1≤n≤10个整数用冒泡排序法对其从小到大排序共进行n-1趟要求输出每一趟的排序情况
输入格式:
先输入个数n再输入n个整数。
输出格式:
第1趟结果
第2趟结果
......
第n-1趟结果
每个数后面有一个空格每个序列占一行。
输入样例:
5
4 2 3 2 1
输出样例:
2 3 2 1 4
2 2 1 3 4
2 1 2 3 4
1 2 2 3 4
代码
#include stdio.hint main()
{int arr[10];int n;scanf(%d, n);for (int i 0; i n; i)scanf(%d, arr[i]);for (int i 0; i n - 1; i){for (int j 0; j n - i - 1; j){if (arr[j] arr[j 1]){int t arr[j];arr[j] arr[j 1];arr[j 1] t;}}for (int j 0; j n; j)printf(%d , arr[j]);printf(\n);}return 0;
}
输入输出
5 4 2 3 2 1 2 3 2 1 4 2 2 1 3 4 2 1 2 3 4 1 2 2 3 4
-------------------------------- Process exited after 12.95 seconds with return value 0 请按任意键继续. . . 2. 有效的数独
请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
数独部分空格内已填入了数字空白格用 . 表示。
注意
一个有效的数独部分已被填充不一定是可解的。只需要根据以上规则验证已经填入的数字是否有效即可。
示例 1 输入board
[[5,3,.,.,7,.,.,.,.]
,[6,.,.,1,9,5,.,.,.]
,[.,9,8,.,.,.,.,6,.]
,[8,.,.,.,6,.,.,.,3]
,[4,.,.,8,.,3,.,.,1]
,[7,.,.,.,2,.,.,.,6]
,[.,6,.,.,.,.,2,8,.]
,[.,.,.,4,1,9,.,.,5]
,[.,.,.,.,8,.,.,7,9]]
输出true示例 2
输入board
[[8,3,.,.,7,.,.,.,.]
,[6,.,.,1,9,5,.,.,.]
,[.,9,8,.,.,.,.,6,.]
,[8,.,.,.,6,.,.,.,3]
,[4,.,.,8,.,3,.,.,1]
,[7,.,.,.,2,.,.,.,6]
,[.,6,.,.,.,.,2,8,.]
,[.,.,.,4,1,9,.,.,5]
,[.,.,.,.,8,.,.,7,9]]
输出false
解释除了第一行的第一个数字从 5 改为 8 以外空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。提示
board.length 9board[i].length 9board[i][j] 是一位数字或者 .
代码
#include bits/stdc.h
using namespace std;class Solution
{
public:bool isValidSudoku(vectorvectorchar board){for (int i 0; i board.size(); i){vectorbool mark(10);for (int j 0; j board.size(); j){if (!valid(board, mark, i, j)){return false;}}}for (int j 0; j board.size(); j){vectorbool mark(10);for (int i 0; i board.size(); i){if (!valid(board, mark, i, j)){return false;}}}for (int k 0; k board.size(); k){int sr k / 3 * 3;int sc (k % 3) * 3;vectorbool mark(10);for (int i sr; i sr 3; i){for (int j sc; j sc 3; j){if (!valid(board, mark, i, j)){return false;}}}}return true;}
private:bool valid(vectorvectorchar board, vectorbool mark, int i, int j){if (board[i][j] ! .){int index board[i][j] - 0;if (mark[index]){return false;}else{mark[index] 1;}}return true;}
};int main()
{Solution s;vectorvectorchar board {{5,3,.,.,7,.,.,.,.},{6,.,.,1,9,5,.,.,.},{.,9,8,.,.,.,.,6,.},{8,.,.,.,6,.,.,.,3},{4,.,.,8,.,3,.,.,1},{7,.,.,.,2,.,.,.,6},{.,6,.,.,.,.,2,8,.},{.,.,.,4,1,9,.,.,5},{.,.,.,.,8,.,.,7,9}};cout s.isValidSudoku(board) endl;board {{8,3,.,.,7,.,.,.,.},{6,.,.,1,9,5,.,.,.},{.,9,8,.,.,.,.,6,.},{8,.,.,.,6,.,.,.,3},{4,.,.,8,.,3,.,.,1},{7,.,.,.,2,.,.,.,6},{.,6,.,.,.,.,2,8,.},{.,.,.,4,1,9,.,.,5},{.,.,.,.,8,.,.,7,9}};cout s.isValidSudoku(board) endl;return 0;
}
输出
1 0 3. 不同的二叉搜索树 II
给你一个整数 n 请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1 输入n 3
输出[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]示例 2
输入n 1
输出[[1]]提示
1 n 8
代码
#include stdio.h
#include stdlib.hstruct TreeNode
{int val;struct TreeNode *left;struct TreeNode *right;
};static struct TreeNode *dfs(int low, int high, int *count)
{int i, j, k;if (low high){*count 0;return NULL;}else if (low high){struct TreeNode *node malloc(sizeof(*node));node-val low;node-left NULL;node-right NULL;*count 1;return node;}else{*count 0;int capacity 5;struct TreeNode *roots malloc(capacity * sizeof(struct TreeNode));for (i low; i high; i){int left_cnt, right_cnt;struct TreeNode *left_subs dfs(low, i - 1, left_cnt);struct TreeNode *right_subs dfs(i 1, high, right_cnt);if (left_cnt 0)left_cnt 1;if (right_cnt 0)right_cnt 1;if (*count (left_cnt * right_cnt) capacity){capacity * 2;capacity left_cnt * right_cnt;roots realloc(roots, capacity * sizeof(struct TreeNode));}for (j 0; j left_cnt; j){for (k 0; k right_cnt; k){roots[*count].val i;roots[*count].left left_subs NULL ? NULL : left_subs[j];roots[*count].right right_subs NULL ? NULL : right_subs[k];(*count);}}}return roots;}
}static struct TreeNode **generateTrees(int n, int *returnSize)
{int i, count 0;struct TreeNode *roots dfs(1, n, count);struct TreeNode **results malloc(count * sizeof(struct TreeNode *));for (i 0; i count; i){results[i] roots[i];}*returnSize count;return results;
}static void dump(struct TreeNode *node)
{printf(%d , node-val);if (node-left ! NULL){dump(node-left);}else{printf(# );}if (node-right ! NULL){dump(node-right);}else{printf(# );}
}int main(int argc, char **argv)
{if (argc ! 2){fprintf(stderr, Usage: ./test n\n);exit(-1);}int i, count 0;struct TreeNode **results generateTrees(atoi(argv[1]), count);for (i 0; i count; i){dump(results[i]);printf(\n);}return 0;
} 附录
二叉搜索树
又称二叉查找树或二叉排序树BSTBinary Search Tree。一棵二叉搜索树是以二叉树来组织的可以使用一个链表数据结构来表示其中每一个结点就是一个对象。一般地除了key和位置数据之外每个结点还包含属性lchild、rchild和parent分别指向结点的左孩子、右孩子和双亲父结点。如果某个孩子结点或父结点不存在则相应属性的值为空NULL。根结点是树中唯一父指针为NULL的结点而叶子结点的孩子结点指针也为NULL。
二叉搜索树作为一种经典的数据结构它既有链表的快速插入与删除操作的特点又有数组快速查找的优势例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。
二叉搜索树能够高效地进行操作1.插入一个数值2.查询是否包含某个数值3.删除某个数值。
性质 设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点那么y.key≤x.key。如果y是x右子树中的一个结点那么y.key≥x.key。 在二叉搜索树中 1.若任意结点的左子树不空则左子树上所有结点的值均不大于它的根结点的值。 2. 若任意结点的右子树不空则右子树上所有结点的值均不小于它的根结点的值。 3.任意结点的左、右子树也分别为二叉搜索树。
复杂度 不论哪一种操作所花的时间都和树的高度成正比。因此如果共有n个元素那么平均每次操作需要O(logn)的时间。
算法实现 二叉排序树的操作主要有 1.查找递归查找是否存在key。 2.插入原树中不存在key插入key返回true否则返回false。 3.构造循环的插入操作。 4.删除 1叶子节点直接删除不影响原树。 2仅仅有左或右子树的节点节点删除后将它的左子树或右子树整个移动到删除节点的位置就可以子承父业。 3既有左又有右子树的节点找到须要删除的节点p的直接前驱或者直接后继s用s来替换节点p然后再删除节点s。
