Leetcode

【LeetCode】669. Trim a Binary Search Tree

题目描述: Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in L, R. You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree. Example 1: Input: 1 / \ 0 2 L = 1 R = 2

【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

【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]. 思路: 给定一个矩阵,以回旋形式以此

【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 的回

【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

【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

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

【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 思路: 从后往前遍历字符串。

【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. 思路: 遍历一次链表即可,每遍历一个元素比较其是否与它的下一个元素相等。若是,指针

【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. 思路: 从后往前遍历两

【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

【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

【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

【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

【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

【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). 思路: 只能进行两

【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. 思路: 题目的意思是将数组当成一个

【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

【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

【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]. 思路: 本题

【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 思路: 大水题

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

【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

【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

【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

【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

【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

【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

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

【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

【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

【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

【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

【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

【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 /

【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

【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

【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

【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. 代码实现: /** *

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

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

【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

【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

【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”

【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

【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());

【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

【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

【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

【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

【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

【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

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

【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]

【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

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

【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. 代码实现

【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 “FizzBuz

【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

【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

【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;

【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 {

【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

【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”,

【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); } }

【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?

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

【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) {

【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

【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 {

【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

【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

【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? 代

【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) {}

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

【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

【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

【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

【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; }

【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 =

【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

【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】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) {} * }; */

【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),

【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? 思路: 这题本质上是斐波那契数列问题。这里采用数组暂存已有结

【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】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. 思路: 这是一道将罗马数字转换成整数的题目。搞清楚罗马数字的表示特点即可。 参见维基百科:罗

【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

【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表示最大值,一次遍历即可

【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]. 思

【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