leetcode 98. 验证二叉搜索树

2020-08-15 algorithm

题目:在二叉搜索树里找符合条件的节点值并求和

给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

  1. 节点的左子树只包含小于当前节点的数。
  2. 节点的右子树只包含大于当前节点的数。
  3. 所有左子树和右子树自身必须也是二叉搜索树。
    Example 1:
    输入:
     5
    / \
      1   4
         / \
        3   6
    输出: false
    解释: 输入为: [5,1,4,null,null,3,6]。
         根节点的值为 5 ,但是其右子节点值为 4 。
    

我的答案

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        } else if (root.left == null && null == root.right) {
            return true;
        } else if (root.left != null && null == root.right) {
            return  maxValLeft(root.left) < root.val && isValidBST(root.left);
        } else if (root.left == null && null != root.right) {
            return root.val < minValRight(root.right) && isValidBST(root.right);
        } else {
            // 左右分别都是BST,且左子树最大值 < 当前 node.val < 右子树最小值
            return maxValLeft(root.left) < root.val
                && root.val < minValRight(root.right) && isValidBST(root.left) && isValidBST(root.right);
        }
    }

    private int maxValLeft(TreeNode left) {
        if (left.right == null) {
            return left.val;
        } else {
            return maxValLeft(left.right);
        }
    }

    private int minValRight(TreeNode right) {
        if (right.left == null) {
            return right.val;
        } else {
            return maxValLeft(right.left);
        }
    }
}

我的分析

这道题首先分析二叉搜索树的特征,根据题目中的3个特征可以在代码里完全拷贝


leetcode 938. Range Sum of BST

2020-08-15 algorithm

题目:127. 单词接龙

给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:

每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。

说明: 如果不存在这样的转换序列,返回 0。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的,且二者不相同。

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

我的答案

public class LadderLengthBFS127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int step = 0;
        int wordLen = beginWord.length();
        Set<String> visited = new HashSet<>(wordList.size());
        String current = "";
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        while (!queue.isEmpty()) {
            step++;
            int curLevelSize = queue.size();
            for (int i = 0; i < curLevelSize; i++) {
                current = queue.poll();
                if (endWord.equals(current)) {
                    return step;
                }
                for (String candidate : wordList) {
                    if (!visited.contains(candidate) && onlyOneCharDiff(current, candidate, wordLen)) {
                        visited.add(candidate);
                        queue.offer(candidate);
                    }
                }
            }
        }
        return 0;
    }

    private boolean onlyOneCharDiff(String current, String endWord, int wordLen) {
        int diffCnt = 0;
        for (int i = 0; i < wordLen; i++) {
            if (current.charAt(i) != endWord.charAt(i)) {
                diffCnt++;
            }
            if (diffCnt > 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String... args) {
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = Stream.of("hot", "dot", "dog", "lot", "log", "cog").collect(Collectors.toList());
        LadderLengthBFS127 ladder = new LadderLengthBFS127();
        printline(ladder.ladderLength(beginWord, endWord, wordList));
    }
}

我的分析

遇到最短路径应该立即想到BFS,BFS的每一层穷举所有情况(注意剪枝优化),最早遇到的即最短路径。本题有2个注意点,1个是用step记录BFS的层数,1个是用visited哈希set记录已访问过的节点 避免产生环状图。


leetcode 938. Range Sum of BST

2020-08-15 algorithm

题目 1109. 航班预订统计

这里有 n 个航班,它们分别从 1 到 n 进行编号。 我们这儿有一份航班预订表,表中第 i 条预订记录 bookings[i] = [i, j, k] 意味着我们在从 i 到 j 的每个航班上预订了 k 个座位。 请你返回一个长度为 n 的数组 answer,按航班编号顺序返回每个航班上预订的座位数。

Example 1:

输入:bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出:[10,55,45,25,25]

我的答案

public class FlightBooking1109 {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] occurs = new int[n];
        for (int[] booking : bookings) {
            occurs[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                occurs[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < occurs.length; i++) {
            occurs[i] += occurs[i - 1];
        }
        return occurs;
    }
}

我的分析

这道题考察的是公交车上下车算法,记录每个时间点上下车分别多少人,然后用增量的方法得到当前的存量状态


java switch case 太多怎么重构

2020-06-03 java

Single-responsibility Principle.单一职责
Open-closed Principle.开闭原则
Liskov substitution principle.里氏替换原则
Interface segregation principle.接口隔离原则
Dependency Inversion principle.依赖倒转原则

结论:对于switch的case then, 要么用map绑定Map<case,then>,要么让case自己实现then

switch语句开发遇到多分支场景的时候经常用到,然而switch语句是不符合SOLID原则的(单一职责/开闭原则),如果switch语句里面case太多怎么重构

  1. 通过enum绑定各有特色的实现方法,来实现策略设计模式
public enum PlayerTypes { 
    TENNIS,FOOTBALL, SNOOKER
}

public class PlayerCreator {
   public Player createPlayer(PlayerTypes playerType)
         { switch (playerType) {
      case TENNIS:
         return new TennisPlayer();
      case FOOTBALL:
         return new FootballPlayer();
      case SNOOKER:
         return new SnookerPlayer();

      default:
         throw new IllegalArgumentException("Invalid player type: "
            + playerType);
      }
   }
}

在enum里定义一个抽象,不同Constant实现方法不同

public enum PlayerTypes { 
    TENNIS {
        @Override
        public Player createPlayer() {
            return new TennisPlayer();
        }
    },
    FOOTBALL {
        @Override
        public Player createPlayer() {
            return new FootballPlayer();
        }
    },
    SNOOKER {
        @Override
        public Player createPlayer() {
            return new SnookerPlayer();
        }
    };

    public abstract Player createPlayer();
}

// 这样获取Player对象就不需要switch语句了:

Player footballPlayer = PlayerTypes.valueOf("FOOTBALL").createPlayer();
  1. 不同于方法1,通过第三方Map来保存enum到实现的映射关系,来实现命令设计模式
// First, we define an interface:

public interface Command {

   Player create();
}

// Second, we provide implementations of this interface for each player type:

public class CreatePlayerCommand {

   private static final Map<String, Command> PLAYERS;

   static {
      final Map<String, Command> players = new HashMap<>();
      players.put("TENNIS", new Command() {
         @Override
         public Player create() {
            return new TennisPlayer();
         }
      });

      players.put("FOOTBALL", new Command() {
         @Override
         public Player create() {
            return new FootballPlayer();
         }
      });

      players.put("SNOOKER", new Command() {
         @Override
         public Player create() {
            return new SnookerPlayer();
         }
      });

      PLAYERS = Collections.unmodifiableMap(players);
   }

   public Player createPlayer(String playerType) {
      Command command = PLAYERS.get(playerType);

      if (command == null) {
         throw new IllegalArgumentException("Invalid player type: "
            + playerType);
      }

      return command.create();
   }

}

// 这样获取Player对象同样不需要switch语句了:

CreatePlayerCommand createCommand = new CreatePlayerCommand();
Player snookerPlayer = createCommand.createPlayer("SNOOKER");
  1. 跟方法2类似,不过Map的值不再是命令,而是java8的Supplier
    ``` java public class PlayerSupplier { private static final Map<String, Supplier> PLAYER_SUPPLIER;

    static { final Map<String, Supplier> players = new HashMap<>(); players.put("TENNIS", TennisPlayer::new); players.put("FOOTBALL", FootballPlayer::new); players.put("SNOOKER", SnookerPlayer::new); // 不可变视图 PLAYER_SUPPLIER = Collections.unmodifiableMap(players); }

    public Player supplyPlayer(String playerType) { Supplier player = PLAYER_SUPPLIER.get(playerType);

    if (player == null) { throw new IllegalArgumentException(“Invalid player type: “ + playerType); } return player.get(); } } // 这样获取Player对象同样不需要switch语句

PlayerSupplier playerSupplier = new PlayerSupplier(); Player snookerPlayer = playerSupplier.supplyPlayer(“SNOOKER”);


4. 除了返回Player,如果想返回带参数的函数怎么办  
``` java
@FunctionalInterface
public interface TriFunction<T, U, V, R> {
   R apply(T t, U u, V v);
}

public final class FunctionalStatistics {

   // 关键点在于定义一个FunctionMap
   private static final Map<String, TriFunction<TennisPlayer, Period, String, String>> STATISTICS = new HashMap<>();

   static {
      STATISTICS.put("SERVE", Statistics::computeServeTrend);
      STATISTICS.put("FOREHAND", Statistics::computeForehandTrend);
      STATISTICS.put("BACKHAND", Statistics::computeBackhandTrend);
   }

   public static String computeTrend(TennisPlayer tennisPlayer,
      Period period, String owner, String trend) {
      TriFunction<TennisPlayer, Period, String, String>
            function = STATISTICS.get(trend);

      if (function == null) {
         throw new IllegalArgumentException("Invalid trend type: "
            + trend);
         }

      return function.apply(tennisPlayer, period, owner);
   }
}
// Getting the FOREHAND trend (we use dummy arguments, because they are not relevant):

String forehandTrend = FunctionalStatistics.computeTrend(
    new TennisPlayer(), Period.ZERO, "SPORT TV", "FOREHAND");
  1. 把switch语句挪到工厂里, 抽象工厂设计模式
    ``` java public interface AbstractPlayerFactory {

    public Player createPlayer(Type type, int delta); }

public class PlayerFactory implements AbstractPlayerFactory {

@Override public Player createPlayer(Type type, int delta) { switch (type) { case TENNIS: return new TennisPlayer(type, delta); case FOOTBALL: return new FootballPlayer(type, delta); case SNOOKER: return new SnookerPlayer(type, delta);

     default:
     throw new IllegalArgumentException("Invalid player type: "
        + type);
  }    }

}


6. 如果switch语句里面还嵌套着判断语句,则可以用Predicate来实现  
``` java
public enum PlayerTypes {

   TENNIS(Collections.unmodifiableList(Arrays.asList(
      () -> new TennisPlayer("Rafael Nadal"),
      () -> new TennisPlayer("Roger Federer"),
      () -> new TennisPlayer("Andy Murray"))
   ),
   Collections.unmodifiableList(Arrays.asList(
      rank -> rank == 1, rank -> rank > 1 &&
      rank < 5, rank -> rank >= 5 && rank <= 10))
   ),
   FOOTBALL(Collections.unmodifiableList(Arrays.asList(
      () -> new FootballPlayer("Lionel Messi"),
      () -> new FootballPlayer("Cristiano Ronaldo"))
   ),
   Collections.unmodifiableList(Arrays.asList(
      rank -> rank == 1 || rank == 2,
      rank -> rank > 2 && rank <= 10))
   ),
   SNOOKER(Collections.unmodifiableList(Arrays.asList(
      () -> new SnookerPlayer("Ronnie O'Sullivan"),
      () -> new SnookerPlayer("Mark Selby"),
      () -> new SnookerPlayer("John Higgins"),
      () -> new SnookerPlayer("Neil Robertson"))
   ),
   Collections.unmodifiableList(Arrays.asList(
      rank -> rank == 1, rank -> rank == 2,
      rank -> rank > 3 && rank < 7,
      rank -> rank >= 7 && rank <= 10))
   );

   private final List<Supplier<Player>> names;
   private final List<Predicate<Integer>> conditions;

   // 2个 有序列表,一个保存Player,一个保存判断条件
   private PlayerTypes(List<Supplier<Player>> names,
         List<Predicate<Integer>> conditions) {
      this.names = names;
      this.conditions = conditions;
   }

   public static final Player supplyPlayer(String playerType,
         int rank) {

      if (rank < 1 || rank > 10) {
         throw new IllegalArgumentException("Invalid rank: " +
            rank);
      }

      List<Predicate<Integer>> selectors =
         PlayerTypes.valueOf(playerType).conditions;

      for (int i = 0; i < selectors.size(); i++) {
         if (selectors.get(i).test(rank)) {
            return PlayerTypes.valueOf(playerType)
               .names.get(i).get();
         }
      }

      throw new IllegalStateException("The enum is corrupted");
   }

}
// Obtaining the output, Snooker player: Neil Robertson:

Player snookerPlayer = PlayerTypes.supplyPlayer("SNOOKER", 10);

非信任代码交互的同步方法

2020-06-02 java

如果一个类可能会和非信任代码交互,使用 private final lock object

共享可变变量的同步访问方法有2种:方法同步和代码块同步。方法被申明为synchronized,或者代码块使用this,他们都使用这个Object的内置锁作为监视器。攻击者能够非法长期获得并持有锁,导致Dos.

解决办法是使用 private final lock object. 它使用了对象this内部申明的field而不是this对象的内置锁。实现方法是 synchronized(obj)而不是 synchronized 方法,攻击者由于访问不到this内部private field,获取不到obj,所以没法造成锁竞争。

对于静态方法,static synchronized方法也容易被攻击。当静态方法被申明为synchronized,执行时会获得该class对象内置锁。非信任代码可以通过object.getClass()方法获得class对象的内置锁。
所以对于static field, 需要用private static final Object上锁来维护它

举几个例子加深理解


  1. 方法同步, 非信任代码获取object后无限期锁住它导致changeValue()获取不到锁
public class SomeObject {

    // Locks on the object's monitor
    public synchronized void changeValue() {
        // ...
    }
    
    public static SomeObject lookup(String name) {
        // ...
    }
}

// Untrusted code
String name = // ...
SomeObject someObject = SomeObject.lookup(name);
if (someObject == null) {
    // ... handle error
}
synchronized (someObject) {
    while (true) {
        // Indefinitely lock someObject
        Thread.sleep(0x7FFFFFFF);
    }
}
  1. Public Non-final Lock Object, 非信任代码可以修改lock指向,比如Integer.valueOf(1),利用IntegerCache搞成全局锁
public class SomeObject {
  public Object lock = new Object();
 
  public void changeValue() {
    synchronized (lock) {
      // ...
    }
  }
}
  1. Private Final Lock Object, 正确合规, lock私有且不可改变,多线程调用this.changeValue方法井然有序
public class SomeObject {
  private final Object lock = new Object(); // private final lock object
 
  public void changeValue() {
    synchronized (lock) { // Locks on the private Object
      // ...
    }
  }
}
  1. 静态不合规同步方法,非信任代码可以获取类型并无限期加锁,导致changeValue()获取不到锁
public class SomeObject {
  //changeValue locks on the class object's monitor
  public static synchronized void changeValue() {
    // ...
  }
}
 
// Untrusted code
synchronized (SomeObject.class) {
  while (true) {
    Thread.sleep(Integer.MAX_VALUE); // Indefinitely delay someObject
  }
}
  1. private static final Object, 正确合规 , SomeObject.lock静态私有且不可改变,多线程调用 SomeObject.changeValue方法井然有序
public class SomeObject {
  private static final Object lock = new Object();
 
  public static void changeValue() {
    synchronized (lock) { // Locks on the private Object
      // ...
    }
  }
}

leetcode 817. 链表组件

2020-04-10 algorithm

题目:817. 链表组件

给定一个链表(链表结点包含一个整型值)的头结点 head。 同时给定列表 G,该列表是上述链表中整型值的一个子集。 返回列表 G 中组件的个数,这里对组件的定义为:链表中一段最长连续结点的值(该值必须在列表 G 中)构成的集合。

示例 1:
输入: 
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释: 
链表中,0 和 1 是相连接的,且 G 中不包含 2,所以 [0, 1] 是 G 的一个组件,同理 [3] 也是一个组件,故返回 2。
示例 2:
输入: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
输出: 2
解释: 
链表中,0 和 1 是相连接的,3 和 4 是相连接的,所以 [0, 1] 和 [3, 4] 是两个组件,故返回 2。

注意: 如果 N 是给定链表 head 的长度,1 <= N <= 10000。 链表中每个结点的值所在范围为 [0, N - 1]。 1 <= G.length <= 10000 G 是链表中所有结点的值的一个子集.

我的答案

public class ListComponent {
    public int numComponents(ListNode head, int[] intArr) {
        int cnt = 0;
        boolean isLastDivision = true;
        while (null != head) {
            if (valInArr(head.val, intArr)) {
                if (isLastDivision) {
                    cnt++;
                    isLastDivision = false;
                }
            } else {
                isLastDivision = true;
            }
            head = head.next;
        }
        return cnt;
    }

    private boolean valInArr(int val, int[] intArr) {
        return IntStream.of(intArr).anyMatch(i -> i == val);
    }
}

我的分析

这道题考察的是对单链表的理解,注意相邻分隔符和临界条件就不容易出错(java8 IntStream处理起来挺慢的)


leetcode 567. 字符串的排列

2020-04-01 algorithm

题目:567. 字符串的排列

给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = “ab” s2 = “eidbaooo” 输出: True 解释: s2 包含 s1 的排列之一 (“ba”). 示例2: 输入: s1= “ab” s2 = “eidboaoo” 输出: False

注意: 输入的字符串只包含小写字母 两个字符串的长度都在 [1, 10,000] 之间

我的答案

    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Long> aimMap = getMapFromString(s1);
        Optional<String> a = IntStream.range(0, s2.length() - s1.length() + 1)
            .mapToObj(i -> s2.substring(i, s1.length() + i))
            .filter(str -> isInclusion(str, aimMap))
            .findFirst();
        return a.isPresent();
    }

    private boolean isInclusion(String str, Map<Character, Long> aimMap) {
        Map<Character, Long> checkMap = getMapFromString(str);
        Optional<Map.Entry<Character, Long>> optional = checkMap.entrySet()
            .stream()
            .filter(entry -> !aimMap.containsKey(entry.getKey()) || aimMap.get(entry.getKey()) < entry.getValue())
            .findFirst();
        return !optional.isPresent();
    }

    private Map<Character, Long> getMapFromString(String e) {
        Map<Character, Long> smallCharCntMap = new HashMap<>();
        for (Character character : e.toCharArray()) {
            smallCharCntMap.merge(character, 1L, Long::sum);
        }
        return smallCharCntMap;
    }
    
    
    // 下面这种解法更好,滑动窗口
    static int[] x;
    static int[] y;

    public static boolean checkInclusion2(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() > s2.length()) {
            return false;
        }
        x = new int[26];
        y = new int[26];
        int w = s1.length();
        for (int i = 0; i < w; i++) {
            x[s1.charAt(i) - 'a']++;
            y[s2.charAt(i) - 'a']++;
        }
        if (isAnagram()) {
            return true;
        }

        for (int i = w; i < s2.length(); i++) {
            y[s2.charAt(i - w) - 'a']--;
            y[s2.charAt(i) - 'a']++;
            if (isAnagram()) {
                return true;
            }
        }
        return false;
    }

    private static boolean isAnagram() {
        for (int i = 0; i < 26; i++) {
            if (x[i] != y[i]) {
                return false;
            }
        }
        return true;
    }

我的分析

这道题采用滑动窗口的方法解题效率更高,每滑动一次窗口,只需要把前一个滑出的减掉,加上滑入的那个


leetcode 1160. 拼写单词

2020-03-28 algorithm

题目:1160. 拼写单词

给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。 假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。 注意:每次拼写(指拼写词汇表中的一个单词)时,chars 中的每个字母都只能用一次。 返回词汇表 words 中你掌握的所有单词的 长度之和。

示例 1: 输入:words = [“cat”,”bt”,”hat”,”tree”], chars = “atach” 输出:6 解释: 可以形成字符串 “cat” 和 “hat”,所以答案是 3 + 3 = 6。

示例 2: 输入:words = [“hello”,”world”,”leetcode”], chars = “welldonehoneyr” 输出:10 解释: 可以形成字符串 “hello” 和 “world”,所以答案是 5 + 5 = 10。

我的答案

    public int countCharacters(String[] words, String chars) {
        Map<Character, Long> groupCharCntMap = getMapFromString(chars);
        return Arrays.stream(words)
            .filter(e -> canBeSpelled(e, groupCharCntMap))
            .mapToInt(String::length)
            .reduce(0, Integer::sum);
    }

    private boolean canBeSpelled(String e, Map<Character, Long> groupCharCntMap) {
        Map<Character, Long> smallCharCntMap = getMapFromString(e);
        for (Map.Entry<Character, Long> e1 : smallCharCntMap.entrySet()) {
            if (!groupCharCntMap.containsKey(e1.getKey()) || groupCharCntMap.get(e1.getKey()) < e1.getValue()) {
                return false;
            }
        }
        return true;
    }

    private Map<Character, Long> getMapFromString(String e) {
        Map<Character, Long> smallCharCntMap = new HashMap<>();
        for (Character character : e.toCharArray()) {
            smallCharCntMap.merge(character, 1L, Long::sum);
        }
        return smallCharCntMap;
    }

我的分析

简单,但我的答案不是最优解,本题还可以和最终结果两两比较,先对目标chararray排序,然后byte之间比对


ms17

Software Engineer and Full Stack Developer, from Shanghai, China.