Leecode面试经典150题
数组 / 字符串
一开始个人写法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] ints = new int[m + n]; int t = 0, t1 = 0, t2 = 0; while (t1 < m && t2 < n) { if (nums1[t1] < nums2[t2]) { ints[t++] = nums1[t1++]; } else { ints[t++] = nums2[t2++]; } } while (t1 < m) { ints[t++] = nums1[t1++]; } while (t2 < n) { ints[t++] = nums2[t2++]; } for (int i = 0; i < m + n; i++) { nums1[i] = ints[i]; } } }
|
倒序双指针就可以做到不开辟空间,直接插入即可,不会出现重叠的情况,可以验证,可以优化如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int t = m + n - 1, t1 = m - 1, t2 = n - 1; while (t1 >= 0 && t2 >= 0) { if (nums1[t1] > nums2[t2]) { nums1[t--] = nums1[t1--]; } else { nums1[t--] = nums2[t2--]; } } while (t1 >= 0) { nums1[t--] = nums1[t1--]; } while (t2 >= 0) { nums1[t--] = nums2[t2--]; } } }
|
1 2 3 4 5 6 7 8 9 10 11
| class Solution { public int removeElement(int[] nums, int val) { int t = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] != val) { nums[t++] = nums[i]; } } return t; } }
|
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution { public int removeDuplicates(int[] nums) { int t = 1, last = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] != last) { last = nums[i]; nums[t++] = nums[i]; } } return t; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public int removeDuplicates(int[] nums) { int t = 1, last = nums[0], count = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] != last) { last = nums[i]; count = 1; nums[t++] = nums[i]; } else { if (count < 2) { count++; nums[t++] = nums[i]; } } } return t; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public int majorityElement(int[] nums) { int temp = nums[0], t = 1; for (int i = 1; i < nums.length; i++) { if (nums[i] != temp) { if (--t == 0) { temp = nums[i]; t = 1; } } else { ++t; } } return temp; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { public void rotate(int[] nums, int k) { boolean[] isSolve = new boolean[nums.length]; for (int i = 0; i < nums.length; i++) { if (!isSolve[i]) { int temp = nums[i], t = i; while (!isSolve[t]) { isSolve[t] = true; t = (t + k) % nums.length; int temp1 = nums[t]; nums[t] = temp; temp = temp1; } } } } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution { public int maxProfit(int[] prices) { int price = 0, min = prices[0]; for (int i = 1; i < prices.length; i++) { if (prices[i] < prices[i - 1] && prices[i] < min) { min = prices[i]; } else { price = (prices[i] - min > price) ? (prices[i] - min) : price; } } return price; } }
|
其实prices[i] < prices[i - 1]用不上,prices[i] < prices[i - 1]不成立那么prices[i] < min一定不成立,反之
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution { public int maxProfit(int[] prices) { int price = 0, min = prices[0]; for (int i = 1; i < prices.length; i++) { if (prices[i] < min) { min = prices[i]; } else { price = (prices[i] - min > price) ? (prices[i] - min) : price; } } return price; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public int maxProfit(int[] prices) { int price = 0, min = prices[0]; for (int i = 1; i < prices.length; i++) { if (prices[i] < prices[i - 1]) { price += (prices[i - 1] - min); min = prices[i]; } if (i == prices.length - 1) { price += (prices[i] - min); } } return price; } }
|
没想出贪心策略,具体解法如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| class Solution { public boolean canJump(int[] nums) { int maxCanGo = 0; for (int i = 0; i < nums.length; i++) { if (i <= maxCanGo) { maxCanGo = Math.max(maxCanGo, nums[i] + i); if (maxCanGo >= nums.length - 1) { return true; } } } return false; } }
|
没想出贪心策略,具体解法如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public int jump(int[] nums) { int length = nums.length; int end = 0; int maxPosition = 0; int steps = 0; for (int i = 0; i < length - 1; i++) { maxPosition = Math.max(maxPosition, i + nums[i]); if (i == end) { end = maxPosition; steps++; } } return steps; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { public int hIndex(int[] citations) { int max = 0; for (int i = 0; i <= citations.length; i++) { int temp = 0; for (int j = 0; j < citations.length; j++) { if (citations[j] >= i) { temp++; } } if (temp >= i) { max = Math.max(max, i); } } return max; } }
|
二分搜索
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public int hIndex(int[] citations) { int left = 0, right = citations.length; while (left < right) { int mid = (left + right + 1) / 2; int count = 0; for (int i = 0; i < citations.length; i++) { if (citations[i] >= mid) { count++; } } if (count >= mid) { left = mid; } else { right = mid - 1; } } return left; } }
|
超时,GG
左右乘积
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public int[] productExceptSelf(int[] nums) { int[] L = new int[nums.length]; int[] R = new int[nums.length]; L[0] = 1; for (int i = 1; i < nums.length; i++) { L[i] = L[i - 1] * nums[i - 1]; } R[nums.length - 1] = 1; for (int i = nums.length - 2; i >= 0; i--) { R[i] = R[i + 1] * nums[i + 1]; } int[] result = new int[nums.length]; for (int i = 0; i < nums.length; i++) { result[i] = L[i] * R[i]; } return result; } }
|
空间复杂度 O(1)O(1)O(1) 的方法
动态构建R,并把答案直接保存到L
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public int[] productExceptSelf(int[] nums) { int[] L = new int[nums.length]; L[0] = 1; for (int i = 1; i < nums.length; i++) { L[i] = L[i - 1] * nums[i - 1]; } int R = 1; for (int i = nums.length - 1; i >= 0; i--) { L[i] *= R; R *= nums[i]; } return L; } }
|
爆时间,GG
直观理解,不用公式推导。可以这样想:假设从x加油站出发经过z加油站最远能到达y加油站,那么从z加油站直接出发,不可能到达y下一个加油站。因为从x出发到z加油站时肯定还有存储的油,这都到不了y的下一站,而直接从z出发刚开始是没有存储的油的,所以更不可能到达y的下一站。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; int i = 0; while (i < n) { int sumOfGas = 0, sumOfCost = 0; int cnt = 0; while (cnt < n) { int j = (i + cnt) % n; sumOfGas += gas[j]; sumOfCost += cost[j]; if (sumOfCost > sumOfGas) { break; } cnt++; } if (cnt == n) { return i; } else { i = i + cnt + 1; } } return -1; } }
|
其他人思路
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int sum = 0, index = 0, min = 0; for (int i = 0; i < gas.length; i++) { sum += gas[i] - cost[i]; if (sum < min) { min = sum; index = i + 1; } } return sum < 0 ? -1 : index; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public int romanToInt(String s) { Map<Character, Integer> map = new HashMap<>(); map.put('I', 1); map.put('V', 5); map.put('X', 10); map.put('L', 50); map.put('C', 100); map.put('D', 500); map.put('M', 1000); int sum = 0; for (int i = 0; i < s.length(); i++) { int temp = map.get(s.charAt(i)); if (i + 1 < s.length() && temp < map.get(s.charAt(i + 1))) { sum -= temp; } else { sum += temp; } } return sum; } }
|
1 2 3 4 5 6
| class Solution { public int lengthOfLastWord(String s) { String[] s1 = s.split(" "); return s1[s1.length - 1].length(); } }
|
会有空格情况,排除掉空格就好做了
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution { public int lengthOfLastWord(String s) { int end = s.length() - 1, t = 0; while (s.charAt(end) == ' ') { end--; } while (end >= 0 && s.charAt(end) != ' ') { t++; end--; } return t; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public String longestCommonPrefix(String[] strs) { String s = ""; int min = Integer.MAX_VALUE; for (int i = 0; i < strs.length; i++) { if (strs[i].length() < min) { min = strs[i].length(); } } for (int j = 0; j < min; j++) { char temp = strs[0].charAt(j); for (int i = 0; i < strs.length; i++) { if (strs[i].charAt(j) != temp) { return s; } if (i == strs.length - 1) { s += temp; } } } return s; } }
|
二分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| class Solution { public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } int min = Integer.MAX_VALUE; for (int i = 0; i < strs.length; i++) { if (strs[i].length() < min) { min = strs[i].length(); } } int left = 0, right = min; while (left < right) { int mid = (left + right + 1) / 2; if (isCommon(strs, mid)) { left = mid; } else { right = mid - 1; } } return strs[0].substring(0, left); }
public boolean isCommon(String[] strs, int length) { String temp = strs[0].substring(0, length); for (int i = 1; i < strs.length; i++) { for (int j = 0; j < length; j++) { if (temp.charAt(j) != strs[i].charAt(j)) { return false; } } } return true; } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| class Solution { public String reverseWords(String s) { s = s.trim(); String[] ss = s.split("\\s+"); StringBuilder builder = new StringBuilder(); for (int i = ss.length - 1; i >= 0; i--) { builder.append(ss[i]); if (i != 0) { builder.append(" "); } } return builder.toString(); } }
|
1 2 3 4 5 6 7 8 9 10
| class Solution { public String reverseWords(String s) { s = s.trim(); List<String> wordList = Arrays.asList(s.split("\\s+")); Collections.reverse(wordList); return String.join(" ", wordList); } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 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(); } }
|
GG
6. Z 字形变换 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Solution { public String convert(String s, int numRows) { if (numRows < 2) { return s; } List<StringBuilder> list = new ArrayList<StringBuilder>(); for (int i = 0; i < numRows; i++) { list.add(new StringBuilder()); } int t = 0, flag = -1; for (int i = 0; i < s.length(); i++) { list.get(t).append(s.charAt(i)); if (t == 0 || t == numRows - 1) { flag = -flag; } t += flag; } StringBuilder ss = new StringBuilder(); for (StringBuilder stringBuilder : list) { ss.append(stringBuilder); } return ss.toString(); } }
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| class Solution { public int strStr(String haystack, String needle) { if (needle.length() > haystack.length()) { return -1; } for (int i = 0; i <= haystack.length() - needle.length(); i++) { String temp = haystack.substring(i, i + needle.length()); if (temp.equals(needle)) { return i; } } return -1; } }
|
KMP算法
KMP 算法是一个快速查找匹配串的算法,它的作用其实就是本题问题:如何快速在「原字符串」中找到「匹配字符串」。
KMP 算法的应用范围要比 Manacher 算法广,Manacher 算法只能应用于「回文串」问题,相对比较局限,而「子串匹配」问题还是十分常见的。
背过这样的算法的意义在于:相当于大脑里有了一个时间复杂度为O(n) 的 api 可以使用,这个 api 传入一个原串和匹配串,返回匹配串在原串的位置。
模式匹配,寻找最长子串
前缀:前缀是包含首字母但不包含尾字母的所有子串
后缀:后缀是包含尾字母但不包含首字母的所有子串
注意i初始为1,也就是开头的两个进行比较,不然一个比较不了