输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
class Solution {
public:
int countDigitOne(int n) {
int res = 0;
for(int i = 1;i <= n;i++)
{
res += helper(i);
}
return res;
}
private:
int helper(int n)
{
int cnt = 0;
while(n)
{
if(n%10 == 1)
cnt++;
n /= 10;
}
r......
方法一:记录每个字符出现次数
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<char,int> hash;
for(auto c:s)
hash[c] += 1;
for(int i = 0;i < s.size();i++)
{
if(hash[s[i]] == 1)
return s[i];
}
return ' ';
}
};
方法二：
class Solution {
public:
char firstUniqChar(string s) {
unorde......
递归解法
class Solution {
public:
int integerBreak(int n) {
if(n <= 2) return 1;
int ans = INT_MIN;
for(int i = 2;i < n;i++)
{
int product = i * max(n-i,integerBreak(n-i));
if(product > ans)
ans = product;
}
return ans;
}
};
运行结果:
Time Limit Exceeded
Details
Last executed input
43
......
自己实现的方法一，思路是先获取空格的个数，然后根据空格个数申请新的字符串长度。
class Solution {
public:
string replaceSpace(string s) {
int size = s.size();
int cnt = 0,loc = 0;
for(int i = 0;i < size;i++)
if(s[i] == ' ')
cnt++;
string res(size + 2*cnt,'0');
for(int i = 0;i < size;i++)
{
if(s[i] != ' ')
{
......
class Solution {
public:
int singleNumber(vector<int>& nums) {
int size = nums.size();
int ans = 0;
for(int i = 0;i < 32;i++)
{
int sum = 0;
for(auto num:nums)
{
sum += ((num >> i)&1);
}
if(sum % 3)
ans |= (1 << i);
}
return ans;
}
};
运行效率:
Runtime: 4 ms, faster t......
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int sum = 0,flag = 1;
vector<int> ans(2,0);
for(int i = 0;i < nums.size();i++)
sum ^= nums[i];
while(!(sum & flag))
flag <<= 1;
for(int i = 0;i < nums.size();i++)
{
if(flag & nums[i])
an......
AC代码：
class Solution {
public:
string multiply(string num1, string num2) {
string res(num1.size()+num2.size(),'0');
for(int i = num1.size() - 1;i >= 0;i--)
{
int carry = 0;
for(int j = num2.size() - 1;j >= 0;j--)
{
int tmp = res[i+j+1]-'0' + (num1[i] - '0')*(num2[j]-'0') + carry;
res[i+j+1]......
首先我们使用一种便于理解的方法，将链表一分为二，然后归并排序，再合并两个有序链表。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* ......
与leetcode15题目类似，大方向是使用双指针 三指针求解问题，细节稍有不同，AC代码如下：
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(),nums.end());
int min_val = INT_MAX;
int res = 0;
for(int i = 0;i < n - 2;i++){
int second = i + 1;
int third = n -1;......
方法一：排序
class Solution {
public:
bool canMakeArithmeticProgression(vector<int>& arr) {
sort(arr.begin(),arr.end());
int diff = arr[1] - arr[0];
for(int i = 1;i < arr.size();i++)
{
if(arr[i] - arr[i-1] != diff)
return false;
}
return true;
}
};
运行效率：
Runtime: 4 ms, faster than 65......