读一读
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n))。
示例 1:
nums1 = [1, 3] nums2 = [2] 中位数是 2.0
示例 2:
nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.Length;
int n = nums2.Length;
int i = 0;
int j = 0;
int index = 0;
int[] datas = new int[m+n];
//合并排序
while(i<m && j<n)
{
if(nums1[i] < nums2[j])
{
datas[index++] = nums1[i++];
}
else
{
datas[index++] = nums2[j++];
}
}
//填充剩下的
while(j<n)
{
datas[index++] = nums2[j++];
}
while(i<m)
{
datas[index++] = nums1[i++];
}
int mid = (m+n)/2;
int offset = (m+n)%2;
if(offset == 0)
{
return (datas[mid]+datas[mid-1])/2.0f;
}else
{
return datas[mid];
}
}使用合并排序的方式，将两个数组合并排序到一个数组中，然后判断长度为偶数就取中间两个的平均数，为奇数就去取中间那位。时间复杂度应该是O(n)或O(m)，空间复杂度是O(m+n)。还有更优的解法。
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列，而不是子串。
public int LengthOfLongestSubstring(string s) {
if(s == null || s == "") return 0;//安全检测
int lLength = 0;
int tempLength = 0;
Dictionary<char,int> dic = new Dictionary<char,int>();//记录字串中是否有重复
for(int i = 0;i<s.Length;i++)
{
if(dic.ContainsKey(s[i]))
{
//有重复的情况
if(tempLength > lLength)
{
lLength = tempLength;//赋予新长度
}
tempLength = i - dic[s[i]];//这个是重点，遗弃重复字符及前面的长度
Dictionary<char,int> nDic = new Dictionary<char,int>();
for(int j = dic[s[i]]+1;j<=i;j++)
{
//保留 重复字符间 的字符在字典中
nDic.Add(s[j],j);
}
dic = nDic;
}else{
//无重复，直接加
dic.Add(s[i],i);
tempLength++;
}
}
//一路绿灯无重复的情况
if(tempLength > lLength)
{
lLength = tempLength;
}
return lLength;
}这段代码写了挺快的，因为之前就看过思路，睡觉前也构思过了。但是无可避免的还是要提交很多次才能通过。
哈希字典主要记录当前字串的字符和每个字符的位置，当发现重复的时候，很容易得到两个重复字符的下标，两个下标相减就是遗弃重复字符前面后的字串长度了。
例如：abcabcbb，bcab，两个b为1和4，那么4-1=3,刚好为cab字串的长度3
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);//生成一个头结点的做法，省去了是否是第一节点的判断
ListNode tempNode = head;
int upVal = 0;
int temp = 0;
while(l1 != null || l2 != null || upVal != 0)//5+5的情况，所以就算两链表为空，进位不为空也要继续
{
temp = (l1==null?0:l1.val) + (l2==null?0:l2.val) + upVal;
tempNode.next = new ListNode(temp%10);//取个位数
upVal = temp/10;//读取出进位
tempNode = tempNode.next;
l1 = (l1==null?null:l1.next);
l2 = (l2==null?null:l2.next);
}
return head.next;//头结点的第一个结点就是真第一节点了
}
}
在一个数组中，寻找两个数的和等于目标值。
例如：[2,7,8,6] 目标值为9 那么输出[0,1]
public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary<int,int> dic = new Dictionary<int,int>();//空间换时间
for(int i = 0;i<nums.Length;i++)
{
int complement = target - nums[i];//通过计算获取另外一个的Key值
if(dic.ContainsKey(complement))
{
return new int[]{dic[complement],i};//得到索引
}
if(!dic.ContainsKey(nums[i]))
dic.Add(nums[i],i);//缓存到哈希表中
}
return null;
}
}缓存一个使用值作为Key的哈希表，这样就可以通过目标值和一个加值获取到另外一个加值了，当然它得存在。
public static int kthLargestElement(int k, int[] nums)
{
//两个哨兵ij，temp为临时值，start和end记录具体查找段的开始和结束
int i, j, temp, start, end;
//初始化值
bool isEnd = false;
i = 0;
start = i;
j = nums.Length - 1;
end = j;
temp = -1;
if (nums.Length < k) return -1;
//快排思想，但是不用管非目标段的排序
while (!isEnd)
{
//处理每一段的排序，将比参考值小的往前靠，比参考值大的往后靠，参考值放中间
temp = start;
while (i != j)
{
while (nums[j] <= nums[temp] && j != i)
{
j--;//在右边找一个比参考值小的
}
while (nums[i] >= nums[temp] && i != j)
{
i++;//在左边找一个比参考值大的
}
if (i == j)
{
//两哨兵相遇，与参考值调换位置
if (i != temp)//注意这两个相等的时候，这种交换就把值变成0了
{
nums[i] = nums[i] + nums[temp];
nums[temp] = nums[i] - nums[temp];
nums[i] = nums[i] - nums[temp];
}
temp = i;
}
else
{
//交换两个找到的值
nums[i] = nums[i] + nums[j];
nums[j] = nums[i] - nums[j];
nums[i] = nums[i] - nums[j];
}
}
//判断是否找到了，参考的位置就是该数据的真实排名了
if (temp + 1 == k)
{
isEnd = true;
break;
}
if (temp + 1 < k)
{
//去右边
j = end;
start = temp + 1;
i = temp + 1;
}
else
{
i = start;
end = temp - 1;
j = temp - 1;
}
}
return nums[temp];
}原来这叫Quick Select，和快排是同一个人提出的。
注释已经写得很明白了 也可以参考 快速排序-不用List速排序-不Lis
计算1000-9999中，插入最少一个运算符后使得结果为原来序列的反序。
例如：886-> 8 * 86 = 688
using System;
using System.Data;
namespace 算法实现
{
class SiZeYunSuan
{
DataTable table = new DataTable();
//private Calculator calculator = new Calculator();我的计算机类已经不知道跑去哪里了
string[] sign = { "+", "-", "*", "/", "" };
public void Cal()
{
string exp = "";
for (int i = 1000; i < 10000; i++)
{
string num = i.ToString();
for (int j = 0; j < sign.Length; j++)
{
for (int k = 0; k < sign.Length; k++)
{
for (int l = 0; l < sign.Length; l++)
{
exp = num[3] + sign[j] + num[2] + sign[k] + num[1] + sign[l] + num[0];
if (exp.Length > 4) {
if (table.Compute(exp,"").ToString() == num) {
Console.WriteLine(" "+num[3]+num[2]+num[1]+num[0]);
}
}
}
}
}
}
}
}
}代码为穷举法，很简单不解释了。
求用十进制、二进制、八进制表示都是回文数的所有数字中，大于十进制数10的最小值
二进制数为回文数，所以不会以0开头结尾，所以必为奇数
class ReverseNum10_8_2
{
public void Cal()
{
bool s_out = false;
int i = 11;
while (!s_out)
{
string str2 = Convert.ToString(i, 2);
string str8 = Convert.ToString(i, 8);
string str10 = Convert.ToString(i, 10);
/*char[] c2 = str2.ToCharArray();
Array.Reverse(c2);
char[] c8 = str8.ToCharArray();
Array.Reverse(c8);
char[] c10 = str10.ToCharArray();
Array.Reverse(c10);*/
if (str2 == reverse(str2) && str8 == reverse(str8) && str10 == reverse(str10))
{
Console.WriteLine("该数字为：" + str10);
Console.WriteLine("二进制为：" + str2);
Console.WriteLine("八进制为：" + str8);
s_out = true;
}
i += 2;
}
}
private string reverse(string str)
{
int Length = str.Length;
char[] rChar = new char[Length];
for (int i = 0; i < Length; i++)
{
rChar[i] = str[Length - i - 1];
}
return new string(rChar);
}
}暴力搞定法啊，哈！
魔术师发牌问题的简介：一位魔术师掏出一叠扑克牌，魔术师取出其中13张黑桃，洗好后，把牌面朝下。说：“我不看牌，只数一数就能知道每张牌是什么？”魔术师口中念一，将第一张牌翻过来看正好是A；魔术师将黑桃A放到桌上，继续数手里的余牌，第二次数1，2，将第一张牌放到这叠牌的下面，将第二张牌翻开，正好是黑桃2，也把它放在桌子上。第三次数1，2，3，前面二张牌放到这叠牌的下面，取出第三张牌，正好是黑桃3，这样依次将13张牌翻出，全部都准确无误。求解：魔术师手中牌的原始顺序是什么样子的？
class MoShuShiFaPai
{
private CycleLink<int> cycle = new CycleLink<int>();
public void Cal()
{
cycle.Clear();
for (int i = 0; i < 13; i++)
{
//初始化为-1 用来区分头结点
cycle.Add(-1);
}
//第一张肯定是1
CycleLink<int>.Node node = cycle.GetNodeByIndex(1);
node.data = 1;
int index = 0;
for (int i = 2; i <= 13; i++)
{
//设置其他位置的牌 头结点也计算进去了
while (index < i)
{
node = node.next;
if (node.data > 0) continue;
index++;
if (node.data == 0) index--;//跳过头结点不能算
}
index = 0;
node.data = i;
}
}
public void Print()
{
int data = 0;
for (int i = 1; i <= 13; i++)
{
cycle.GetElement(i, ref data);
Console.Write(data + " ");
}
}
}
41一个人围成一个圈，由第一个人开始报数，没数到第3个人就自杀，那么剩下的是在第几个。
圈的问题，使用循环链表的数据结构就很好解答了
我这里没有用到循环链表的特性，我这种做法，普通的链表数组其实都可以做到。
使用一个计数器，每记到第几位，就移除对应位置的元素，所以需要一个能够准确指向对应元素的index,index随着计数器往下加，注意不能超过数组范围，超过就回到原点。
最重要的是，在移除之后，index指向的元素就是移除元素的后一个了，所以要把index往前移动一下再进行计数。
如果使用循环链表的特性，就是不停的下几位，移除，下几位，移除.....
class YueSeFuProbrom
{
CycleLink<int> cycleLink = new CycleLink<int>();
public void Cal(int pNum, int which)
{
cycleLink.Clear();
//构建循环链表 表示圆圈
for (int i = 1; i <= pNum; i++)
{
cycleLink.Add(i);
}
int index = 0;
int counter = 0;
int who = 0;
while (cycleLink.GetCycleLinkLength() >= which)
{
index = index % cycleLink.GetCycleLinkLength();
counter++;
index++;
if (counter % which == 0)
{
cycleLink.Delete(index, ref who);
Console.Write(who + " ");
index--;
}
}
Console.WriteLine();
Console.Write("活着的有:");
for (int i = 1; i < which; i++)
{
cycleLink.GetElement(i, ref who);
Console.Write(who + " ");
}
Console.WriteLine();
Console.WriteLine();
}
}//测试
static void TestYueSeFu()
{
YueSeFuProbrom yueSeFu = new YueSeFuProbrom();
yueSeFu.Cal(5, 2);
yueSeFu.Cal(100, 3);
yueSeFu.Cal(6, 3);
yueSeFu.Cal(41, 3);
}
给你一个整数n. 从 1 到 n 按照下面的规则打印每个数：
如果这个数被3整除，打印
fizz.如果这个数被5整除，打印
buzz.如果这个数能同时被
3和5整除，打印fizz buzz.
要求：只用一个if判断
static List<string> Cal(int n)
{
List<string> res = new List<string>();
string[] temp = { "fizz", "fizz buzz", "buzz" };
for (int i = 1; i <= n; i++)
{
if (i % 3 != 0 && i % 5 != 0)
{
res.Add(i.ToString());
}
else
{
int a = i % 3;
int b = i % 5;
int off = a - b;
//映射（-1-0），（0,1），（1,2）
int index = Math.Sign(off / (double)int.MaxValue) + 1;
res.Add(temp[index]);
}
}
return res;
}我想的办法就是排除不是3和5倍数的数，然后将是3和5倍数的数通过一个映射计算到数组的下标，得到对应的字符串。
这里使用了Math.Sign不知道是不是取巧了，刚好这个函数是返回-1,0,1的，估计函数里面也有判断的，估计不是这样解的哈