211. 添加与搜索单词 - 数据结构设计
class WordDictionary {
class TrieNode {
TrieNode[] links;
boolean end;
public TrieNode() {
this.links = new TrieNode[26];
}
}
TrieNode root;
public WordDictionary() {
this.root = new TrieNode();
}
public void addWord(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.links[c - 'a'] == null) {
cur.links[c - 'a'] = new TrieNode();
}
cur = cur.links[c - 'a'];
}
cur.end = true;
}
private boolean helper(String word, TrieNode root) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (c != '.') {
if (cur.links[c - 'a'] != null) {
cur = cur.links[c - 'a'];
} else {
return false;
}
} else {
for (int j = 0; j < 26; j++) {
if (cur.links[j] != null && helper(word.substring(i + 1), cur.links[j])) {
return true;
}
}
return false;
}
}
return cur.end;
}
public boolean search(String word) {
return helper(word, root);
}
}
212. 单词搜索 II
class Solution {
int[] X = {0, 0, 1, -1}, Y = {1, -1, 0, 0};
boolean[][] isVisit;
private boolean helper(char[][] board, int i, int j, int num, String word) {
if (num == word.length()) {
return true;
}
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || isVisit[i][j] == true) {
return false;
}
if (board[i][j] == word.charAt(num)) {
isVisit[i][j] = true;
for (int k = 0; k < 4; k++) {
int newI = i + X[k], newJ = j + Y[k];
if (helper(board, newI, newJ, num + 1, word) == true) {
return true;
}
}
isVisit[i][j] = false;
return false;
} else {
return false;
}
}
public List<String> findWords(char[][] board, String[] words) {
isVisit = new boolean[board.length][board[0].length];
Set<String> set = new HashSet<>();
for (String word : words) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
for (int k = 0; k < board.length; k++) {
Arrays.fill(isVisit[k], false);
}
if (helper(board, i, j, 0, word)) {
set.add(word);
}
}
}
}
return new ArrayList<>(set);
}
}
213. 打家劫舍 II
偷第一间就不能偷最后一间，不偷第一间就可以偷最后一间。取两种情况的较大值。
class Solution {
public int rob(int[] nums) {
int[] dp = new int[nums.length];//偷第一间
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
if (i == nums.length - 1) {
dp[i] = dp[i - 1];
continue;
}
dp[i] = Math.max((i - 2 >= 0 ? dp[i - 2] : 0) + nums[i], dp[i - 1]);
}
int res = dp[nums.length - 1];
Arrays.fill(dp, 0);//不偷第一间
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max((i - 2 >= 0 ? dp[i - 2] : 0) + nums[i], dp[i - 1]);
}
return Math.max(res, dp[nums.length - 1]);
}
}
214. 最短回文串
暴力法：
不断从大到小枚举s的前缀，只要某个前缀是回文串，那么把后面的子串反转之后加到前面，便是最短的回文串。
时间复杂度On2，最后一个案例超时。
class Solution {
private boolean isPar(String s) {
if ("".equals(s)) {
return true;
}
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) {
return false;
}
}
return true;
}
public String shortestPalindrome(String s) {
if ("".equals(s)) {
return "";
}
StringBuilder res = new StringBuilder();
for (int i = s.length() - 1; i >= 0; i--) {
if (isPar(s.substring(0, i + 1))) {
StringBuilder str = new StringBuilder(s.substring(i + 1));
str.reverse();
res.append(str).append(s);
return res.toString();
}
}
StringBuilder str = new StringBuilder(s.substring(1));
str.reverse();
res.append(str).append(s);
return res.toString();
}
}
字符串哈希:
如果测试数据比较刁钻，改一下base和mod或者在left==right的时候加一个双重验证，手动判断是不是回文串。
class Solution {
public String shortestPalindrome(String s) {
int len = s.length();
long base = 131, mod = 1000000007;
long left = 0, right = 0, mul = 1, best = -1;
for (int i = 0; i < len; i++) {
left = (left * base + s.charAt(i)) % mod;
right = (right + mul * s.charAt(i)) % mod;
if (left == right) {
best = i;
}
mul = mul * base % mod;
}
String add = (best == len - 1 ? "" : s.substring((int) best + 1));
StringBuilder res = new StringBuilder(add).reverse();
res.append(s);
return res.toString();
}
}
215. 数组中的第K个最大元素
自己写的快排37ms。
class Solution {
public int partition(int lo, int hi, int[] nums) {
int temp = nums[lo];
while (lo < hi) {
while (lo < hi && nums[hi] > temp) {
hi--;
}
nums[lo] = nums[hi];
while (lo < hi && nums[lo] < temp) {
lo++;
}
nums[hi] = nums[lo];
}
nums[lo] = temp;
return lo;
}
public void quickSort(int lo, int hi, int[] nums) {
if (lo < hi) {
int pivot = partition(lo, hi, nums);
quickSort(lo, pivot - 1, nums);
quickSort(pivot + 1, hi, nums);
}
}
public int findKthLargest(int[] nums, int k) {
quickSort(0, nums.length - 1, nums);
return nums[nums.length - k];
}
}
库函数的快排2ms。
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
最大堆 2ms：
class Solution {
public int findKthLargest(int[] nums, int k) {
int heapSize = nums.length;
buildMaxHeap(nums, heapSize);
for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
swap(nums, 0, i);
--heapSize;
maxHeapify(nums, 0, heapSize);
}
return nums[0];
}
public void buildMaxHeap(int[] a, int heapSize) {
for (int i = heapSize / 2; i >= 0; --i) {
maxHeapify(a, i, heapSize);
}
}
public void maxHeapify(int[] a, int i, int heapSize) {
int l = i * 2 + 1, r = i * 2 + 2, largest = i;
if (l < heapSize && a[l] > a[largest]) {
largest = l;
}
if (r < heapSize && a[r] > a[largest]) {
largest = r;
}
if (largest != i) {
swap(a, i, largest);
maxHeapify(a, largest, heapSize);
}
}
public void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
216. 组合总和 III
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public void dfs(int begin, int k, int n) {
if (n < 0 || k < 0) {
return;
}
if (k == 0 && n == 0) {
res.add(new ArrayList<>(temp));
}
for (int i = begin; i <= 9; i++) {
temp.add(i);
dfs(i + 1, k - 1, n - i);
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
dfs(1, k, n);
return res;
}
}
217. 存在重复元素
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i : nums) {
if (!set.add(i)) {
return true;
}
}
return false;
}
}
218. 天际线问题
线段树，面试应该不会考，先不做了。
219. 存在重复元素 II
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
if (i - map.get(nums[i]) <= k) {
return true;
} else {
map.put(nums[i], i);
}
} else {
map.put(nums[i], i);
}
}
return false;
}
}
网友评论