文章目录
前言
前段时间趁着周末更新了一波简历，写上了一些关于这次实习的项目技术，更重要的是投递了几个简历，其中就在上周就去做了蔚来的笔试题，投递的Java开发，发现前面很多选择题都是C++相关的知识，多少还是有点力不从心，毕竟那家公司大多数需要的貌似是智能制造，也很正常，这次就当我来了一次模拟考试，所以我大部分时间都在写后面三道算法题。题目貌似都是一般难度，分别是删除排序链表中的重复元素，二叉树的中序遍历，和一个关于栈的括号匹配问题，我等会先把这三道题贴出来吧，说实话到了手撕算法的时候不是这出错就是那出错。先贴出来给大家看看
本次算法考试真题
删除排序链表中的重复元素
/**
* 删除排序链表中的重复元素
* @Description: 给定一个已排序的链表的头 head ，
* 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表
* @author: William
* @date: 2022-07-16
*/classListNode{int val;ListNode next;ListNode(){}ListNode(int val){this.val = val;}ListNode(int val,ListNode next){this.val = val;this.next = next;}}publicclassNum83{publicListNodedeleteDuplicates(ListNode head){if(head ==null)returnnull;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;}}classNum82{//来对比一下这道中等的题目//给定一个已排序的链表的头 head ， //删除原始链表中所有重复数字的节点，只留下不同的数字 返回已排序的链表publicListNodedeleteDuplicates1(ListNode head){if(head ==null)return head;ListNode hair =newListNode(-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;}//递归解法publicListNodedeleteDuplicates2(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;}returndeleteDuplicates2(notDup);}}}
刚开始就遇到的这道题，开始就想着指针，刚吃饱饭也没太想清楚是双指针还是三指针，最后又想使用递归来解，递归递到自己都不知道在写些什么了，真让自己做起来还真是不太会分析，使用的三指针感觉怎么都不合适，总有一些用例过不去
有效的括号字符串
/**
* 有效的括号字符串
* @Description: 给定一个只包含三种字符的字符串：（ ，） 和 *
* @author: William
* @date: 2022-07-17
*/publicclassNum678{//先来双栈吧 自己当时想到的也是这个方法publicbooleancheckValidString(String s){//注意栈存的是下标而不是具体char 这样更方便比对Deque<Integer> lStack =newLinkedList<>();//左栈Deque<Integer> mStack =newLinkedList<>();//*栈int n = s.length();for(int i =0; i < n; i++){char c = s.charAt(i);if(c =='('){
lStack.push(i);//入栈}elseif(c =='*'){
mStack.push(i);}else{// ) 先弹出左栈中元素 再看*栈 如果*栈没有 返回falseif(!lStack.isEmpty()){
lStack.pop();}elseif(!mStack.isEmpty()){
mStack.pop();}else{returnfalse;}}}//对应左括号和*还有的情况while(!lStack.isEmpty()&&!mStack.isEmpty()){int lIndex = lStack.pop();int mIndex = mStack.pop();if(lIndex > mIndex){//左括号下标不能比*的下标大returnfalse;}}return lStack.isEmpty();//再检查左栈是否为空}//定义dp[i][j] 表示字符串s从下标i到j的子串是否为有效的括号字符串//但是本题对于我来说动态规划很不友好 需要分的情况太多 难以处理//我更偏向于栈和贪心方法publicbooleancheckValidString1(String s){int n = s.length();boolean[][] dp =newboolean[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)publicbooleancheckValidString2(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++;}elseif(c ==')'){//任何情况下，未匹配的左括号数量必须非负，因此当最大值变成负数时，//说明没有左括号可以和右括号匹配，返回false
minCount =Math.max(minCount -1,0);
maxCount--;//未匹配的左括号数-1if(maxCount <0){returnfalse;}}else{//*//minCount是把所有的'*'都当成')'而maxCount是把所有的'*'当成'('
minCount =Math.max(minCount -1,0);
maxCount++;}}return minCount ==0;}}
刚开始写这道题想到的肯定是用栈来解决，可惜自己少想了一步，栈中存的是char而不是下标，这就导致很不方便，我写来写去也整不出来，后来想到直接用贪心思路，用两个计数器来记录，可惜也还差点意思，不会处理那两个计数器，可以看上面最后一种解法，维护minCount和maxCount，同时注意他们是怎么来的
二叉树的中序遍历
/**
* 二叉树的中序遍历
* @Description:
* @author: William
* @date: 2022-07-17
*/publicclassNum94{publicList<Integer>inorderTraversal(TreeNode root){List<Integer> res =newArrayList<>();inorder(root, res);return res;}publicvoidinorder(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
*/publicclassNum05{publicStringlongestPalindrome(String s){int len = s.length();if(len <2){return s;}int maxLen =1, begin =0;// dp[i][j] 表示 s[i..j] 是否是回文串boolean[][] dp =newboolean[len][len];// 初始化：所有长度为 1 的子串都是回文串for(int i =0; i < len; i++){
dp[i][i]=true;}char[] charArray = s.toCharArray();// 递推开始// 先枚举子串长度for(intL=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);}//中心扩展法publicStringlongestPalindrome1(String s){int len = s.length();if(s ==null|| s.length()<2)return s;int maxStart =0, maxEnd =0, maxLen =1;//最长回文串的起点 终点 长度boolean[][] dp =newboolean[len][len];for(intR=1;R< len;R++){for(intL=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
*/publicclassNum10{publicintnumWays(int n){if(n ==0|| n ==1){return1;}int[] dp =newint[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)复杂度的动态规划publicintnumWays1(int n){if(n ==0|| n ==1){return1;}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
*/classTreeNode{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;}}publicclassNum110{publicbooleanisBalanced(TreeNode root){//dfsreturndfs(root)>=0;}//求出当前以root为根节点的树的高度publicintdfs(TreeNode root){if(root ==null)return0;int left =dfs(root.left);int right =dfs(root.right);//下面返回-2都是因为不符合题意if(left <0|| right <0)return-2;//注意不能返回-1 不然不知道是因为root为空还是因为左右子树高度差大于1if(Math.abs(left - right)>1)return-2;returnMath.max(left, right)+1;}}
买卖股票的最佳时机
/**
* 买卖股票的最佳时机
* @Description: 给定一个数组 prices ，它的第i个元素 prices[i]表示一支给定股票第i天的价格。
* 你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。
* 设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。
* 如果你不能获取任何利润，返回 0 。
* @author: William
* @date: 2022-07-19
*/publicclassNum121{//暴力法 这样会超出时间限制publicintmaxProfit(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]);publicintmaxProfit1(int[] prices){int max =0;int[] dp =newint[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;}//单调栈 当你需要高效率查询某个位置左右两侧比他大（或小）的数的位置的时候publicintmaxProfit2(int[] prices){int[] prices2 =newint[prices.length +1];for(int i =0; i < prices.length; i++){
prices2[i]= prices[i];}
prices2[prices.length]=-1;//哨兵，保证所有的元素出栈ArrayDeque<Integer> stack =newArrayDeque<>();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
*/publicclassNum146{classLRUCache{classDLinkedNode{int key;int value;DLinkedNode prev;DLinkedNode next;publicDLinkedNode(){}publicDLinkedNode(int _key,int _value){ key = _key; value = _value;}}privateMap<Integer,DLinkedNode> cache =newHashMap<>();privateint size;privateint capacity;privateDLinkedNode head, tail;publicLRUCache(int capacity){this.size =0;this.capacity = capacity;//使用伪头部和伪尾部节点
head =newDLinkedNode();
tail =newDLinkedNode();
head.next = tail;
tail.prev = head;}publicintget(int key){DLinkedNode node = cache.get(key);if(node ==null){return-1;}//如果key存在，先通过哈希表定位，再移到头部moveToHead(node);return node.value;}publicvoidput(int key,int value){DLinkedNode node = cache.get(key);if(node ==null){//如果key不存在， 创建一个新的节点DLinkedNode newNode =newDLinkedNode(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);}}privatevoidaddToHead(DLinkedNode node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;}privatevoidremoveNode(DLinkedNode node){
node.prev.next = node.next;
node.next.prev = node.prev;}privatevoidmoveToHead(DLinkedNode node){removeNode(node);addToHead(node);}privateDLinkedNoderemoveTail(){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
*/publicclassNum155{classMinStack{Deque<Integer> xStack;Deque<Integer> minStack;publicMinStack(){
xStack =newLinkedList<>();
minStack =newLinkedList<>();
minStack.push(Integer.MAX_VALUE);}publicvoidpush(int x){
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));}publicvoidpop(){
xStack.pop();
minStack.pop();}publicinttop(){return xStack.peek();}publicintgetMin(){return minStack.peek();}}}
有效的括号匹配
/**
* 有效的括号
* @Description: 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，
* 判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合
* @author: William
* @date: 2022-07-19
*/publicclassNum20{publicbooleanisValid(String s){Map<Character,Character> map =newHashMap<>(){{put(')','(');put(']','[');put('}','{');}};Deque<Character> stack =newLinkedList<>();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())returnfalse;//配对成功 弹出栈中元素
stack.pop();break;}}return stack.isEmpty();}//更加优雅的写法privatestaticfinalMap<Character,Character> map1 =newHashMap<Character,Character>(){{put('{','}');put('[',']');put('(',')');put('?','?');}};publicbooleanisValid1(String s){if(s.length()>0&&!map1.containsKey(s.charAt(0)))returnfalse;LinkedList<Character> stack =newLinkedList<>(){{add('?');}};for(Character c : s.toCharArray()){if(map1.containsKey(c)) stack.addLast(c);elseif(map1.get(stack.removeLast())!= c)returnfalse;}return stack.size()==1;}}
剑指Offer Ⅱ 链表中环的入口节点
/**
* 剑指Offer Ⅱ 链表中环的入口节点
* @Description:
* @author: William
* @date: 2022-07-19
*/publicclassNum22{publicListNodedetectCycle(ListNode head){ListNode pos = head;//哈希表存储Set<ListNode> visited =newHashSet<>();while(pos !=null){if(visited.contains(pos)){return pos;}else{
visited.add(pos);}
pos = pos.next;}returnnull;}publicListNodedetectCycle1(ListNode head){//快慢指针if(head ==null|| head.next ==null)returnnull;// 特判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)returnnull;// 无环时返回null，若能往下执行必有环
fast = head;// 重复利用fast，放到表头处while(slow != fast){
fast = fast.next;
slow = slow.next;}return slow;// return fast也可以}}
在排序数组中查找元素的第一个和最后一个位置
/**
* 在排序数组中查找元素的第一个和最后一个位置
* @Description:
* @author: William
* @date: 2022-07-23
*/publicclassNum34{publicint[]searchRange(int[] nums,int target){int[] ans =newint[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;}publicintbinarySearch(int[] nums,int target){intL=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肯定不指向targetreturnL;//L此时是第一个出现的位置}}
反转字符串
/**
* 反转字符串
* @Description: 编写一个函数，其作用是将输入的字符串反转过来。
* 输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，
* 你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
* @author: William
* @date: 2022-07-20
*/publicclassNum344{publicvoidreverseString(char[] s){int n = s.length;for(intL=0,R= n -1;L<R;++L,--R){char tmp = s[L];
s[L]= s[R];
s[R]= tmp;}}//只记录一个值也可以publicvoidreverseString1(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
*/publicclassNum42{//动态规划解法publicinttrap1(int[] height){int n = height.length;if(n ==0)return0;int[] leftMax =newint[n];
leftMax[0]= height[0];//先初始化左右两边的最高高度for(int i =1; i < n;++i){//然后遍历
leftMax[i]=Math.max(leftMax[i -1], height[i]);}int[] rightMax =newint[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;}//单调栈publicinttrap2(int[] height){int ans =0;//栈存储的是下标Deque<Integer> stack =newLinkedList<>();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变成新的topint 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)publicinttrap3(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
*/publicclassNum451{publicStringfrequencySort(String s){Map<Character,Integer> map =newHashMap<>();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 =newArrayList<>(map.keySet());//键由大到小排序Collections.sort(list,(a,b)-> map.get(b)- map.get(a));StringBuffer sb =newStringBuffer();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();}//桶排序 由于每个字符在字符串中出现的频率存在上限，因此可以使用桶排序的思想，// 根据出现次数生成排序后的字符串。publicStringfrequencySort1(String s){Map<Character,Integer> map =newHashMap<>();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 =newStringBuffer[maxFreq +1];for(int i =0; i <= maxFreq; i++){
buckets[i]=newStringBuffer();}for(Map.Entry<Character,Integer> entry : map.entrySet()){char c = entry.getKey();int frequency = entry.getValue();
buckets[frequency].append(c);}StringBuffer sb =newStringBuffer();//按照出现频率从大到小的顺序遍历桶，对于每个出现频率，获得对应的字符//然后将每个字符按照出现频率拼接到排序后的字符串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
*/publicclassNum541{publicStringreverseStr(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[]) 即可returnnewString(arr);}//反转char数组privatevoidresvese(char[] s,intL,intR){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
*/publicclassNum56{publicint[][]merge(int[][] intervals){Arrays.sort(intervals,newComparator<int[]>(){@Overridepublicintcompare(int[] o1,int[] o2){return o1[0]= o2[0];//也就是默认按第一个元素从小到大排序}});//区间开始位置相减int[][] res =newint[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]);}}returnArrays.copyOf(res, ind +1);//copyOf(T[] original, int newLength)对应的是数据源和新的长度}}
用数组设计循环队列
/**
* 用数组设计循环队列
* @Description:
* @author: William
* @date: 2022-07-16
*/publicclassNum622{classMyCircularQueue{//front -> 队首 rear -> 队尾下一位置int[] queue;int front, rear;int max, count;publicMyCircularQueue(int k){
queue =newint[k];
front =0; rear =0;
max = k; count =0;}publicbooleanenQueue(int value){if(isFull())returnfalse;
queue[rear]= value;
rear++;
rear %= max;
count++;returntrue;}publicbooleandeQueue(){if(isEmpty())returnfalse;
front++;
front %= max;
count--;returntrue;}publicintFront(){if(isEmpty())return-1;return queue[front];}publicintRear(){if(isEmpty())return-1;return queue[(rear -1+ max)% max];}publicbooleanisEmpty(){return count ==0;}publicbooleanisFull(){return count == max;}}}
剑指 Offer II 070. 排序数组中只出现一次的数字
/**
* 剑指 Offer II 070. 排序数组中只出现一次的数字 对应Num540
* @Description: 给定一个只包含整数的有序数组 nums ，
* 每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
* 你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度
* @author: William
* @date: 2022-07-19
*/publicclassNum70{//全数组的二分查找 假设只出现一次的元素位于下标 xx，由于其余每个元素都出现两次//因此下标 x 的左边和右边都有偶数个元素，数组的长度是奇数//细节：利用位或的性质//当mid是偶数时 mid + 1 = mid ^ 1//当mid是奇数时 mid - 1 = mid ^ 1//因此在二分查找的过程中，不需要判断mid的奇偶性//mid和mid^1即为每次需要比较元素的两个下标publicintsingleNonDuplicate(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];}publicintsingleNonDuplicate1(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
*/publicclassNum88{//直接合并后排序publicvoidmerge1(int[] nums1,int m,int[] nums2,int n){for(int i =0; i != n;++i){
nums1[m+i]= nums2[i];}Arrays.sort(nums1);}//逆向双指针publicvoidmerge2(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手游，有点罪恶，原来自己压力是这么大，现实中呢也得不到缓解，生活上也受到了一些来自外界的影响，一个人在这个城市工作确实闲下来感觉挺没意思的，想找个人好好说话都比较难，最近更加想念我的朋友们了，先继续让自己忙起来吧，把技术实力提上去，以后的选择也就更多了，加油吧，你我都是。
本文转载自: https://blog.csdn.net/qq_57469718/article/details/125952126
版权归原作者 慢慢敲吧 所有， 如有侵权，请联系我们删除。
版权归原作者 慢慢敲吧 所有， 如有侵权，请联系我们删除。