8.22刷题

第一题 653. Two Sum IV - Input is a BST

题目描述

给定二叉搜索树BST与一个目标数target，判断BST中是否存在两个数之和等于target。

算法

两种方法：一种是利用HashSet进行查看；另一种将BST按sort的顺序取出后，利用two pointer进行遍历。

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        if (root == null)
            return false;
        List<Integer> list = new ArrayList<>();
        // Set<Integer> set = new HashSet<>();
        // backtrack(root, list);
        // for (int num : list) {
        //     if (set.contains(k - num))
        //         return true;
        //     set.add(num);
        // }
        // return false;
        backtrack(root, list);
        int low = 0, high = list.size() - 1;
        while (low < high) {
            int sum = list.get(low) + list.get(high);
            if (sum == k)
                return true;
            else if (sum > k)
                high--;
            else 
                low++;
        }
        return false;
    }
    
    public void backtrack(TreeNode root, List<Integer> list) {
        if (root == null)
            return;
        backtrack(root.left, list);
        list.add(root.val);
        backtrack(root.right, list);
    }
}

第二题 288. Unique Word Abbreviation

题目描述

进行缩略后，查看在一个word在lists中是否存在了重复的缩略

算法

关键是对于某个word重现出现的情况的判断，如果一个word在list中出现多次，按照题目的理解，可以算为出现一次。需要对出现的次数进行一定的查看。

class ValidWordAbbr {
    Map<String, String> map;

    public ValidWordAbbr(String[] dictionary) {
        map = new HashMap<>();
        for (String word : dictionary) {
            String key = getKey(word);
            if (map.containsKey(key)) {
                if (map.get(key).equals(word))
                    continue;
                map.put(key, "");
            } else {
                map.put(key, word);
            }
        }
    }
    
    public boolean isUnique(String word) {
        String key = getKey(word);
        if (map.containsKey(key)) {
            return map.get(key).equals(word);
        } else {
            return true;
        }
    }
    
    public String getKey(String word) {
        if (word.length() > 2)
            word = word.charAt(0) + String.valueOf(word.length() - 2) + word.charAt(word.length() - 1);
        return word;
    }
}

相关题目

对于回溯，如果有for循环，可以不用在开始的时候设置if语句提前结束循环，在for循环结尾处会自动结束。

对于可以通过某个长度或标识start结束的，可以考虑在开头利用长度条件，结束回溯的循环。

78. Subsets

关键思路：

for循环每一个在Array中的数，合理的选择结束（或自动让循环结束），并进行递归循环

320. Generalized Abbreviation

关键思路：

依然利用for循环，从头到尾的对word进行缩略。

第三题 408. Valid Word Abbreviation

题目描述

给定一个非空字符串s以及一个单词缩写abbr，返回字符串是否与单词缩写相匹配。

一个诸如”word”的字符串只包含如下有效的缩写：

[“word”, “1ord”, “w1rd”, “wo1d”, “wor1”, “2rd”, “w2d”, “wo2”, “1o1d”, “1or1”, “w1r1”, “1o2”, “2r1”, “3d”, “w3”, “4”]

请注意只有上面的缩写是”word”的有效缩写。其他任何字符串都不是”word”的有效缩写。其他任何字符串都不是

算法

简单基本的对照即可, 但是注意0的处理

public class validWordAbbreviation408 {
    public boolean validWordAbbreviation(String word, String abbr) {
        int sIndex = 0, abIndex = 0;
        while (sIndex < word.length() && abIndex < abbr.length()) {
            if (word.charAt(sIndex) == abbr.charAt(abIndex)) {
                sIndex++; abIndex++;
                continue;
            }
            if (abbr.charAt(abIndex) <= '0' || abbr.charAt(abIndex) > '9')
                return false;

            int start = abIndex;
            while (abIndex < abbr.length() && abbr.charAt(abIndex) >= '0' && abbr.charAt(abIndex) <= '9')
                abIndex++;
            int size = Integer.valueOf(abbr.substring(start, abIndex));
            sIndex += size;
        }
        return sIndex == word.length() && abIndex == abbr.length();
    }
}