思路：二分法思想，先找出该数存在的某段有序数组中，随意取一个下边，它的左边和右边总有一个是有序的段，而如果这个查找的数刚好在这个段中，就可以利用二分法了。
class XuanZhuanYouXuChaZhao
{
public int Find(int[] datas,int num)
{
int left = 0;
int right = datas.Length - 1;
int mid = 0;
while (true)
{
if (left > right) return -1;
mid = (left + right) / 2;
if (num == datas[mid]) return mid;
if (datas[mid] > datas[left])//左边有序
{
if (num < datas[mid] && num >= datas[left])
{
//左边二分法
right = mid - 1;
break;
}
else
{
//在右边 继续找有序
left = mid + 1;
}
}
else//右边有序
{
if (num > datas[mid] && num <= datas[right])
{
//右边二分法
left = mid + 1;
break;
}
else
{
//在左边，继续查找有序
right = mid - 1;
}
}
}
//二分法查找
while (left <= right)
{
mid = (left + right) / 2;
if (num == datas[mid]) return mid;
if (num > datas[mid])//右边找
{
left = mid + 1;
}
else//左边找
{
right = mid - 1;
}
}
return -1;
}
}//旋转有序数组中查找
static void TestXuanZhuanYouXuChaZhao()
{
XuanZhuanYouXuChaZhao XZY = new XuanZhuanYouXuChaZhao();
int[] datas = {20,50,90,2,5,9,11,18,19 };
int[] datas2 = { 300,500,1,2,3,4,5,6,7,8,9,10,11,13,15,18,22,30,38,40,45,55,66,77,88 };
Console.WriteLine(XZY.Find(datas, 18));//7
Console.WriteLine(XZY.Find(datas, 20));//0
Console.WriteLine(XZY.Find(datas2, 9));//10
Console.WriteLine(XZY.Find(datas2, 77));//23
Console.WriteLine(XZY.Find(datas2, 22));//16
}给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]示例 2:
输入:[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]//硬推着写的......
public IList<int> SpiralOrder(int[,] matrix)
{
int yLength = matrix.GetLength(0);
int xLength = matrix.GetLength(1);
bool isX = true;//标识符 是X方向还是Y方向
int xDir = 1;//x和y也分正负方向
int yDir = 1;
int x = 0;//这个是表明当前的位置
int y = 0;
int turnXLeft = 0;//上下左右的偏移，遍历过的就不能再去了
int turnXRight = 0;
int turnYUp = 0;
int turnYDown = 0;
IList<int> res = new List<int>();
for (int i = 0; i < matrix.Length; i++)
{
//这里遍历完所有元素
if (isX)
{
res.Add(matrix[y, x]);
x += xDir;
//边界判定
if (x < 0 + turnXLeft || x == xLength - turnXRight)
{
if (x < 0 + turnXLeft)
{
x = 0 + turnXLeft;
}
else
{
x = xLength - turnXRight - 1;
}
isX = false;//变换标志
if (xDir > 0)
{
y += 1;
turnYUp += 1;
}
else
{
y -= 1;
turnYDown += 1;
}
xDir = xDir == 1 ? -1 : 1;//变换方向
}
}
else
{
res.Add(matrix[y, x]);
y += yDir;
if (y < 0 + turnYUp || y == yLength - turnYDown)
{
if (y < 0 + turnYUp)
{
y = 0 + turnYUp;
}
else
{
y = yLength - turnYDown - 1;
}
isX = true;
if (yDir > 0)
{
x -= 1;
turnXRight += 1;
}
else
{
x += 1;
turnXLeft += 1;
}
yDir = yDir == 1 ? -1 : 1;
}
}
}
return res;
}public IList<int> SpiralOrder(int[,] matrix)
{
List<int> Ls = new List<int>();
//4个边界
int top = 0;
int bottom = matrix.GetLength(0) - 1;
int left = 0;
int right = matrix.GetLength(1) - 1;
while (true)//运行一次就是一圈
{
//从左往右
for (int i = left; i <= right; i++) Ls.Add(matrix[top, i]);
top++;
if (left > right || top > bottom) break;
//从上到下
for (int i = top; i <= bottom; i++) Ls.Add(matrix[i, right]);
right--;
if (left > right || top > bottom) break;
//从右到左
for (int i = right; i >= left; i--) Ls.Add(matrix[bottom, i]);
bottom--;
if (left > right || top > bottom) break;
//从下到上
for (int i = bottom; i >= top; i--) Ls.Add(matrix[i, left]);
left++;
if (left > right || top > bottom) break;
}
return Ls;
}两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
示例:
输入: x = 1, y = 4输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。public int HammingDistance(int x, int y) {
int res = 0;
int val = x^y;
while(val != 0)
{
res++;
val &= val -1;
}
return res;
}你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
示例 1:
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.//很简单滴
public int ArrangeCoins(int n) {
int step = 1;
while(n > 0)
{
n -= step;
step++;
}
if(n < 0)
{
step--;
}
return --step;
}给定一种 pattern(模式) 和一个字符串 str ，判断 str 是否遵循相同的模式。
这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应模式
示例1:
输入: pattern = "abba", str = "dog cat cat dog"
输出: true
示例 2:
输入:pattern = "abba", str = "dog cat cat fish"
输出: false
示例 3:
输入: pattern = "aaaa", str = "dog cat cat dog"
输出: falsepublic bool WordPattern(string pattern, string str) {
string[] datas = str.Split(' ');
if(pattern.Length != datas.Length) return false;
Dictionary<char,string> match = new Dictionary<char,string>();
for(int i = 0;i<datas.Length;i++)
{
if(!match.ContainsKey(pattern[i]))
{
//双向的关系，值存在，模式字符不存在那是不对的
if(match.ContainsValue(datas[i])) return false;
match.Add(pattern[i],datas[i]);
}
else
{
if(match[pattern[i]] != datas[i])
return false;
}
}
return true;
}给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
示例 1：
输入： 16
输出： True
示例 2：
输入： 14
输出： False//任意的完全平方数都可以表示为奇数和
public bool IsPerfectSquare(int num) {
for(int i = 1;num > 0;i += 2)
{
num -= i;
}
return num == 0;
}给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]public int[] Intersect(int[] nums1, int[] nums2) {
Dictionary<int,int> dic = new Dictionary<int,int>();
for(int i = 0;i<nums1.Length;i++)
{
if(dic.ContainsKey(nums1[i]))
{
dic[nums1[i]]++;
}
else
{
dic.Add(nums1[i],1);
}
}
List<int> res = new List<int>();
for(int i = 0;i<nums2.Length;i++)
{
if(dic.ContainsKey(nums2[i]) && dic[nums2[i]] > 0)
{
dic[nums2[i]]--;
res.Add(nums2[i]);
}
}
return res.ToArray();
}给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]说明:
1.输出结果中的每个元素一定是唯一的。
2.我们可以不考虑输出结果的顺序。
public int[] Intersection(int[] nums1, int[] nums2) {
Dictionary<int,bool> dic = new Dictionary<int,bool>();
for(int i = 0;i<nums1.Length;i++)
{
if(!dic.ContainsKey(nums1[i]))
{
dic.Add(nums1[i],true);
}
}
List<int> res = new List<int>();
for(int i = 0;i<nums2.Length;i++)
{
if(dic.ContainsKey(nums2[i]) && dic[nums2[i]] == true)
{
dic[nums2[i]] = false;
res.Add(nums2[i]);
}
}
return res.ToArray();
}给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:[4,3,2,7,8,2,3,1]
输出:[5,6]//额外空间标志法
public IList<int> FindDisappearedNumbers(int[] nums) {
Dictionary<int,bool> dic = new Dictionary<int,bool>();
for(int i = 0;i<nums.Length;i++)
{
if(!dic.ContainsKey(nums[i]))
{
dic.Add(nums[i],true);
}
}
IList<int> res = new List<int>();
for(int i = 1;i<=nums.Length;i++)
{
if(!dic.ContainsKey(i))
{
res.Add(i);
}
}
return res;
}//标志法 存在的值下标标志为负数
public IList<int> FindDisappearedNumbers(int[] nums) {
for(int i = 0;i<nums.Length;i++)
{
int val = Math.Abs(nums[i]);
nums[val - 1] = -Math.Abs(nums[val - 1]);
}
IList<int> res = new List<int>();
for(int i = 0;i<nums.Length;i++)
{
if(nums[i] > 0)
res.Add(i+1);
}
return res;
}给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]说明:
1.必须在原数组上操作，不能拷贝额外的数组。
2.尽量减少操作次数。
public void MoveZeroes(int[] nums) {
for(int i = 0;i<nums.Length;i++)
{
if(nums[i] != 0) continue;
int j = i + 1;
int target = j;
for(;j<nums.Length;j++)
{
if(nums[j] == 0) continue;
target = j;
break;
}
if(target<nums.Length)
{
nums[i] += nums[target];
nums[target] = nums[i] - nums[target];
nums[i] -= nums[target];
}
}
}public void MoveZeroes(int[] nums) {
int index = 0;
for(int i = 0;i<nums.Length;i++)
{
if(nums[i] != 0)
{
nums[index++] = nums[i];
}
}
for(int i = index;i<nums.Length;i++)
{
nums[index++] = 0;
}
}