Algorithm多次写的 一些代码有关的问题 关于排序的问题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 ①①Queue<Integer> queue = new PriorityQueue <>((aa, bb) -> aa - bb); ①②Queue<Integer> queue1 = new PriorityQueue <>(new Comparator <Integer>() { @Override public int compare (Integer o1, Integer o2) { return 0 ; } }); ②②TreeMap<Integer, Integer> treeMap = new TreeMap <>(new Comparator <Integer>() { @Override public int compare (Integer o1, Integer o2) { return 0 ; } }); ③①TreeSet<Integer> treeSet = new TreeSet <>((aa, bb) -> aa - bb); public class MyComparator implements Comparator <Integer> { @Override public int compare (Integer o1, Integer o2) { return 0 ; } } Integer[] aa = new Integer []; Arrays.sort(aa,new Comparator <Integer>() { @Override public int compare (Integer o1, Integer o2) { return (int )(o2-o1); } }); int [] temp = queue.pollFirst();Arrays.sort(temp); for (int i = 0 ; i < temp.length / 2 ; i++) { int tempTemp = temp[i]; temp[i] = temp[temp.length - i - 1 ]; temp[temp.length - i - 1 ] = tempTemp; } List<Integer> list = new ArrayList <>(); Collections.sort(list, new Comparator <Integer>() { @Override public int compare (Integer o1, Integer o2) { return 0 ; } }); Queue<Double> queue = new PriorityQueue <>((a, b) -> { if (a.equals(b)) { return 0 ;} else if (b > a) { return 1 ;} return -1 ; });
关于TreeSet和TreeMap
floor(E e) 方法返回在这个集合中小于或者等于给定元素的最大元素,如果不存在这样的元素,返回null. ceiling(E e) 方法返回在这个集合中大于或者等于给定元素的最小元素,如果不存在这样的元素,返回null.
lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的元素,如果不存在这样的元素,则返回 null。
注意:
1 声明的时候要用TreeSet,而不能用Set
2 取结果的时候用包装类型取,因为如果返回null,那么拆箱失败会nullpointexception
1 2 TreeSet<Integer> set = new TreeSet <>(); set.ceiling(23 );
TreeSet的first()和last()
ceilingKey(K key), 返回大于或等于给定键的最小键,如果没有这样的键,则null
floorKey(K key), 返回小于或等于给定键的最大键,如果没有这样的键,则null
注意:
1 声明的时候需要使用TreeMap,而不能只是Map
2 取结果的时候用包装类型取,因为如果返回null,那么拆箱失败会nullpointexception
1 2 3 TreeMap<Integer, Integer> map = new TreeMap <>(); map.ceilingKey(213 ); Map.Entry<Integer, Integer> integerIntegerEntry = map.ceilingEntry(123 );
关于Scanner的next()和nextLine()的问题
next(),一定要读取到有效字符后才可以结束输入,对输入有效字符之前遇到的空格键、Tab键或Enter键等结束符,next()方法会自动将其去掉,只有在输入有效字符之后,next()方法才将其后输入的空格键、Tab键或Enter键等视为分隔符或结束符。完整标记的前后是与分隔模式匹配的输入信息所以next()不能得到带空格的字符串。
nextLine(),遇到回车是才结束,所以可以得到带空格的字符串。
在输入一个int类型的数字之后,如果后边采用nextLine的话,最后打印结果发现会少一个字符,原因是在你使用nextInt的时候后边有一个换行符,没有接受,前边的int变量只是接受了你输入的数值,所以在你继续输入nextLine之后,会自动读取还未读取的换行,所以会导致后边的结果有一列为空,所以此时你需要多输入一个NextLine把未接受的换行符接收到。
所以以后最好统一使用nextLine,但是如果前面nextInt读取了一个数字,那么需要先nextLine一下将换行符读取掉,然后在nextLine读取这一行字符串。
5 RBBRB
1 2 3 4 5 Scanner sc = new Scanner (System.in);int n = sc.nextInt();sc.nextLine(); String str = sc.nextLine();
但是如果要根据空格读取,那还是得用next()函数的
关于拷贝 1 2 3 4 5 6 7 8 9 char [] temp = Arrays.copyOfRange(chars, curIndex, i + 1 );Arrays.copyOf(chars, 2 ); curAns.add(new String (temp)); Arrays.fill(temp, '9' ); Arrays.fill(temp, 0 , 2 , '9' ); String s = "132" ;String substring = s.substring(0 , 2 );
问题 1、Deque<int[]>中存放两次temp的,深浅拷贝问题
2、java中集合存储的元素,是对象的引用。
3、int[]这个数组也是对象的,所以说前面的Comparator的时候对int[]
是不能排序的,对int[][]
可以排序的,因为Comparator的时候里面的每一个元素是iny[]
,那么也就是对象了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Deque<List<Integer>> deque = new ArrayDeque <>(); List<Integer> list = new ArrayList <>(); list.add(2 ); deque.add(list); list.set(0 , 123 ); System.out.println(deque.peekFirst().get(0 )); Deque<List<Integer>> deque = new ArrayDeque <>(); List<Integer> list = new ArrayList <>(); list.add(2 ); deque.add(new ArrayList <>(list)); list.set(0 , 123 ); System.out.println(deque.peekFirst().get(0 ));
二叉树根节点到叶子所有路径 dfs + 回溯 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 import java.util.*;public class 二叉树根到节点所有路径 { public static void main (String[] args) { TreeNode root = new TreeNode (3 ); root.left = new TreeNode (5 ); root.right = new TreeNode (6 ); root.left.right = new TreeNode (234 ); root.right.left = new TreeNode (12 ); root.right.right = new TreeNode (2 ); new 二叉树根到节点所有路径().new Solution ().solve(root); } private static class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val) { this .val = val; } } public class Solution { public void solve (TreeNode root) { List<List<Integer>> ans = new ArrayList <>(); dfsTrace(root, new ArrayList <>(), ans); for (List<Integer> path : ans) { for (Integer e : path) { System.out.print(e + " " ); } System.out.println(); } } public void dfsTrace (TreeNode node, List<Integer> path, List<List<Integer>> ans) { if (node.left == null && node.right == null ) { path.add(node.val); ans.add(new ArrayList <>(path)); path.remove(path.size() - 1 ); return ; } path.add(node.val); if (node.left != null ) { dfsTrace(node.left, path, ans); } if (node.right != null ) { dfsTrace(node.right, path, ans); } path.remove(path.size() - 1 ); } } }
链表排序 归并排序 反转M~N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public ListNode reverseBetween (ListNode head, int left, int right) { if (left == right) { return head; } ListNode dummyNode = new ListNode (-1 ); dummyNode.next = head; ListNode pre = dummyNode; int count = 1 ; while (count != left) { pre = pre.next; count += 1 ; } ListNode leftNode = pre.next; ListNode curNode = pre.next; ListNode nextNode = curNode.next; while (count != right) { ListNode nextnextNode = nextNode.next; nextNode.next = curNode; curNode = nextNode; nextNode = nextnextNode; count += 1 ; } pre.next = curNode; leftNode.next = nextNode; return dummyNode.next; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public ListNode reverseList (ListNode head) { ListNode prev = null ; ListNode curNode = head; while (curNode != null ) { ListNode next = curNode.next; curNode.next = prev; prev = curNode; curNode = next; }9 - return prev; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public int getNext (int num) { int ans = 0 ; while (num != 0 ) { int temp = num % 10 ; ans += temp * temp; num /= 10 ; } return ans; } public boolean isHappy (int n) { int slow = n, fast = getNext(n); while (fast != 1 && slow != fast) { slow = getNext(slow); fast = getNext(getNext(fast)); } if (fast == 1 ) { return true ; } return false ; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 class Solution { public int lengthOfLIS (int [] nums) { int n = nums.length; int [] dp = new int [n]; Arrays.fill(dp, 1 ); for (int i = 1 ; i < n; i++) { for (int j = 0 ; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j]+1 ); } } } return Arrays.stream(dp).max().getAsInt(); } } class Solution { public int lengthOfLIS (int [] nums) { int n = nums.length; int [] dp = new int [n]; int [] g = new int [n+1 ]; int ans = 1 ; Arrays.fill(dp, 1 ); g[1 ] = nums[0 ]; for (int i = 1 ; i < n; i++) { int left = 1 , right = ans; while (left <= right) { int mid = left + (right - left >> 1 ); if (g[mid] == nums[i]) { right = mid - 1 ; break ; } else if (g[mid] > nums[i]) { right = mid - 1 ; } else { left = mid + 1 ; } } ans = Math.max(ans, right + 1 ); g[right + 1 ] = nums[i]; } return ans; } }
使用归并
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 class Solution { public ListNode sortList (ListNode head) { return sortList(head, null ); } public ListNode sortList (ListNode head, ListNode tail) { if (head == null ) { return head; } if (head.next == tail) { head.next = null ; return head; } ListNode slow = head, fast = head; while (fast != tail) { fast = fast.next; slow = slow.next; if (fast != tail) { fast = fast.next; } } ListNode left = sortList(head, slow); ListNode right = sortList(slow, tail); return merge(left, right); } public ListNode merge (ListNode node1, ListNode node2) { ListNode dummyNode = new ListNode (-1 ); ListNode node = dummyNode; while (node1 != null && node2 != null ) { if (node1.val < node2.val) { node.next = node1; node1 = node1.next; } else { node.next = node2; node2 = node2.next; } node = node.next; } if (node1 != null ) { node.next = node1; } if (node2 != null ) { node.next = node2; } return dummyNode.next; } } class Solution { public ListNode sortList (ListNode head) { return sortList(head, null ); } public ListNode sortList (ListNode head, ListNode tail) { if (head == null ) { return null ; } if (head.next == tail) { head.next = null ; return head; } ListNode slow = head, fast = head; while (fast != tail && fast.next != tail) { slow = slow.next; fast = fast.next.next; } ListNode leftHead = sortList(head, slow); ListNode rightHead = sortList(slow, tail); return merge(leftHead, rightHead); } public ListNode merge (ListNode node1, ListNode node2) { ListNode dummyNode = new ListNode (-1 ); ListNode node = dummyNode; while (node1 != null && node2 != null ) { if (node1.val < node2.val) { node.next = node1; node1 = node1.next; } else { node.next = node2; node2 = node2.next; } node = node.next; } if (node1 != null ) { node.next = node1; } if (node2 != null ) { node.next = node2; } return dummyNode.next; } }
LRU缓存 最近最久未使用 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 class LRUCache { class LRULinkedNode { int key; int val; LRULinkedNode pre; LRULinkedNode next; public LRULinkedNode () {} public LRULinkedNode (int key, int val) { this .key = key; this .val = val; } } LRULinkedNode head, tail; int capacity; Map<Integer, LRULinkedNode> map = new HashMap <>(); public LRUCache (int capacity) { this .capacity = capacity; head = new LRULinkedNode (); tail = new LRULinkedNode (); head.next = tail; tail.pre = head; } public int get (int key) { if (map.containsKey(key)) { LRULinkedNode node = map.get(key); moveToTail(node); return node.val; } return -1 ; } public void put (int key, int value) { if (map.containsKey(key)) { LRULinkedNode node = map.get(key); node.val = value; moveToTail(node); } else { LRULinkedNode newNode = new LRULinkedNode (key, value); map.put(key, newNode); addToTail(newNode); } if (capacity < map.size()) { removeHead(); } } public void removeHead () { LRULinkedNode del = head.next; head.next = head.next.next; head.next.pre = head; map.remove(del.key); } public void addToTail (LRULinkedNode newNode) { LRULinkedNode pre = tail.pre; pre.next = newNode; newNode.pre = pre; tail.pre = newNode; newNode.next = tail; } public void moveToTail (LRULinkedNode node) { node.pre.next = node.next; node.next.pre = node.pre; addToTail(node); } }
【C++】十大排序(冒泡、选择、插入、希尔、归并、快排、堆、计数、桶、基数)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public int [] sortArray(int [] nums) { quickSort(nums, 0 , nums.length-1 ); return nums; } public void quickSort (int [] nums, int start, int end) { if (start >= end) { return ; } int randomLeft = new Random ().nextInt(end - start + 1 ) + start; swap(nums, start, randomLeft); int base = nums[start]; int left = start, right = end; while (left < right) { while (right > left && nums[right] >= base) { right -= 1 ; } nums[left] = nums[right]; while (right > left && nums[left] <= base) { left += 1 ; } nums[right] = nums[left]; } nums[left] = base; quickSort(nums, start, left - 1 ); quickSort(nums, right + 1 , end); } public void swap (int [] nums, int a, int b) { int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public class Solution { public boolean hasCycle (ListNode head) { if (head == null || head.next == null ) { return false ; } ListNode slow = head; ListNode fast = head.next; while (fast != slow) { if (fast == null || fast.next == null ) { return false ; } slow = slow.next; fast = fast.next.next; } return true ; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 public class Solution { public ListNode detectCycle (ListNode head) { if (head == null || head.next == null ) { return null ; } ListNode slow = head, fast = head; while (true ) { if (fast == null || fast.next == null ) { return null ; } fast = fast.next.next; slow = slow.next; if (fast == slow) { break ; } } fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return slow; } }
二叉树的遍历 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 class Solution { public List<Integer> preorderTraversal (TreeNode root) { if (root == null ) { return new ArrayList <Integer>(); } List<Integer> ans = new ArrayList <>(); Deque<TreeNode> stack = new ArrayDeque <>(); stack.offerLast(root); while (!stack.isEmpty()) { TreeNode node = stack.pollLast(); ans.add(node.val); if (node.right != null ) { stack.offerLast(node.right); } if (node.left != null ) { stack.offerLast(node.left); } } return ans; } } class Solution { public List<Integer> inorderTraversal (TreeNode root) { if (root == null ) { return new ArrayList <>(); } List<Integer> ans = new ArrayList <>(); Deque<TreeNode> stack = new ArrayDeque <>(); while (!stack.isEmpty() || root != null ) { while (root != null ) { stack.offerLast(root); root = root.left; } root = stack.pollLast(); ans.add(root.val); root = root.right; } return ans; } } class Solution { public List<Integer> postorderTraversal (TreeNode root) { if (root == null ) { return new ArrayList <>(); } List<Integer> ans = new ArrayList <>(); Deque<TreeNode> stack = new ArrayDeque <>(); TreeNode pre = null ; while (!stack.isEmpty() || root != null ) { while (root != null ) { stack.offerLast(root); root = root.left; } root = stack.pollLast(); if (root.right == null || root.right == pre) { ans.add(root.val); pre = root; root = null ; } else { stack.offerLast(root); root = root.right; } } return ans; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution { public double myPow (double x, int n) { double ans = 1.0 ; double con = x; boolean flag = false ; long N = n; if (N < 0 ) { flag = true ; N = -N; } while (N > 0 ) { if (N % 2 == 1 ) { ans *= con; } con *= con; N /= 2 ; } return !flag ? ans : 1.0 / ans; } }