冲刺001：无重复字符的最长子串

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         int left = 0, n = s.length(), ans = 0;
  4.         Map<Character, Integer> map = new HashMap<>();
  5.         for (int i = 0; i < n; i++) {
  6.             if (map.containsKey(s.charAt(i))) {
  7.                 left = Math.max(left, map.get(s.charAt(i)) + 1);
  8.             }
  9.             map.put(s.charAt(i), i);
  10.             ans = Math.max(ans, i - left + 1);
  11.         }
  12.         return ans;
  13.     }
  14. }

冲刺002：K 个一组翻转链表

  1. class Solution {
  2.     public ListNode reverseKGroup(ListNode head, int k) {
  3.         ListNode hair = new ListNode(0);
  4.         hair.next = head;
  5.         ListNode pre = hair;
  6.         ListNode cur = head;
  8.         while (cur != null) {
  9.             ListNode tail = pre;
  11.             for (int i = 0; i < k; i++) {
  12.                 tail = tail.next;
  13.                 if (tail == null) {
  14.                     return hair.next;
  15.                 }
  16.             }
  18.             ListNode next = tail.next;
  19.             ListNode[] reverse = myReverse(cur, tail);
  20.             cur = reverse[0];
  21.             tail = reverse[1];
  23.             pre.next = cur;
  24.             tail.next = next;
  25.             pre = tail;
  26.             cur = tail.next;
  27.         }
  28.         return hair.next;
  29.     }
  31.     public ListNode[] myReverse(ListNode cur, ListNode tail) {
  32.         ListNode head = cur;
  33.         ListNode pre = null;
  34.         while (cur != tail) {
  36.             ListNode next = cur.next;
  37.             cur.next = pre;
  38.             pre = cur;
  39.             cur = next;
  41.         }
  42.         cur.next = pre;
  43.         return new ListNode[]{cur, head};
  44.     }
  45. }

冲刺003：有效的括号

  1. class Solution {
  2.     public boolean isValid(String s) {
  3.         Stack<Character> stack = new Stack<>();
  4.         Map<Character, Character> map = new HashMap<>(){{
  5.             put(')', '(');
  6.             put(']', '[');
  7.             put('}', '{');
  8.         }};
  9.         for (int i = 0; i < s.length(); i++) {
  10.             Character c = s.charAt(i);
  11.             if (c == '(' || c == '[' || c == '{') {
  12.                 stack.add(c);
  13.             } else {
  14.                 if (!stack.empty() && map.get(c) == stack.peek()) {
  15.                     stack.pop();
  16.                 } else {
  17.                     return false;
  18.                 }
  19.             }
  20.         }
  21.         if (stack.empty()) {
  22.             return true;
  23.         } else {
  24.             return false;
  25.         }
  26.     }
  27. }

冲刺004：两数之和

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         Map<Integer, Integer> map = new HashMap<>();
  4.         for (int i = 0; i < nums.length; i++) {
  5.             int pair = target - nums[i];
  6.             if (map.containsKey(pair)) {
  7.                 return new int[] {i, map.get(pair)};
  8.             }
  9.             map.put(nums[i], i);
  10.         }
  11.         return new int[0];
  12.     }
  13. }

冲刺005：三数之和

  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         Arrays.sort(nums);
  5.         for (int first = 0; first < nums.length; first++) {
  6.             if (first > 0 && nums[first] == nums[first-1]) {
  7.                 continue;
  8.             }
  9.             int third = nums.length - 1;
  10.             int target = - nums[first];
  11.             for (int second = first + 1; second < nums.length; second++) {
  12.                 if (second > first + 1 && nums[second] == nums[second-1]) {
  13.                     continue;
  14.                 }
  15.                 while (second < third && nums[second] + nums[third] > target) {
  16.                     third--;
  17.                 }
  18.                 if (second == third) { 
  19.                     break;
  20.                 }
  21.                 if (nums[second] + nums[third] == target) {
  22.                     List<Integer> tmp = new ArrayList<>();
  23.                     tmp.add(nums[first]);
  24.                     tmp.add(nums[second]);
  25.                     tmp.add(nums[third]);
  26.                     res.add(tmp);
  27.                 }
  28.             }
  29.         }
  30.         return res;
  31.     }
  32. }

冲刺006：螺旋矩阵

  1. class Solution {
  2.     public List<Integer> spiralOrder(int[][] matrix) {
  3.         List<Integer> res = new ArrayList<>();
  4.         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  5.             return res;
  6.         }
  7.         int rows = matrix.length;
  8.         int cols = matrix[0].length;
  9.         int total = rows * cols;
  10.         int x = 0, y = 0;
  11.         int dirIndex = 0;
  12.         int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  13.         boolean[][] vis = new boolean[rows][cols];
  14.         for (int i = 0; i < total; i++) {
  15.             res.add(matrix[x][y]);
  16.             vis[x][y] = true;
  17.             int tx = x + dir[dirIndex][0];
  18.             int ty = y + dir[dirIndex][1];
  19.             if (tx < 0 || tx >= rows || ty < 0 || ty >= cols || vis[tx][ty]) {
  20.                 dirIndex = (dirIndex + 1) % 4;
  21.             }
  22.             x += dir[dirIndex][0];
  23.             y += dir[dirIndex][1];
  24.         }
  25.         return res;
  26.     }
  27. }

冲刺007：搜索旋转排序数组

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int n = nums.length;
  4.         if (n == 0) return -1;
  5.         else if (n == 1) return nums[0] == target ? 0 : -1;
  6.         int l = 0, r = nums.length - 1;
  7.         while(l <= r) {
  8.             int mid = (l + r) / 2;
  9.             if (nums[mid] == target) {
  10.                 return mid;
  11.             }
  12.             if (nums[l] <= nums[mid]) {
  13.                 if (nums[l] <= target && target < nums[mid]) {
  14.                     r = mid - 1;
  15.                 } else {
  16.                     l = mid + 1;
  17.                 }
  18.             } else {
  19.                 if (nums[mid] < target && target <= nums[r]) {
  20.                     l = mid + 1;
  21.                 } else {
  22.                     r = mid - 1;
  23.                 }
  24.             }
  25.         }
  26.         return -1;
  27.     }
  28. }

冲刺008：合并两个有序链表

冲刺009：下一个排列