算法-查找

发表于 | 分类于 ，

数组重复元素问题

给定一个数组，查看数组是否存在重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package leetcode.search;
import java.util.HashSet;
import java.util.Set;
/**
 * Created by cdx0312
 * 2018/4/6
 */
public class ContainsDuplicate_217 {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> record = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (record.contains(nums[i]))
                return true;
            record.add(nums[i]);
        }
        return false;
    }
}

给定一个数组，是否存在两个元素重复，并且两个元素下标之差的绝对值小于等于k。

维持set的长度为K

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package leetcode.search;
import java.util.HashMap;
import java.util.HashSet;
/**
 * Created by cdx0312
 * 2018/4/6
 */
public class ContainsDuplicateII {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> record = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (record.contains(nums[i]))
                return true;
            record.add(nums[i]);
            if (record.size() == k + 1)
                record.remove(nums[i-k]);
        }
        return false;
    }
}

给定一个数组，是否存在两个元素的之差的绝对值小于等于t，并且两个元素下标之差的绝对值小于等于k。

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
package leetcode.search;
import java.util.HashSet;
import java.util.TreeSet;
/**
 * Created by cdx0312
 * 2018/4/6
 */
public class ContainsDuplicateIII {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums.length < 2 || k == 0) {
            return false;
        }
        TreeSet<Long> set = new TreeSet<>();
        int i = 0;
        while (i < nums.length) {
            Long floor = set.floor((long) nums[i]);
            Long ceiling = set.ceiling((long) nums[i]);
            if ((floor != null && nums[i] - floor <= t ) ||
                    (ceiling != null && ceiling - nums[i] <= t)) {
                return true;
            }
            set.add((long) nums[i++]);
            if (i > k) {
                set.remove((long) nums[i - k - 1]);
            }
        }
        return false;
    }
}

数组和问题

数组中查找是否存在和为target的问题

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
36
37
38
39
40
41
package leetcode.search;
import java.util.HashMap;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class TwoSum_1 {
    //1、暴力O(N^2)
    public int[] twoSum3(int[] nums, int target) {
        int[] res = new int[2];
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
        return res;
    }
    //O(N) O(N)
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        HashMap<Integer, Integer> record = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (record.containsKey(complement)) {
                res[1] = i;
                res[0] = record.get(complement);
                return res;
            }
            record.put(nums[i], i);
        }
        return res;
    }
}

查找表问题

给定四个整形列表，A[i] + B[j] + C[k] + D[l] = 0,找出所有的i,j,k,l的个数。

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
package leetcode.search;
import java.util.HashMap;
/**
 * Created by cdx0312
 * 2018/4/5
 */
public class FourSumII_454 {
    //查找表中记录C,D中任意两个和的可能次数O(N^2)
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        HashMap<Integer, Integer> record = new HashMap<>();
        for (int aC : C) {
            for (int aD : D) {
                int tmp = aC + aD;
                if (record.containsKey(tmp)) {
                    record.put(tmp, record.get(tmp) + 1);
                } else {
                    record.put(tmp, 1);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                int tmp = 0 - A[i] - B[j];
                if (record.containsKey(tmp)) {
                    count += record.get(tmp);
                }
            }
        }
        return count;
    }
}

返回两个数组的交集

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
package leetcode.search;
import java.util.HashSet;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class IntersectoionOfTwoArray {
    public int[] intersection(int[] num1, int[] num2) {
        HashSet<Integer> record = new HashSet<>();
        HashSet<Integer> result = new HashSet<>();
        for (int aNum1 : num1) {
            record.add(aNum1);
        }
        for (int aNum1 : num2) {
            if (record.contains(aNum1))
                result.add(aNum1);
        }
        int[] resultA = new int[result.size()];
        int j = 0;
        for (int i : result) {
            resultA[j++] = i;
        }
        return resultA;
    }
}

给定两个字符串s,t，确定s是否可以通过替换变成t。Given “egg”, “add”, return true.Given “foo”, “bar”, return false.Given “paper”, “title”, return true.

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
package leetcode.search;
import java.util.HashSet;
import java.util.Set;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class IsomorphicStrings_205 {
    public boolean isIsomorphic(String s, String t) {
        int[] num = new int[256];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < num.length; i++)
            num[i] = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            int tmp = t.charAt(i);
            if (num[s.charAt(i)] == Integer.MAX_VALUE) {
                num[s.charAt(i)] = tmp;
                if (set.contains(tmp))
                    return false;
                else
                    set.add(tmp);
            } else {
                if (tmp != num[s.charAt(i)])
                    return false;
            }
        }
        return true;
    }
}

i和j的距离与i和k的距离相等

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
36
37
38
package leetcode.search;
import java.util.HashMap;
/**
 * Created by cdx0312
 * 2018/4/5
 */
public class NumberOfBoomerangs_447 {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        for (int i = 0; i < points.length; i++) {
            //和i点的距离，距离出现的频率
            HashMap<Integer, Integer> record = new HashMap<>();
            for (int j = 0; j < points.length; j++) {
                if (j != i) {
                    int dis = dis(points[i], points[j]);
                    if (record.containsKey(dis)){
                        record.put(dis, record.get(dis)+1);
                    } else {
                        record.put(dis, 1);
                    }
                }
            }
            for (Integer integer : record.keySet()) {
                if (record.get(integer) >= 2) {
                    res += record.get(integer) * (record.get(integer)-1);
                }
            }
        }
        return res;
    }
    private int dis(int[] point, int[] point1) {
        return (point[0] - point1[0]) * (point[0] - point1[0])
                + (point[1] - point1[1]) * (point[1] - point1[1]);
    }
}

按照字符串的频率逆序排列

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
36
package leetcode.search;
import java.util.*;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class SortCharactersByFrequency_451 {
    public String frequencySort(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            if (map.containsKey(c))
                map.put(c, map.get(c) + 1);
            else
                map.put(c, 1);
        }
        List<Character> [] bucket = new List[s.length() + 1];
        for (char key : map.keySet()) {
            int freq = map.get(key);
            if (bucket[freq] == null)
                bucket[freq] = new ArrayList<>();
            bucket[freq].add(key);
        }
        StringBuilder sb = new StringBuilder();
        for (int j = bucket.length - 1; j >= 0; j--) {
            if (bucket[j] != null) {
                for (char ch : bucket[j]) {
                    for (int i = 0; i < map.get(ch); i++)
                        sb.append(ch);
                }
            }
        }
        return sb.toString();
    }
}

判断t和S是否由相同的char组成

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package leetcode.search;
import java.util.HashMap;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class ValidAnagram_242 {
    public boolean isAnagram(String s, String t) {
        if (s == null && t == null)
            return true;
        if (s == null || t == null)
            return false;
        if (s.length() != t.length())
            return false;
        HashMap<Character, Integer> sMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char s1 = s.charAt(i);
            char t1 = t.charAt(i);
            if (sMap.containsKey(s1))
                sMap.put(s1, sMap.get(s1)+1);
            else
                sMap.put(s1,1);
            if (sMap.containsKey(t1))
                sMap.put(t1, sMap.get(t1)-1);
            else
                sMap.put(t1, -1);
        }
        for (Character ch : sMap.keySet()) {
            if (sMap.get(ch) != 0)
                return false;
        }
        return true;
    }
    public boolean isAnagram1(String s, String t) {
        int[] chars = new int[26];
        for (char c : s.toCharArray()) {
            chars[c-'a']++;
        }
        for (char c : t.toCharArray()) {
            chars[c-'a']--;
        }
        for (int i : chars) {
            if (i != 0)
                return false;
        }
        return true;
    }
}

判断一个字符串是否遵循固定的样式，如pattern = “abba”, str = “dog cat cat dog” should return true.

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package leetcode.search;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class WordPattern_290 {
    public boolean wordPattern(String pattern, String str) {
        if (pattern == null || str == null)
            return false;
        HashMap<Object, Integer> map = new HashMap<>();
        char[] chars = pattern.toCharArray();
        String[] strings = str.split(" ");
        if (chars.length != strings.length)
            return false;
        for (int i = 0; i < chars.length; i++) {
            if (!Objects.equals(map.put(chars[i], i), map.put(strings[i], i)))
                return false;
        }
        return true;
    }
    public boolean wordPattern1(String pattern, String str) {
        char[] chars = pattern.toCharArray();
        String[] strings = str.split(" ");
        String[] pat = new String[26];
        if (chars.length != strings.length)
            return false;
        Set<String> set = new HashSet<>();
        for (int i = 0; i < chars.length; i++) {
            if (pat[chars[i]-'a'] == null) {
                pat[chars[i]-'a'] = strings[i];
                if (set.contains(strings[i]))
                    return false;
                else
                    set.add(strings[i]);
            } else {
                if (!strings[i].equals(pat[chars[i]-'a']))
                    return false;
            }
        }
        return true;
    }
}

happy Number判定

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
package leetcode.search;
import java.util.HashSet;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class HappyNum_202 {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        int sum = 0;
        while (n != 1) {
            set.add(n);
            while (n != 0) {
                sum += (n % 10) * (n % 10);
                n = n / 10;
            }
            n = sum;
            sum = 0;
            if (set.contains(n))
                return false;
        }
        return true;
    }
}
Donate comment here