Combination Sum II Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. Elements […]
First Missing Positive Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2. Your algorithm should run in O(n) time and uses constant space. 关键是只允许常数空间。这里要突破思维定势，要改变给定数组的结构。 对于A[i]，如果A[i] > 0 && A[i] <= n，则将它与A[i] – 1 位置的元素互换位置。 遍历一遍后，再从左到右找到第一个A[i] != i + […]
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. 简单题，归并排序即可。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * […]
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. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. 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 […]
Multiply Strings Given two numbers represented as strings, return multiplication of the numbers as a string. Note: The numbers can be arbitrarily large and are non-negative. Tags: math, string 字符串相乘，关键是模拟我们平时手算乘法时的过程。取出num2的每一位，乘以num1，再把之前得到的re向左移一位，再加上这个循环中的结果。所以我们需要实现两个函数multiplyNum（字符串乘以数字）和sum（两个字符串相加）。 num1或num2为零需要单独考虑，否则结果会出现类似0000的情况。 class Solution { public: string multiply(string num1, string num2) { int i = 0; string re; if(num1 == “0” […]
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 […]
Combinations Given two integers n and k, return all possible combinations of k numbers out of 1 … n. For example, If n = 4 and k = 2, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] tag: backtracking 回溯问题，用递归求解就好。 class Solution { public: vector<vector<int> > combine(int […]
Search in Rotated Sorted Array Suppose a sorted array 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 […]
Best Time to Buy and Sell Stock IV 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 k transactions. Note: You may not engage in multiple […]
Compare Version Numbers Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal […]
