# LeetCode Weekly Contest 42解题思路

## Leetcode 645. Set Mismatch

Problem:

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number. Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4] Output: [2,3]

Note:

• The given array size will in the range [2, 10000].
• The given array’s numbers won’t have any order.

```    public int[] findErrorNums(int[] nums) {
int[] map = new int[nums.length + 1];

for (int i = 0; i < nums.length; ++i){
map[nums[i]]++;
}

int a1 = 0;
int a2 = 0;
for (int i = 1; i <= nums.length; ++i){
if (map[i] == 2){
a1 = i;
}
if (map[i] == 0){
a2 = i;
}
}

return new int[]{a1, a2};
}```

```    public int[] findErrorNums(int[] nums) {
int[] res = new int[2];
for (int i : nums){
if (nums[Math.abs(i) - 1] < 0) res[0] = Math.abs(i);
else nums[Math.abs(i) - 1] *= -1;
}
for (int i = 0; i < nums.length; ++i){
if (nums[i] > 0) res[1] = i + 1;
}
return res;
}```

## Leetcode 646. Maximum Length of Pair Chain

Problem:

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion. Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order.

Example 1:

Input: [[1,2], [2,3], [3,4]] Output: 2 Explanation: The longest chain is [1,2] -> [3,4]

Note:

• The number of given pairs will be in the range [1, 1000].

```    public int findLongestChain(int[][] pairs) {
int n = pairs.length;
Arrays.sort(pairs, (a, b) -> (a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]));
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; ++i){
for (int j = 0; j < i; ++j){
if (pairs[i][0] > pairs[j][1]){
dp[i] = Math.max(dp[i], dp[j] + 1);
}
else{
dp[i] = Math.max(dp[i], dp[j]);
}
}
}
return dp[n - 1];
}```

DP方法时间复杂度为O(n2)O(n^2)，此题还可以更优，时间复杂度为O(nlogn)O(n\log n)，先对start排序，直接按照贪心法会出错，如：`[1,20],[2,3],[4,5]`，所以可以对end进行排序，于是有了`[2,3],[4,5],[1,20]`，此时再根据贪心选择start > end的区间，再更新end，即能得到答案。

```    public int findLongestChain(int[][] pairs) {
int n = pairs.length;
Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
int ans = 0;
int end = Integer.MIN_VALUE;
for (int i = 0; i < n; ++i){
while (i < n && pairs[i][0] <= end){
i ++;
}
if (i < n){
end = pairs[i][1];
ans ++;
}
}
return ans;
}```

## Leetcode 647. Palindromic Substrings

Problem:

Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: “abc” Output: 3 Explanation: Three palindromic strings: “a”, “b”, “c”.

Example 2:

Input: “aaa” Output: 6 Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

Note:

• The input string length won’t exceed 1000.

```    public int countSubstrings(String s) {
char[] cs = s.toCharArray();
int n = s.length();
int start = 0;
int cnt = 0;
while (start < n){
for (int i = start; i < n; ++i){
if (isPalidrome(cs, start, i)){
cnt++;
}
}
start++;
}
return cnt;
}

public boolean isPalidrome(char[] cs, int i, int j){
while (i < j){
if (cs[i] != cs[j]) return false;
i++;
j--;
}
return true;
}```

```abacba

a. bacb
b. abacba

```    public int countSubstrings(String s) {
int n = s.length();
char[] cs = s.toCharArray();
boolean[][] dp = new boolean[n][n];
int ans = 0;
for (int i = 0; i < n; ++i){
for (int j = i; j >= 0; --j){
if (i == j || (dp[i - 1][j + 1] && cs[i] == cs[j]) || (cs[i] == cs[j] && i - j == 1)){
dp[i][j] = true;
ans ++;
}
}
}
return ans;
}```

```    public int countSubstrings(String s) {
int n = s.length();
int ans = 0;
for (int i = 0; i < n; ++i){
ans += extendPalindrom(s.toCharArray(), i, i, 0);
ans += extendPalindrom(s.toCharArray(), i, i + 1, 0);
}
return ans;
}

public int extendPalindrom(char[] cs, int i, int j, int count){
while (i >= 0 && j < cs.length && cs[i] == cs[j]){
count ++;
i --;
j ++;
}
return count;
}```

## Leetcode 648. Replace Words

Problem:

In English, we have a concept called root, which can be followed by some other words to form another longer word - let’s call this word successor. For example, the root an, followed by other, which can form another word another. Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length. You need to output the sentence after the replacement.

Example 1:

Input: dict = [“cat”, “bat”, “rat”] sentence = “the cattle was rattled by the battery” Output: “the cat was rat by the bat”

Note:

• The input will only have lower-case letters.
• 1 <= dict words number <= 1000
• 1 <= sentence words number <= 1000
• 1 <= root length <= 100
• 1 <= sentence words length <= 1000

```    class TrieNode{
TrieNode[] children;
String str;
public TrieNode(){
children = new TrieNode[26];
}
}

public TrieNode add(TrieNode root, String str){
if (root == null) root = new TrieNode();
TrieNode cur = root;
for (char c : str.toCharArray()){
int pos = c - 'a';
if (cur.children[pos] == null) cur.children[pos] = new TrieNode();
cur = cur.children[pos];
}
cur.str = str;
return root;
}

public List<String> search(TrieNode root, String prefix){
List<String> ans = new ArrayList<>();
if (root == null) return ans;
TrieNode cur = root;
for (char c : prefix.toCharArray()){
int pos = c -'a';
if (cur.children[pos] == null){
break;
}
if (cur.children[pos] != null){
cur = cur.children[pos];
}
}
return ans;
}

TrieNode root;
public String replaceWords(List<String> dict, String sentence) {
root = new TrieNode();
for (String word : dict){
}
String[] replace = sentence.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < replace.length; ++i){
List<String> lists = search(root, replace[i]);
if (lists.isEmpty()){
sb.append(replace[i] + " ");
}
else{
int minLen = 1 << 30;
String ans = "";
for (String c : lists){
if (c.length() < minLen){
ans = c;
minLen = c.length();
}
}
sb.append(ans + " ");
}
}
return sb.toString().substring(0, sb.length() - 1);
}```

```    class TrieNode{
TrieNode[] children;
String str;
public TrieNode(){
children = new TrieNode[26];
}
}

public TrieNode add(TrieNode root, String str){
if (root == null) root = new TrieNode();
TrieNode cur = root;
for (char c : str.toCharArray()){
int pos = c - 'a';
if (cur.children[pos] == null) cur.children[pos] = new TrieNode();
cur = cur.children[pos];
}
cur.str = str;
return root;
}

public String search(TrieNode root, String prefix){
if (root == null) return null;
TrieNode cur = root;
for (char c : prefix.toCharArray()){
int pos = c -'a';
if (cur.children[pos] == null){
break;
}
if (cur.children[pos] != null){
cur = cur.children[pos];
if (cur.str != null){
return cur.str;
}
}
}
return null;
}

TrieNode root;
public String replaceWords(List<String> dict, String sentence) {
root = new TrieNode();
for (String word : dict){
}
String[] replace = sentence.split(" ");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < replace.length; ++i){
String key = search(root, replace[i]);
if (key == null){
sb.append(replace[i] + " ");
}
else{
sb.append(key + " ");
}
}
return sb.toString().substring(0, sb.length() - 1);
}```

```public String replaceWords(List<String> dict, String sentence) {
if (dict == null || dict.size() == 0) return sentence;

Set<String> dictSet = new HashSet<>();
for (String key : dict){
}

StringBuilder sb = new StringBuilder();
String[] replace = sentence.split(" ");
for (int i = 0; i < replace.length; ++i){
String prefix = "";
for (int j = 0; j < replace[i].length(); ++j){
prefix = replace[i].substring(0, j + 1);
if (dictSet.contains(prefix)){
break;
}
}
sb.append(" " + prefix);
}
return sb.deleteCharAt(0).toString();
}```

0 条评论

• ### LeetCode Weekly Contest 37解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### LeetCode Weekly Contest 44解题思路

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（80）：4.3 2-SAT（4）

挑战程序竞赛系列（80）：4.3 2-SAT（4） 传送门：POJ 2749: Building roads 题意： 阳关路与独木桥：有N个农场，其中A对相...

• ### 简单ac自动机学习

简单的来讲解一下自动机，虽然都在说这是和的组合，但个人觉得不需要深入理解这两个仍然可以学会它。同时由于网上已经存在了很多教程，本文尽量避免采取和网上一样的说法，...

• ### 105. 从前序与中序遍历序列构造二叉树

前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树：

• ### PAT 甲级 1021 Deepest Root (并查集，树的遍历)

1021. Deepest Root (25) 时间限制 1500 ms 内存限制 65536 kB 代码长度限制 16000 B ...

• ### 常见内存错误

C语言强大的原因之一在于几乎能掌控所有的细节，包括对内存的处理，什么时候使用内存，使用了多少内存，什么时候该释放内存，这都在程序员的掌控之中。而不像Java中，...

• ### C++ STL stack 用法

Stack(栈)是一种后进先出的数据结构，也就是LIFO(last in first out) ，最后加入栈的元素将最先被取出来，在栈的同一端进行数据的插入与取...

• ### 剑指offer刷题记(C++版本)

也算是临时抱佛脚了吧，3月之前刷了lintcode100多道题吧，后来发文章什么的就放下了，最近秋招在即在牛客网上想着把剑指offer这本书刷完，尽量早刷完吧，...

• ### 线性同余同余方程组解法（excrt）

【问题描述】 求关于 x 的同余方程组 x%a 1 =b 1  a1=b1 x%a 2 =b 2  a2=b2 x%a 3 =b 3  a3=b3 x%a...