你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
//别人的
public int Rob(int[] nums) {
int a = 0;
int b = 0;
for(int i = 0;i<nums.Length;i++)
{
if(i%2 == 0)
{
a = Math.Max(nums[i] + a,b);
}
else
{
b = Math.Max(a,nums[i] + b);
}
}
return Math.Max(a,b);
}//我的
public int Rob(int[] nums) {
if(nums.Length == 0) return 0;
if(nums.Length == 1) return nums[0];
//动态规划
int Max = 0;
int[] saveMax = new int[nums.Length];
saveMax[0] = nums[0];
Max = Math.Max(saveMax[0],nums[1]);
saveMax[1] = Max;
if(nums.Length == 2) return Max;
for(int i = 2;i<nums.Length;i++)
{
//当前只能跟前前一个整合
saveMax[i] = nums[i] + saveMax[i-2];
saveMax[i] = Math.Max(saveMax[i],saveMax[i-1]);
Max = Math.Max(Max,saveMax[i]);
}
return Max;
}
编写一个程序，找到两个单链表相交的起始节点。
例如，下面的两个链表：
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 在节点 c1 开始相交。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存
/**
* 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 GetIntersectionNode(ListNode headA, ListNode headB) {
ListNode TempA = headA;
ListNode TempB = headB;
int lenA = 0;
int lenB = 0;
//计算链表1的长度
while(TempA != null)
{
lenA++;
TempA = TempA.next;
}
//计算链表二的长度
while(TempB != null)
{
lenB++;
TempB = TempB.next;
}
TempA = headA;
TempB = headB;
//使他们起始到结束的长度相等
if(lenA > lenB)
{
for(int i = 0;i<lenA - lenB;i++)
{
TempA = TempA.next;
}
}
else
{
for(int i = 0;i<lenB - lenA;i++)
{
TempB = TempB.next;
}
}
while(TempA != TempB)
{
TempA = TempA.next;
TempB = TempB.next;
}
return TempA;
}
}
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
//时间O(n) 空间O(n)，可以用在乱序的数组中寻找
public int[] TwoSum(int[] numbers, int target) {
//索引存放值，值存放数组下标，值加减的检索变成索引key的加减检索
Dictionary<int,int> dic = new Dictionary<int,int>();
for(int i = 0;i<numbers.Length;i++)
{
if(dic.ContainsKey(target - numbers[i]))
{
return new int[]{Math.Min(i,dic[target - numbers[i]]) + 1, Math.Max(i,dic[target - numbers[i]]) + 1};
}
if(!dic.ContainsKey(numbers[i]))
{
dic.Add(numbers[i],i);
}
}
return null;
}//有序数组，所以用两个指标i和j指向两个极端，小了i++，大了j--，将sum向target靠近
//时间O(n)，空间O(1)
public int[] TwoSum(int[] numbers, int target) {
int i = 0;
int j = numbers.Length - 1;
int sum = 0;
while(i < j)
{
sum = numbers[i] + numbers[j];
if(sum == target)
{
return new int[]{i+1,j+1};
}
else if(sum > target)
{
j--;
}
else
{
i++;
}
}
return null;
}
编写一个 SQL 查询，获取 Employee 表中第二高的薪水（Salary） 。
+----+--------+ | Id | Salary | +----+--------+ | 1 | 100 | | 2 | 200 | | 3 | 300 | +----+--------+
例如上述 Employee 表，SQL查询应该返回 200 作为第二高的薪水。如果不存在第二高的薪水，那么查询应返回 null。
+---------------------+ | SecondHighestSalary | +---------------------+ | 200 | +---------------------+
其实难度在于null值的返回，一条select的情况下需要union一个null值的记录
SELECT (SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT 1,1) AS SecondHighestSalary;
SELECT Salary as SecondHighestSalary FROM Employee GROUP BY SecondHighestSalary UNION ALL (SELECT NULL AS SecondHighestSalary) ORDER BY SecondHighestSalary DESC LIMIT 1,1;
给定一个链表，判断链表中是否有环。
进阶：
你能否不使用额外空间解决此题？
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public bool HasCycle(ListNode head) {
ListNode p1 = head;
ListNode p2 = head;
//一个快指针和一个慢指针，如果有环，这两指针就会相遇
//如果无环，快指针就会跳出循环了
while(p1 != null && p1.next != null)
{
p1 = p1.next.next;
p2 = p2.next;
if(p2 == p1)
{
return true;
}
}
return false;
}
}
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"输出: true
示例 2:
输入: "race a car"输出: false
public bool IsPalindrome(string s) {
if(s.Length == 0) return true;
s = s.ToLower();
int i = 0;
int j = s.Length - 1;
while(i < j)
{
//排除非数字和字母字符
if( !((s[i] >= '0' && s[i] <= '9') || (s[i] >= 'a' && s[i] <= 'z')) )
{
i++;
continue;
}
//排除非数字和字母字符
if( !((s[j] >= '0' && s[j] <= '9') || (s[j] >= 'a' && s[j] <= 'z')) )
{
j--;
continue;
}
//比较对称的字符是否相等
if(s[i] != s[j])
{
return false;
}
else
{
i++;
j--;
}
}
return true;
}
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]输出: 4解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
public int MaxProfit(int[] prices) {
int Max = 0;
for(int i = 0;i<prices.Length-1;i++)
{
//无脑一天，有赚就买和卖
if(prices[i] < prices[i+1])
{
Max += prices[i+1] - prices[i];
}
}
return Max;
}
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
public int MaxProfit(int[] prices) {
int maxP = 0;
int curMax = 0;
for(int i = prices.Length - 1; i >= 0 ;i--)
{
if(prices[i] > curMax)
{
//要保证min在前面
curMax = prices[i];
continue;
}
//前面已经保证curMax在后面了，放心尝试最大利润
if(curMax - prices[i] > maxP)
{
maxP = curMax - prices[i];
}
}
return maxP;
}
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public bool HasPathSum(TreeNode root, int sum) {
if(root == null) return false;
if(root.left == null && root.right == null && root.val == sum)
{
return true;
}
//从上到下，用递减的方式递归
bool left = HasPathSum(root.left,sum-root.val);
bool right = HasPathSum(root.right,sum-root.val);
return left || right;
}
}
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3输出: [5,6,7,1,2,3,4]解释:向右旋转 1 步: [7,1,2,3,4,5,6]向右旋转 2 步: [6,7,1,2,3,4,5]向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入: [-1,-100,3,99] 和 k = 2输出: [3,99,-1,-100]解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100]
public void Rotate(int[] nums, int k) {
int len = nums.Length;
int temp = nums[0];
int index = 0;
int targetIndex = 0;
int startIndex = 0;
for(int i = 0;i< len; i++)
{
targetIndex = (index + k) % len;
//交换这两个数
temp = temp + nums[targetIndex];
nums[targetIndex] = temp - nums[targetIndex];
temp = temp - nums[targetIndex];
index = targetIndex;
if(index == startIndex)
{
//转回到了原点，将指标往下指
index = (index+1)%len;
startIndex = index;
temp = nums[index];
}
}
}