/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
private ListNode mergerList(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null){
if (l1.val > l2.val) {
cur.next = l2;
l2 = l2.next;
} else {
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode fast = head;
ListNode slow = head;
ListNode pre = null;
while (fast != null && fast.next != null){
fast = fast.next.next;
pre = slow;
slow = slow.next;
}
if (pre != null) pre.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return mergerList(l1, l2);
}
}
class Solution {
private void swap(String[] strs, int i, int j) {
String temp = strs[i];
strs[i] = strs[j];
strs[j] = temp;
}
private int commpare(String o1, String o2) {
String str1 = o1 + o2;
String str2 = o2 + o1;
return str1.compareTo(str2);
}
private int partion(String[] strs, int left, int right) {
String pv = strs[right];
int j = left;
for (int i = left; i < right; i++){
if (commpare(strs[i], pv) < 0) {
swap(strs, j, i);
j++;
}
}
swap(strs, j, right);
return j;
}
private void quickSort(String[] strs, int left, int right) {
if (left >= right) return;
int pi = partion(strs, left, right);
quickSort(strs, left, pi - 1);
quickSort(strs, pi + 1, right);
}
public String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++){
strs[i] = nums[i] + "";
}
quickSort(strs, 0, strs.length - 1);
StringBuilder res = new StringBuilder();
for (int i = strs.length - 1; i >= 0; i--) {
res.append(strs[i]);
}
String result = res.toString();
if (result.charAt(0) == '0') result = "0";
return result;
}
}
class Solution {
public String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = nums[i] + "";
}
Arrays.sort(strs, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
StringBuilder res = new StringBuilder();
for (String str:strs){
res.append(str);
}
String result = res.toString();
if (result.charAt(0) == '0') result = "0";
return result;
}
}
class Solution {
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private int partition(int[] nums, int left, int right) {
Random random = new Random();
int ranIndex = random.nextInt(right - left + 1) + left;
swap(nums, ranIndex, right);
int pv = nums[right];
int j = left;
for (int i = left; i < right; i++){
if (nums[i] < pv) {
swap(nums, i, j);
j++;
}
}
swap(nums, j, right);
return j;
}
private int findKthLargest(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
if (left > right) return -1;
int pi = partition(nums, left, right);
if (pi == k) return nums[pi];
else if (pi > k) return findKthLargest(nums, left, pi - 1, k);
else return findKthLargest(nums, pi + 1, right, k);
}
public int findKthLargest(int[] nums, int k) {
int length = nums.length;
return findKthLargest(nums, 0,length - 1, length - k);
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)-> o1 - o2);
for (int i = 0; i < nums.length; i++) {
queue.offer(nums[i]);
if (queue.size() > k) {
queue.poll();
}
}
return queue.poll();
}
}
class Solution {
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private int partition(int[] nums, int left, int rigth) {
Random random = new Random();
int ranIndex = random.nextInt(rigth - left + 1) + left;
swap(nums, ranIndex, left);
int pv = nums[left];
int i = left;
int j = rigth;
while (i < j) {
while (i < j && nums[j] > pv) {
j--;
}
while (i < j && nums[i] <= pv) {
i++;
}
swap(nums, i, j);
}
swap(nums, left, i);
return i;
}
private int findKthLargest(int[] nums, int left, int rigth, int k) {
if (left == rigth) return nums[left];
if (left > rigth) return -1;
int pi = partition(nums, left, rigth);
if (pi == k) return nums[pi];
else if (pi > k) return findKthLargest(nums, left, pi - 1, k);
else return findKthLargest(nums, pi + 1, rigth, k);
}
public int findKthLargest(int[] nums, int k) {
int length = nums.length;
return findKthLargest(nums, 0, length - 1, length - k);
}
}
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
}
//最小堆
PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2)->o1[1] - o2[1]);
for (Map.Entry<Integer, Integer> entry:hashMap.entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
queue.offer(new int[]{key, value});
if (queue.size() > k) queue.poll();
}
int[] result = new int[k];
for (int i = result.length - 1; i >= 0; i--) {
result[i] = queue.poll()[0];
}
return result;
}
}
class Solution {
private void swap(ArrayList<int[]> list, int i, int j) {
int[] temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
private int partition(ArrayList<int[]> list, int left, int rigth) {
Random random = new Random();
int ranIndex = random.nextInt(rigth - left + 1) + left;
swap(list, ranIndex, rigth);
int pv = list.get(rigth)[1];
int j = left;
for (int i = left; i < rigth; i++){
if (list.get(i)[1] < pv) {
swap(list, i, j);
j++;
}
}
swap(list, j, rigth);
return j;
}
private int[] topKFrequent(ArrayList<int[]> list, int left, int rigth, int k) {
if (left == rigth) {
int[] result = new int[list.size() - k];
for (int i = 0; i < result.length; i++) {
result[i] = list.get(left + i)[0];
}
return result;
}
int pi = partition(list, left, rigth);
if (pi == k) {
int[] result = new int[list.size() - k];
// System.out.println(result.length);
for (int i = 0; i < result.length; i++) {
result[i] = list.get(pi + i)[0];
}
return result;
} else if (pi > k) return topKFrequent(list, left, pi - 1, k);
else return topKFrequent(list, pi + 1, rigth, k);
}
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++){
hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
}
ArrayList<int[]> list = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry:hashMap.entrySet()) {
list.add(new int[]{entry.getKey(), entry.getValue()});
// System.out.println(entry.getKey() + " " + entry.getValue());
}
int length = list.size();
return topKFrequent(list, 0, length - 1, length - k);
}
}
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < strs.length; i++) {
strs[i] = nums[i] + "";
}
Arrays.sort(strs, (o1, o2)->(o1 + o2).compareTo(o2 + o1));
StringBuilder res = new StringBuilder();
for (String str:strs) {
res.append(str);
}
String result = res.toString();
// if (result.charAt(0) == '0') result = "0";
return result;
}
}
网友评论