买商标最好的平台_海南创想_域名搜索_他达拉非片的作用及功效副作用

其他:

今日总结
往期打卡

---

491. 非递减子序列

跳转: 491. 非递减子序列

学习: 代码随想录公开讲解

问题:

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

思路:

相当于求特殊子集,遍历startIndex,每层去重即可.

复杂度:

• 时间复杂度: $O(2^n\ast n)$
• 空间复杂度: $O(n)$

代码:

class Solution {int[] nums;int n;List<List<Integer>> ans;List<Integer> path = new ArrayList<>();void dfs(int startIndex) {if (startIndex >= n)return;int[] hash = new int[201];for (int i = startIndex; i < n; i++) {if (hash[nums[i] + 100] == 1)continue;hash[nums[i] + 100] = 1;if (path.isEmpty() || path.get(path.size() -1)<= nums[i]) {path.add(nums[i]);if (path.size() > 1)ans.add(new ArrayList(path));dfs(i + 1);path.remove(path.size() - 1);}}}public List<List<Integer>> findSubsequences(int[] nums) {this.nums = nums;ans = new ArrayList<>();n = nums.length;dfs(0);return ans;}
}

---

46. 全排列

跳转: 46. 全排列

学习: 代码随想录公开讲解

问题:

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列

思路:

全排列问题需要去重值,之前选过的不能再选,和组合问题不同的是选择不能单纯的顺序选,所以不需要StartIndex,但是要标识选过的元素,避免之后重复选择.

复杂度:

• 时间复杂度: $O(n\ast n!)$
• 空间复杂度: $O(n)$

代码:

class Solution {int[] nums;int n;List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();int[] hash = new int[21];void dfs() {if (path.size() == n) {ans.add(new ArrayList<>(path));return;}for (int i : nums) {int tmp = i+10;if (hash[tmp]!=1) {hash[tmp] =1;path.add(i);dfs();hash[tmp] =0;path.remove(path.size() - 1);}}}public List<List<Integer>> permute(int[] nums) {this.nums = nums;n = nums.length;dfs();return ans;}
}

---

47. 全排列 II

跳转: 47. 全排列 II

学习: 代码随想录公开讲解

问题:

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

思路:

相对上题讲有重复的元素,所以除了需要保证各索引只选一次,还需要保证一层一个值只选一次

复杂度:

• 时间复杂度: $O(n\ast n!)$
• 空间复杂度: $O(n)$

代码:

class Solution {int[] nums;int n;List<List<Integer>> ans = new ArrayList<>();List<Integer> path = new ArrayList<>();int[] hash = new int[21];void dfs() {if (path.size() == n) {ans.add(new ArrayList<>(path));return;}int[] t = new int[21];for (int i=0;i<n;i++) {if (hash[i] != 1&&t[nums[i]+10]==0) {t[nums[i]+10]=1;hash[i] = 1;path.add(nums[i]);dfs();hash[i] = 0;path.remove(path.size() - 1);}}}public List<List<Integer>> permuteUnique(int[] nums) {this.nums = nums;n = nums.length;dfs();return ans;}
}

---

51. N 皇后

跳转: 51. N 皇后

学习: 代码随想录公开讲解

问题:

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思路:

递归行,遍历列,判断列和两个斜线不重

复杂度:

• 时间复杂度: $O(n!)$
• 空间复杂度: $O(n)$

代码:

class Solution {int n;List<List<String>> ans = new ArrayList<>();List<String> path = new ArrayList<>();int[] v;int[] diagonal1;int[] diagonal2;String[] str;void dfs(int N){if(N==n){ans.add(new ArrayList<>(path));return;}for(int i=0;i<n;i++){if(v[i]==0&&diagonal1[i+n-N]==0&&diagonal2[i+N]==0){v[i]=1;diagonal1[i+n-N]=1;diagonal2[i+N]=1;path.add(str[i]);dfs(N+1);path.remove(path.size()-1);v[i]=0;diagonal1[i+n-N]=0;diagonal2[i+N]=0;}}}public List<List<String>> solveNQueens(int n) {this.n = n;v = new int[n];diagonal1 = new int[n*2];diagonal2 = new int[n*2];str = new String[n];for(int i=0;i<n;i++){String s = "";for(int j=0;j<n;j++){if(i==j) s+="Q";else s+=".";}str[i] = s;}//System.out.println(Arrays.toString(str));dfs(0);return ans;}
}

---

37. 解数独

跳转: 37. 解数独

学习: 代码随想录公开讲解

问题:

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

思路:

回溯,二维遍历整个棋盘,填一个合法的数后继续遍历.
记录遍历到的行减少重复.
出现不能填的路径直接毙掉.
直到有一条路径能填满棋盘直接返回

代码:

class Solution {char[][] board;int m;int n;boolean dfs(int i){for(int x=i;x<m;x++){for(int y=0;y<n;y++){if(board[x][y]=='.'){for(int k=1;k<10;k++){if(isvalid(x,y,(char)(k+'0'))){board[x][y] = (char)(k+'0');if(dfs(x)) return true;board[x][y] = '.';}}return false;}}}return true;}boolean isvalid(int x,int y,char k){for(int i=0;i<3;i++){for(int j=0;j<3;j++){int a = (x/3)*3+i;int b = (y/3)*3+j;// if(a==x&&b==y) continue;if(board[a][b]==k) return false;}}for(int i=0;i<m;i++){if(board[i][y]==k) return false;}for(int i=0;i<n;i++){if(board[x][i]==k) return false;}return true;}public void solveSudoku(char[][] board) {this.board = board;m = board.length;n = board[0].length;System.out.println(m+" "+n);dfs(0);}
}

---

2563. 统计公平数对的数目(每日一题4-19)

跳转: 2563. 统计公平数对的数目

问题:

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

• 0 <= i < j < n，且
• lower <= nums[i] + nums[j] <= upper

思路:

树状数组记录前缀,定右找左前缀
因为空间范围太大,需要对数据做去重获得离散表,之后通过二分查找映射索引

复杂度:

• 时间复杂度: $O(n\ast n!)$
• 空间复杂度: $O(n)$

代码:

class Solution {class TreeArray{int[] arr;TreeArray(int n){arr = new int[n];}void add(int num){while(num<arr.length){arr[num]++;num+=(num&(-num));}}long getVal(int num){long ans = 0;while(num>0){ans+=arr[num];num-=(num&(-num));}return ans;}}public long countFairPairs(int[] nums, int lower, int upper) {int n = nums.length;long ans = 0;TreeSet<Integer> set = new TreeSet<>();for(int i:nums){set.add(i);}set.add(Integer.MAX_VALUE);set.add(Integer.MIN_VALUE);Integer[] arr = set.toArray(new Integer[0]);TreeArray tree = new TreeArray(arr.length);for(int i:nums){int a = Arrays.binarySearch(arr,upper-i);int b = Arrays.binarySearch(arr,lower-1-i);a = a<0?-a-2:a;b = b<0?-b-2:b;ans+=tree.getVal(a)-tree.getVal(b);int c = Arrays.binarySearch(arr,i);tree.add(c);}return ans;}
}

---

总结

练习了排列回溯,n皇后和解数独的回溯解法,以及树状数组和离散化数组.

往期打卡

代码随想录算法训练营第二十一天

代码随想录算法训练营第二十天

代码随想录算法训练营第十九天

代码随想录算法训练营第十八天

代码随想录算法训练营第十七天

代码随想录算法训练营周末三

代码随想录算法训练营第十六天

代码随想录算法训练营第十五天

代码随想录算法训练营第十四天

代码随想录算法训练营第十三天

代码随想录算法训练营第十二天

代码随想录算法训练营第十一天

代码随想录算法训练营周末二

代码随想录算法训练营第十天

代码随想录算法训练营第九天

代码随想录算法训练营第八天

代码随想录算法训练营第七天

代码随想录算法训练营第六天

代码随想录算法训练营第五天

代码随想录算法训练营周末一

代码随想录算法训练营第四天

代码随想录算法训练营第三天

代码随想录算法训练营第二天

代码随想录算法训练营第一天