note

In a standard HashMap implementation, each key must be unique. If you attempt to put the same key with a different value into a HashMap, the new value will overwrite the existing value associated with that key. This is because the purpose of a HashMap is to provide a one-to-one mapping between keys and values.

  1. pros/cons

Advantages of Hash:

  • Hash provides better synchronization than other data structures.
  • Hash tables are more efficient than search trees or other data structures.
  • Hash provides constant time for searching, insertion and deletion operations on average.
  • Hash tables are space-efficient.
  • Most Hash table implementation can automatically resize itself.
  • Hash tables are easy to use.
  • Hash tables offer a high-speed data retrieval and manipulation.

Disadvantages of Hash:

  • Hash is inefficient when there are many collisions.
  • Hash collisions are practically not be avoided for large set of possible keys.
  • Hash does not allow null values.
  • Hash tables have a limited capacity and will eventually fill up.
  • Hash tables can be complex to implement.
  • Hash tables do not maintain the order of elements, which makes it difficult to retrieve elements in a specific order.
  1.  difference
  • HashMap:
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
// Import the HashMap class
import java.util.HashMap;

public class Main {
  public static void main(String[] args) {
    // Create a HashMap object called capitalCities
    HashMap<String, String> capitalCities = new HashMap<String, String>();

    // Add keys and values (Country, City)
    capitalCities.put("England", "London");
    capitalCities.put("Germany", "Berlin");
    capitalCities.put("Norway", "Oslo");
    capitalCities.put("USA", "Washington DC");
    System.out.println(capitalCities);
      
      
    capitalCities.get("England");
    capitalCities.remove("England");
    capitalCities.clear();  
    capitalCities.size();  
      
      
      // Print keys
      for (String i : capitalCities.keySet()) {
          System.out.println(i);
      }
      // Print values
      for (String i : capitalCities.values()) {
          System.out.println(i);
      }
      
  }
}



// Java example
for (String key : hashMap.keySet()) {
    // Process each key
}

for (Integer value : hashMap.values()) {
    // Process each value
}

for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
    // Process each key-value pair
    String key = entry.getKey();
    Integer value = entry.getValue();
}

  • HashSet:
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
// Import the HashSet class
import java.util.HashSet;

public class Main {
  public static void main(String[] args) {
    HashSet<String> cars = new HashSet<String>();
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");
    cars.add("BMW");
    cars.add("Mazda");
    System.out.println(cars);
      
    cars.contains("Mazda");
    cars.remove("Volvo");
    //To remove all items, use the clear() method:
    cars.clear();
    cars.size();
    //Loop through the items of an HashSet with a for-each loop:
	for (String i : cars) {
  		System.out.println(i);
	}
      
  }
}
  • ArrayList:

a resizable array

ArrayList allows duplicate values in its collection. On other hand duplicate elements are not allowed in Hashset.

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
public class Main {
  public static void main(String[] args) {
      
    ArrayList<String> cars = new ArrayList<String>();
      
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");
    cars.add("Mazda");
      
    for (int i = 0; i < cars.size(); i++) {
      System.out.println(cars.get(i));
    }
      
     for (int i = 0; i < cars.size(); i++) {
      System.out.println(cars.get(i));
    }
      
  }
}
//To modify an element, use the set() method and refer to the index number:
cars.set(0, "Opel"); 
//To remove an element, use the remove() method and refer to the index number:
cars.remove(0); 
//To remove all the elements in the ArrayList, use the clear() method:
cars.clear();
//To find out how many elements an ArrayList have, use the size method:
cars.size();

242. Valid Anagram

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example :

1
2
Input: s = "anagram", t = "nagaram"
Output: true

Coding:

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
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] mark = new int[26];
        for(int i = 0; i < s.length(); i++ )
            mark[s.charAt(i) - 'a']++;
        for(int i = 0; i < t.length(); i++ )
            mark[t.charAt(i) - 'a']--;
        for(int i : mark){
            if(i != 0)
                return false;
        }
        return true;
    }
}

	//HashMap
   public boolean isAnagram(String s, String t) {
        if (s==null && t==null) return true;
        else if (s==null || t==null) return false;
        else if (s.length() != t.length()) return false;
        
        Map<Character, Integer> dict = new HashMap<>();
        for(char c : s.toCharArray()) dict.put(c, dict.getOrDefault(c, 0) + 1);
        for(char c : t.toCharArray()) {
            int count = dict.getOrDefault(c, 0);
            if (count == 0) return false;
            else dict.put(c, count - 1);
        }
        
        return true;
    }

1002. Find Common Characters

easy

Example :

1
2
Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

Coding:

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
class Solution {
    public List<String> commonChars(String[] words) {
        
        int numb = words.length;
        List<String> result = new ArrayList<>();
        if(words.length == 0) return result;
        int[] dict = new int[26];
        // first string in the array
        for(int i = 0; i < words[0].length(); i++){
            dict[words[0].charAt(i) - 'a']++;
        }
        for(int i = 1;i < words.length; i++){
            int[] temp = new int[26];
            for(int j = 0; j < words[i].length(); j++){
                temp[words[i].charAt(j) - 'a']++;
            }
            //compare ith string to the first string, take the min
            for(int k = 0; k < 26; k++){               
                dict[k]=Math.min(dict[k],temp[k]);
            }
        }
        for(int x = 0; x < 26; x++){
            while(dict[x] != 0){     // notice, here we should use while not if
                char res = (char)(x + 'a');
                String re = Character.toString(res);
                result.add(re);   
                dict[x] --;
            }
        }
        return result;
    }
}

ArrayList –> arraylist.add(re);

StringBuilder –> str.append(“point”);

349. Intersection of Two Arrays

Example 1:

1
2
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
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 int[] intersection(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> dict = new HashMap<>();
        HashSet<Integer> ans = new HashSet<Integer>(); // use HashSet cause we don't want repetitive number
        for(int i : nums1){
            dict.put(i , dict.getOrDefault(i ,0) + 1);
        }
        for(int j : nums2){
            if(dict.getOrDefault(j,0) > 0){
                ans.add(j);
                dict.put(j , dict.getOrDefault(j, 0) - 1);
            }
        }
        // convert hashset into int array
        int[] num = new int[ans.size()];
        int index = 0;
        for(Integer i : ans){  // you can write --> int i : ans , it is also right
            num[index++] = i;
        }
        
        return num;      
    }
}

toArray() function:

​ https://www.geeksforgeeks.org/arraylist-toarray-method-in-java-with-examples/

202. Happy Number

easy

A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

Example :

1
2
3
4
5
6
7
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

coding:

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
class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> rec = new HashSet<> ();
        while( n != 1 ){
            n = cal(n);
            if(rec.contains(n)){
                return false;
            } else{
                rec.add(n);
            }
        }

        return true;
        
    }
    public int cal(int m){
        int res = 0;
        while(m > 0){
            int temp = m % 10;
            res += temp * temp;
            m /= 10;
        }
        return res;
    }
}



// 2nd time
class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<>();
        int temp = 0;
        while( true ){
            while(n != 0){
                int dig = n%10;
                temp += dig * dig;
                n = n / 10;
            }
            if(set.contains(temp)) return false;
            set.add(temp);
            if(temp == 1) return true;
            n = temp;
            temp = 0; //!!!!
        }
        
    }
}

1. Two Sum

easy

Example :

1
2
3
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

coding:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] twoSum(int[] nums, int target) { 
        HashMap<Integer, Integer> mark = new HashMap<Integer, Integer>();
        for( int i = 0; i < nums.length; i ++){
            int num = nums[i];
            int diff = target - num;

            if(mark.containsKey(diff)){
                return new int[]{mark.get(diff),i};
            }else{
                mark.put(num, i);
            }
        }
        return new int[]{};
    }
}


WRONG:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }

        for(int i = 0; i < nums.length; i++){
            int addNum = target - nums[i];
            if(map.containsKey(addNum)){
                int[] res = {i, map.get(addNum)};
                return res;
            }
            
        }
        return new int[]{};
    }
}

Here’s an example to illustrate the problem:

Input:

1
2
makefileCopy codenums = [3, 2, 4, 4]
target = 8

With your current code, it would return [2, 2] because the number 4 appears twice in the array, and the HashMap will only store one of the occurrences.

454. 4Sum II

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example :

1
2
3
4
5
6
Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Coding:

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 fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> add1 = new HashMap<>();
        int res = 0;
        for(int i = 0; i < nums1.length; i++){
            for(int j = 0; j < nums2.length; j++){
                add1.put(nums1[i]+nums2[j], add1.getOrDefault(nums1[i]+nums2[j],0)+1);
            }
        }
        for(int i = 0; i < nums3.length; i++){ 
        // you don't need another hashmap here to record the sum of nums3 and nums4
            for(int j = 0; j < nums4.length; j++){
                int add2 = nums3[i]+nums4[j];
                if(add1.containsKey( 0 - add2)){
                    res += add1.get(0 - add2); // important
                }
            }
        }
        return res;       
    }
}

383. Ransom Note

iven two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example :

1
2
Input: ransomNote = "aa", magazine = "aab"
Output: true

Coding:

其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！if you want to record the number that a certain letter appears in a string you can actually just use Array instead of HashMap, it’s simpler and save more space.

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
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> map = new HashMap<>();
        
        for(int i = 0; i < magazine.length(); i++){
            map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0)+1);
        }
        for(int i = 0; i < ransomNote.length(); i++){
            if( map.containsKey(ransomNote.charAt(i)) ){
                map.put( ransomNote.charAt(i),map.get(ransomNote.charAt(i)) - 1 );
                if(map.get(ransomNote.charAt(i)) < 0){
                    return false;
                }
            }else{
                return false;
            }
        }
        return true;
    }
}
// !!! Array !!!
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 定义一个哈希映射数组
        int[] record = new int[26];

        // 遍历
        for(char c : magazine.toCharArray()){
            record[c - 'a'] += 1;
        }

        for(char c : ransomNote.toCharArray()){
            record[c - 'a'] -= 1;
        }
        
        // 如果数组中存在负数，说明ransomNote字符串总存在magazine中没有的字符
        for(int i : record){
            if(i < 0){
                return false; // can check if there's negative in the last loop. two loops are enough to solve this question.
            }
        }

        return true;
    }
}

15. 3Sum

Medium

Notice that the solution set must not contain duplicate triplets.

Example :

1
2
3
4
5
6
7
8
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

coding:

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
	// 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
	    // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) { 
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a  
        //notice这里只能是 i - 1不能是 i + 1， 因为如果是i + 1的话，判断的是结果集里面有没有重复的元素eg:{-1,-1,2}
                continue;
            }
            
/* you can also write like this
             while (i > 0 && i < nums.length && nums[i] == nums[i - 1]) {  // 去重a  
               i++;
            }
 */
            
            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right])); //!!!
		    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    
                    right--; //!!!!!!!
                    left++; //!!!!!!!!
                }
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
while(left < right){
               if(nums[i] + nums[left] + nums[right] > 0) right--;
               if(nums[i] + nums[left] + nums[right] < 0) left ++;
               if(nums[i] + nums[left] + nums[right] == 0){
                   res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                   while(right > left &&  nums[left] == nums[left + 1]) left++;
                   while(right > left && nums[right] == nums[right - 1] ) right--;
               left++;
               right--;   
               }
           }
       }
//!!!!!!!!!!! here use three if's  -> it's wrong
//!!!!!!!!!!!!should use if, else if, else

In Java, Arrays.asList is a method that is used to convert an array into a fixed-size list.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Arrays;
import java.util.List;

public class ArrayToListExample {
    public static void main(String[] args) {
        // Create an array
        String[] array = {"Java", "is", "awesome"};

        // Convert the array to a list
        List<String> list = Arrays.asList(array);

        // Now you can work with the list
        System.out.println("List elements: " + list);

        // Note that this list is backed by the original array, so changes to the list
        // will affect the array, and vice versa
        list.set(1, "rocks");
        System.out.println("Updated list: " + list);
        System.out.println("Original array: " + Arrays.toString(array));
    }
}

18. 4Sum

Medium

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

1
2
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

1
2
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
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
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
       
        for (int i = 0; i < nums.length; i++) {
		
            // nums[i] > target 直接返回, 剪枝操作 !!!!
            //两个条件缺一不可
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }
		
            if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重
                continue;
            }
            
            for (int j = i + 1; j < nums.length; j++) {

                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while (right > left) {
		    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}
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
// 2nd try
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
       
        for(int k = 0 ; k < nums.length; k++){
             while(k>0 && k < nums.length && nums[k] == nums[k-1]) k++;
            for(int i = k + 1; i < nums.length; i++){
                while(i > k + 1 && i < nums.length && nums[i] == nums[i-1]) i++;
                int left = i + 1;
                int right = nums.length - 1;
                while(left < right){
                    long sum = (long)nums[k]+nums[i]+nums[left]+nums[right];
                    if(sum > target) right --;
                    else if(sum < target) left ++;
                    else{
                        res.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right]));
                        while(right > left && nums[left] == nums[left + 1]) left++;
                        while(right > left && nums[right] == nums[right - 1 ]) right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;

    }
}

12. Integer to Roman

Medium

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

1
2
3
4
5
6
7
8
Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        
        StringBuilder res = new StringBuilder();
        
        for (int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                res.append(symbols[i]);
            }
        }
        
        return res.toString();
    }
}

128. Longest Consecutive Sequence

Medium

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

1
2
3
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

1
2
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
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 int longestConsecutive(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int res = 0 ;
        for(int i = 0; i < nums.length; i++){
            if(!map.containsKey(nums[i])){
                
                int left = map.getOrDefault(nums[i] - 1, 0);
                int right = map.getOrDefault(nums[i] + 1, 0);
                int sum = left + right + 1;
                //renew the map inf
                map.put(nums[i], sum);
                map.put(nums[i] - left, sum);// notice here you should substract left not substract 1. cause there might be more than one consecutive numbers.
                map.put(nums[i] + right, sum);

                res = Math.max(res, sum);

            }else{
                continue;
            }
        }
        return res;
    }
}

187. Repeated DNA Sequences

Medium

The DNA sequence is composed of a series of nucleotides abbreviated as 'A', 'C', 'G', and 'T'.

  • For example, "ACGAATTCCG" is a DNA sequence.

When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

Example 1:

1
2
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Example 2:

1
2
Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]
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
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        HashSet<String> map = new HashSet<>();
        HashSet<String> ress = new HashSet<>(); // to get rid of duplicates
        for(int i = 0; i < s.length() - 9; i++){
        //!!!! -9  not  - 10
        //think about s.length = 11, it should loop twice
            StringBuilder sb = new StringBuilder();
            for(int j = i; j < i+10; j++){
                sb.append(s.charAt(j));
            }
            String dna = sb.toString();
            if(map.contains(dna)){
                ress.add(dna);
            }else{
                map.add(dna);
            }
        }
        
        return new ArrayList<>(ress); //!!!!
}

improve:

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        HashSet<String> map = new HashSet<>();
        HashSet<String> res = new HashSet<>();
        for(int i = 0; i < s.length() - 9; i++){
            String dna = s.substring(i, i+10);
            //!!!! not subString
            if(map.contains(dna)){
                res.add(dna);
            }else{
                map.add(dna);
            }
        }
    

        return new ArrayList<>(res);
    }
}

299. Bulls and Cows

Medium

You are playing the Bulls and Cows game with your friend.

You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

  • The number of “bulls”, which are digits in the guess that are in the correct position.
  • The number of “cows”, which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.

Given the secret number secret and your friend’s guess guess, return the hint for your friend’s guess.

The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.

Example 1:

1
2
3
4
5
6
Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
  |
"7810"

Example 2:

1
2
3
4
5
6
7
Input: secret = "1123", guess = "0111"
Output: "1A1B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1123"        "1123"
  |      or     |
"0111"        "0111"
Note that only one of the two unmatched 1s is counted as a cow since the non-bull digits can only be rearranged to allow one 1 to be a bull.
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
class Solution {
    public String getHint(String secret, String guess) {
        char[] s = secret.toCharArray();
        char[] g = guess.toCharArray();
        int[] sc = new int[10];
        int[] gc = new int[10];
        int A = 0;
        int B = 0;
        for(int i = 0; i < s.length; i ++){
            if(s[i] == g[i]) {
                A++;
            }else{
                sc[s[i] - '0'] ++;
                gc[g[i] - '0'] ++;
            }
        }

        for(int i = 0 ; i < 10; i ++){
            B += Math.min(sc[i], gc[i]);
        }

        return Integer.toString(A) + "A" + Integer.toString(B) + "B";
        
        //IMPROVE:
        //return A + "A" + B + "B";
    }
}

781. Rabbits in Forest

Medium

There is a forest with an unknown number of rabbits. We asked n rabbits “How many rabbits have the same color as you?” and collected the answers in an integer array answers where answers[i] is the answer of the ith rabbit.

Given the array answers, return the minimum number of rabbits that could be in the forest.

Example 1:

1
2
3
4
5
6
7
8
Input: answers = [1,1,2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit that answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Example 2:

1
2
Input: answers = [10,10,10]
Output: 11
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 int numRabbits(int[] answers) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int res = 0;
        for(int i = 0 ; i < answers.length; i++){
            if(answers[i] == 0) res+= 1;
            else if(!map.containsKey(answers[i])){
                res += answers[i] + 1;
                 map.put(answers[i],1);
            }
            else{ 
               if(map.get(answers[i])>= 1 + answers[i]){
               //notice here is >= not >
               // this if statement is very important
                   res += answers[i] + 1;
                    map.put(answers[i],1);
               }else{
                   map.put(answers[i],map.get(answers[i])+1);
               }
            }
        }
        return res;
    }
}

1.this question is simple but hard to think about the situation like [0,0,1,1,1]

  1. use if elseif else, it easy to get in trouble to use if if if sometimes:
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
//wrong version, spent quite a few mintues to debug, it's tricky
public class MyClass {
    public int numRabbits(int[] answers) {
        HashSet<Integer> map = new HashSet<>();
        int res = 0;
        for(int i = 0 ; i < answers.length; i++){
            if(answers[i] == 0) res+= 1;
            //!!!
            if(!map.contains(answers[i])){
                res += answers[i] + 1;
                 map.add(answers[i]);
                 System.out.println("loop" + i + "is"+ answers[i]+"    +1");
            }
            if(map.contains(answers[i])){
                System.out.println("loop" + i + "is"+ answers[i]+"      +0");
               continue;
            }
        }
        return res;
    }
    public static void main(String args[]) {
      
        MyClass myClass = new MyClass();
      System.out.println(myClass.numRabbits(new int[]{1, 0, 1, 0, 0}));
    }

notice this kind of input:

answers =

[0,0,1,1,1]

Expected

6