215 数组中的第k个最大元素
剑指offer同样的题目
1.库函数排序
调用Arrays.sort()
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length-k];
}
}
时间复杂度o(nlogn)
空间复杂度o(1) : 原地排序，没有借助额外的辅助空间
2.快排中的partition函数
注意随机化pivot以避免极端测试用例
为了应对极端测试用例，使得递归树加深，可以在循环一开始的时候，随机交换第 1 个元素与它后面的任意1 个元素的位置；
说明：最极端的是顺序数组与倒序数组，此时递归树画出来是链表，时间复杂度是o(n^2)，根本达不到减治的效果。
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/
下次写代码注意 partition有两种方法可以实现!而且要记得使用random类随机化：
Random r = new Random()
该构造方法使用一个和当前系统时间对应的相对时间有关的数字作为种子数，然后使用这个种子数构造Random对象。
public Random(long seed)
该构造方法可以通过制定一个种子数进行创建。
示例代码：
Random r = new Random();
Random r1 = new Random(10);
public int nextInt(int n)：是生成一个介于[0,n)的区间int值，包含0而不包含n
ps:若是相同种子数的Random对象，相同次数生成的随机数字是完全相同的。
本题中：int randomIndex = left + 1 + random.nextInt(right - left);
别人的代码写得更好 自己写的太慢了 也不好
时间复杂度o(n) 需要一些数学分析
空间复杂度o(1)
3.堆
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/partitionfen-er-zhi-zhi-you-xian-dui-lie-java-dai-/
可以运用实现好的堆
或者自己手写堆代码
没看 没写
31 下一个排列
不会写
非常清晰的思路：
https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/
先举一个简单的例子 123456 再举一个稍微复杂的例子 123465
照着思路写的代码
class Solution {
public void nextPermutation(int[] nums) {
int index=-1;
for(int i=nums.length-1;i>0;i--){
if(nums[i]>nums[i-1]){
index=i;
break;
}
}
if(index!=-1){
for(int i=nums.length-1;i>=index && index!=-1;i--){
if(nums[i]>nums[index-1]){
int temp=nums[i];
nums[i]=nums[index-1];
nums[index-1]=temp;
break;
}
}
Arrays.sort(nums,index,nums.length);
}
else{
Arrays.sort(nums);
}
}
}
其实不用设置index，不用在意如果本身就是最大字典序的情况
如下
class Solution {
public void nextPermutation(int[] nums) {
int len = nums.length;
for (int i = len - 1; i > 0; i--) {
if (nums[i] > nums[i - 1]) {
Arrays.sort(nums, i, len);
for (int j = i; j <len; j++) {
if (nums[j] > nums[i - 1]) {
int temp = nums[j];
nums[j] = nums[i - 1];
nums[i - 1] = temp;
return;
}
}
}
}
Arrays.sort(nums);
return;
}
}
55 跳跃游戏
思路1：dfs
遍历每一条路径，只要找到一条可以到达最后一个下标，那就直接结束dfs。
可惜TLE
class Solution {
public boolean canJump(int[] nums) {
return dfs(nums,0);
}
boolean dfs(int[] nums,int index){
int len=nums[index];
//错误代码
// if(len==0){
// return false;
// }
// else if(index==nums.length-1){
// return true;
// }
//注意顺序
//特殊的case [0] 是可以到达末端的。
//而且到达末端了，最后一个下标的可跳跃长度是0也可以，因为我已经到达了！！！
if(index==nums.length-1){
return true;
}
else if(len==0){
return false;
}
//如果找到一条成功的就直接return
boolean flag=false;
for(int i=len;i>0&&!flag;i--){
if(index+i>nums.length-1) continue;
flag=dfs(nums,index+i);
}
return flag;
}
}
利用vistied记录，勉强通过5% 5%
class Solution {
public boolean canJump(int[] nums) {
boolean[] visited=new boolean[nums.length];
return dfs(nums,0,visited);
}
boolean dfs(int[] nums,int index,boolean[] visited){
int len=nums[index];
if(index==nums.length-1){
return true;
}
else if(len==0){
return false;
}
else if(visited[index]) return false;
//如果找到一条成功的就直接return
boolean flag=false;
for(int i=len;i>0&&!flag;i--){
if(index+i>nums.length-1) continue;
flag=dfs(nums,index+i,visited);
}
visited[index]=true;
return flag;
}
}
思路2:贪心 尽可能到达越远的位置
解题思路：
如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。
重点在于 - 遍历的同时更新所能跳到的最远距离：对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离不断更新。
即：初始化最远位置为 0，然后遍历数组，如果当前位置能到达，并且当前位置+跳数>最远位置，就更新最远位置。最后比较最远位置和数组长度。
class Solution {
public boolean canJump(int[] nums) {
int k=0;
for(int i=0;i<nums.length;i++){
if(k<i) return false;
k=Math.max(k,i+nums[i]);
}
return true;
}
}
优化一下
class Solution {
public boolean canJump(int[] nums) {
int k=0;
for(int i=0;i<nums.length;i++){
if(k<i) return false;
k=Math.max(k,i+nums[i]);
if(k>=nums.length-1) return true;
}
return true;
}
}
时间复杂度 O(n)，空间复杂度 O(1)
114 二叉树展开为链表
对于二叉树的题目，无非就以下几种解题思路：
先序遍历（深度优先搜索）
中序遍历（深度优先搜索）（尤其二叉搜索树）
后序遍历（深度优先搜索）
层序遍历（广度优先搜索）（尤其按照层来解决问题的时候）
序列化与反序列化（结构唯一性问题）
根据我们的观察，本题应该是使用深度优先搜索的方式来解决
思路1:
(题目提示说如果可以就原地展开，才突然想到可以利用辅助内存)
先序遍历二叉树，利用队列保存每一个节点的地址。
然后再从根节点修改指针的指向。
但是注意，这道题不可以新建结点来构造链表。因为题目的原意就是改造原二叉树为一个链表。直接在原来的节点上改变指向。
”给你二叉树的根结点 root ，请你将它展开为一个单链表“
class Solution {
public void flatten(TreeNode root) {
Queue<TreeNode> tree = new LinkedList<TreeNode>();
dfs(root,tree);
if(tree.size()>=1) tree.poll();
while(tree.size()>0){
root.right=tree.peek();
root.left=null;
tree.poll();
root=root.right;
}
}
void dfs(TreeNode root,Queue<TreeNode> tree){
if(root==null){
return ;
}
tree.offer(root);
dfs(root.left,tree);
dfs(root.right,tree);
}
}
利用数组保存每一个节点的值
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
preorderTraversal(root, list);
int size = list.size();
for (int i = 1; i < size; i++) {
TreeNode prev = list.get(i - 1), curr = list.get(i);
prev.left = null;
prev.right = curr;
}
}
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
if (root != null) {
list.add(root);
preorderTraversal(root.left, list);
preorderTraversal(root.right, list);
}
}
}
非递归写法，没有理解与实现
涉及到的知识点：# 二叉树的遍历：先序中序后序遍历的递归与非递归实现及层序遍历
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
Deque<TreeNode> stack = new LinkedList<TreeNode>();
//双端队列 继承自queue
TreeNode node = root;
while (node != null || !stack.isEmpty()) {
while (node != null) {
list.add(node);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
int size = list.size();
for (int i = 1; i < size; i++) {
TreeNode prev = list.get(i - 1), curr = list.get(i);
prev.left = null;
prev.right = curr;
}
}
}
时间复杂度空间复杂度 o(n)
思路2:原地展开 空间复杂度o(1)
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/114-er-cha-shu-zhan-kai-wei-lian-biao-by-ming-zhi-/
超级棒
其实是后序遍历：在还没操作节点右子树前，不能破坏该节点的右子树指向。所以采用后序遍历。
class Solution {
public void flatten(TreeNode root) {
if(root == null){
return ;
}
//将根节点的左子树变成链表
flatten(root.left);
//将根节点的右子树变成链表
flatten(root.right);
TreeNode temp = root.right;
//把树的右边换成左边的链表
root.right = root.left;
//记得要将左边置空
root.left = null;
//找到树的最右边的节点
while(root.right != null) root = root.right;
//把右边的链表接到刚才树的最右边的节点
root.right = temp;
}
}
非递归写法：
class Solution {
public void flatten(TreeNode root) {
Stack<TreeNode> stack = new Stack();
while (root != null || !stack.isEmpty()){
while (root != null){
stack.push(root);
root = root.left;
}
if (!stack.isEmpty()){
TreeNode node = stack.pop();
TreeNode tmp = node.right;
node.right = node.left;
node.left = null;
while(node.right != null) node = node.right;
node.right = tmp;
root = tmp;
}
}
}
}
思考为什么要用后序遍历？
看看：
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--26/
（解法2、3）
