高频笔试题(蔚来)

前言

前段时间趁着周末更新了一波简历，写上了一些关于这次实习的项目技术，更重要的是投递了几个简历，其中就在上周就去做了蔚来的笔试题，投递的Java开发，发现前面很多选择题都是C++相关的知识，多少还是有点力不从心，毕竟那家公司大多数需要的貌似是智能制造，也很正常，这次就当我来了一次模拟考试，所以我大部分时间都在写后面三道算法题。题目貌似都是一般难度，分别是删除排序链表中的重复元素，二叉树的中序遍历，和一个关于栈的括号匹配问题，我等会先把这三道题贴出来吧，说实话到了手撕算法的时候不是这出错就是那出错。先贴出来给大家看看

本次算法考试真题

删除排序链表中的重复元素

/** * 删除排序链表中的重复元素 * @Description: 给定一个已排序的链表的头 head ， * 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 * @author: William * @date: 2022-07-16 */
class ListNode {
    
    int val;
    ListNode next;
    ListNode() {
    }
    ListNode(int val) {
     this.val = val; }
    ListNode(int val, ListNode next) {
     this.val = val; this.next = next; }
}
public class Num83 {
    
	public ListNode deleteDuplicates(ListNode head) {
    
		if(head == null) return null;
		ListNode cur = head;
		while(cur != null && cur.next != null) {
    
			if(cur.next.val == cur.val) {
    //遇到相同的 直接删除即可
				cur.next = cur.next.next;
			}else {
    
				cur = cur.next;
			}
		}
		return head;
    }
}
class Num82{
    
	//来对比一下这道中等的题目
	//给定一个已排序的链表的头 head ， 
	//删除原始链表中所有重复数字的节点，只留下不同的数字 返回已排序的链表
	public ListNode deleteDuplicates1(ListNode head) {
    
		if(head == null) return head;
		ListNode hair = new ListNode(-1, head);
		ListNode pre = hair, cur = head;
		while(cur != null && cur.next != null) {
    
			if(cur.val != cur.next.val) {
    
				pre = pre.next;
				cur = cur.next;
			}else {
    
				while(cur != null && cur.next != null && cur.val == cur.next.val) {
    
					cur = cur.next;
				}
				pre.next = cur.next;
				cur = cur.next;//因为当时cur指向的是最后一个重复的元素 
				//题目要求所有重复元素都删掉
			}
		}
		return hair.next;
	}
	//递归解法
	public ListNode deleteDuplicates2(ListNode head) {
    
		//没有节点或者只有一个节点，必然没有重复元素
		if(head == null|| head.next == null) return head;
		//当前节点和下一节点，值不同，则head的值是需要保留的，对head.next继续递归
		if(head.val != head.next.val) {
    
			head.next = deleteDuplicates2(head.next);
			return head;
		}else {
    
			//当前节点与下一个节点的值重复了，重复的值都不能要
			//一直往下找，找到不重复的节点。返回对不重复节点的递归结果
			ListNode notDup = head.next.next;
			while(notDup != null && notDup.val == head.val) {
    
				notDup = notDup.next;
			}
			return deleteDuplicates2(notDup);
		}
	}
}

刚开始就遇到的这道题，开始就想着指针，刚吃饱饭也没太想清楚是双指针还是三指针，最后又想使用递归来解，递归递到自己都不知道在写些什么了，真让自己做起来还真是不太会分析，使用的三指针感觉怎么都不合适，总有一些用例过不去

有效的括号字符串

/** * 有效的括号字符串 * @Description: 给定一个只包含三种字符的字符串：（ ，） 和 * * @author: William * @date: 2022-07-17 */
public class Num678 {
    
	//先来双栈吧 自己当时想到的也是这个方法
	public boolean checkValidString(String s) {
    
		//注意栈存的是下标而不是具体char 这样更方便比对
		Deque<Integer> lStack = new LinkedList<>();//左栈
		Deque<Integer> mStack = new LinkedList<>();//*栈
		int n = s.length();
		for(int i = 0; i < n; i++) {
    
			char c = s.charAt(i);
			if(c == '(') {
    
				lStack.push(i);//入栈
			}else if(c == '*') {
    
				mStack.push(i);
			}else {
    // ) 先弹出左栈中元素 再看*栈 如果*栈没有 返回false
				if(!lStack.isEmpty()) {
    
					lStack.pop();
				}else if(!mStack.isEmpty()) {
    
					mStack.pop();
				}else {
    
					return false;
				}
			}
		}//对应左括号和*还有的情况
		while(!lStack.isEmpty() && !mStack.isEmpty()) {
    
			int lIndex = lStack.pop();
			int mIndex = mStack.pop();
			if(lIndex > mIndex) {
    //左括号下标不能比*的下标大
				return false;
			}
		}
		return lStack.isEmpty();//再检查左栈是否为空
    }
	//定义dp[i][j] 表示字符串s从下标i到j的子串是否为有效的括号字符串
	//但是本题对于我来说动态规划很不友好 需要分的情况太多 难以处理
	//我更偏向于栈和贪心方法
	public boolean checkValidString1(String s) {
    
		int n = s.length();
		boolean[][] dp = new boolean[n][n];
		for(int i = 0; i < n; i++) {
    
			if(s.charAt(i) == '*') {
    //无论几个* 都是true
				dp[i][i] = true;
			}
		}
		for(int i = 1; i < n; i++) {
    
			char c1 = s.charAt(i - 1), c2 = s.charAt(i);
			//前面为(或* 后面为)或*
			dp[i-1][i] = (c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*');
		}
		for(int i = n - 3; i >= 0; i--) {
    //从倒数第三个开始
			char c1 = s.charAt(i);
			for(int j = i + 2; j < n; j++) {
    //这就是从最后一个开始了
				char c2 = s.charAt(j);
				if((c1 == '(' || c1 == '*') && (c2 == ')' || c2 == '*')) {
    
					dp[i][j] = dp[i+1][j-1];
				}
				for(int k = i; k < j && !dp[i][j]; k++) {
    
					dp[i][j] = dp[i][k] && dp[k+1][j];
				}
			}
		}
		return dp[0][n-1];
	}
	//贪心 这个方法在笔试的时候也想到了 就是采用一个计数器 空间复杂度O(1)
	public boolean checkValidString2(String s) {
    
		int minCount = 0, maxCount = 0;
		int n = s.length();
		for(int i = 0; i < n; i++) {
    
			char c = s.charAt(i);
			if(c == '(') {
    
				minCount++;
				maxCount++;
			}else if(c == ')') {
    
				//任何情况下，未匹配的左括号数量必须非负，因此当最大值变成负数时，
				//说明没有左括号可以和右括号匹配，返回false
				minCount = Math.max(minCount - 1, 0);
				maxCount--;//未匹配的左括号数-1
				if(maxCount < 0) {
    
					return false;
				}
			}else {
    //*
				//minCount是把所有的'*'都当成')'而maxCount是把所有的'*'当成'('
				minCount = Math.max(minCount - 1, 0);
				maxCount++;
			}
		}
		return minCount == 0;
	}
}

刚开始写这道题想到的肯定是用栈来解决，可惜自己少想了一步，栈中存的是char而不是下标，这就导致很不方便，我写来写去也整不出来，后来想到直接用贪心思路，用两个计数器来记录，可惜也还差点意思，不会处理那两个计数器，可以看上面最后一种解法，维护minCount和maxCount，同时注意他们是怎么来的

二叉树的中序遍历

/** * 二叉树的中序遍历 * @Description: * @author: William * @date: 2022-07-17 */
public class Num94 {
    
	public List<Integer> inorderTraversal(TreeNode root) {
    
		List<Integer> res = new ArrayList<>();
		inorder(root, res);
		return res;
    }
	
	public void inorder(TreeNode root, List<Integer> res) {
    
		if(root == null) return;
		inorder(root.left, res);
		res.add(root.val);
		inorder(root.right, res);
	}
}

第三道题还是比较容易的，相信对只要细心学到dfs的朋友们来说并不困难，树的题目呢主要就是遍历，无论是层序遍历还是啥的，把模板学会，自己再进行对应的操作，一般问题都不大。
以上呢就是那三道题，做完之后真的觉得自己需要去做的还有太多了，为了弥补非科班的差距，中间肯定也是要付出更多的努力，好在年轻还有这么多时间和精力来整这些。在这一周我利用了下班的时间完成了在牛客上看到的关于蔚来的高频试题，中间也有我自己的一些见解和注释，下面就来给大家看看。

其他的高频题

最长回文子串

/** * 最长回文子串 * @Description: * @author: William * @date: 2022-07-16 */
public class Num05 {
    

	public String longestPalindrome(String s) {
    
        int len = s.length();
        if (len < 2) {
     return s; }
        int maxLen = 1, begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
    
            dp[i][i] = true;
        }
        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
    
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
    
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
    
                    break;
                }
                if (charArray[i] != charArray[j]) {
    
                    dp[i][j] = false;
                } else {
    
                    if (j - i < 3) {
    
                        dp[i][j] = true;
                    } else {
    
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
    
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
	//中心扩展法
	public String longestPalindrome1(String s) {
    
		int len = s.length();
		if(s == null || s.length() < 2) return s;
		int maxStart = 0, maxEnd = 0, maxLen = 1;//最长回文串的起点 终点 长度
		
		boolean[][] dp = new boolean[len][len];
		for(int R = 1; R < len; R++) {
    
			for(int L = 0; L < R; L++) {
    
				//R-L<=2 ==> R-1<=L+1 所以去中心化就是重复的 用来初始化
				//后面那个是边界存在
				if(s.charAt(L) == s.charAt(R) && (R - L <= 2 || dp[L+1][R-1])) {
    
					dp[L][R] = true;//boolean dp[l][r] 表示字符串从 i 到 j 这段是否为回文
					if(R - L + 1 > maxLen) {
    
						maxLen = R - L + 1;
						maxStart = L;//从L开始到R结束
						maxEnd = R;
					}
				}
			}
		}
		return s.substring(maxStart, maxEnd + 1);
	}
}

剑指Offer10 II.青蛙跳台阶问题

/** * 剑指Offer10 II.青蛙跳台阶问题 * @Description: 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。 * 求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 * @author: William * @date: 2022-07-18 */
public class Num10 {
    
	public int numWays(int n) {
    
		if(n == 0 || n == 1) {
     return 1; }
		int[] dp = new int[n + 1];
		dp[1] = 1;
		dp[2] = 2;//初始化条件
		for(int i = 3; i <= n; i++) {
    //防止越界
			dp[i] = (dp[i - 2] + dp[i - 1]) % 1000_000_007;
		}
		return dp[n];
	}
	//O(1)复杂度的动态规划
	public int numWays1(int n) {
    
		if(n == 0 || n == 1) {
     return 1; }
		int pre = 1, cur = 2;
		for(int i = 3; i <= n; i++) {
    
			int tmp = (pre + cur) % 1000_000_007;
			pre = cur;
			cur = tmp;
		}
		return cur;
	}
}

平衡二叉树

/** * 平衡二叉树 * @Description: 给定一个二叉树，判断它是否是高度平衡的二叉树。 * 本题中，一棵高度平衡二叉树定义为： * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 * @author: William * @date: 2022-07-16 */
class TreeNode {
    
int val;
TreeNode left;
TreeNode right;
TreeNode() {
    }
TreeNode(int val) {
     this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
    
this.val = val;
this.left = left;
this.right = right;
	}
}

public class Num110 {
    
	public boolean isBalanced(TreeNode root) {
    
		//dfs
		return dfs(root) >= 0;
	}
	//求出当前以root为根节点的树的高度
	public int dfs(TreeNode root) {
    
		if(root == null) return 0;
		int left = dfs(root.left);
		int right = dfs(root.right);
		//下面返回-2都是因为不符合题意
		if(left < 0 || right < 0) return -2;
		//注意不能返回-1 不然不知道是因为root为空还是因为左右子树高度差大于1
		if(Math.abs(left - right) > 1) return -2;
		return Math.max(left, right) + 1;
	}
	
}

买卖股票的最佳时机

/** * 买卖股票的最佳时机 * @Description: 给定一个数组 prices ，它的第i个元素 prices[i]表示一支给定股票第i天的价格。 * 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。 * 设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。 * 如果你不能获取任何利润，返回 0 。 * @author: William * @date: 2022-07-19 */
public class Num121 {
    
	//暴力法 这样会超出时间限制
	public int maxProfit(int[] prices) {
    
		int maxprofit = 0;
		//我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）
		//此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）
		for(int i = 0; i < prices.length - 1; i++) {
    
			for(int j = i + 1; j < prices.length; j++) {
    
				int profit = prices[j] - prices[i];
				if(profit > maxprofit) {
    
					maxprofit = profit;
				}
			}
		}
		return maxprofit;
    }
	//优化之后的动态规划 dp[i]表示截止到i，价格的最低点是多少 dp[i]=min(dp[i-1],nums[i]);
	public int maxProfit1(int[] prices) {
    
		int max = 0;
		int[] dp = new int[prices.length];
		dp[0] = prices[0];//初始化
		for(int i = 1; i < prices.length; i++) {
    
			//遍历一次 取得每个位置之前对应最小的数 注意这里容易角标越界
			dp[i] = (dp[i-1] < prices[i]) ? dp[i-1] : prices[i];
			//遍历一次 看该天价格与dp相减 取得最大值
			max = (prices[i] - dp[i]) > max ? prices[i] - dp[i] : max;
		}
		return max;
	}
	//单调栈 当你需要高效率查询某个位置左右两侧比他大（或小）的数的位置的时候
	public int maxProfit2(int[] prices) {
    
		int[] prices2 = new int[prices.length + 1];
		for(int i = 0; i < prices.length; i++) {
    
			prices2[i] = prices[i];
		}
		prices2[prices.length] = -1;//哨兵，保证所有的元素出栈
		
		ArrayDeque<Integer> stack = new ArrayDeque<>();
		int ans = 0;
		for(int i = 0; i < prices2.length; i++) {
    
			while(!stack.isEmpty() && stack.peek() >= prices2[i]) {
    
				int top = stack.pop();
				if(stack.isEmpty()) {
    
					continue;
				}//出栈时栈顶减去栈底元素
				ans = Math.max(ans, top - stack.peekLast());
			}
			stack.push(prices2[i]);
		}
		return ans;
	}
}

LRU缓存

/** * LRU缓存 * @Description: 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 * 实现 LRUCache 类：LRUCache(int capacity) 以正整数作为容量 capacity 初始化LRU缓存 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value * 如果不存在，则向缓存中插入该组 key-value * 如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行 * @author: William * @date: 2022-07-19 */
public class Num146 {
    
	class LRUCache {
    
		class DLinkedNode {
    
			int key;
			int value;
			DLinkedNode prev;
			DLinkedNode next;
			public DLinkedNode() {
    }
			public DLinkedNode(int _key, int _value) {
     key = _key; value = _value; }
		}
		
		private Map<Integer, DLinkedNode> cache = new HashMap<>();
		private int size;
		private int capacity;
		private DLinkedNode head, tail;
		
	    public LRUCache(int capacity) {
    
	    	this.size = 0;
	    	this.capacity = capacity;
	    	//使用伪头部和伪尾部节点
	    	head = new DLinkedNode();
	    	tail = new DLinkedNode();
	    	head.next = tail;
	    	tail.prev = head;
	    }
	    
	    public int get(int key) {
    
	    	DLinkedNode node = cache.get(key);
	    	if(node == null) {
    
	    		return -1;
	    	}
	    	//如果key存在，先通过哈希表定位，再移到头部
	    	moveToHead(node);
	    	return node.value;
	    }
	    
	    public void put(int key, int value) {
    
	    	DLinkedNode node = cache.get(key);
	    	if(node == null) {
    
	    		//如果key不存在， 创建一个新的节点
		    	DLinkedNode newNode = new DLinkedNode(key, value);
		    	//添加进哈希表
		    	cache.get(newNode);
		    	//添加至双向链表的头部
		    	addToHead(newNode);
		    	++size;
		    	if(size > capacity) {
    
		    		//如果超出容量，删除双向链表的尾部节点
		    		DLinkedNode tail = removeTail();
		    		//删除哈希表中对应的项
		    		cache.remove(tail.key);
		    		--size;
		    	}
	    	}
	    	else {
    
		    	//如果key存在，先通过哈希表定位，再修改value 并移到头部
		    	node.value = value;
		    	moveToHead(node);
		    }
	    }
	    
	    private void addToHead(DLinkedNode node) {
    
	    	node.prev = head;
	    	node.next = head.next;
	    	head.next.prev = node;
	    	head.next = node;
	    }
	    
	    private void removeNode(DLinkedNode node) {
    
	    	node.prev.next = node.next;
	    	node.next.prev = node.prev;
	    }
	    
	    private void moveToHead(DLinkedNode node) {
    
	    	removeNode(node);
	    	addToHead(node);
	    }
	    
	    private DLinkedNode removeTail() {
    
	    	DLinkedNode res = tail.prev;
	    	removeNode(res);
	    	return res;
	    }
	}
}

最小栈

/** * 最小栈 * @Description: 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 * 实现 MinStack 类: * MinStack() 初始化堆栈对象。void push(int x) 将元素x推入堆栈。 * void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。 * @author: William * @date: 2022-07-16 */
public class Num155 {
    
	class MinStack {
    
		Deque<Integer> xStack;
		Deque<Integer> minStack;
		
	    public MinStack() {
    
	    	xStack = new LinkedList<>();
	    	minStack = new LinkedList<>();
	    	minStack.push(Integer.MAX_VALUE);
	    }
	    
	    public void push(int x) {
    
	    	xStack.push(x);
	    	minStack.push(Math.min(minStack.peek(), x));
	    }
	    
	    public void pop() {
    
	    	xStack.pop();
	    	minStack.pop();
	    }
	    
	    public int top() {
    
	    	return xStack.peek();
	    }
	    
	    public int getMin() {
    
	    	return minStack.peek();
	    }
	}
}

有效的括号匹配

/** * 有效的括号 * @Description: 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ， * 判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。 * 左括号必须以正确的顺序闭合 * @author: William * @date: 2022-07-19 */
public class Num20 {
    
	public boolean isValid(String s) {
    
        Map<Character, Character> map = new HashMap<>(){
    {
    
            put(')','(');
            put(']','[');
            put('}','{');
        }};
        Deque<Character> stack = new LinkedList<>();
        for(int i = 0; i < s.length(); i++){
    
            switch(s.charAt(i)){
    
                case '(':
                case '[':
                case '{':
                stack.push(s.charAt(i));
                break;
                case ')':
                case ']':
                case '}':
                if(stack.isEmpty() || map.get(s.charAt(i)) != stack.peek()) return false;
                //配对成功 弹出栈中元素
                stack.pop();
                break;
            }
        }
        return stack.isEmpty();
    }
	
	//更加优雅的写法
	private static final Map<Character, Character> map1 = new HashMap<Character, Character>() {
    {
    
		put('{','}'); put('[',']'); put('(', ')'); put('?', '?');
	}};
	public boolean isValid1(String s) {
    
		if(s.length() > 0 && !map1.containsKey(s.charAt(0))) return false;
		LinkedList<Character> stack = new LinkedList<>() {
    {
     add('?'); }};
		for(Character c : s.toCharArray()) {
    
			if(map1.containsKey(c)) stack.addLast(c);
			else if(map1.get(stack.removeLast()) != c) return false;
		}
		return stack.size() == 1;
	}
	
}

剑指Offer Ⅱ 链表中环的入口节点

/** * 剑指Offer Ⅱ 链表中环的入口节点 * @Description: * @author: William * @date: 2022-07-19 */
public class Num22 {
    
	public ListNode detectCycle(ListNode head) {
    
		ListNode pos = head;
		//哈希表存储
		Set<ListNode> visited = new HashSet<>();
		while(pos != null) {
    
			if(visited.contains(pos)){
    
				return pos;
			}else {
    
				visited.add(pos);
			}
			pos = pos.next;
		}
		return null;
	}
	
	public ListNode detectCycle1(ListNode head) {
    
		//快慢指针
		 if(head == null || head.next == null) return null; // 特判
	        ListNode fast = head, slow = head;
	        while(fast != null && fast.next != null){
     // 注意两个条件的先后顺序（短路策略）
	            fast = fast.next.next;
	            slow = slow.next;
	            if(slow == fast) break; // 快慢指针相遇
	        }
	        if(slow != fast) return null; // 无环时返回null，若能往下执行必有环
	        fast = head; // 重复利用fast，放到表头处
	        while(slow != fast){
    
	            fast = fast.next;
	            slow = slow.next;
	        }
	        return slow; // return fast也可以
    }
}

在排序数组中查找元素的第一个和最后一个位置

/** * 在排序数组中查找元素的第一个和最后一个位置 * @Description: * @author: William * @date: 2022-07-23 */
public class Num34 {
    
	public int[] searchRange(int[] nums, int target) {
    
		int[] ans = new int[2];
		ans[0] = binarySearch(nums, target);
		if(ans[0] == nums.length || nums[ans[0]] != target) {
    
			ans[0] = ans[1] = -1;//此时没有
			return ans;
		}
		ans[1] = binarySearch(nums, target + 1) - 1;
		return ans;
    }
	
	public int binarySearch(int[] nums, int target) {
    
		int L = 0, R = nums.length - 1, mid;
		while(L <= R) {
    
			mid = (L + R) / 2;
			if(nums[mid] >= target) {
    //找到第一个出现的位置
				R = mid - 1;
			}else {
    
				L = mid + 1;
			}
		}//最后R肯定不指向target
		return L;//L此时是第一个出现的位置
	}
}

反转字符串

/** * 反转字符串 * @Description: 编写一个函数，其作用是将输入的字符串反转过来。 * 输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间， * 你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 * @author: William * @date: 2022-07-20 */
public class Num344 {
    
	public void reverseString(char[] s) {
    
		int n = s.length;
	    for (int L = 0, R = n - 1; L < R; ++L, --R) {
    
	        char tmp = s[L];
	        s[L] = s[R];
	        s[R] = tmp;
	    }
	}
	//只记录一个值也可以
	public void reverseString1(char[] s) {
    
        int n = s.length;
        for (int i = 0; i < n/2; i++) {
    
        	//这个很巧妙 就两个对称的位置元素交换即可
            char temp = s[i];
            s[i] = s[n-i-1];
            s[n-i-1] = temp;
        }
    }
}

接雨水(hard)

/** * 接雨水(hard) * @Description: 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 * @author: William * @date: 2022-07-16 */
public class Num42 {
    
	//动态规划解法
	public int trap1(int[] height) {
    
		int n = height.length;
		if(n == 0) return 0;
		
		int[] leftMax = new int[n];
		leftMax[0] = height[0];//先初始化左右两边的最高高度
		for(int i = 1; i < n; ++i) {
    //然后遍历
			leftMax[i] = Math.max(leftMax[i - 1], height[i]);
		}
		
		int[] rightMax = new int[n];
		rightMax[n - 1] = height[n - 1];
		for(int i = n - 2; i >= 0; --i) {
    
			rightMax[i] = Math.max(rightMax[i + 1], height[i]);
		}
		
		int ans = 0;
		for(int i = 0; i < n; ++i) {
    
			ans += Math.min(leftMax[i], rightMax[i]) - height[i];
		}
		return ans;
    }
	//单调栈
	public int trap2(int[] height) {
    
		int ans = 0;//栈存储的是下标
		Deque<Integer> stack = new LinkedList<>();
		int n = height.length;
		for(int i = 0; i < n; ++i) {
    
			//height[i] > height[top]，则得到一个可以接雨水的区域
			//该区域的宽度是 i−left−1
			//高度是 min(height[left],height[i])-height[top]
			while(!stack.isEmpty() && height[i] > height[stack.peek()]) {
    
				int top = stack.pop();//为了能得到left需要将top出栈
				if(stack.isEmpty()) {
    
					break;
				}//top出栈之后left变成新的top
				int left = stack.peek();
				int curWidth = i - left - 1;
				int curHeight = Math.min(height[left], height[i]) - height[top];
				ans += curWidth * curHeight;
			}
			stack.push(i);
		}
		return ans;
	}
	//双指针 空间复杂度O(1)
	public int trap3(int[] height) {
    
		//下标i处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定
		//两指针一个往右 一个往左
		int ans = 0;
		int left = 0, right = height.length - 1;
		int leftMax = 0, rightMax = 0;
		while(left < right) {
    //两指针未相遇时
			leftMax = Math.max(leftMax, height[left]);
			rightMax = Math.max(rightMax, height[right]);
			if(height[left] < height[right]) {
    
				ans += leftMax - height[left];
				++left;
			}else {
    
				ans += rightMax - height[right];
				--right;
			}
		}
		return ans;
	}
}

根据字符出现频率排序

/** * 根据字符出现频率排序 * @Description: 给定一个字符串s，根据字符出现的频率对其进行降序排序 * 一个字符出现的 频率 是它出现在字符串中的次数。 * 返回已排序的字符串 。如果有多个答案，返回其中任何一个。 * @author: William * @date: 2022-07-18 */
public class Num451 {
    
	public String frequencySort(String s) {
    
		Map<Character, Integer> map = new HashMap<>();
		int n = s.length();
		//遍历字符串，统计每个字符出现的频率
		for(int i = 0; i < n; i++) {
    
			char c = s.charAt(i);
			int frequency = map.getOrDefault(c, 0) + 1;
			//键是char字符 值是频率
			map.put(c, frequency);
		}//然后每次得到频率最高的字符 生成排序后的字符串
		//map.keySet() 这个集合得到的是map中所有的key值
		List<Character> list = new ArrayList<>(map.keySet());
		//键由大到小排序
		Collections.sort(list, (a,b) -> map.get(b) - map.get(a));
		StringBuffer sb = new StringBuffer();
		for(int i = 0; i < list.size(); i++) {
    
			char c = list.get(i);
			int frequency = map.get(c);//遍历之后拿出来
			for(int j = 0; j < frequency; j++) {
    
				sb.append(c);
			}
		}
		return sb.toString();
	}
	//桶排序 由于每个字符在字符串中出现的频率存在上限，因此可以使用桶排序的思想，
	// 根据出现次数生成排序后的字符串。
	public String frequencySort1(String s) {
    
		Map<Character, Integer> map = new HashMap<>();
		int maxFreq = 0;
		for(int i = 0; i < s.length(); i++) {
    
			char c = s.charAt(i);
			int frequency = map.getOrDefault(c, 0) + 1;
			map.put(c, frequency);//记录最高频率maxFreq
			maxFreq = Math.max(maxFreq, frequency);
		}
		//创建桶，存储从1到maxFreq的每个出现频率的字符
		StringBuffer[] buckets = new StringBuffer[maxFreq + 1];
		for(int i = 0; i <= maxFreq; i++) {
    
			buckets[i] = new StringBuffer();
		}
		for(Map.Entry<Character, Integer> entry : map.entrySet()) {
    
			char c = entry.getKey();
			int frequency = entry.getValue();
			buckets[frequency].append(c);
		}
		StringBuffer sb = new StringBuffer();
		//按照出现频率从大到小的顺序遍历桶，对于每个出现频率，获得对应的字符
		//然后将每个字符按照出现频率拼接到排序后的字符串
		for(int i = maxFreq; i > 0; i--) {
    
			StringBuffer bucket = buckets[i];
			int size = bucket.length();
			for(int j = 0; j < size; j++) {
    
				for(int k = 0; k < i; k++) {
    
					sb.append(bucket.charAt(j));
				}
			}
		}
		return sb.toString();
	}
	
}

反转字符串Ⅱ

/** * 反转字符串Ⅱ * @Description: 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符， * 就反转这 2k 字符中的前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转。 * 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。 * 示例 ：输入：s = "abcdefg", k = 2 输出："bacdfeg" * @author: William * @date: 2022-07-23 */
public class Num541 {
    
	public String reverseStr(String s, int k) {
    
		int n = s.length();
        //2k的前k个翻转
        char[] arr = s.toCharArray();
        for(int i = 0; i < n; i += 2*k){
    
        	//注意右边区间 是n和i+k中较小的一个
            resvese(arr, i, Math.min(i+k, n) - 1);
        }//API的使用：char数组转String：new String(char[]) 即可
        return new String(arr);
    }
	//反转char数组
    private void resvese(char[] s, int L, int R){
    
        while(L < R){
    
            char tmp = s[L];
            s[L] = s[R];
            s[R] = tmp;
            L++;
            R--;
        }
    }
}

合并区间

/** * 合并区间 * @Description: 输入：intervals = [[1,3],[2,6],[8,10],[15,18]] * 输出：[[1,6],[8,10],[15,18]] * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. * @author: William * @date: 2022-07-23 */
public class Num56 {
    
	public int[][] merge(int[][] intervals) {
    
		Arrays.sort(intervals, new Comparator<int[]>() {
    
			@Override
			public int compare(int[] o1, int[] o2) {
    
				return o1[0] = o2[0];//也就是默认按第一个元素从小到大排序
			}
		});//区间开始位置相减
		int[][] res = new int[intervals.length][2];//前行后列
		int ind = -1;//下标确定位置 保存的是上个区间的下标
		for(int[] interval : intervals) {
    
			//注意第二个判断条件 是当前元素与结果集中保存的元素比较 如果跟数组本身比较就会少很多结果
			if(ind == -1 || interval[0] > res[ind][1]) {
    //当前区间头大于上个区间尾
				res[++ind] = interval;//把当前interval 赋给答案中后面一个下标
			}else {
    //此时相交确定边界
				res[ind][1] = Math.max(res[ind][1], interval[1]);
			}
		}
		return Arrays.copyOf(res, ind + 1);//copyOf(T[] original, int newLength)对应的是数据源和新的长度
	}
}

用数组设计循环队列

/** * 用数组设计循环队列 * @Description: * @author: William * @date: 2022-07-16 */
public class Num622 {
    

class MyCircularQueue {
    
	//front -> 队首 rear -> 队尾下一位置
			int[] queue;
			int front, rear;
			int max, count;
			
	public MyCircularQueue(int k) {
    
		queue = new int[k];
    	front = 0; rear = 0;
    	max = k; count = 0;
    }
    public boolean enQueue(int value) {
    
    	if(isFull()) return false;
    	queue[rear] = value;
    	rear++;
    	rear %= max;
    	count++;
    	return true;
    }
    
    public boolean deQueue() {
    
    	if(isEmpty()) return false;
    	front++;
    	front %= max;
    	count--;
    	return true;
    }
    
    public int Front() {
    
    	if(isEmpty()) return -1;
    	return queue[front];
    }
    
    public int Rear() {
    
    	if(isEmpty()) return -1;
    	return queue[(rear - 1 + max) % max];
    }
    
    public boolean isEmpty() {
    
    	return count == 0;
    }
    
    public boolean isFull() {
    
    	return count == max;
    }
	
}
	
}

剑指 Offer II 070. 排序数组中只出现一次的数字

/** * 剑指 Offer II 070. 排序数组中只出现一次的数字 对应Num540 * @Description: 给定一个只包含整数的有序数组 nums ， * 每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。 * 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度 * @author: William * @date: 2022-07-19 */
public class Num70 {
    
	//全数组的二分查找 假设只出现一次的元素位于下标 xx，由于其余每个元素都出现两次
	//因此下标 x 的左边和右边都有偶数个元素，数组的长度是奇数
	//细节：利用位或的性质
	//当mid是偶数时 mid + 1 = mid ^ 1
	//当mid是奇数时 mid - 1 = mid ^ 1
	//因此在二分查找的过程中，不需要判断mid的奇偶性
	//mid和mid^1即为每次需要比较元素的两个下标
	public int singleNonDuplicate(int[] nums) {
    
		int low = 0, high = nums.length - 1;
		while(low < high) {
    
			int mid = (high - low) / 2 + low;
			if(nums[mid] == nums[mid ^ 1]) {
    
				low = mid + 1;
			}else {
    
				high = mid;
			}
		}
		return nums[low];
    }
	
	public int singleNonDuplicate1(int[] nums) {
    
		int low = 0, high = nums.length - 1;
		while(low < high) {
    
			int mid = (high - low) / 2 + low;
			mid -= mid & 1;
			if(nums[mid] == nums[mid + 1]) {
    
				low = mid + 2;
			}else {
    
				high = mid;
			}
		}
		return nums[low];
	}
}

合并两个有序数组

/** * 合并两个有序数组 * @Description: 你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数m和n，分别表示 nums1和nums2中的元素数目。 * 请你合并nums2到nums1 中，使合并后的数组同样按非递减顺序排列。注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。 * 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。 * @author: William * @date: 2022-07-16 */
public class Num88 {
    
	//直接合并后排序
	public void merge1(int[] nums1, int m, int[] nums2, int n) {
    
		for(int i = 0; i != n; ++i) {
    
			nums1[m+i] = nums2[i];
		}
		Arrays.sort(nums1);
	}
	
	//逆向双指针
	public void merge2(int[] nums1, int m, int[] nums2, int n) {
    
		int p1 = m - 1;
		int p2 = n - 1;
		int p = m + n - 1;
		
		while((p1 >= 0) && (p2 >= 0)) {
    //当两个指针都不小于0时
			//两指针元素比较 谁大那个指针往前移 所以指针总是指向小的元素 最后留下的就是排序的
			nums1[p--] = (nums1[p1]<nums2[p2]) ? nums2[p2--] : nums1[p1--];
			//把num2从0开始复制到num1的位置 复制p2+1长度的元素
		}	
		System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
    }
}

结语

又经历了一周的忙碌，还有好多待完成的任务，昨晚通宵玩了LOL手游，有点罪恶，原来自己压力是这么大，现实中呢也得不到缓解，生活上也受到了一些来自外界的影响，一个人在这个城市工作确实闲下来感觉挺没意思的，想找个人好好说话都比较难，最近更加想念我的朋友们了，先继续让自己忙起来吧，把技术实力提上去，以后的选择也就更多了，加油吧，你我都是。