|
今天刷题比昨天顺利一些了，居然一口气刷了三道树形问题，虽然还是要时不时参考题解，但是也能自己思考回溯到底是怎么实现的了。看来多刷题还是挺有用的。希望能够保持较高的学习效率，晚上能有时间来锻炼和阅读就更好了。
今日进度：
1.坚持听网课，坚持刷题
2.坚持锻炼
3.坚持录小王子
4.坚持记录
学习笔记：
1.时间戳，查业务问题的后悔药，create_time：数据创建时间，update_time:数据更新时间
2.回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案
3.剪枝策略就是在搜索过程中利用过滤条件来剪去完全不用考虑（已经判断这条路走下去得不到最优解）的搜索路径，从而避免了一些不必要的搜索，大大优化了算法求解速度，还保证了结果的正确性。
4.结构化查询语言(Structured Query Language)简称SQL(发音：/?es kju? ?el/ “S-Q-L”)，是一种数据库查询和程序设计语言，用于存取数据以及查询、更新和管理关系数据库系统；同时也是数据库脚本文件的扩展名。
5.结构化查询语言包含6个部分：
一：数据查询语言（DQL:Data Query Language）：
其语句，也称为“数据检索语句”，用以从表中获得数据，确定数据怎样在应用程序给出。保留字SELECT是DQL（也是所有SQL）用得最多的动词，其他DQL常用的保留字有WHERE，ORDER BY，GROUP BY和HAVING。这些DQL保留字常与其他类型的SQL语句一起使用。
二：数据操作语言（DML：Data Manipulation Language）：
其语句包括动词INSERT，UPDATE和DELETE。它们分别用于添加，修改和删除表中的行。也称为动作查询语言。
三：事务处理语言（TPL）：
它的语句能确保被DML语句影响的表的所有行及时得以更新。TPL语句包括BEGIN TRANSACTION，COMMIT和ROLLBACK。
四：数据控制语言（DCL）：
它的语句通过GRANT或REVOKE获得许可，确定单个用户和用户组对数据库对象的访问。某些RDBMS可用GRANT或REVOKE控制对表单个列的访问。
五：数据定义语言（DDL）：
其语句包括动词CREATE和DROP。在数据库中创建新表或删除表（CREAT TABLE 或 DROP TABLE）；为表加入索引等。DDL包括许多与人数据库目录中获得数据有关的保留字。它也是动作查询的一部分。
六：指针控制语言（CCL）：
它的语句，像DECLARE CURSOR，FETCH INTO和UPDATE WHERE CURRENT用于对一个或多个表单独行的操作。
6.结构化查询语言中的五种数据类型：字符型，文本型，数值型，逻辑型和日期型。
7.SQL可以创建新的数据库及其对象（表，索引，视图，存储过程，函数和触发器）。
SQL可以修改现有数据库的结构。
SQL可以从数据库中删除（删除）对象。
SQL可以TRUNCATE（删除）表中的所有记录。
SQL可以对数据字典进行COMMENT。
SQL可以RENAME一个对象。
SQL可以从数据库中选择（检索）数据。
SQL可以将数据插入到表中。
SQL可以更新表中的现有数据。
SQL可以从数据库表中删除记录。
SQL可以在数据库中设置用户的GRANT和REVOKE权限。
8.SQL约束是在表上的数据列上强制执行的规则。它们用于限制可以进入表中的数据类型。这确保了数据库中数据的准确性和可靠性。约束可以是列级别，也可以是表级别。列级约束仅应用于一列，而表级约束则应用于整个表。以下是sql?中可用的一些最常用的约束：
NOT NULL 约束：保证列中数据不能有 NULL 值
DEFAULT 约束：提供该列数据未指定时所采用的默认值
UNIQUE 约束：保证列中的所有数据各不相同
主键约束：唯一标识数据表中的行/记录
外键约束：唯一标识其他表中的一条行/记录
CHECK 约束：此约束保证列中的所有值满足某一条件
索引：用于在数据库中快速创建或检索数据
9.46. 全排列
给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
解题思路：使用数组used来存储状态，访问过为true，否则为false。使用dfs探索所有组合的可能性，得到一个解之后，将它添加到结果集里，再回溯到上一个节点，删除最后一个元素，将userd状态改为false，直到所有的情况都遍历完。
import java.util.ArrayList;
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if(nums.length==0){
return res;
}
ArrayList<Integer> p = new ArrayList<Integer>();
used = new boolean[nums.length];
Arrays.fill(used, false);
generateP(nums, 0, p);
return res;
}
public void generateP(int[] nums, int index, ArrayList<Integer> p){
if(index==nums.length){
res.add((ArrayList<Integer>)p.clone());
return;
}
for(int i=0; i<nums.length;i++){
if(!used[i]){
p.add(nums[i]);
used[i] = true;
generateP(nums, index+1, p);
p.remove(p.size()-1);
used[i] = false;
}
}
return;
}
}
10.47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
解题思路：使用数组used来存储状态，如果未访问是false，如果已访问是true。使用dfs遍历每一种情况，如果找到一种情况之后，将它加入HashSet结果集，保证没有重复的情况，再回溯到上一个节点，将最后一个元素删除，状态改为false，继续搜索下一种情况，直到所有情况都探索完。
class Solution {
HashSet<List<Integer>> h = new HashSet<List<Integer>>();
boolean[] used;
public List<List<Integer>> permuteUnique(int[] nums) {
used = new boolean[nums.length];
ArrayList<Integer> p = new ArrayList<Integer>();
dfs(nums, 0, p);
Arrays.fill(used, false);
List<List<Integer>> res = new ArrayList<List<Integer>>(h);
return (res);
}
public void dfs(int[] nums, int index, ArrayList<Integer> p){
if(index==nums.length){
h.add((ArrayList<Integer>)p.clone());
}
for(int i=0; i<nums.length; i++){
if(!used[i]){
p.add(nums[i]);
used[i] = true;
dfs(nums, index+1, p);
p.remove(p.size()-1);
used[i] = false;
}
}
}
}
11.77. 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解题思路：使用dfs来遍历每一种情况，当选够k个数之后，回溯到上一个节点，直到获得所有情况。这里使用了i<=len-(k-p.size())+1来进行剪枝，如果剩下的元素个数小于剩余的目标选择，就没有必要再进行下去了。
class Solution {
List<List<Integer>> res = new ArrayList<List<Integer>>();
int len;
public List<List<Integer>> combine(int n, int k) {
len=n;
ArrayList<Integer> p = new ArrayList<Integer>();
if(k>n){
return res;
}
generateC(k, 1, p);
return res;
}
public void generateC(int k, int start, ArrayList<Integer> p){
if(p.size()==k){
res.add((ArrayList<Integer>)p.clone());
return;
}
for(int i=start; i<=len-(k-p.size())+1; i++){
p.add(i);
generateC(k, i+1, p);
p.remove(p.size()-1);
}
}
}
今天的内容还挺多的，不知道为什么，晚上睡得越来越晚了，7个小时的睡眠其实也没有保证到，明天继续加油！
|