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 […]
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 […]
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. […]
N-Queens II Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. tag: backtracking 此题与上一题非常相似，只是把“输出所有可能情况”改成了“输出所有可能情况的个数”。详细解析请看上一题的结题报告： N-Queens class Solution { public: int totalNQueens(int n) { if(n == 0){ return 0; } int queen[n] = {0}; int sum = 0; for(int i = 0; i < […]
N-Queens The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ […]
