class Solution:
def digitsCount(self, d: int, low: int, high: int) -> int:
#Same as problem 233
def helper(d, n):
S = str(n)[::-1]
res = 0
if d != 0:
for i in range(len(S)):
left = n // (10**(i+1))
res = res + left*(10**i)
if int(S[i]) > d:
res = res + 10**i
elif int(S[i]) == d:
right = n % (10**i) + 1
res = res + right
else:
for i in range(len(S)):
left = n // (10**(i+1))
res = res + (left-1)*(10**i)
if int(S[i]) > d:
res = res + 10**i
elif int(S[i]) == d:
right = n % (10**i) + 1
res = res + right
return res
return helper(d, high) - helper(d, low-1)
class Solution:
def countDigitOne(self, n: int) -> int:
#let m number of digits of n
#TC: O(m)
#SC: O(m)
#For explanation, see Guan Huifeng
#https://www.youtube.com/watch?v=uB7DfQul6GU
S = str(n)[::-1]
res = 0
for i in range(len(S)):
left = n // (10**(i+1))
res = res + left*(10**i)
if int(S[i]) > 1:
res = res + 10**i
elif int(S[i]) == 1:
right = n % (10**i) + 1
res = res + right
return res
分治递归思想
不断分割归并
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n;
int q[N],tmp[N];
LL merge_sort(int q[],int l,int r){
if(l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(q,l,mid) + merge_sort(q,mid + 1,r);
int k = 0,i = l,j = mid + 1;
while(i <= mid && j <= r){
if(q[i] <= q[j]) tmp[k++] = q[i++];
else{
res += mid - i + 1;
tmp[k++] = q[j++];
}
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(i = l,j = 0;i <= r;++i,++j) q[i] = tmp[j];
return res;
}
int main(){
cin >> n;
for(int i = 0;i < n;++i){
cin >> q[i];
}
cout << merge_sort(q,0,n - 1) << endl;
return 0;
}
//分治递归思想
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r){
if(l >= r) return;
int mid = l + r >> 1;
merge_sort(q,l,mid);
merge_sort(q,mid + 1,r);//排序过程
int k = 0,i = l,j = mid + 1;
while(i <= mid && j <= r){//归并过程
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(i = l,j = 0;i <= r;++i,++j) q[i] = tmp[j];//放入原来数组
}
int main(){
int n;
cin >> n;
for(int i = 0;i < n;++i){
cin >> q[i];
}
merge_sort(q,0,n - 1);
for(int i = 0;i < n;++i){
cout << q[i] << ' ';
}
cout << endl;
return 0;
}
一道经典的数学问题：
通过观察可以发现，当$n<5$时，无论怎么剪切，乘积永远小于等于$n$；当$n>=5$时，可以将$n$拆分成
$3 * (n - 3) = 3n - 9 > n$。所以我们应该尽可能地多剪长度为3的绳子段。
class Solution {
public:
int maxProductAfterCutting(int length) {
if (length <= 3) return 1 * (length - 1); //长度小于等于3的情况
int res = 1;
//下面两行判断长度不为3的整数倍的情况
if (length % 3 == 1) res = 4, length -= 4; //余数为1且总长度大于3，则可以剪切成2*2即4，不能剪切成1*3
else if (length % 3 == 2) res = 2, length -= 2; //余数为2时表示多余一个2
while (length) length -= 3, res *= 3; //剩下的就是3的整数倍，全部剪切成3
return res;
}
};
java题解
import java.util.*;
public class Main{
static int N=200003;
static int INF=0x3f3f3f;
static class Hash{
int h[];
int n;
public Hash(int x){
n=x;
h=new int[n];
Arrays.fill(h,INF);
}
int find(int x){
int k=(x%N+N)%N;
while(h[k]!=INF&&h[k]!=x){
k++;
if(k==n)k=0;
}
return k;
}
}
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
Hash hash=new Hash(N);
int n=sc.nextInt();
while(n-->0){
String op=sc.next();
int x=sc.nextInt();
int k=hash.find(x);
if("I".equals(op)){
hash.h[k]=x;
}else{
String res=hash.h[k]==INF?"No":"Yes";
System.out.println(res);
}
}
}
}
#include <iostream>
#include <vector>
using namespace std;
/**
* 64 最小路径和
* 给定一个二维矩阵，然后从左上角走到右下角，求路径的最小和是多少
* 每个格子只能从左往右或者是从上往下走
*/
/**
* 方法 1，使用动态规划来做
* f[i][j]表示从起点到ij这个格子的所有方案，最后要求的是最小的方案即可
* 初始化f状态数组
* 首先行的话是当前状态=前一个状态 + 二维数组的数字即可，列也是如此
* 最后直接遍历ij从1开始
*/
int minPathSum(vector<vector<int> > &g)
{
int n = g.size(), m = g[0].size();
// f[i][j] 表示从原点到ij这个格子的所有路径
vector<vector<int> > f(n, vector<int>(m, INT_MAX));
f[0][0] = g[0][0];
for (int i = 1; i < n; i++)
f[i][0] = g[i][0] + f[i - 1][0];
for (int i = 1; i < m; i++)
f[0][i] = g[0][i] + f[0][i - 1];
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + g[i][j];
}
}
return f[n - 1][m - 1];
}
/**
* 方法 2，思路还是动态规划，但是写法不一样，直接遍历，然后如果是ij=起点的话，那么
* 就让初始状态等于起点，然后如果i大于0说明从上到下，如果j大于0说明从左到右
*/
int minPathSum(vector<vector<int> > &g)
{
int n = g.size(), m = g[0].size();
// f[i][j] 表示从原点到ij这个格子的所有路径
vector<vector<int> > f(n, vector<int>(m, INT_MAX));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == 0 && j == 0)
f[i][j] = g[i][j];
if (i)
f[i][j] = min(f[i][j], f[i - 1][j] + g[i][j]);
if (j)
f[i][j] = min(f[i][j], f[i][j - 1] + g[i][j]);
}
}
return f[n - 1][m - 1];
}
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
char a[100+1],b[100+1];
int num=0;
void turn(int a){
if(b[a]=='*') b[a]='o'; else b[a]='*';
if(b[a+1]=='*') b[a+1]='o'; else b[a+1]='*';
}
void work(){
for(int i=0;a[i]!='\0';i++){
if(a[i]!=b[i]){
turn(i);
num++;
}
}
}
int main(){
scanf("%s",a);
scanf("%s",b);
work();
printf("%d",num);
return 0;
}
