Leetcode

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. 解法1 vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>> res; unordered_map<string, vector<string>> m; for (string str : strs) { string t = str; sort(t.begin(), t.end()); // 这里可以不用判断m[t]存不存在 m[t].push_back(str); } for (auto a : m) { res.

48. Rotate Image 旋转图像

Medium You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation. Example 1: Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ] Example 2: Given input matrix = [ [ 5, 1, 9,11], i=0,j=1,n=4 [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], rotate the input matrix in-place such that it becomes: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ] 这道题让我们将一个n*n的二维矩阵顺时针旋转90度.

47. PermutationsII 全排列2

Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] 跟上道题不一样的地方就是会有重复的数字 vector<vector<int>> permuteUnique(vector<int>& nums) { // 这里用set来去重,因为递归回退的时候可能会有重复的元素 set<vector<int>> res{}; if (nums.size()==0) return vector<vector<int>>(); sort(nums.begin(), nums.end()); permuteUniqueCore(res, nums, 0, nums.size()); return vector<vector<int>> (res.begin(),res.end()); } void permuteUniqueCore(set<vector<int>> &res,vector<int> &nums,int k,int n){ if (k == n) { printArr(nums); res.insert(nums); return; } for (int i = k; i<n; i++) { if (nums[k]==nums[i] && i!

46 Permutations 全排列

Given a collection of distinct(不同) integers, return all possible permutations(全排列). Example: Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 这道题跟这道题https://github.com/longpf/AtOffer#27-字符串的排列简直一模一样 vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res{}; if (nums.size() == 0) return res; permuteCore(res, nums, 0, nums.size()); return res; } void permuteCore(vector<vector<int>> &res,vector<int> &num,int k,int n){ if (k == n) { res.push_back(num); return; } for (int i = k; i<n; i++) { swap(num[i], num[k]); permuteCore(res, num, k+1, n); swap(num[i], num[k]); } }

45. Jump Game 2 跳跃游戏2

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. Your goal is to reach the last index in the minimum number of jumps. Example: Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

44. Wildcard Matching 通配符匹配

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and characters like ?

146. LRU Cache 最近最少使用置换缓存器

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.

43. Multiply Strings 字符串相乘

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. Example 1: Input: num1 = "2", num2 = "3" Output: "6" Example 2: Input: num1 = "123", num2 = "456" Output: "56088" Note: The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself.

42. Trapping Rain Water 收集雨水

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 解法1 这道题给出一个数组,每个元素是一个宽为1的bar,问这些bar组成的图行最多能装多少水,就是图上蓝色的部分.如果当前位置高度大于两边的高度,我们就认为当前位置对结果有贡献.当前位置的贡献值,为左边高度的最大值和右边高度的最大值,取其中最小的和当前的高度相减. class Solution { public: int trap(vector<int>& height) { int l=0,r=height.size()-1,level=0,water=0; while(l < r){ int lower = height[height[l]<height[r]?

41. First Missing Positive 首个缺失的正数

Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your algorithm should run in O(n) time and uses constant extra space. Difficulty: Hard 这道题让我们找出数组中首个缺失的整数. 并且限定了时间负责度为O(n),空间复杂度为O(1),就是不让新建新的集合. 那这样只能在原数组上进行操作. 这里只能是把对应的数放到对应的索引上.比如例2中,3需要放到index为2的位置上,1要放到index为0的位置上.4和-1因为没有对应的索引被舍弃,-1本来就是负数,4越界了.这样先通过一次for循环排好数值对应的索引.再通过一次for循环找到第一个位置不对的就ok. class Solution { public: int firstMissingPositive(vector<int>& nums) { int n = nums.size(); if (n==0) return 1; for (int i=0;i<n;i++){ while (nums[i]>0 && nums[i]<=n && nums[i]!

40. Combination Sum II 组合之和之二

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be used once in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] Example 2:

39. Combination Sum 组合之和

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ] Example 2:

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, generate the nth term of the count-and-say sequence. Note: Each term of the sequence of integers will be represented as a string.

37. Sudoku Solver 求数独的一个解

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character ‘.

36. Valid Sudoku 验证数独

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.

35. Search Insert Position 搜索插入位置

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Example 1 : Input: [1,3,5,6], 5 Output: 2 Example 2 : Input: [1,3,5,6], 2 Output: 1 Example 3 : Input: [1,3,5,6], 7 Output: 4 Example 4 :

34. Search for a Range 搜索一个范围

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. 解法1 这道题让我们在一个有序数组中查找与输入target相同的起始位置和结束位置,限定时间复杂度为O(logn),这个是典型的二分查找时间复杂度.这道题我们先采用二分法找到一个与target相同的index,再想index的左边和右边搜索. class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { int index = search(nums,0,nums.

33. Search in Rotated Sorted Array 在旋转有序数组中搜索

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Difficulty: Medium 这道题让我们求一个旋转有序数组中是否存在一个给定的值,存在返回下标,不存在返回-1.如体重的例子0 1 2 4 5 6 7,我们不知道从哪开始旋转的,他的选择情况有7种

32. Longest Valid Parentheses 最长有效括号

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longest valid (well-formed) parentheses substring. For “(()”, the longest valid parentheses substring is “()”, which has length = 2. Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4. Difficulty: Hard 这道题比20. Valid Parentheses 验证括号难一些. 解法1 还是利用栈来求解,并定义start记录合法括号串的起始位置.遍历字符串,如果遇到左括号,则将当前下标压栈,如果遇到右括号,如果当前栈为空,则将下一个位置的下标记为start,如果栈不为空,则将栈顶元素取出.此时如果站为空,则更新结果和i-start+1的最大值,否则更新结果为i-栈顶元素的最大值. class Solution { public: int longestValidParentheses(string s) { int res = 0,start = 0; stack<int> m; for (int i=0;i<s.

31. Next Permutation 下一个排列

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 Difficulty: Medium

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. For example, given: s: "barfoothefoobarman" words: ["foo", "bar"] You should return the indices: [0,9]. (order does not matter). Difficulty: Hard 这道题让我们求串联所有单词的子串.所有单词来自输入的数组.所有单词的长度一样,串联的顺序不一定.如题中的例子,可以串联成foobar, barfoo. 这里我们用两个哈希表,一个用来存输入单词数组的每个单词和其的出现次数.然后遍历输入的字符串.设单词的个数为n,每个单词长度为m.每次遍历检查母字符串从该位置开始,每m截取一下查看在第一个哈希表是否存在.如果存在,存入第二个哈希表.如果n个次截取都匹配则这次遍历是符合要求的,存一下结果. 解法1 就是上面分析 class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int>res; if (s.

29. Divide Two Integers 两数相除

Divide two integers without using multiplication, division and mod operator. If it is overflow, return MAX_INT. Difficulty: Medium 这道题让我们求两个数相除A/B,并且不让使用乘法,除法,取余运算.这样我们只能优先想到位运算和加减法了. 假设A>B,最容易想到的是把A-B赋值给A,并且结果+1,然后再把A-B赋值给A,结果+1.这样一直下去.不过如果是2147483647/1这种情况不会不会通过OJ,因为效率太低,会提示Time Limit Exceeded,不可行.回头想想上面的位运算还没用到,如果A>2*B那么结果是不是加2,如果A>2*2*2B结果是不是加2*2.定义t为除数,p为结果的计数m为被除数的绝对值,n为除数的绝对值.例如100/2 t (除数) p (计数) res (结果) m (被除数) t (除数) p (计数) res (结果) m (被除数) t (除数) p (计数) res (结果) m (被除数) 2 1 32 36 2 1 48 4 2 1 50 0 4 2 4 2 4 2 8 4 8 4 16 8 16 8 32 16 32 16 64 32 解法1 class Solution { public: int divide(int dividend, int divisor) { if (divisor==0||(dividend==INT_MIN&&divisor==-1)) return INT_MAX; int sign = ((dividend<0)^(divisor<0))?

28. Implement strStr() 实现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 Difficulty: Easy 这道题让我们找出字符串中某个子字符串第一次出现的index.如果子字符串的长度为0,则返回0,如果子字符传的长度大于母字符串,则返回-1.遍历字符串的时候只需要遍历到剩下的长度等于字符串的位置即可. class Solution { public: int strStr(string haystack, string needle) { if (needle.empty()) return 0; int m = haystack.size(),n=needle.size(); if (m<n) return -1; for (int i=0;i<=m-n;++i) { int j=0; for (j=0;j<n;j++) if (haystack[i+j]!

27. Remove Element 移除元素

Given an array and a value, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn’t matter what you leave beyond the new length. Example: Given nums = [3,2,2,3], val = 3, Your function should return length = 2, with the first two elements of nums being 2.

26. Remove Duplicates From Sorted Array 有序数组中去除重复项

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. Example: Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

25 Reverse Nodes in K Group 每k个一组翻转链表

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed.

24. Swap Nodes in Pairs 成对交换节点

Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. Difficulty: Medium 解法1 迭代.建立dummy结点(注意之后释放该结点),拿1,2,3,4举例,第一次循环pre=dummy,将1指向3,将2指向1,再将pre设为1 class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode *dummy = new ListNode(-1),*pre = dummy; dummy->next = head; while (pre->next && pre->next->next) { // t=2 ListNode* t = pre->next->next; // 1 ->(指向next) 3 pre->next->next = t->next; // 2 -> 1 t->next = pre->next; // pre(dummy) -> t pre->next = t; // pre = 1 pre = t->next; //所以第一次while循环后的结果为 //dummy-> t(2) -> 1 -> 3 //pre = 1 然后到下一次循环 } ListNode* res = dummy->next; delete dummy; dummy = NULL; return res; } }; 解法2 递归,先递归到最后两个进行交换,再依次向前迭代.

23. Merge K Sorted Lists 合并k个有序链表

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Difficulty: Hard 合并k个排序列表.是前面21. Merge Two Sorted Lists 混合插入有序链表的升级版. 解法1 最先想到的就是利用21. Merge Two Sorted Lists 混合插入有序链表拿第一个链表与第二个合并,合并结果在于第三个比较.这样需要合并k-1次才能完成. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeKLists(vector<ListNode*>& lists) { int n = lists.

22. Generate Parentheses 生成括号

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Difficulty: Medium 这道题让我们列举出所有的括号字符串,前面还有一题20. Valid Parentheses 验证括号也是关于括号的.这里让列举出所有可能,可以优先考虑递归和DFS.定义left,right分别表示剩余左括号的数量和剩余的右括号的数量.如果在某次的递归中,left>right说明在已经生成的字符串中右括号的数量大于左括号的数量,是不合理的.当left,right都为0的时候,说明已经生成一个可用的括号串.其实这里有DFS的思想.为什么呢.看看下面是怎样递归的顺序,以题目给的例子n=3. ( (( ((( ((() ((()) ((())) (()()) ~ ()()() DFS(深度优先),这里可以想象成左括号优先 解法1 就是上面分析的解法 class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; generateParenthesisDFS(n,n,"",res); return res; } void generateParenthesisDFS(int left,int right,string out,vector<string>& res) { if (left>right) return; if (left==0 && right==0) res.

21. Merge Two Sorted Lists 混合插入有序链表

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 Difficulty: Easy 这道题让我们把两个有序的链表合并成一个有序的链表,与剑指offer 16题完全相同. 解法1 按照剑指offer 16题的递归解法 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1==NULL) return l2; if (l2==NULL) return l1; ListNode* head = NULL; if (l1->val<l2->val) { head = l1; head->next = mergeTwoLists(l1->next,l2); } else { head = l2; head->next = mergeTwoLists(l2->next,l1); } return head; } }; 解法2 采用循环的方式

20. Valid Parentheses 验证括号

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not. Difficulty: Easy 这道题让我们验证字符串是否是可用的括号,这个字符串只有括号.需要用到栈,当遇到左括号的时候压入到栈里,遇到右括号的时候需要检查栈顶元素是否为对应的左括号,如果不是对应的就返回false. class Solution { public: bool isValid(string s) { stack<char> parentheses; for (int i = 0; i<s.size();i++){ if (s[i]=='('||s[i]=='['||s[i]=='{') parentheses.push(s[i]); else { if (parentheses.empty()) return false; if (s[i]==')' && parentheses.

19. Remove Nth Node From End of List 移除链表倒数第N个节点

Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: Given n will always be valid. Try to do this in one pass. Difficulty: Medium 这道题让我们溢出链表中第N个节点,并制定n为有效的,就是n不会大于链表元素的总个数.看网上说这道题在问的时候可能会加上限制在一次循环的条件完成.如果用一次循环完成的话,就不能单独用一次循环来求链表元素的个数,要在循环到要删除的元素的位置时就该删除该元素.所以需要一点技巧. 我们可以定义两个指针pre,cur.先让cur前进N步,如果此时cur指向的为NULL,说明该链表的长度为N,所以移除首个元素就可以.如果cur指向的不为NULL,那么此时同时让pre,cur同时前进,直到cur指向最后一个元素,此时pre指向的就是倒数第N个元素,删除即可. 剑指offer 56题与这道题稍微有点像,可以一起看下 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { if (!

18. 4Sum 四数之和

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ] Difficulty: Medium

17. Letter Combinations of a Phone Number 电话号码的字母组合

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Input: Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want. 这道题让我们求电话号码的字母组合, 既2~9中,每个数字都代表2到3个字母,然后给出一个数字的字符串,求出这串数字可能代表的所有字母串.这道题可以用DFS的思想解决,关于DFS可以看二叉树 深度优先搜索(DFS)、广度优先搜索(BFS),可以简单的了解一下.那为什么说是DFS思想呢,比如给出”2345”,那个对应的结果为adgj,adgk,adgl,adhj,adhk,adhl...cfil这个顺序可以看做DFS的思想.大概这个意思. 解法1 解法1就是上面的分析的解法. class Solution { public: vector<string> letterCombinations(string digits) { vector<string> res; if (digits.

16. 3Sum Closest 最近三数之和

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

15. 3Sum 三数之和

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ] 这道题比Two Sum 两数之和等于一个输入的数复杂一些.

14. Longest Common Prefix 最长共同前缀

Write a function to find the longest common prefix string amongst an array of strings. Difficulty: Easy 可以把输入的字符串数组,看成一个char的二维数组,定义指针i,j分别代表行数和列数,逐列查找,如果char[i][j]不等于char[0][j]或者第i个字符串的长度小于j就可以返回之前的结果了. class Solution { public: string longestCommonPrefix(vector<string>& strs) { if (strs.empty()) return ""; string res = ""; for (int j=0;j<strs[0].size();j++) { char c = strs[0][j]; for (int i=1;i<strs.size();i++) { if (j>=strs[i].size() || strs[i][j]!=c) return res; } res += c; } return res; } };

13. Roman to Integer 罗马数字转化成整数

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. Difficulty: Easy 这道题是把罗马数字转化成整数,和12. Integer to Roman 整数转罗马数字正好反着.关于罗马数字的简单介绍可以回看12. Integer to Roman 整数转罗马数字. 这道题明确告诉我们输入的是罗马数字,所有不需要验证是否为罗马数字.下面只需要考虑 如果当前数字是最后一个数字,或之后的数字比它小的话,则加上当前的数字.举个反例CD-400,D比C大,所以先减去C(100)再加上D(500),就得到结果400 其他情况则减去这个数字 #include <unordered_map> using namespace std; class Solution { public: int romanToInt(string s) { int res = 0; unordered_map<char, int> m{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; for (int i = 0; i < s.size(); i++) { int val = m[s[i]]; //m[s[i+1]]不需要考虑越界,因为有'\0' m['\0']=0 if (i == s.

目录

Number 题号 Problems 题目 Difficulty 难度 Topics(Tags) 标签 1 Two Sum 两数之和等于一个输入的数 Easy Array, Hash Table 2 Add TwoNumbers 两个链表相加 Medium Linked List, Math 3 Longest Substring Without Repeating Characters 子字符串的最大不重复长度 Medium Hash Table, Two Pointers, String 4 Median of Two Sorted Arrays两个数组的中位数 Hard Array, Binary Search, Divide and Conquer 5 Longest Palindromic Substring 最长回文子字符串 Medium String, Dynamic Programming 6 ZigZag Conversion 之子形转换字符串 Medium String 7 Reverse Integer 翻转整数 Easy Math 8 String to Integer Atoi 把字符串转换成整数 Medium String, Math 9 Palindrome Number 验证回文数字 Easy Math 10 Regular Expression Matching 正则表达式匹配 Hard String, Dynamic Programming, Backtracking 11 Container With Most Water 装最多水的容器 Medium Array, Hash Table 12 Integer to Roman 整数转罗马数字 Medium String, Math 13 Roman to Integer 罗马数字转化成整数 Easy String, Math 14 Longest Common Prefix 最长共同前缀 Easy String 15 3Sum 三数之和 Medium Array, Two Pointers 16 3Sum Closest 最近三数之和 Medium Array, Two Pointers 17 Letter Combinations of a Phone Number 电话号码的字母组合 Medium String, Backtracking, DFS 18 4Sum 四数之和 Medium Array, Hash Table, Two Pointers 19 Remove Nth Node From End of List 移除链表倒数第N个节点 Medium Linked List, Two Pointers 20 Valid Parentheses 验证括号 Easy String, Stack 21 Merge Two Sorted Lists 混合插入有序链表 Easy Linked List 22 Generate Parentheses 生成括号 Medium String, Backtracking, DFS 23 Merge K Sorted Lists 合并k个有序链表 Hard Linked List, Divide and Conquer, Heap 24 Swap Nodes in Pairs 成对交换节点 Medium Linked List 25 Reverse Nodes in K Group 每k个一组翻转链表 Hard Linked List 26 Remove Duplicates From Sorted Array 有序数组中去除重复项 Easy Array, Two Pointers 27 Remove Element 移除元素 Easy Array, Two Pointers 28 Implement strStr() 实现strStr()函数 Easy Two Pointers, String 29 Divide Two Integers 两数相除 Medium Math , Binary Search 30 Substring With Concatenation of All Words 串联所有单词的子串 Hard Hash Table, Two Pointers, String 31 Next Permutation 下一个排列 Medium Array 32 Longest Valid Parentheses 最长有效括号 Hard String, Dynamic Programming 33 Search in Rotated Sorted Array 在旋转有序数组中搜索 Medium Array, Binary Search 34 Search for a Range 搜索一个范围 Medium Array, Binary Search 35 Search Insert Position 搜索插入位置 Easy Array, Binary Search 36 Valid Sudoku 验证数独 Medium Hash Table 37 Sudoku Solver 求数独的一个解 Hard Backtracking,Hash Table 38 Count and Say 计数和读法 Easy String 39 Combination Sum 组合之和 Medium Array, Backtracking 40 Combination Sum II 组合之和之二 Medium Array, Backtracking 41 First Missing Positive 首个缺失的正数 Hard Array 42 Trapping Rain Water 收集雨水 Hard Array, Two Pointers, Stack 43 Multiply Strings 字符串相乘 Medium String, Math 44 Wildcard Matching 通配符匹配 Hard Math, Dynamic Programming, Backtracking, Greedy 45 Jump Game 2 跳跃游戏2 Hard Array, Greedy 46 Permutations 全排列 Medium Backtracking 47 PermutationsII 全排列2 Medium Backtracking 48 Rotate Image 旋转图像 Medium Array 49 Group Anagrams 群组错位词 Medium String,Hash Table 146 LRU Cache 最近最少使用置换缓存器 Hard Design

12. Integer to Roman 整数转罗马数字

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999. Difficulty: Medium 罗马字符: I V X L C D M 阿拉伯数字: 1 5 10 50 100 500 1000 1~9 : I, II, III, IV, V, VI, VII, VIII, IX 10~90 : X, XX, XXX, XL, L, LX, LXX, LXXX, XC 100~900: C, CC, CCC, CD, D, DC, DCC, DCCC, CM 1000~3000: M, MM, MMM 例如: 整数1437的罗马数字为MCDXXXVII.

11. Container With Most Water 装最多水的容器

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container and n is at least 2. Difficulty: Medium

10. Regular Expression Matching 正则表达式匹配

Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → true Difficulty: Hard

9. Palindrome Number 验证回文数字

Determine whether an integer is a palindrome. Do this without extra space. Some hints: Could negative integers be palindromes? (ie, -1) If you are thinking of converting the integer to string, note the restriction of using extra space. You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case? There is a more generic way of solving this problem.

8 String to Integer Atoi 把字符串转换成整数

Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases. Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front. Difficulty: Medium 把字符串转换成整数,和剑指offer 49题相似,不过这里的要求比较多,实现atoi 判断开头是否有空格 判断开头是否有 '+','-' 如果遇到非法字符返回已有的结果 如果超过边界,返回边界值 class Solution { public: int myAtoi(string str) { int len = str.

7 Reverse Integer 翻转整数

Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. 分析 Difficulty: Easy

6 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:

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. Difficulty:Medium Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example: Input: "cbbd" Output: "bb" 这道题参考Grandyang,他博客里有全套leetcode讲解. 求最长回文串,回文串就是正着读反着读都一样的字符串.下面的解法是以一个字符为中心向两边扩散并比较 解法1: O(n^2) class Solution { public: public: string longestPalindrome(string s) { int startIdx = 0, left = 0, right = 0, len = 0; for (int i = 0; i < s.

Median of Two Sorted Arrays两个数组的中位数

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example2 nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5 分析 解法一: 思路来自Very concise O(log(min(M,N))) iterative solution with detailed explanation 看到O(log (m+n))一般来说就是分治法或是二分搜索,一个数组(长度为N)在中间切一刀,那它左边的索引L为(N-1)/2,右边的索引R为N/2.

Longest Substring Without Repeating Characters 子字符串的最大不重复长度

Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with the length of 1. Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring. 滑动窗口问题,比如abcabcbb,滑动到abca的时候需要丢弃第一个a变成bca,继续向右滑动,每次滑动都要检查有没有重复.感觉涉及到最大,最多的问题都可以试着网哈希表上靠. class Solution { public: int lengthOfLongestSubstring(string s) { int size = s.

Add TwoNumbers 两个链表相加

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.

Two Sum 两数之和等于一个输入的数

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. 要返回数组中两个数的索引,这两个数的和等于输入的数.最简单的两层for循环可定不能满足要求.考虑优化时间复杂度,可尝试牺牲时间复杂度. stack?queue?vector?还是hash_map.stack,queue,vector查找都是O(n),hash_map为O(1).接下来尝试用hash_map解决问题. class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int>res; if(nums.