给定一个字符串和一个偏移量，根据偏移量旋转字符串（从左往右旋转），要求在数组上原地旋转，空间复杂度O(1)
static void reverse(char[] str,int offset) {
int len = str.Length;
if (len == 0) return;
char temp = str[0];
char temp2 = str[0];
int curent = 0;
int target = 0;
int start = 0;
for (int i = 0; i < len; i++)
{
target = (curent + offset) % len;
temp2 = str[target];//将原来的值弹出来保存
str[target] = temp;//替换到目标位置为上次弹出来的值
temp = temp2;//保存起来
curent = target;
if (start == target)
{
//如果目标的值是原来起始的位置，当前位置是旋转过的，那就往下走一步
start = (start + 1) % len;
curent = start;
temp = str[curent];
}
}
}看注释。
要求：计算数字k在0到n中的出现的次数，k可能是0~9的一个值。
样例
例如n=12，k=1，在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]，我们发现1出现了5次 (1, 10, 11, 12)
public static int digitCounts(int k, int n)
{
if (n == 0 && k == 0)
return 1; // 特殊情况
int temp = n, cnt = 0, pow = 1;//pow代表当前位的后面低位是多少，1为个位，10为十位，100位千位
while (temp != 0)
{
int digit = temp % 10; // 根据当前位置数和k的大小关系，可以算出当前位置出现过k的次数
if (digit < k)
cnt += (temp / 10) * pow;
else if (digit == k)
cnt += (temp / 10) * pow + (n - temp * pow + 1);
else
{
if (!(k == 0 && temp / 10 == 0)) // 排除没有更高位时，寻找的数为0的情况
cnt += (temp / 10 + 1) * pow;
}
temp /= 10;
pow *= 10;
}
return cnt;
}总结以下规律，我们要从1到ABCDE中找到k这个数字在某一位上出现了多少次
当某一位的数字小于k时，那么该位出现i的次数为：更高位数字x当前位数
当某一位的数字等于k时，那么该位出现i的次数为：更高位数字x当前位数+低位数字+1
当某一位的数字大于k时，那么该位出现i的次数为：(更高位数字+1)x当前位数
要求：计算数字k在0到n中的出现的次数，k可能是0~9的一个值。
样例
例如n=12，k=1，在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]，我们发现1出现了5次 (1, 10, 11, 12)
static void StaticNum(int num, int search)
{
int temp = 0;
int test = 0;
int count = 0;
for (int i = 0; i <= num; i++)
{
temp = i;
do
{
test = temp % 10;
temp = temp / 10;
if (test == search)
count++;
} while (temp != 0);
}
Console.WriteLine("0到" + num + "数字" + search + "出现了" + count + "次");
}
判断一个数是不是快乐数？快乐数的定义为一个正整数，计算出它各位数字的平方和，得到一个新的数字，再对这个新的数字重复这一过程，直到最后得到数字1或是其他某几个数字的无限循环。在这些数字中，经过上述流程最终能得到数字1的数字，被称为“快乐数”。
据观察规律发现，不是快乐数的都会陷入到4,16,37,58,89,145,42,20,4的死循环中，也就是说出现了4这个和就不是快乐数了。
namespace 快乐数
{
class Program
{
static void Main(string[] args)
{
CalNum(4);
Console.ReadKey();
}
static void CalNum(int n)
{
int sum = 0;
while (n != 0)
{
int i = n % 10;
n = n / 10;
sum += i * i;
}
Console.WriteLine(sum);
if (sum == 1)
{
Console.WriteLine("快乐数");
return;
}
else if (sum == 4) {
Console.WriteLine("不太快乐数");
return;
}
CalNum(sum);
}
}
}while循环体中计算正整数n的每位数的平方和。
问题：假设玻璃球在k层楼及以上扔下时就会碎，以下不会碎，一共n层楼，你有两个玻璃球，怎么确定这个k是多少且使可能的最大次数最小。
分析：玻璃球的个数有限，所以无法使用二分法。所以考虑还是范围性搜索，第一个玻璃球用来确定范围，第二个玻璃球来确定结果。主要的问题就演变为怎么划分这个范围来使这个最大次数最小。任何不稳定的因素可能会使确认次数减小，可能也会让最大次数增大，所以这个值应该是一个稳定的值，那么假设这个可能的最大次数最小值为m，一共n层，且怎么扔最大次数都是m次，则可以这样，第一次在m楼扔，第二次在m*2-1楼扔，第三次在m*3-2层扔，这样子无论确定在哪个范围，它的最多次数都是一样的。
计算：那么，n - 1 <= m + (m-1) + (m-2) + ... + 1，这里n-1是因为最后一楼不用试了，如果前面一楼都没碎(第m次)，那么就是最后一层楼会碎了。
class Program
{
static void Main(string[] args)
{
//输入层数，限制两个玻璃球
while (true) {
string num = Console.ReadLine();
int inum = Int32.Parse( num );
Cal(inum);
}
}
static void Cal(int num)
{
int res = 0;
//搜索一个能覆盖所有楼层的扔法
int temp = (int)Math.Sqrt(num);
while (res == 0) {
if ((temp + 1) * temp >= （num-1） * 2) {
res = temp;
}
temp++;
}
Console.WriteLine("结果为：" + res);
//分别在第几层楼扔
for (int i = 0; i < res; i++) {
int stand = res * (i + 1);
//偏移保证最大次数一样
int offset = (i + 1) * i / 2;
int floot = stand - offset;
Console.Write(floot + " ");
}
Console.WriteLine();
}
}100层的结果为14次。
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。
using System;
using System.Diagnostics;
using System.Linq;
namespace 八皇后_回溯算法
{
class Program
{
private static int[,] geizi = new int[8, 8];
private static int[] rowHas = Enumerable.Repeat(-1,8).ToArray();
private static int resultNum = 0;
static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
Place(0);
stopwatch.Stop();
Console.WriteLine(resultNum + " 用时：" + stopwatch.ElapsedMilliseconds);
Console.ReadKey();
}
static void Place(int row) {
if (row == -1) {
return;
}
int i = 0;
int col = -1;
int isP = rowHas[row];
if (isP != -1) {
//表示这行放过皇后，取消先前放的
geizi[row, isP] = 0;
rowHas[row] = -1;
}
//寻找这行可以放置皇后的地方
for (i = isP + 1; i < 8; i++)
{
if (col != -1)
{
continue;
}
if (CheckPlace(row, i))
{
col = i;
geizi[row, i] = 1;
rowHas[row] = i;
}
}
//判断有没有找到这样的一个位置
if (col != -1)
{
if (row == 7)
{
//出结果了，打印结果
PrintAll();
resultNum++;
geizi[row, col] = 0;
rowHas[row] = -1;
Place(row - 1);
}
else
{
Place(row + 1);
}
}
else
{
//没有位置，往上层走，修改上层放置的位置
Place(row - 1);
}
}
//检测是否可以放置
static bool CheckPlace(int row, int col) {
//3个方向检测
bool CanPlace = true;
for (int i = 0; i < row; i++) {
int tRow = row - i - 1;
int lCol = col - i - 1;
int rCol = col + i + 1;
if (tRow < 0) {
continue;
}
//向上
if (geizi[tRow, col] == 1) {
CanPlace = false;
}
//左上
if (lCol >= 0) {
if (geizi[tRow, lCol] == 1)
{
CanPlace = false;
}
}
//右上
if (rCol <= 7) {
if (geizi[tRow, rCol] == 1)
{
CanPlace = false;
}
}
}
return CanPlace;
}
//输出结果
static void PrintAll() {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
Console.Write(geizi[i, j] + " ");
}
Console.WriteLine();
}
Console.WriteLine();
}
}
}输出结果有92种，排除输出后用时2-5ms
static int Add(int a, int b) {
int c = 0;
int d = 0;
while (b != 0) {
c = a ^ b;
d = (a & b) << 1;
a = c;
b = d;
}
return a;
}使用位运算符，使用^异或得到不算进位的和，使用&再左移一位得到进位的值，合并这两个组成有进位的和，继续判断有没有进位，没有就结束。
例如：2+3 就是 10+11
不算进位和为：01，进位为:100
异或合并：101，进位：000
退出，得到101，就是5
为什么要循环到进位没有，这里第一次进位就完事了，想想如果不算进位和为101时，最高位合并还是0，这就还要进位了。
static void Main(string[] args)
{
while (true) {
int data = Convert.ToInt32( Console.ReadLine());
Console.WriteLine(Check2(data));
}
}
static bool Check2(int data) {
//就是只有一句
return (data & (data - 1)) == 0;
}研究发现数的2的乘方的值，都是只有最高位是1，其他都为0
例如：2^1=10,2^2=100,2^3=1000
而-1后对应就是：2^1-1=1,2^2-1=11,2^3-1=111
所以对这两个数进行与操作为0的就是2的乘方数了
static void Main(string[] args)
{
Console.WriteLine("输入两个整数，求最大公约数");
int a, b;
Stopwatch stopwatch = new Stopwatch();
while (true) {
a = Convert.ToInt32(Console.ReadLine());
b = Convert.ToInt32(Console.ReadLine());
stopwatch.Reset();
stopwatch.Start();
int res = getGYSByQuick(a, b);
stopwatch.Stop();
Console.WriteLine(res + " 用时：" + stopwatch.ElapsedMilliseconds);
}
}
//更向减损术和移位结合
static int getGYSByQuick(int a, int b) {
if (a == b) {
return a;
}
if ((a & 1) == 0 && (b & 1) == 0)
{
//两个都是偶数
return getGYSByQuick(a >> 1, b >> 1) << 1;
}
else if ((a & 1) == 0 && (b & 1) == 1)
{
//a是偶数,b不是
return getGYSByQuick(a >> 1, b);
}
else if ((a & 1) == 1 && (b & 1) == 0)
{
//b是偶数，a不是
return getGYSByQuick(a, b >> 1);
}
else {
//都是奇数，奇数减奇数必为偶
int mid = 0;
int min = 0;
if (a > b)
{
mid = a - b;
min = b;
}
else {
mid = b - a;
min = a;
}
return getGYSByQuick(mid, min);
}
}可以看出如果是偶数的话，可以右移一位（除以2），缩小一半的范围
计算什么都是 0ms
static void Main(string[] args)
{
Console.WriteLine("输入两个整数，求最大公约数");
int a, b;
Stopwatch stopwatch = new Stopwatch();
while (true) {
a = Convert.ToInt32(Console.ReadLine());
b = Convert.ToInt32(Console.ReadLine());
stopwatch.Reset();
stopwatch.Start();
int res = getGYSByXJF2(a, b);
stopwatch.Stop();
Console.WriteLine(res + " 用时：" + stopwatch.ElapsedMilliseconds);
}
}
//相减法--递归的方式别用，999999和1？栈会崩的。
static int getGYSByXJF(int a, int b) {
if (a == b) {
return a;
}
if (a > b)
{
return getGYSByXJF(a - b, b);
}
else {
return getGYSByXJF(b - a, a);
}
}
//相减法 不用递归
static int getGYSByXJF2(int a, int b)
{
while (a != b) {
if (a > b)
{
a = a - b;
}
else {
b = b - a;
}
}
return a;
}思路是大数和小数相加得差，如果这个差和小数不相等，那么这个小数和差的最大公约数就是大数和小数的最大公约数
计算99999999和88888888，时间为0ms
但是如果计算99999999和1，时间为296ms（这就和穷举法差不多了）