文章 217
评论 6
浏览 143928
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” 思路: 遍历字符串,找出....

String - 179. Largest Number

String - 179. Largest Number

179. Largest Number Given a list of non negative integers, arrange them such that they form the largest number. Example 1: Input: [10,2] Output: “210” Example 2: Input: [3,30,34,5,9] Output: “9534330” Note: The result may be very large, so you need to return a string instead of an integer. 思路: 贪心的思想,比较相邻两个字符串拼接结果,比较大小。 代码: java: class Solution { public String largestNumber(int[] nums) { if (nums == null || nums.length == 0) return ""; int len = nums.length; String [] strs = new S....

String - 49. Group Anagrams

String - 49. Group Anagrams

49. Group Anagrams 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. 思路: 问题主要是如何选出字符串数组中同构异形的字符串,所以制造一个唯一标识,或者对每一个字符串进行排序,加上O(1)操作的map来找出相同的字符串。 代码: java: class Solution { public List<List<String>> groupAnagrams(String[] strs) { List<List<String>> res = new Arr....

String - 242. Valid Anagram

String - 242. Valid Anagram

242. Valid Anagram Given two strings s and _t _, write a function to determine if t is an anagram of s. Example 1: Input: s = “anagram”, t = “nagaram” Output: true Example 2: Input: s = “rat”, t = “car” Output: false Note: You may assume the string contains only lowercase alphabets. Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case? 思路: 记录第一个数组每个元素出现的次数,然后去对比另一个数组。 代码: java: class Solution { /*pu....

String - 290. Word Pattern

String - 290. Word Pattern

290. Word Pattern Given two strings s and _t _, write a function to determine if t is an anagram of s. Example 1: Input: s = “anagram”, t = “nagaram” Output: true Example 2: Input: s = “rat”, t = “car” Output: false Note: You may assume the string contains only lowercase alphabets. Follow up: What if the inputs contain unicode characters? How would you adapt your solution to such case? 思路: 题目的实质是两个数组相同元素的索引匹配,可以抽象为两个数组,分别记录某个元素在源字符串中的下标。这里用map来做,因为put....

String - 205. Isomorphic Strings

String - 205. Isomorphic Strings

205. Isomorphic Strings Given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself. Example 1: Input: s = “egg”, t = “add” Output: true Example 2: Input: s = “foo”, t = “bar” Output: false ....

String - 345. Reverse Vowels of a String

String - 345. Reverse Vowels of a String

345. Reverse Vowels of a String Write a function that takes a string as input and reverse only the vowels of a string. Example 1: Input: “hello” Output: “holle” Example 2: Input: “leetcode” Output: “leotcede” Note: The vowels does not include the letter “y”. 思路: 只翻转元音字母,就只用两个指针,首尾移动来翻转元音字母。 代码: java: class Solution { public static boolean[] vowels = new boolean[256]; static{ vowels['a'] = true; vowels['o'] = true; vowels['e'] = true; vowels['i'] = true; vowels['u'] = true; vowels['A'] =....

String - 186. Reverse Words in a String II

String - 186. Reverse Words in a String II

Reverse Words in a String II Given an input character array, reverse the array word by word. A word is defined as a sequence of non-space characters. The input character array does not contain leading or trailing spaces and the words are always separated by a single space. Have you met this question in a real interview?  Yes Problem Correction Example Example1 Input: s = "the sky is blue" Output: "blue is sky the" Example2 Input: "a b c" Output: "c b a" Challenge Could you do i....

String - 151. Reverse Words in a String

String - 151. Reverse Words in a String

151. Reverse Words in a String Given an input string, reverse the string word by word. Example 1: Input: “the sky is blue” **Output: **“blue is sky the” Example 2: Input: "  hello world!  " **Output: **“world! hello” Explanation: Your reversed string should not contain leading or trailing spaces. Example 3: Input: “a good   example” **Output: **“example good a” Explanation: You need to reduce multiple spaces between two words to a single space in the rever....

String - 344. Reverse String

String - 344. Reverse String

344. Reverse String Write a function that reverses a string. The input string is given as an array of characters char[]. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. You may assume all the characters consist of printable ascii characters. Example 1: Input: [“h”,“e”,“l”,“l”,“o”] Output: [“o”,“l”,“l”,“e”,“h”] 思路: two pointers 代码: java: class Solution { public void reverseString(char[]....

String - 383. Ransom Note

String - 383. Ransom Note

383. Ransom Note Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false. Each letter in the magazine string can only be used once in your ransom note. Note: You may assume that both strings contain only lowercase letters. canConstruct(“a”, “b”) -> false canConstruct(“aa”, “ab”) -> false canConstruct(“aa”, “aab”)....

String - 58. Length of Last Word

String - 58. Length of Last Word

58. Length of Last Word Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1. Examples: s = “leetcode” return 0. s = “loveleetcode”, return 2. Note: You may assume the string contain only lowercase letters. 思路: 找出第一个不重复出现的字母,这题最容易想到的是用一个map记录下每个字母出现的次数,然后根据map去寻找只出现一次的字母的索引。这样做的时间消耗太多,采用另一种思路:题目中的字母默认只会有小写字母,那就可以以a - z来遍历字符串,如果第一次出现的索引下标和最后一次相同,就是结果,然后记录这其中下标最小的。 代码: java: class Solution { /*public int firstUniqChar(Stri....

String - 14. Longest Common Prefix

String - 14. Longest Common Prefix

14. Longest Common Prefix Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: [“flower”,“flow”,“flight”] Output: “fl” Example 2: Input: [“dog”,“racecar”,“car”] Output: "" Explanation: There is no common prefix among the input strings. Note: All given inputs are in lowercase letters a-z. 思路: leetcode 一共有四种解法,这里就只写第一种,就是以一个string为标准,不断的调用api接口判断子串是否在字符串开头(注意,这一题只用判断从索引为....

String - 28. Implement strStr()

String - 28. Implement strStr()

28. Implement strStr() Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Example 1: Input: haystack = “hello”, needle = “ll” Output: 2 Example 2: Input: haystack = “aaaaa”, needle = “bba” Output: -1 Clarification: What should we return when needle is an empty string? This is a great question to ask during an interview. For the purpose of this problem, we will return 0 when needle&nbs....

Array - 508. Wiggle Sort

Array - 508. Wiggle Sort

508. Wiggle Sort Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3].... Example Example 1: Input: [3, 5, 2, 1, 6, 4] Output: [1, 6, 2, 5, 3, 4] Explanation: This question may have multiple answers, and [2, 6, 1, 5, 3, 4] is also ok. Example 2: Input: [1, 2, 3, 4] Output: [2, 1, 4, 3] Notice Please complete the problem in-place. 思路: 仔细分析输出数组,可以发现下标索引为奇数的数是极大值点,下标索引是偶数的是极小值点,只要遍历数组的时候,移动相邻两个数,就可以。 代码: java: public c....

Array - 376. Wiggle Subsequence

Array - 376. Wiggle Subsequence

376. Wiggle Subsequence A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence. For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,....

Array - 283. Move Zeroes

Array - 283. Move Zeroes

283. Move Zeroes Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements. Example: Input: [0,1,0,3,12] Output: [1,3,12,0,0] Note: You must do this in-place without making a copy of the array. Minimize the total number of operations. 思路: 把零放到数组最后,使用two points做,就是使用一个指针记录0和非零的数的分界线,另一个指针去寻找非零的数来和这个分界线的数进行交换。 代码: java: class Solution { public void moveZeroes(int[] nums) { if (nums == null || ....

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