著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。
示例 1：
输入：n = 2 输出：["1/2"] 解释："1/2" 是唯一一个分母小于等于 2 的最简分数。
示例 2：
输入：n = 3 输出：["1/2","1/3","2/3"]
示例 3：
输入：n = 4 输出：["1/2","1/3","1/4","2/3","3/4"] 解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。
示例 4：
输入：n = 1 输出：[]
提示：
1 <= n <= 100GCD辗转相除法【欧几里德算法（Euclidean algorithm）】
相关知识链接碾转相除法
这是一个求最大公约数的方法
gcd(int a, int b)辗转相除方法，判断两个数的最大公约数是否为1i到n和从i+1到n的分子分母关系了class Solution {
public List<String> simplifiedFractions(int n) {
List<String> list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <=n ; j++) {
if (gcd(i,j)==1){
list.add(i+"/"+j);
}
}
}
return list;
}
int gcd(int a, int b){
if (b==0){
return a;
}
return gcd(b,a%b);
}
}给你二叉树的根结点 root ，请你将它展开为一个单链表：
TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
示例 1：
输入：root = [1,2,5,3,4,null,6] 输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [0] 输出：[0]
提示：
[0, 2000] 内-100 <= Node.val <= 100
进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？
前序遍历，原地递归修改
按照题意为前序遍历的结果，声明一个TreeNode pre记录前一个访问的节点
这样直接进行前序遍历，把当前节点挂载到pre节点的right上，记得要清除left节点
遍历当前节点的时候left、right节点的值记得先存下来，会在递归的时候被修改掉
class Solution {
/*
1
2 5
3 4 n 6
1
n 2
n 3
n 4
n 5
n 6
*/
TreeNode pre;
public void flatten(TreeNode root) {
dfs(root);
}
public void dfs(TreeNode node){
if (null == node){
return;
}
if (pre!=null){
pre.right = node;
}
pre = node;
TreeNode left = node.left;
TreeNode right = node.right;
node.left = null;
dfs(left);
dfs(right);
}
}给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123""132""213""231""312""321"给定 n 和 k，返回第 k 个排列。
示例 1：
输入：n = 3, k = 3 输出："213"
示例 2：
输入：n = 4, k = 9 输出："2314"
示例 3：
输入：n = 3, k = 1 输出："123"
提示：
1 <= n <= 91 <= k <= n!逆康托展开 与 康托展开【Cantor Expansion】
关于本题原型可以参见下康托展开【Cantor Expansion】 ,就是原题了，具体内容不做更多赘述
(n-1)!(n-2)!(n-1)!，得到第一位的数字，记下余数(n-2)!，知道了第二位数字，继续记下余数用来处理第三位数字(n-?)!得到的结果是确定的未使用的数字的顺序，即在确定这个数字的时候需要跳过前面已经使用过的数字，见方法findNthNum(int nth)容易掉的坑，k--，上来记得要减下，被这步坑了好久，减一之后直接除了便于取整取余划分区间
class Solution {
boolean[] usedNums;
public String getPermutation(int n, int k) {
k--;
usedNums = new boolean[n+1];
int[] factorial = new int[n];
factorial[n-1] = 1;
for (int i = n-2; i >= 0; i--) {
factorial[i] = factorial[i+1] * (n-i);
}
char[] ans = new char[n];
int idx = 0;
while (++idx < n){
int i = k / factorial[idx];
k %= factorial[idx];
int num = findNthNum(i+1);
ans[idx-1] = (char)('0'+ num);
}
ans[idx-1] = (char)('0'+ findNthNum(1));
return new String(ans);
}
int findNthNum(int nth){
for (int i = 1; i < usedNums.length; i++) {
if(!usedNums[i]){
nth--;
if (nth==0){
usedNums[i] = true;
return i;
}
}
}
return -1;
}
}以上其实是逆康托展开的过程，根据第k的数值，确定这个数值是什么
根据定义，与这一过程相对的是康托展开的过程，根据数值确定这个数值的排序
那么相应思路为
i（从0下标开始或者你认为从正数1开始排序i'那么前面有i'-1组）,那么前面有i * (n-1)!个i_1(下标)，第二位则对应为i_1 * (n-2)!给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。
城市的 天际线 是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。
我们被允许为 任意数量的建筑物 的高度增加 任意增量（不同建筑物的增量可能不同） 。 高度为 0 的建筑物的高度也可以增加。然而，增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。
在 不改变 从任何主要方向观测到的城市 天际线 的前提下，返回建筑物可以增加的 最大高度增量总和 。
示例 1：
输入：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出：35
解释：建筑物的高度如上图中心所示。
用红色绘制从不同方向观看得到的天际线。
在不影响天际线的情况下，增加建筑物的高度：
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
示例 2：
输入：grid = [[0,0,0],[0,0,0],[0,0,0]] 输出：0 解释：增加任何建筑物的高度都会导致天际线的变化。
提示：
n == grid.lengthn == grid[r].length2 <= n <= 500 <= grid[r][c] <= 100题面的示例已经给出了基本实现思路
题面的示例已经给出了基本实现思路，顺着这个思路写代码就对了、
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int[] rowMin = new int[grid.length];
int[] colMin = new int[grid[0].length];
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[row].length; col++) {
int height = grid[row][col];
rowMin[row] = Math.max(rowMin[row],height);
colMin[col] = Math.max(colMin[col],height);
}
}
int ans = 0;
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[row].length; col++) {
ans += Math.min(rowMin[row],colMin[col]) - grid[row][col];
}
}
return ans;
}
}给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]
提示：
[1, 104] 范围内-231 <= Node.val <= 231 - 1bfs
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if (null == root){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
double sum = 0;
int i=-1;
while (++i < size){
TreeNode node = queue.poll();
sum += (double) node.val;
if (node.left!=null){
queue.offer(node.left);
}
if (node.right!=null){
queue.offer(node.right);
}
}
res.add(sum/size);
}
return res;
}
}给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736 输出: 7236 解释: 交换数字2和数字7。
示例 2 :
输入: 9973 输出: 9973 解释: 不需要交换。
注意:
凑合写了个费劲巴拉的方法
排序之后跟原序列对比，如果不同则交换位置
交换的新数字取最右边出现的位置
class Solution {
public int maximumSwap(int num) {
int size = stringSize(num);
if (size==1){
return num;
}
int[] arr = new int[size];
int[] map = new int[10];
Arrays.fill(map,-1);
int idx = size;
while ( num != 0){
arr[--idx] = num%10;
num /= 10;
if (map[arr[idx]]==-1){
map[arr[idx]]=idx;
}
}
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o2[0]-o1[0];
}
});
for (int i = arr.length-1; i >=0; i--) {
queue.offer(new int[]{arr[i],map[arr[i]]});
}
int i = -1;
int ans = 0;
while (!queue.isEmpty() && queue.peek()[0] == arr[++i]){
ans = ans * 10 + queue.poll()[0];
}
if (queue.isEmpty()){
return ans;
}
ans = ans * 10 + queue.peek()[0];
int[] swapIdx = new int[]{i,queue.peek()[1]};
while (++i < arr.length){
if (i == swapIdx[1]){
ans = ans * 10 + arr[swapIdx[0]];
}else{
ans = ans * 10 + arr[i];
}
}
return ans;
}
final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999, Integer.MAX_VALUE };
// Requires positive x
static int stringSize(int x) {
for (int i=0; ; i++)
if (x <= sizeTable[i])
return i+1;
}
}给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的 最短补全词 。
补全词 是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的 数字和空格 。不区分大小写。如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。
例如：licensePlate = "aBc 12c"，那么它的补全词应当包含字母 'a'、'b' （忽略大写）和两个 'c' 。可能的 补全词 有 "abccdef"、"caaacab" 以及 "cbca" 。
请返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中 第一个 出现的那个。
示例 1：
输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"] 输出："steps" 解释：最短补全词应该包括 "s"、"p"、"s"（忽略大小写） 以及 "t"。 "step" 包含 "t"、"p"，但只包含一个 "s"，所以它不符合条件。 "steps" 包含 "t"、"p" 和两个 "s"。 "stripe" 缺一个 "s"。 "stepple" 缺一个 "s"。 因此，"steps" 是唯一一个包含所有字母的单词，也是本例的答案。
示例 2：
输入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"] 输出："pest" 解释：licensePlate 只包含字母 "s" 。所有的单词都包含字母 "s" ，其中 "pest"、"stew"、和 "show" 三者最短。答案是 "pest" ，因为它是三个单词中在 words 里最靠前的那个。
提示：
1 <= licensePlate.length <= 7licensePlate 由数字、大小写字母或空格 ' ' 组成1 <= words.length <= 10001 <= words[i].length <= 15words[i] 由小写英文字母组成哈希表，字符统计，简单，特纯粹的哈希表统计
licensePlate中字符出现次数words[] 分别统计每个word的字符出现次数licensePlate中出现的字符，在word中出现的次数要大于等于在licensePlate中出现的次数ans 和当前word的长度，取较小的一个，相等的情况不变，即长度相等取现出现的就…纯粹的哈希表统计
class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
int[] arr = charCnt(licensePlate);
String ans = null;
for (String word : words) {
int[] wArr = charCnt(word);
boolean flag = true;
for (int i = 0; flag && i < arr.length; i++) {
if (arr[i]>0 && wArr[i] <arr[i]){
flag = false;
}
}
ans = flag && ( ans == null || word.length() < ans.length()) ? word : ans;
}
return ans;
}
private int[] charCnt(String str){
int[] arr = new int[26];
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c >= 'a' && c <= 'z'){
arr[str.charAt(i)-'a']++;
}
if (c >= 'A' && c <= 'Z'){
arr[str.charAt(i)-'A']++;
}
}
return arr;
}
}