给定两个大小为 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的,估计函数里面也有判断的,估计不是这样解的哈