文章 224
评论 6
浏览 177807
palindrome - 132. Palindrome Partitioning II

palindrome - 132. Palindrome Partitioning II

132. Palindrome Partitioning II Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. Example: Input: “aab” Output: 1 Explanation: The palindrome partitioning [“aa”,“b”] could be produced using 1 cut. 思路: 这一题和131题的条件增加了只要找出切割字符串最少的一种分割方法。用dp来做,状态转移方程就是i到j是否是文字符串。 代码: java: class Solution { public int minCut(String s) { char[] c = s.toCharArray(); int n = c.leng....

palindrome - 131. Palindrome Partitioning

palindrome - 131. Palindrome Partitioning

131. Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Input: “aab” Output: [ [“aa”,“b”], [“a”,“a”,“b”] ] 思路: 题目意思是找出字符串中子串是回文字符串的所有组合,使用回溯来做。 代码: java: public class Solution { List<List<String>> resultLst; ArrayList<String> currLst; public List<List<String>> partition(String s) { resultLst = new ArrayList<Li....

Palindrome  - 9. Palindrome Number

Palindrome - 9. Palindrome Number

Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Example 1: Input: 121 Output: true Example 2: Input: -121 Output: false Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome. Example 3: Input: 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome. Follow up: Coud you solve it wi....

Palindrome - 5. Longest Palindromic Substring

Palindrome - 5. Longest Palindromic Substring

Longest Palindromic Substring Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: “babad” Output: “bab” Note: “aba” is also a valid answer. Example 2: Input: “cbbd” Output: “bb” 思路: 找出字符串中的回文字符串,解法有很多,比如dp,这里采用中容易想到的中心扩散法。主要区分一下偶回文和奇回文的处理,时间复杂度O(n^2),空间复杂度O(1) 代码: java: class Solution { public String longestPalindrome(String s) { if (s == null || s.length() == 0) return ""; int start = 0,....

Sliding Window - 395. Longest Substring with At Least K Repeating Characters

Sliding Window - 395. Longest Substring with At Least K Repeating Characters

395. Longest Substring with At Least K Repeating Characters Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times. Example 1: Input: s = "aaabb", k = 3 Output: 3 The longest substring is "aaa", as 'a' is repeated 3 times. Example 2: Input: s = "ababbc", k = 2 Output: 5 The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times. ....

Sliding Window - 340. Longest Substring with At Most K Distinct Characters

Sliding Window - 340. Longest Substring with At Most K Distinct Characters

Longest Substring with At Most K Distinct Characters Given a string S, find the length of the longest substring T that contains at most k distinct characters. Example 1: Input: S = “eceba” and k = 3 Output: 4 Explanation: T = “eceb” Example 2: Input: S = “WORLD” and k = 4 Output: 4 Explanation: T = “WORL” or “ORLD” 思路: 题目意思是说给定一个k,找出一个连续子串,子串里面最多只允许出现k个不同的字符。所以,使用两个指针来限定窗口大小,当超过k个不同的字符的时候,就调整窗口大小,而调整窗口的时候,需要用字符出现的频率来区分去除的字符是重复的还是不重复的。 代码: java: public class Solution { /** *....

Sliding Window - 3. Longest Substring Without Repeating Characters

Sliding Window - 3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters Given a string, find the length of the longest substring without repeating characters. Example 1: Input: “abcabcbb” Output: 3 Explanation: The answer is “abc”, with the length of 3. Example 2: Input: “bbbbb” Output: 1 Explanation: The answer is “b”, with the length of 1. Example 3: Input: “pwwkew” Output: 3 Explanation: The answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence....

Sliding Window - 76. Minimum Window Substring

Sliding Window - 76. Minimum Window Substring

76. Minimum Window Substring Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = “ADOBECODEBANC”, T = “ABC” Output: “BANC” Note: If there is no such window in S that covers all characters in T, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in S. 思路: 这是一道经典的sliding window的题目,题目意思是给定两个字符串,字符串S如果包含另一个字符串T的所有字符,....

Sliding Window - 30. Substring with Concatenation of All Words

Sliding Window - 30. Substring with Concatenation of All Words

30. Substring with Concatenation of All Words You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters. Example 1: Input: s = “barfoothefoobarman”, words = [“foo”,“bar”] Output: [0,9] Explanation: Substrings starting at index 0 and 9 are “barfoor” and “foobar” respectively. The output or....

GET和POST的区别

GET和POST的区别

一、GET和POST GET用于获取信息,是无副作用的,是幂等的,且可以缓存的。 POST用于修改服务器上的数据,有副作用,非幂等的,不可缓存。 二、报文的区别 GET和POST没有实质的区别,只是报文格式的不同 GET和POST只是HTTP协议中的两种请求方式,而HTTP协议是基于TCP/IP的应用层协议,无论是GET还是POST,用的都是同一个传输层协议,所以在传输上没有区别。 报文格式上,不带参数时,最大的却别是第一行方法名不同。POST方法请求报文第一行是:POST /uri HTTP/1.1 \r\n,而GET方法请求报文第一行是:GET /uri HTTP/1.1 \r\n。 所以,不带参数的时候,它们的区别仅仅就是报文前面几个字符不同而已,至于带参数的报文的区别就是:约定GET方法的参数应该放在url中,POST方法参数应该放在body中。 例如:如果参数是:page=2,name=bitbo,那么GET方法的报文头部前面可能是: GET /book?page=2&name=bitbo HTTP/1.1 Host: localhost POST方法简约版报文....

String - 68. Text Justification

String - 68. Text Justification

68. Text Justification Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters. Extra spaces between words should be distributed as evenly as possible. If the number of spac....

String - 273. Integer to English Words

String - 273. Integer to English Words

273. Integer to English Words Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1. Example 1: Input: 123 Output: “One Hundred Twenty Three” Example 2: Input: 12345 Output: “Twelve Thousand Three Hundred Forty Five” 思路: 把数字按照英文输出,这和有一题读阿拉伯数字是类似的,就是一个实现题,思想就是把"Thousand", "Million", "Billion"作为单位,分段计算每一段应该读做多少,然后加上这个单位就可以。 代码: java: class Solution { private static final String[] LESS_THAN_20 = {"", "One", "Two", "Thre....

String - 12. Integer to Roman

String - 12. Integer to Roman

12. Integer to Roman Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. **Symbol** **Value** I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II. Roman numerals are usually....

String - 13. Roman to Integer

String - 13. Roman to Integer

13. Roman to Integer Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. **Symbol** **Value** I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II. Roman numerals are usually....

String - 171. Excel Sheet Column Number

String - 171. Excel Sheet Column Number

171. Excel Sheet Column Number Given a column title as appear in an Excel sheet, return its corresponding column number. For example: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... Example 1: Input: “A” Output: 1 思路: 这一 题是168的逆过程实质就是26进制转换为10进制。 代码: java: class Solution { public int titleToNumber(String s) { int res = 0, i = 0; while (i < s.length())res = res * 26 + s.charAt(i++) - 'A' + 1; return res; } }

String - 168. Excel Sheet Column Title

String - 168. Excel Sheet Column Title

168. Excel Sheet Column Title Given a positive integer, return its corresponding column title as appear in an Excel sheet. For example: 1 -> A 2 -> B 3 -> C ... 26 -> Z 27 -> AA 28 -> AB ... Example 1: Input: 1 Output: “A” 思路: 对于输入n进行取模,来确定这一位应该是什么字母,再计算剩下的数。依次类推,需要注意A是第一个,所以对n先减一再取模。 代码: java: class Solution { public String convertToTitle(int n) { StringBuilder sb = new StringBuilder(); while (n > 0) { n--; sb.append((char)('A' + n % 26)); n /= 26; } sb.reverse()....

String - 316. Remove Duplicate Letters

String - 316. Remove Duplicate Letters

316. Remove Duplicate Letters Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results. Example 1: Input: “bcabc” Output: “abc” Example 2: Input: “cbacdcbc” Output: “acdb” 思路: 题目意思是指移除字符串中重复的数字,剩下的字符串是按字典序排序的。可以先遍历一遍数组,记录每个字母出现的次数,然后根据这个数组去组装字符串res,使得这个字符串是字典序,具体细节就是,对于某一位字符,去判断输出结果的最后一位和当前字符大小,以及后面还有没有这个字符。如果说,res的最后一位....

String - 38. Count and Say

String - 38. Count and Say

38. Count and Say The count-and-say sequence is the sequence of integers with the first five terms as following: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n where 1 ≤ n ≤ 30, generate the _n_th term of the count-and-say sequence. Note: Each term of the sequence of integers wi....

String - 161. One Edit Distance

String - 161. One Edit Distance

One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. Have you met this question in a real interview?  Yes Problem Correction Example Example 1: Input: s = "aDb", t = "adb" Output: true Example 2: Input: s = "ab", t = "ab" Output: false Explanation: s=t ,so they aren't one edit distance apart 思路: 题目意思是两个字符串,通过一次替换或者增加或者删除操作,使得两个字符串相等。增加和删除其实属于一类,因为相对于短的字符串是增加,而长的字符串是减少,所以问题分类为两类。一类是替换,一类是增加删除。替换的在一次遍历的时候,只允许相同位置,出现一次字符不相同,增加和删除也是类似,找出相邻字符不....

String - 6. ZigZag Conversion

String - 6. ZigZag Conversion

ZigZag Conversion The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows); Example 1: Input: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR” 思路: 遍历字符串,找出....

Nothing just happens, it's all part of a plan.