Leetcode

【LeetCode】1. 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]. 思路: 先用 map 存储每个元素对应的原始下标,方便后续查找特定元素。 从头开始查找符合条件的结果,用 target 减去 nums[i] ,得到两数之差 t ,在 map 中寻找是否存在 t 且元素 t 的索引不等于 i ,若是则为最终结果,否则继续查找 nums[i+1] 。

【LeetCode】2. Add Two Numbers

题目描述: 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. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

【LeetCode】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:

【LeetCode】7. Reverse Integer

题目描述: Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 click to show spoilers. Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this! If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100. Did you notice that the reversed integer might overflow?

【LeetCode】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. Update (2015-02-10): The signature of the C++ function had been updated.

【LeetCode】9. Palindrome Number

题目描述: Determine whether an integer is a palindrome. Do this without extra space. click to show spoilers. 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?

【LeetCode】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.

【LeetCode】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. 思路: 这是一道将罗马数字转换成整数的题目。搞清楚罗马数字的表示特点即可。 参见维基百科:罗马数字 代码实现: class Solution { public: int romanToInt(string s) { unordered_map<char,int> hm; hm.insert(pair<char,int>('I',1)); hm.insert(pair<char,int>('V',5)); hm.insert(pair<char,int>('X',10)); hm.insert(pair<char,int>('L',50)); hm.insert(pair<char,int>('C',100)); hm.insert(pair<char,int>('D',500)); hm.insert(pair<char,int>('M',1000)); int sum=hm[s[s.size()-1]]; for(int i=s.size()-1;i>0;--i){ if(hm[s[i]]>hm[s[i-1]]){ sum-=hm[s[i-1]]; }else{ sum+=hm[s[i-1]]; } } return sum; } };

【LeetCode】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. 思路: 通过一个指针 newhead 指示新的链表头部,比较链表 l1 和链表 l2 的第一个结点; 若 l1 的第一个节点比 l2 小,则将其尾插进新链表,移动指针 l1->next;若 l2 的第一个节点比 l1 小,同理; 递归得解。 代码实现: /** * 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==nullptr&&l2==nullptr) return nullptr; if(l1==nullptr || l2==nullptr) return (l1==nullptr)?

【LeetCode】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 in place with constant memory. For example, Given input array 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.

【LeetCode】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 in place with constant memory. The order of elements can be changed. It doesn’t matter what you leave beyond the new length. Example: Given input array nums = [3,2,2,3], val = 3 Your function should return length = 2, with the first two elements of nums being 2.

【LeetCode】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]. 思路: 本题要求时间复杂度为 O(logn) ,自然应该想到二分查找。 首先,找到target的位置,然后分别从前从后找首尾位置即可,这是简单明了的解法。 注:在找到 target 后继续二分查找首尾出现的位置效率会更高一些。

【LeetCode】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. Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0 思路: 大水题,通过二分查找实现。 注意:如果数组中找不到 target 。 要么 target 比当前元素小,返回当前元素的位置(mid)。因为数组后移,当前位置存放 target ; 要么 target 比当前元素大,返回当前元素的位置的后一个位置(mid+1)。

【LeetCode】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.

【LeetCode】53. Maximum Subarray

题目描述: Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6. 思路: 用sum保存连续序列之和,用max表示最大值,一次遍历即可,时间复杂度O(n)。 sum<0,则舍弃前面的数 sum>max,则更新最大值max 代码实现: int maxSubArray(int* nums, int numsSize) { int sum=0; int max=INT_MIN; for(int i=0;i<numsSize;i++){ sum+=nums[i]; if(sum>max){ max = sum; } if(sum<0){ sum = 0; } } return max; }

【LeetCode】54. Spiral Matrix

题目描述: Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5]. 思路: 给定一个矩阵,以回旋形式以此遍历矩阵中的每个元素。 设置 direction ,表示遍历方向(向右,向下,向左,向上); 设置 left、right、top、buttom ,分别指示矩阵左边界、右边界、上边界、下边界; 每遍历一个元素将其添加到 ret 中,直至 left>right 或 top>buttom 。

【LeetCode】58. Length of Last Word

题目描述: Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a character sequence consists of non-space characters only. Example: Input: “Hello World” Output: 5 思路: 从后往前遍历字符串。 注意字符串后面是否有空格,所以先判断字符串是否以空格结尾; 若当前字符不是空格,开始计数,直到遇到空格,返回计数的结果。 代码实现: class Solution { public int lengthOfLastWord(String s) { int count = 0; int i = s.

【LeetCode】59. Spiral Matrix II

题目描述: Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. For example, Given n = 3, You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 思路: 题意要求根据 n ,创建一个 n*n 的回旋矩阵。 设置 direction ,表示构造方向(向右,向下,向左,向上); 设置 left、right、top、buttom ,分别指示矩阵左边界、右边界、上边界、下边界; 设置 count 指示当前的数值; 按右-下-左-上的顺序不断循环构造,直至 left>right 或 top>buttom 。

【LeetCode】66. Plus One

题目描述: Given a non-negative integer represented as a non-empty array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits are stored such that the most significant digit is at the head of the list. 思路: 题目的意思是将数组当成一个整数,然后对这个整数加 1 ,返回结果。 比如,[9,9,9] 返回 [1,0,0,0] ; [9,9,8] 返回 [9,9,9] 。 从数组最右边开始遍历: 如果当前元素小于 8 ,则将当前元素加 1 后,直接返回数组 digits ; 如果当前元素等于 9 ,将当前元素置为 0 ,继续判断; 若遍历结束还没返回结果,说明数组 digits 内的元素全为 9 ,则创建一个新的数组,首位为 1 ,其余位为 0 ,返回新数组。

【LeetCode】67. Add Binary

题目描述: Given two binary strings, return their sum (also a binary string). For example, a = “11” b = “1” Return “100”. 思路: 设置flag表示进位标志,将字符串 a 和 b 依次拿出来“相加”,并将相加的结果存放在 char 数组; 假设字符串 a 已经结束,若字符串 b 还有没处理的字符,则操作 b ,注意是否还有进位;反之同理; 将 char 数组转换成 String 返回。 注意: 这种题难度不大,但要考虑全面,细心!! 通过常规的解法,时间复杂度为 O(n); 注意最后是否进位,若是 char 数组的首字符为‘1’,否则为空。 代码实现: class Solution { public String addBinary(String a, String b) { if(a==null){ return b; }else if(b==null){ return a; } int lenA = a.

【LeetCode】69. Sqrt(x)

题目描述: Implement int sqrt(int x). Compute and return the square root of x. 代码实现: class Solution { public: int mySqrt(int x) { if(x==0){ return 0; } int low=1,high=x; int mid; while(1){ mid = (low+high)/2; if(mid>x/mid){ high = mid-1; } else{ if((mid+1)>(x/(mid+1))){ return mid; } low = mid+1; } } } };

【LeetCode】70. Climbing Stairs

题目描述: You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 思路: 这题本质上是斐波那契数列问题。这里采用数组暂存已有结果,以时间换空间,减少递归带来的重复计算。 代码实现: class Solution { public: int climbStairs(int n) { int f[n+1]; f[0]=1; f[1]=1; for(int i=2;i<=n;++i){ f[i]=f[i-1]+f[i-2]; } return f[n]; } };

【LeetCode】75. Sort Colors

题目描述: Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library’s sort function for this problem. 思路: 本题实质上为三元数组排序。

【LeetCode】83. Remove Duplicates from Sorted List

题目描述: Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. 思路: 遍历一次链表即可,每遍历一个元素比较其是否与它的下一个元素相等。若是,指针指向下下个元素;否则继续遍历下一个元素。 代码实现: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { if(head==null){ return null; } ListNode p = head; while(p.

【LeetCode】88. Merge Sorted Array

题目描述: Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively. 思路: 从后往前遍历两个数组,分别比较,大的放在数组 nums1 后面,直到两个数组都遍历完毕。 注:如果从前往后遍历的话,数组合并时需要将元素后移,效率低。 代码实现: class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int index = m+n-1; int i1 = m-1; int i2 = n-1; while(i1>=0&&i2>=0){ if(nums1[i1]>=nums2[i2]){ nums1[index] = nums1[i1]; i1--; }else{ nums1[index] = nums2[i2]; i2--; } index--; } while(i1>=0){ nums1[index] = nums1[i1]; i1--; index--; } while(i2>=0){ nums1[index] = nums2[i2]; i2--; index--; } } }

【LeetCode】94. Binary Tree Inorder Traversal

题目描述: Given a binary tree, return the inorder traversal of its nodes’ values. For example: Given binary tree [1,null,2,3], 1 \ 2 / 3 return [1,3,2]. 思路: 二叉树的中序遍历,这里直接用递归的方法求解。 代码实现: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ret = new ArrayList<Integer>(); inorder(root,ret); return ret; } public void inorder(TreeNode root, List<Integer> ret){ if(root==null){ return ; } inorder(root.

【LeetCode】100. Same Tree

题目描述: Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value. 代码实现: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if(p==nullptr && q==nullptr){ return true; } else if(p==nullptr || q==nullptr){ return false; } if(p->val!

【LeetCode】104. Maximum Depth of Binary Tree

题目描述: Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 代码实现: /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode *root) { int Ldepth=0,Rdepth=0; if(root==NULL){ return 0; } if(root->left==NULL && root->right==NULL){ return 1; } Ldepth=maxDepth(root->left); Rdepth=maxDepth(root->right); return 1+(Ldepth>Rdepth?

【LeetCode】116. Populating Next Right Pointers in Each Node

题目描述: Given a binary tree struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note: You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

【LeetCode】121. Best Time to Buy and Sell Stock

题目描述: Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. Example 1: Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

【LeetCode】122. Best Time to Buy and Sell Stock II

题目描述: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

【LeetCode】123. Best Time to Buy and Sell Stock III

题目描述: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 思路: 只能进行两次交易,要求两次交易获利之和最大; 第一次交易:从前往后遍历,计算每天的最大获利 left[] , left[i] 表示第 i 天的最多能获利多少; 第二次交易:从后往前遍历,计算每天的最大获利 right[] , right[i] 表示第 i 天的最多能获利多少; 最大获利:计算哪一天的 left[i] + right[i] 最大,即为两次交易的最大获利。

【LeetCode】136. Single Number

题目描述: Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 代码实现: class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; for(int num:nums){ ret^=num; } return ret; } };

【LeetCode】167. Two Sum II - Input array is sorted

题目描述: Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have exactly one solution and you may not use the same element twice.

【LeetCode】169. Majority Element

题目描述: Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. 代码实现: class Solution { public: int majorityElement(vector<int>& nums) { int major=nums[0]; int cnt=1; for(int num:nums){ if(num==major){ ++cnt; }else{ --cnt; } if(cnt==0){ ++cnt; major = num; } } return major; } };

【LeetCode】171. Excel Sheet Column Number

题目描述: Related to question Excel Sheet Column Title 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 代码实现: class Solution { public: int titleToNumber(string s) { int sum=0; for(int i=0;i<s.length();i++){ sum = sum*26+(s[i]-'A'+1); } return sum; } };

【LeetCode】191. Number of 1 Bits

题目描述: Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight). For example: the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3. 代码实现: class Solution { public: int hammingWeight(uint32_t n) { int sum=0; while(n>0){ if(n&1==1){ sum++; } n=n>>1; } return sum; } };

【LeetCode】202. Happy Number

题目描述: Write an algorithm to determine if a number is “happy”. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

【LeetCode】206. Reverse Linked List

题目描述: Reverse a singly linked list. 代码实现: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* pPre=nullptr; ListNode* pNode=head; ListNode* pRet=nullptr; while(pNode!=nullptr){ ListNode* pNext=pNode->next; if(pNext==nullptr){ pRet=pNode; } pNode->next=pPre; pPre=pNode; pNode=pNext; } return pRet; } };

【LeetCode】217. Contains Duplicate

题目描述: Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct. 代码实现: class Solution { public: bool containsDuplicate(vector<int>& nums) { unordered_set<int> set; for(int num:nums){ if(set.count(num)){ return true; } set.insert(num); } return false; } };

【LeetCode】226. Invert Binary Tree

题目描述: Invert a binary tree. 4 / \ 2 7 / \ / \ 1 3 6 9 to 4 / \ 7 2 / \ / \ 9 6 3 1 代码实现: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* invertTree(TreeNode* root) { if(root==NULL){ return NULL; } TreeNode* nl; TreeNode* nr; nl = invertTree(root->right); nr = invertTree(root->left); root->left = nl; root->right = nr; return root; } };

【LeetCode】231. Power of Two

题目描述: Given an integer, write a function to determine if it is a power of two. 代码实现: class Solution { public: bool isPowerOfTwo(int n) { int flag=0; if(n<=0){ return false; } while(n>0){ if(n&1==1){ if(flag==1){ return false; } flag=1; } n=n>>1; } return true; } };

【LeetCode】237. Delete Node in a Linked List

题目描述: Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function. 代码实现: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void deleteNode(ListNode* node) { auto next = node->next; *node = *next; delete next; } };

【LeetCode】238. Product of Array Except Self

题目描述: Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in O(n). For example, given [1,2,3,4], return [24,12,8,6]. Follow up: Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.

【LeetCode】242. Valid Anagram

题目描述: Given two strings s and t, write a function to determine if t is an anagram of s. For example, s = “anagram”, t = “nagaram”, return true. s = “rat”, t = “car”, return 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? 代码实现: class Solution { public: bool isAnagram(string s, string t) { if(s.

【LeetCode】258. Add Digits

题目描述: Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. For example: Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it. Follow up: Could you do it without any loop/recursion in O(1) runtime? 代码实现: class Solution { public: int addDigits(int num) { return 1+(num-1)%9; } };

【LeetCode】263. Ugly Number

题目描述: Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7. Note that 1 is typically treated as an ugly number. 代码实现: class Solution { public: bool isUgly(int num) { if(num<=0){ return false; } while(num%2==0){ num/=2; } while(num%3==0){ num/=3; } while(num%5==0){ num/=5; } return num==1?

【LeetCode】268. Missing Number

题目描述: Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array. For example, Given nums = [0, 1, 3] return 2. Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity? 代码实现: class Solution { public: int missingNumber(vector<int>& nums) { int sum=0; int realsum=0; bool flag=false; for(int i=0;i<nums.

【LeetCode】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. For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [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. 代码实现: class Solution { public: void moveZeroes(vector<int>& nums) { int index=0; for(int i=0;i<nums.

【LeetCode】292. Nim Game

题目描述: You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones. Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

【LeetCode】326. Power of Three

题目描述: Given an integer, write a function to determine if it is a power of three. Follow up: Could you do it without using any loop / recursion? 代码实现: class Solution { public: bool isPowerOfThree(int n) { if(n<=0){ return false; } while(n%3==0){ n/=3; } if(n==1){ return true; } return false; } };

【LeetCode】328. Odd Even Linked List

题目描述: Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example: Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL. Note: The relative order inside both the even and odd groups should remain as it was in the input.

【LeetCode】338. Counting Bits

题目描述: Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array. Example: For num = 5 you should return [0,1,1,2,1,2]. Follow up: It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?

【LeetCode】344. Reverse String

题目描述: Write a function that takes a string as input and returns the string reversed. Example: Given s = “hello”, return “olleh”. 代码实现: class Solution { public: string reverseString(string s) { reverse(s.begin(),s.end()); return s; } };

【LeetCode】349. Intersection of Two Arrays

题目描述: Given two arrays, write a function to compute their intersection. Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2]. Note: Each element in the result must be unique. The result can be in any order. 代码实现: class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> s; vector<int> ret; for(int num1:nums1){ if(s.count(num1)==0){ s.insert(num1); } } for(int num2:nums2){ if(s.count(num2)){ ret.push_back(num2); s.erase(num2); } } return ret; } };

【LeetCode】350. Intersection of Two Arrays II

题目描述: Given two arrays, write a function to compute their intersection. Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2]. Note: Each element in the result should appear as many times as it shows in both arrays. The result can be in any order. Follow up: What if the given array is already sorted? How would you optimize your algorithm? What if nums1’s size is small compared to nums2’s size?

【LeetCode】371. Sum of Two Integers

题目描述: Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -. Example: Given a = 1 and b = 2, return 3. 代码实现: class Solution { public: int getSum(int a, int b) { return b==0?a:getSum(a^b,(a&b)<<1); } };

【LeetCode】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”) -> true 代码实现: class Solution { public: bool canConstruct(string ransomNote, string magazine) { if(magazine.

【LeetCode】387. First Unique Character in a String

题目描述: 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. 代码实现: class Solution { public: int firstUniqChar(string s) { int arr[26]; for(int i=0;i<26;++i){ arr[i]=0; } for(int i=0;i<s.size();++i){ ++arr[s[i]-'a']; } for(int i=0;i<s.size();++i){ if(arr[s[i]-'a']==1){ return i; } } return -1; } };

【LeetCode】389. Find the Difference

题目描述: Given two strings s and t which consist of only lowercase letters. String t is generated by random shuffling string s and then add one more letter at a random position. Find the letter that was added in t. Example: Input: s = “abcd” t = “abcde” Output: e Explanation: ‘e’ is the letter that was added. 代码实现: class Solution { public: char findTheDifference(string s, string t) { char ch = t[0]; for(int i=1;i<t.

【LeetCode】401. Binary Watch

题目描述: A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right. For example, the above binary watch reads “3:25”. Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

【LeetCode】404. Sum of Left Leaves

题目描述: Find the sum of all left leaves in a given binary tree. Example: 3 / \ 9 20 / \ 15 7 There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24. 代码实现: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if(root==nullptr){ return 0; } int sum=0; if(root->left){ if(root->left->left==nullptr && root->left->right==nullptr){ sum+=root->left->val; }else{ sum+=sumOfLeftLeaves(root->left); } } if(root->right){ sum+=sumOfLeftLeaves(root->right); } return sum; } };

【LeetCode】409. Longest Palindrome

题目描述: Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters. This is case sensitive, for example “Aa” is not considered a palindrome here. Note: Assume the length of given string will not exceed 1,010. Example: Input: “abccccdd” Output: 7 Explanation: One longest palindrome that can be built is “dccaccd”, whose length is 7.

【LeetCode】412. Fizz Buzz

题目描述: Write a program that outputs the string representation of numbers from 1 to n. But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”. Example: n = 15, Return: [ “1”, “2”, “Fizz”, “4”, “Buzz”, “Fizz”, “7”, “8”, “Fizz”, “Buzz”, “11”, “Fizz”, “13”, “14”, “FizzBuzz” ]

【LeetCode】414. Third Maximum Number

题目描述: Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n). Example 1: Input: [3, 2, 1] Output: 1 Explanation: The third maximum is 1. Example 2: Input: [1, 2] Output: 2 Explanation: The third maximum does not exist, so the maximum (2) is returned instead. Example 3: Input: [2, 2, 3, 1] Output: 1

【LeetCode】415. Add Strings

题目描述: Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2. Note: The length of both num1 and num2 is < 5100. Both num1 and num2 contains only digits 0-9. Both num1 and num2 does not contain any leading zero. You must not use any built-in BigInteger library or convert the inputs to integer directly. 代码实现: class Solution { public: string addStrings(string num1, string num2) { string str; int index1=num1.

【LeetCode】447. Number of Boomerangs

题目描述: Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters). Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range -10000, 10000.

【LeetCode】448. Find All Numbers Disappeared in an Array

题目描述: Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example: Input: [4,3,2,7,8,2,3,1] Output: [5,6]

【LeetCode】453. Minimum Moves to Equal Array Elements

题目描述: Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1. Example: Input: [1,2,3] Output: 3 Explanation: Only three moves are needed (remember each move increments two elements): [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4] 代码实现: class Solution { public: int minMoves(vector<int>& nums) { int min=INT_MAX; int sum=0; for(int num:nums){ min=min<num?

【LeetCode】455. Assign Cookies

题目描述: Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content.

【LeetCode】461. Hamming Distance

题目描述: The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note: 0 ≤ x, y < 231. Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different.

【LeetCode】463. Island Perimeter

题目描述: You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1.

【LeetCode】476. Number Complement

题目描述: Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation. Note: The given integer is guaranteed to fit within the range of a 32-bit signed integer. You could assume no leading zero bit in the integer’s binary representation. Example 1: Input: 5 Output: 2 Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010.

【LeetCode】485. Max Consecutive Ones

题目描述: Given a binary array, find the maximum number of consecutive 1s in this array. Example 1: Input: [1,1,0,1,1,1] Output: 3 Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3. Note: The input array will only contain 0 and 1. The length of input array is a positive integer and will not exceed 10,000 代码实现: class Solution { public: int findMaxConsecutiveOnes(vector<int>& nums) { int cnt=0,max=0; for(int num:nums){ if(num==1){ cnt++; }else{ cnt=0; } max = max>cnt?

【LeetCode】492. Construct the Rectangle

题目描述: For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements: The area of the rectangular web page you designed must equal to the given target area. The width W should not be larger than the length L, which means L >= W.

【LeetCode】496. Next Greater Element I

题目描述: You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2. The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number. Example 1: Input: nums1 = [4,1,2], nums2 = [1,3,4,2].

【LeetCode】504. Base 7

题目描述: Given an integer, return its base 7 string representation. Example 1: Input: 100 Output: “202” Example 2: Input: -7 Output: “-10” Note: The input will be in range of [-1e7, 1e7]. 代码实现: class Solution { public: string convertToBase7(int num) { string str=""; int nega=0; if(num<0){ nega = 1; num = abs(num); } while(num/7){ str+=to_string(num%7); num/=7; } str+=to_string(num%7); if(nega){ str+="-"; } reverse(str.begin(),str.end()); return str; } };

【LeetCode】506. Relative Ranks

题目描述: Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”. Example 1: Input: [5, 4, 3, 2, 1] Output: [“Gold Medal”, “Silver Medal”, “Bronze Medal”, “4”, “5”] Explanation: The first three athletes got the top three highest scores, so they got “Gold Medal”, “Silver Medal” and “Bronze Medal”.

【LeetCode】507. Perfect Number

题目描述: We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself. Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not. Example: Input: 28 Output: True Explanation: 28 = 1 + 2 + 4 + 7 + 14 Note: The input number n will not exceed 100,000,000.

【LeetCode】520. Detect Capital

题目描述: Given a word, you need to judge whether the usage of capitals in it is right or not. We define the usage of capitals in a word to be right when one of the following cases holds: All letters in this word are capitals, like “USA”. All letters in this word are not capitals, like “leetcode”. Only the first letter in this word is capital if it has more than one letter, like “Google”.

【LeetCode】521. Longest Uncommon Subsequence I

题目描述: Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings. A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements.

【LeetCode】523. Continuous Subarray Sum

题目描述: Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer. Example 1: Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

【LeetCode】530. Minimum Absolute Difference in BST

题目描述: Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes. Example: Input: 1 \ 3 / 2 Output: 1 Explanation: The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3). Note: There are at least two nodes in this BST. 代码实现: /** * Definition for a binary tree node.

【LeetCode】532. K-diff Pairs in an Array

题目描述: Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k. Example 1: Input: [3, 1, 4, 1, 5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).

【LeetCode】537. Complex Number Multiplication

题目描述: Given two strings representing two complex numbers. You need to return a string representing their multiplication. Note i2 = -1 according to the definition. Example 1: Input: “1+1i”, “1+1i” Output: “0+2i” Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i. Example 2: Input: “1+-1i”, “1+-1i” Output: “0+-2i” Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

【LeetCode】541. Reverse String II

题目描述: Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original. Example: Input: s = “abcdefg”, k = 2 Output: “bacdfeg”

【LeetCode】543. Diameter of Binary Tree

题目描述: Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. Example: Given a binary tree 1 / \ 2 3 / \ 4 5 Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

【LeetCode】551. Student Attendance Record I

题目描述: You are given a string representing an attendance record for a student. The record only contains the following three characters: ‘A’ : Absent. ‘L’ : Late. ‘P’ : Present. A student could be rewarded if his attendance record doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late). You need to return whether the student could be rewarded according to his attendance record.

【LeetCode】557. Reverse Words in a String III

题目描述: Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1: Input: “Let’s take LeetCode contest” Output: “s’teL ekat edoCteeL tsetnoc” Note: In the string, each word is separated by single space and there will not be any extra space in the string. 代码实现: class Solution { public: string reverseWords(string s) { vector<int> stack; int index = 0; for(int i=0;i<s.

【LeetCode】561. Array Partition I

题目描述: Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible. Example 1: Input: [1,4,3,2] Output: 4 Explanation: n is 2, and the maximum sum of pairs is 4. Note: n is a positive integer, which is in the range of [1, 10000].

【LeetCode】563. Binary Tree Tilt

题目描述: Given a binary tree, return the tilt of the whole tree. The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0. The tilt of the whole tree is defined as the sum of all nodes’ tilt. Example: Input: 1 / \ 2 3 Output: 1

【LeetCode】566. Reshape the Matrix

题目描述: In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data. You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively. The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

【LeetCode】575. Distribute Candies

题目描述: Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain. Example 1: Input: candies = [1,1,2,2,3,3] Output: 3 Explanation: There are three different kinds of candies (1, 2 and 3), and two candies for each kind.

【LeetCode】598. Range Addition II

题目描述: Given an m * n matrix M initialized with all 0’s and several update operations. Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b. You need to count and return the number of maximum integers in the matrix after performing all the operations.

【LeetCode】599. Minimum Index Sum of Two Lists

题目描述: Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings. You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer. Example 1: Input: [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”] [“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]

【LeetCode】617. Merge Two Binary Trees

题目描述: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

【LeetCode】682. Baseball Game

题目描述: You’re now a baseball game point recorder. Given a list of strings, each string can be one of the 4 following types: Integer (one round’s score): Directly represents the number of points you get in this round. ”+” (one round’s score): Represents that the points you get in this round are the sum of the last two valid round’s points. “D” (one round’s score): Represents that the points you get in this round are the doubled data of the last valid round’s points.