剑指 Offer 58 - I. 翻转单词顺序
输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"I am a student. “,则输出"student. a am I”。
双指针:
class Solution {public String reverseWords(String s) {s = s.trim(); int j = s.length() - 1, i = j;StringBuilder res = new StringBuilder();while(i >= 0) {while(i >= 0 && s.charAt(i) != ' ') i--; res.append(s.substring(i + 1, j + 1) + " "); while(i >= 0 && s.charAt(i) == ' ') i--; j = i; }return res.toString().trim(); }
}
分割+倒序:
class Solution {public String reverseWords(String s) {String[] strs = s.trim().split(" "); StringBuilder res = new StringBuilder();for(int i = strs.length - 1; i >= 0; i--) { if(strs[i].equals("")) continue; res.append(strs[i] + " "); }return res.toString().trim(); }
}
剑指 Offer 58 - II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。
substring或者StringBuffer append
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length &#61;&#61; 0 || k &#61;&#61; 0) return new int[0];Deque<Integer> deque &#61; new LinkedList<>();int[] res &#61; new int[nums.length - k &#43; 1];for(int i &#61; 0; i < k; i&#43;&#43;) {while(!deque.isEmpty() && deque.peekLast() < nums[i])deque.removeLast();deque.addLast(nums[i]);}res[0] &#61; deque.peekFirst();for(int i &#61; k; i < nums.length; i&#43;&#43;) {if(deque.peekFirst() &#61;&#61; nums[i - k]) deque.removeFirst();while(!deque.isEmpty() && deque.peekLast() < nums[i])deque.removeLast();deque.addLast(nums[i]);res[i - k &#43; 1] &#61; deque.peekFirst();}return res;}
}
剑指 Offer 59 - II. 队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值&#xff0c;要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空&#xff0c;pop_front 和 max_value 需要返回 -1
剑指 Offer 60. n个骰子的点数
把n个骰子扔在地上&#xff0c;所有骰子朝上一面的点数之和为s。输入n&#xff0c;打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案&#xff0c;其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
剑指 Offer 61. 扑克牌中的顺子
从若干副扑克牌中随机抽 5 张牌&#xff0c;判断是不是一个顺子&#xff0c;即这5张牌是不是连续的。2&#xff5e;10为数字本身&#xff0c;A为1&#xff0c;J为11&#xff0c;Q为12&#xff0c;K为13&#xff0c;而大、小王为 0 &#xff0c;可以看成任意数字。A 不能视为 14。
class Solution {public boolean isStraight(int[] nums) {Set<Integer> repeat &#61; new HashSet<>();int max &#61; 0, min &#61; 14;for(int num : nums) {if(num &#61;&#61; 0) continue; max &#61; Math.max(max, num); min &#61; Math.min(min, num); if(repeat.contains(num)) return false; repeat.add(num); }return max - min < 5; }
}