文章目录
一、替换空格
public String replaceSpace(String s) {
StringBuilder stringBuilder = new StringBuilder();
for (char c : s.toCharArray()) {
if(c == ' '){
stringBuilder.append("%20");
}else{
stringBuilder.append(c);
}
}
return stringBuilder.toString();
}
二、从尾到头打印链表
public int[] reversePrint(ListNode head) {
return dfs(head,0);
}
public int[] dfs(ListNode head,int cnt){
if(head == null){
return new int[cnt];
}
int[] arr = dfs(head.next, cnt + 1);
arr[arr.length - cnt - 1] = head.val;
return arr;
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
三、用两个栈实现队列
法一：LinkedList模拟
class CQueue {
LinkedList<Integer> A, B;
public CQueue() {
A = new LinkedList<Integer>();
B = new LinkedList<Integer>();
}
public void appendTail(int value) {
A.addLast(value);
}
public int deleteHead() {
if(!B.isEmpty()) {
return B.removeLast();
}
if(A.isEmpty()) {
return -1;
}
while(!A.isEmpty()) {
B.addLast(A.removeLast());
}
return B.removeLast();
}
}
法二：用原生的Queue
class CQueue{
Queue<Integer> queue = new ArrayDeque<>();
public void appendTail(int value) {
queue.add(value);
}
public int deleteHead() {
if(queue.isEmpty()){
return -1;
}
return queue.poll();
}
}
四、表示数值的字符串
本题使用有限状态自动机。根据字符类型和合法数值的特点，先定义状态，再画出状态转移图，最后编写代码即可。
public boolean isNumber(String s) {
Map[] states = {
new HashMap<Character,Integer>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
new HashMap<Character,Integer>() {{ put('d', 2); put('.', 4); }}, // 1.
new HashMap<Character,Integer>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
new HashMap<Character,Integer>() {{ put('d', 3); put('e', 5); put(' ', 8); }}, // 3.
new HashMap<Character,Integer>() {{ put('d', 3); }}, // 4.
new HashMap<Character,Integer>() {{ put('s', 6); put('d', 7); }}, // 5.
new HashMap<Character,Integer>() {{ put('d', 7); }}, // 6.
new HashMap<Character,Integer>() {{ put('d', 7); put(' ', 8); }}, // 7.
new HashMap<Character,Integer>() {{ put(' ', 8); }} // 8.
};
int p = 0;
char t;
for(char c : s.toCharArray()) {
if(c >= '0' && c <= '9') {
t = 'd';
} else if(c == '+' || c == '-') {
t = 's';
} else if(c == 'e' || c == 'E') {
t = 'e';
} else if(c == '.' || c == ' ') {
t = c;
} else {
t = '?';
}
if(!states[p].containsKey(t)) {
return false;
}
p = (int)states[p].get(t);
}
return p == 2 || p == 3 || p == 7 || p == 8;
}
五、反转链表
ListNode node;
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
dfs(head);
return node;
}
private ListNode dfs(ListNode head) {
if(head.next == null){
node = new ListNode(head.val);
return node;
}
ListNode listNode = dfs(head.next);
listNode.next = new ListNode(head.val);
return listNode.next;
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
六、包含 min 函数的栈
class MinStack {
Stack<Integer> stack = new Stack<>();
Stack<Integer> minStack = new Stack<>();
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
if(minStack.isEmpty() || minStack.peek() >= x){
minStack.add(x);
}
stack.add(x);
}
public void pop() {
int pop = stack.pop();
if(!minStack.isEmpty() && pop == minStack.peek()){
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int min() {
if(minStack.isEmpty()){
return -1;
}
return minStack.peek();
}
}
七、复杂链表的复制
public Node copyRandomList(Node head) {
if(head == null) {
return null;
}
Node cur = head;
Map<Node, Node> map = new HashMap<>();
// 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
while(cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
// 4. 构建新链表的 next 和 random 指向
while(cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
// 5. 返回新链表的头节点
return map.get(head);
}
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
八、II. 左旋转字符串
public String reverseLeftWords(String s, int n) {
StringBuilder stringBuilder = new StringBuilder();
char[] chars = s.toCharArray();
for (int i = n; i < chars.length; i++) {
stringBuilder.append(chars[i]);
}
for (int i = 0; i < n; i++) {
stringBuilder.append(chars[i]);
}
return stringBuilder.toString();
}
九、I. 滑动窗口的最大值
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || k == 0) {
return new int[0];
}
Deque<Integer> deque = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
// 删除 deque 中对应的 nums[i-1]
if(i > 0 && deque.peekFirst() == nums[i - 1]) {
deque.removeFirst();
}
// 保持 deque 递减
while(!deque.isEmpty() && deque.peekLast() < nums[j]) {
deque.removeLast();
}
deque.addLast(nums[j]);
// 记录窗口最大值
if(i >= 0) {
res[i] = deque.peekFirst();
}
}
return res;
}
十、II. 队列的最大值
class MaxQueue {
Queue<Integer> queue;
Deque<Integer> deque;
public MaxQueue() {
queue = new LinkedList<>();
deque = new LinkedList<>();
}
public int max_value() {
return deque.isEmpty() ? -1 : deque.peekFirst();
}
public void push_back(int value) {
queue.offer(value);
while(!deque.isEmpty() && deque.peekLast() < value) {
deque.pollLast();
}
deque.offerLast(value);
}
public int pop_front() {
if(queue.isEmpty()) {
return -1;
}
if(queue.peek().equals(deque.peekFirst())) {
deque.pollFirst();
}
return queue.poll();
}
}
十一、把字符串转换成整数
public int strToInt(String str) {
int res = 0, bndry = Integer.MAX_VALUE / 10;
int i = 0, sign = 1, length = str.length();
if(length == 0) {
return 0;
}
while(str.charAt(i) == ' ') {
if(++i == length) {
return 0;
}
}
if(str.charAt(i) == '-') {
sign = -1;
}
if(str.charAt(i) == '-' || str.charAt(i) == '+') {
i++;
}
for(int j = i; j < length; j++) {
if(str.charAt(j) < '0' || str.charAt(j) > '9') {
break;
}
if(res > bndry || res == bndry && str.charAt(j) > '7') {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
res = res * 10 + (str.charAt(j) - '0');
}
return sign * res;
}