Leetcode

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels. The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so “a” is considered a different type of stone from “A”. ...

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad. ...

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements. Example 1: Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1 Example 2: Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3 Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine? ...

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. ``` Solution ```java class Solution { public int countSubstrings(String s) { int n = s.length(); int[][] a = new int[n][n]; int count = 0; for (int i = 0; i < n; i++) { a[i][i] = 1; count++; } for (int col = 1; col < n; col++) { for (int row = 0; row < col; row++) { if (row == col - 1 && s.charAt(col) == s.charAt(row)) { a[row][col] = 1; count++; } else if (a[row + 1][col - 1] == 1 && s.charAt(col) == s.charAt(row) ) { a[row][col] = 1; count++; } } } return count; } } ```  

Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lowercase. The order of your output does not matter. Solution class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); int[] c = new int[26]; for (String s : strs) { Arrays.fill(c, 0); for (int i = 0 ; i < s.length(); i++) { c[s.charAt(i) - 'a']++; } String code = Arrays.toString(c); List<String> list = map.get(code); if (list == null) { list = new ArrayList<>(); } list.add(s); map.put(code, list); } return new ArrayList<>(map.values()); } } Solution 2021-11-15 class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> keyToList = new HashMap<>(); for (String s: strs) { char[] charString = s.toCharArray(); Arrays.sort(charString); String sortedWord = String.valueOf(charString); List<String> anagrams = keyToList.getOrDefault(sortedWord, new ArrayList<>()); anagrams.add(s); keyToList.put(sortedWord, anagrams); } List<List<String>> res = new ArrayList<>(); for (var anagrams: keyToList.values()) { res.add(anagrams); } return res; } }

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: ...

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area. Example: Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4 Solution class Solution { public int maximalSquare(char[][] matrix) { int n = matrix.length; if (n == 0) { return 0; } int m = matrix[0].length; int[][] dp = new int[n][m]; int answer = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (matrix[i][j] == '1') { dp[i][j] = 1; if (i > 0 && j > 0) { dp[i][j] += Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])); } answer = Math.max(answer, dp[i][j]); } } } return answer * answer; } }

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings. If there is no common subsequence, return 0. ...

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example 1: Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index. Constraints: ...

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. ...