数组：
/** * 209. 长度最小的子数组 * * @param target 正整数 * @param nums 含有 n 个正整数的数组 * @return 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0 。 */ public int minSubArrayLen(int target, int[] nums) { // 首先应该想到就是滑动窗口法，不用滑动窗口可以试试暴力解法 int res = Integer.MAX_VALUE; // 滑动窗口起始位置 int left = 0; // 滑动窗口数值之和 int sum = 0; for (int right = 0; right < nums.length; right++) { sum += nums[right]; // 注意这里使用while，每次更新 left（起始位置），并不断比较子序列是否符合条件 while (sum >= target) { // 取子序列的长度 res = Math.min(res, right - left + 1); sum -= nums[left]; // 这里体现出滑动窗口的精髓之处，不断变更 left（子序列的起始位置） left ++; } } return res == Integer.MAX_VALUE ? 0 : res; }
链表：
/** * 206. 反转链表 * @param head 头节点 head * @return 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 */ public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; ListNode temp = null; // cur.next != null 的话会漏掉最后一个节点 while (cur != null) { // 保存 cur 的下一个节点，下一步要改变 cur.next temp = cur.next; // 翻转操作 cur.next = prev; // 更新prev 和 cur 的指向 prev = cur; cur = temp; } return prev; } public ListNode reverseList2(ListNode head) { // 递归法实现，过程和双指针法类似 // 第一次递归，prev 为空 return reverse2(null, head); } public ListNode reverse2(ListNode prev, ListNode head) { if (head == null) { return prev; } ListNode temp = null; // 保存 cur 的下一个节点，下一步要改变 cur.next temp = head.next; // 翻转操作 head.next = prev; // 更新prev 和 cur 的指向 // prev = cur; // cur = temp; return reverse2(prev, temp); }
哈希表：
/** * 202. 快乐数 * @param n 编写一个算法来判断一个数 n 是不是快乐数 * @return 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。 */ public static boolean isHappy(int n) { Set<Integer> set = new HashSet<>(); // 如果这个sum曾经出现过，说明已经陷入了无限循环了 while (n != 1 && !set.contains(n)) { set.add(n); n = calcSquareSum(n); } return n == 1; } public static int calcSquareSum(int num) { // 计算数值各个位上的单数之和 int sum = 0; while (num > 0) { sum += Math.pow(num % 10, 2); num /= 10; } return sum; }
字符串：
/** * 剑指 Offer 05. 替换空格 * @param s 字符串 s * @return 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 */ public String replaceSpace(String s) { // 双指针法比较麻烦，需要扩展空间 // StringBuilder，虽然线程不安全，但是单线程使用速度快 StringBuilder sb = new StringBuilder(); // sb 逐个复制 s ，碰到空格则替换，否则直接复制 for (char c : s.toCharArray()) { if (c == ' ') { sb.append("%20"); continue; } sb.append(c); } return sb.toString(); }
双指针：
/** * 151. 反转字符串中的单词 * * @param s * @return */ public String reverseWords(String s) { // 解法一： // 移除多余空格: "the sky is blue" // 字符串反转："eulb si yks eht" // 单词反转："blue is sky the" // // 1.去除首尾以及中间多余空格 // StringBuilder sb = removeSpace(s); // // 2.反转整个字符串 // reverseString(sb, 0, sb.length() - 1); // // 3.反转各个单词 // reverseEachWord(sb); // return sb.toString(); // 解法二：创建新字符数组填充。时间复杂度O(n) // 源字符数组 char[] initialArr = s.toCharArray(); // 新字符数组 // 下面循环添加"单词 "，最终末尾的空格不会返回 char[] newArr = new char[initialArr.length + 1]; int newArrPos = 0; // i来进行整体对源字符数组从后往前遍历 int i = initialArr.length - 1; while (i >= 0) { //跳过空格 while (i >= 0 && initialArr[i] == ' ') { i--; } // 此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定单词的首字母的位置 int right = i; while (i >= 0 && initialArr[i] != ' ') { i--; } // 指定区间单词取出(由于i为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格 for (int j = i + 1; j <= right; j++) { newArr[newArrPos++] = initialArr[j]; if (j == right) { // 空格 newArr[newArrPos++] = ' '; } } } // 若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回) if (newArrPos == 0) { return ""; } else { return new String(newArr, 0, newArrPos - 1); } } private StringBuilder removeSpace(String s) { // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]"); int start = 0; int end = s.length() - 1; while (s.charAt(start) == ' ') { start++; } while (s.charAt(end) == ' ') { end--; } StringBuilder sb = new StringBuilder(); while (start <= end) { char c = s.charAt(start); if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') { sb.append(c); } start++; } // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]"); return sb; } private void reverseString(StringBuilder sb, int start, int end) { // System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]"); while (start < end) { char temp = sb.charAt(start); sb.setCharAt(start, sb.charAt(end)); sb.setCharAt(end, temp); start++; end--; } // System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]"); } private void reverseEachWord(StringBuilder sb) { int start = 0; int end = 1; int n = sb.length(); while (start < n) { while (end < n && sb.charAt(end) != ' ') { end++; } reverseString(sb, start, end - 1); start = end + 1; end = start + 1; } }