孙云增的博客

删除最外层括号题目 有效括号字符串为空 (“”)、”(“ + A + “)” 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，””，”()”，”(())()” 和 “(()(()))” 都是有效的括号字符串。 如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。 给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + … + P_k，其中 P_i 是有效括号字符串原语。 对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。 示例1 输入：”(()())(())”输出：”()()()”解释：输入字符串为 “(()())(())”，原语化分解得到 “(()())” + “(())”，删除每个部分中的最外层括号后得到 “()()” + “()” = “()()()”。 示例2 输入：”(()())(())(()(()))”输出：”()()()()(())”解释：输入字符串为 “(()())(...

Dynamic ProgrammingMinimum Path SumTitle Detail Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray. Return the largest sum of the given array after partitioning. Example 1:123Input: A = [1,15,7,9,2,5,10], K = 3Output: 84Explanation: A becomes [15,15,15,9,10,10,10]Note:121 <= K <= A.length <= 5000 <= A[i] <= 10^6 思路动态规划 问题。 用...

Dynamic ProgrammingPartition Array for Maximum SumTitle Detail Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray. Return the largest sum of the given array after partitioning. Example 1:123Input: A = [1,15,7,9,2,5,10], K = 3Output: 84Explanation: A becomes [15,15,15,9,10,10,10] Note:121 <= K <= A.length <= 5000 <= A[i] <= 10^...

Java for循环里面的 i++ 与 ++i在for循环里两者的作用是一样的 i++12345for(int i=0; i<5; i++){ System.out.print(i + ",");}>> 0, 1, 2, 3, 4 ++i12345for(int i=0; i<5; ++i){ System.out.print(i + ",");}>> 0, 1, 2, 3, 4 工作原理 i++1234{ System.out.print(i + ","); i++;} ++i1234{ System.out.print(i + ","); ++i;} 区别 在Java里面，i++ 需要开辟新的存储空间用于存储结果，++i 直接在原存储空间中存储结果。故 ++i 在 for 循环里面执行效率要高。 可以作为代码优化的一部分。 foreach 与 ...

Java Map常用类型 类型 特征 HashMap 根据 HashCode 存储数据，访问速度快。至多允许一条记录键为 null;允许多条记录的值为 null；线程非同步 TreeMap 保存的记录按照键(key)排序，也可自定义排序规则。用生成的 Iterator 遍历 TreeMap 得到记录是排序后的。不允许记录的键为 null；线程非同步 Hashtable 用 HashMap 类似,不同的是键值都不允许为 null。 支持线程同步，但写入较慢 LinkedHashMap 保留记录的插入顺序，生成Iterator遍历顺序与插入顺序一致。遍历比HashMap慢，键值都允许为 null；线程非同步 —> HashMap剖析 常用 API 方法 描述 Object put(Object k, Object v) 存入键值对 Object get(Object k) 返回键所映射的值；如果不存在该映射则返回 null boolean containsKey(Object k) 是否包含键 k ...

Dynamic ProgrammingCoin ChangeTitle Detail You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. Example 1:123Input: coins = [1, 2, 5], amount = 11Output: 3 Explanation: 11 = 5 + 5 + 1Example 1:12Input: coins = [2], amount = 3Output: -1Note: You may assume that you have an infinite numbe...

Some Algorithm using Math AlgorithmAlgorithm-1 Sqrt(x)Title detail Implement int sqrt(int x)Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned. Example 1:12Input: 4Output: 2Example 2:1234Input: 8Output: 2Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned. 思路 牛顿迭代法 ...

Map的应用Jewels and StonesTitle Detail 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”. Example 1:12Input: J = "aA", S = "aAAbbbb&quo...

快慢指针的应用判断链表是否存在环Title Detail Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list. Example 1: 123Input: head = [3,2,0,-4], pos = 1Output: trueExplanation: There is a cycle in the linked list, where tail connects to the second node. 思路利用快慢指针，快指针每次走两步，慢指针每次走一步。如果快指针能够追上慢指针，则链表存在环。 A...

Find Common CharactersTitle detail Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer. You may return the answer in any order. Example 112Input: ["bella","label","roller"]Output: ["e","l","...