YYC

Coming

2.3万

chy_7

Hyper
acw学徒
loveka
Tingting

carotwang

luyunix
PDX
measukidesu

Siriuss

zombotany
Bug-Free

YYC
2个月前
class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
return quickSort(nums, 0, n - 1, n - k + 1);
}

int quickSort(int[] nums, int l, int r, int k) {
if (l == r) return nums[l];

int x = nums[l + r >>> 1];
int i = l - 1, j = r + 1;
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) swap(nums, i, j);
}
int sl = j - l + 1;
if (k <= sl) return quickSort(nums, l, j, k);
else return quickSort(nums, j + 1, r, k - sl);
}

void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}


YYC
2个月前
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) return false;
int n = matrix.length, m = matrix[0].length;
int l = 0, r = n * m - 1;
while (l < r) {
int mid = l + r >>> 1;
if (matrix[mid/m][mid%m] >= target) r = mid;
else l = mid + 1;
}
return matrix[l/m][l%m] == target;
}
}


YYC
2个月前
class Solution {
public int[] searchRange(int[] nums, int t) {
int[] ans = new int[2];
int n = nums.length;
if (n == 0) return new int[]{-1, -1};
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >>> 1;
if (nums[mid] >= t) r = mid;
else l = mid + 1;
}
ans[0] = nums[l] == t ? l : -1;
l = 0; r = n - 1;
while (l < r) {
int mid = l + r + 1 >>> 1;
if (nums[mid] <= t) l = mid;
else r = mid - 1;
}
ans[1] = nums[r] == t ? r : -1;
return ans;
}
}


YYC
2个月前
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >>> 1;
if (nums[mid] < nums[0]) r = mid;
else l = mid + 1;
}
return r == n - 1 && nums[l] > nums[0] ? nums[0] : nums[l];
}
}


YYC
2个月前
class Solution {
public int singleNonDuplicate(int[] nums) {
int n = nums.length;
int l = 0, r = n >>> 1;
while (l < r) {
int mid = l + r >>> 1;
if (nums[mid * 2] != nums[mid * 2 + 1]) r = mid;
else l = mid + 1;
}
return nums[l * 2];
}
}


YYC
2个月前
class Solution {
public boolean isPerfectSquare(int num) {
int l = 1, r = num;
while (l < r) {
int mid = l + r + 1 >>> 1;
if (mid <= num / mid) l = mid;
else r = mid - 1;
}
return r * r == num;
}
}


YYC
2个月前
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
int count, ans;
public int kthSmallest(TreeNode root, int k) {
dfs(root, k);
return ans;
}

void dfs(TreeNode root, int k) {
if (root == null) return;
dfs(root.left, k);
if (++count == k) {
ans = root.val;
return;
}
dfs(root.right, k);
}
}


YYC
2个月前
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return dfs(root, p, q);
}

TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
int val = root.val;
if (val < p.val && val > q.val) return root;
if (val < p.val && val < q.val) return dfs(root.right, p, q);
if (val > p.val && val > q.val) return dfs(root.left, p, q);
return root;
}
}


YYC
2个月前
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
if (root == null) return ans;
ArrayDeque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
int max = Integer.MIN_VALUE;
while (size-- > 0) {
TreeNode cur = q.poll();
max = Math.max(max, cur.val);
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
}
return ans;
}
}


YYC
2个月前
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
int ans = 0, maxDepth = 0;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 1);
return ans;
}

void dfs(TreeNode root, int u) {
if (root == null) return;
if (u > maxDepth) {
ans = root.val;
maxDepth = u;
}
dfs(root.left, u + 1);
dfs(root.right, u + 1);
}
}