算法基础面试题(二)
数据范围
整数类型
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 同“星”；（二） líng 同“零”。）
占3个字节的：基本等同于GBK，含21000多个汉字
占4个字节的：中日韩超大字符集里面的汉字，有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) ---按位反转整数
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;
}
}
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的个数
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的值
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的值
public static int lowestOneBit(int i) {
// HD, Section 2-1
return i & -i;
}
Integer.numberOfLeadingZeros(3) ---前面0的个数
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的个数
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
Set
List
Set
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
升序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
List<Integer> intList = new ArrayList<>();
intList.add(12);
intList.add(15);
Collections.swap(intList, 0, 1); //swap list里面的两个元素
反转数组：
Integer[] arr = {1, 2, 3, 4, 5};
Collections.reverse(Arrays.asList(arr)); //不能反转数组，需要 把数组转换成list, 最后arr数组的值被反转
-
排序 (
sort)：List<Integer> 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] -
反转 (
reverse)：List<String> names = new ArrayList<>(List.of("Alice", "Bob", "Charlie", "David"));
Collections.reverse(names);
System.out.println(names); // 输出 [David, Charlie, Bob, Alice] -
打乱 (
shuffle)：List<Character> letters = new ArrayList<>(List.of('A', 'B', 'C', 'D', 'E'));
Collections.shuffle(letters);
System.out.println(letters); // 输出可能为 [C, A, B, E, D] -
查找最大值和最小值 (
max和min)：List<Double> 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 -
替换所有元素 (
replaceAll)：List<String> words = new ArrayList<>(List.of("apple", "banana", "cherry"));
Collections.replaceAll(words, "banana", "orange");
System.out.println(words); // 输出 [apple, orange, cherry] -
查找元素位置 (
binarySearch)：在列表中进行二分查找，该列表必须是按升序排序的，如果未找到，则返回一个负值List<Integer> 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
Character.isDigit,
Character.isLetterOrDigit,
Character.isLetter,
Character.toLowerCase
java.util.Stack,PriorityQueue
Stack<Integer> stack = new Stack<>();
stack.push(1);
int top = stack.peek();
int poppedElement = stack.pop();
PriorityQueue<Float> minHeap = new PriorityQueue<>(k);
Deque
Deque<Character> stack = new LinkedList<Character>();
Deque<Integer> deque = new ArrayDeque<Integer>();
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(线程安全)
ConcurrentLinkedDeque<String> 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
链表
反转链表：
//迭代反转
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;
}
点我查看更多精彩内容:www.flydean.com
