# 002-arithmetic-02 ## 算法基础面试题(二) ## 数据范围 ### 整数类型 byte：8 位，范围为 -128 到 127 short：16 位，范围为 -32,768 到 32,767 3万 int：32 位，范围为 -2^31 到 2^31-1 21亿， 4bytes,100w int占4M，1亿int 400M. long：64 位，范围为 -2^63 到 2^63-1 4G内存可以表示340亿bits， 1G内存可以表示85亿bits 100w int占4M， 1亿int 400M. 1亿bytes 100M, 4亿bytes 400M。 1亿bits 12M，4亿bits 48M内存 ### 浮点类型 float：32 位，范围为 IEEE 754 单精度浮点数表示的取值范围。4bytes,100w float占4M，1亿 400M double：64 位，范围为 IEEE 754 双精度浮点数表示的取值范围。 ### 字符类型 char：16 位 Unicode 字符，范围为 0 到 65,535。 6万 java中理论上一个字符占用两个字节 **Unicode只是一个编码规范，目前实际实现的unicode编码只要有三种：UTF-8,UCS-2和UTF-16，三种unicode字符集之间可以按照规范进行转换。** UTF-8最大的一个特点，就是它是一种**变长**的编码方式。它可以使用1\~6个字节表示一个符号，根据不同的符号而**变化字节长度**。 占2个字节的：〇（〇有两个读音 xīng líng，（一） [xīng](https://www.zhihu.com/search?q=xīng\&search_source=Entity\&hybrid_search_source=Entity\&hybrid_search_extra={"sourceType"%3A"answer"%2C"sourceId"%3A2289164118}) 同“星”；（二） líng 同“零”。） 占3个字节的：基本等同于GBK，含21000多个汉字 占4个字节的：中日韩超大[字符集](https://www.zhihu.com/search?q=字符集\&search_source=Entity\&hybrid_search_source=Entity\&hybrid_search_extra={"sourceType"%3A"answer"%2C"sourceId"%3A2289164118})里面的汉字，有5万多个 一个utf8数字占1个字节 一个utf8英文字母占1个字节 ### 布尔类型 boolean：表示逻辑值，只能取 true 或 false。 ## java.lang.Integer *MIN\_VALUE* = 0x80000000 -2^31 *MAX\_VALUE* = 0x7fffffff 2^31-1 Integer.toBinaryString(int)方法将一个整数转换成二进制表示的字符串 Integer.parseInt(binaryString, 2) 把一个二进制字符串转换成为整数 Integer.reverse(123) ---按位反转整数 ```java public class Solution { // you need treat n as an unsigned value public int reverseBits(int n) { int rev =0; for(int i=0; i<32 && n!=0; i++){ rev |=(n&1)<<(31-i); n >>>=1; } return rev; } } ``` ```java public class Solution { private static final int M1 = 0x55555555; // 01010101010101010101010101010101 private static final int M2 = 0x33333333; // 00110011001100110011001100110011 private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111 private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111 public int reverseBits(int n) { //交换不同的位置 n = n >>> 1 & M1 | (n & M1) << 1; n = n >>> 2 & M2 | (n & M2) << 2; n = n >>> 4 & M4 | (n & M4) << 4; n = n >>> 8 & M8 | (n & M8) << 8; return n >>> 16 | n << 16; } } ``` Integer.bitCount(122) --统计int中1的个数 ```java public static int bitCount(int i) { // HD, Figure 5-2 i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; } ``` Integer.highestOneBit(123) ---最高位的1的值 ```java public static int highestOneBit(int i) { // 先把i最高位1以下的所有位都变成1。折半法 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); //用移位运算得到最高位的i return i - (i >>> 1); } ``` Integer.*lowestOneBit*(3) ---最低位的1的值 ```java public static int lowestOneBit(int i) { // HD, Section 2-1 return i & -i; } ``` Integer.*numberOfLeadingZeros*(3) ---前面0的个数 ```java public static int numberOfLeadingZeros(int i) { // HD, Figure 5-6 if (i == 0) return 32; int n = 1; //折半法 if (i >>> 16 == 0) { n += 16; i <<= 16; } if (i >>> 24 == 0) { n += 8; i <<= 8; } if (i >>> 28 == 0) { n += 4; i <<= 4; } if (i >>> 30 == 0) { n += 2; i <<= 2; } //如果前面条件都不满足 n -= i >>> 31; return n; } ``` Integer.numberOfTrailingZeros(3) ---后面0的个数 ```java public static int numberOfTrailingZeros(int i) { // HD, Figure 5-14 int y; if (i == 0) return 32; int n = 31; y = i <<16; if (y != 0) { n = n -16; i = y; } y = i << 8; if (y != 0) { n = n - 8; i = y; } y = i << 4; if (y != 0) { n = n - 4; i = y; } y = i << 2; if (y != 0) { n = n - 2; i = y; } return n - ((i << 1) >>> 31); } ``` ## java.util.HashMap map.getOrDefault(a,b); map.remove(key); map.containsKey(key) map.values() ## java.util.HashSet 把List转成Set List list = Arrays.asList("apple", "orange", "banana"); Set set = new HashSet<>(list); List list = Arrays.asList("apple", "orange", "banana"); Set set = new HashSet<>(); set.addAll(list); ## java.util.List list.add("apple"); // 在末尾添加元素 list.add(0, "banana"); list.remove("apple"); // 删除元素"apple" list.remove(1); list.clear(); //list转数组： list.toArray(new int\[0]) list.toArray(new int\[0]\[2]) //list to数组字符串: list.toString() \[1, 2] ## Array \[]: int\[] array = {1, 2, 3, 4, 5}; int length = array.length; ## java.util.Arrays List wordList = Arrays.asList(s.split("\\\s+")); ----数组变成list 升序Arrays.sort 降序:Arrays.sort(arr, (o1, o2) -> o2 - o1); ---注意如果要对sort进行反向排序，要确保arr不是基础类型的数组，必须是对象类型的数组。 如果对int进行排序,两个int的减法运算可能溢出，需要将其转换成long来计算，compare的返回值是1或者-1. Arrays.sort(points, (a, b)-> (long)a\[1]-(long)b\[1]>0?1:-1) ------int\[]\[]是可以的，但是int\[]不行。 Arrays.equals(str1,str2) ---两个数组相等 System.arraycopy(src, srcPos, dest, destPos, length) ---拷贝数组 byte\[] partArray = Arrays.copyOfRange(fullArray, start, end) ---end不包含，长度可以大于原始数组的长度 byte\[] mergedArray = Arrays.copyOf(byteArray1, byteArray1.length + byteArray2.length) ---拷贝数组,长度可以大于原始数组的长度 Arrays.fill(dp, max) ---填充数组 Integer\[] a = new Integer\[]{1,2,35,34,21}; Arrays.toString(a) ----数组转成字符串。\[35, 34, 21, 2, 1] byte转字符：直接用(char)a byte数组转字符串：byte\[] byteArray = {65, 66, 67}; String result = new String(byteArray)； 打印数组 Arrays.*stream*(arr).forEach(System.*out*::println); ## String char\[] str1 = s.toCharArray() ---字符串转成char数组 s.charAt(1) str.substring(0, 3) ----不包含end str.length() int转String：String s = String.valueOf(x); String.join(" ",d) ----合并集合，变成字符串。只要是Iterable的都可以join。比如List，Set，但是不能是数组 mainString.contains(subString) "abc".indexOf("a") "abc".lastIndexOf("a") ## StringBuffer ans.reverse() ---反转字符 ans.toCharArray() ---转换成char数组 修改其中的某个字符 StringBuffer sb = new StringBuffer(curr); sb.setCharAt(j, keys\[k]); String next = sb.toString(); ## java.util.Random ``` new Random().nextInt(10) ``` ## java.util.Collections ```java List intList = new ArrayList<>(); intList.add(12); intList.add(15); Collections.swap(intList, 0, 1); //swap list里面的两个元素 ``` 反转数组： ```java Integer[] arr = {1, 2, 3, 4, 5}; Collections.reverse(Arrays.asList(arr)); //不能反转数组，需要把数组转换成list, 最后arr数组的值被反转 ``` 1. **排序 (`sort`)：** ```java List numbers = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9, 2, 6, 5)); Collections.sort(numbers); System.out.println(numbers); // 输出 [1, 1, 2, 3, 4, 5, 5, 6, 9] ``` 2. **反转 (`reverse`)：** ```java List names = new ArrayList<>(List.of("Alice", "Bob", "Charlie", "David")); Collections.reverse(names); System.out.println(names); // 输出 [David, Charlie, Bob, Alice] ``` 3. **打乱 (`shuffle`)：** ```java List letters = new ArrayList<>(List.of('A', 'B', 'C', 'D', 'E')); Collections.shuffle(letters); System.out.println(letters); // 输出可能为 [C, A, B, E, D] ``` 4. **查找最大值和最小值 (`max` 和 `min`)：** ```java List prices = new ArrayList<>(List.of(19.99, 29.99, 15.99, 39.99, 9.99)); double maxPrice = Collections.max(prices); double minPrice = Collections.min(prices); System.out.println("Max Price: " + maxPrice); // 输出 Max Price: 39.99 System.out.println("Min Price: " + minPrice); // 输出 Min Price: 9.99 ``` 5. **替换所有元素 (`replaceAll`)：** ```java List words = new ArrayList<>(List.of("apple", "banana", "cherry")); Collections.replaceAll(words, "banana", "orange"); System.out.println(words); // 输出 [apple, orange, cherry] ``` 6. **查找元素位置 (`binarySearch`)：在列表中进行二分查找**，该列表必须是按升序排序的，如果未找到，则返回一个负值 ```java List sortedNumbers = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6, 7, 8, 9)); //必须是排序数组 int index = Collections.binarySearch(sortedNumbers, 5); System.out.println("Index of 5: " + index); // 输出 Index of 5: 4 ``` ## Character ```java Character.isDigit, Character.isLetterOrDigit, Character.isLetter, Character.toLowerCase ``` ## java.util.Stack,PriorityQueue ```java Stack stack = new Stack<>(); stack.push(1); int top = stack.peek(); int poppedElement = stack.pop(); PriorityQueue minHeap = new PriorityQueue<>(k); ``` ## Deque ```java Deque stack = new LinkedList(); Deque deque = new ArrayDeque(); add/remove源自集合，所以添加到队尾，从队头删除； offer/poll源自队列（先进先出 => 尾进头出），所以添加到队尾，从队头删除； push/pop源自栈（先进后出 => 头进头出），所以添加到队头，从队头删除； offerFirst/offerLast/pollFirst/pollLast源自双端队列（两端都可以进也都可以出），根据字面意思，offerFirst添加到队头，offerLast添加到队尾，pollFirst从队头删除，pollLast从队尾删除。 总结： add/offer/offerLast添加队尾，三个方法等价； push/offerFirst添加队头，两个方法等价。 remove/pop/poll/pollFirst删除队头，四个方法等价； pollLast删除队尾。 ``` ## ConcurrentLinkedDeque(线程安全) ```java ConcurrentLinkedDeque deque = new ConcurrentLinkedDeque<>(); deque.add("element1"); deque.addLast("element2"); // 添加到队列的末尾 deque.addFirst("element3"); // 添加到队列的头部 String firstElement = deque.getFirst(); // 获取队列的头部元素，如果不存在则返回null String lastElement = deque.getLast(); // 获取队列的尾部元素，如果不存在则返回null deque.removeFirst(); // 删除队列的头部元素 deque.removeLast(); // 删除队列的尾部元素 if (deque.isEmpty()) { // 队列为空时执行操作 } for (String element : deque) { // 遍历队列中的每个元素并执行操作 } ``` ## LinkedList, ArrayDeque, Queue ## 链表 反转链表： ```java //迭代反转 private void reverseLinkedList(ListNode head) { // 也可以使用递归反转一个链表 ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } } //迭代反转两个具体的节点 public ListNode[] myReverse(ListNode head, ListNode tail) { ListNode prev = tail.next; ListNode cur = head; while (prev != tail) { ListNode nex = cur.next; cur.next = prev; prev = cur; cur = nex; } return new ListNode[]{tail, head}; } //递归反转 ListNode reverse(ListNode head) { if (head.next == null) return head; ListNode last = reverse(head.next); head.next.next = head; head.next = null; return last; } //反转前n个节点 ListNode successor = null; // 后驱节点 // 反转以 head 为起点的 n 个节点，返回新的头结点 ListNode reverseN(ListNode head, int n) { if (n == 1) { // 记录第 n + 1 个节点 successor = head.next; return head; } // 以 head.next 为起点，需要反转前 n - 1 个节点 ListNode last = reverseN(head.next, n - 1); head.next.next = head; // 让反转之后的 head 节点和后面的节点连起来 head.next = successor; return last; } //反转m-n之间的节点: ListNode reverseBetween(ListNode head, int m, int n) { // base case if (m == 1) { return reverseN(head, n); } // 前进到反转的起点触发 base case---只到m=1 head.next = reverseBetween(head.next, m - 1, n - 1); return head; } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.flydean.com/www.flydean.com/docs/interview/arithmetic/more/002-arithmetic-02.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.