Z**********4
发帖数: 528 | 1 来自主题: JobHunting版 - 谈G家面经 可以这么做：
先必须用一个maxValue记录最大数的值，用作比对。
然后还需要记录maxIndex就是最大值所在的index.
还需要一个occur记录最大值出现的个数。
每次如果遇到一个没有当前maxValue大的数字，无视之。
如果遇到一个比当前maxValue大的数字，当然要更新maxValue. 而且也可以放心地更新
maxIndex，因为目前最大值是第一次出现。 occur也reset到1.
问题关键在于出现跟maxValue一样大的数字如何操作。就需要random地替换一个。先更
新orrcur让orrcur++
然后出个随机数使得当前的这个index有1/occur的概率被采用即可。
随机数可以就用C里面的 (rand()%occur + 1)这个范围就是[1, occur]而且可以
assume是等概率。
如果这个随机数==1， 那么就把当前的maxIndex更新，不然就do nothing.
数学证明应该可以用数学归纳法，这里只推前三个。
假设最大值出现的index是i1, i2, i3
P(maxIndex == i1) = 1 * (1-1/2) *(1-1/... 阅读全帖 |
|
l*****s
发帖数: 279 | 2 For 第二题, 随便写了一下，
public static int maxValue(int[] l, int[] w, int[] p, int L, int W) {
int len = l.length;
assert(l.length == w.length && l.length == p.length);
int[] v = new int[len+1];
for (int i=len-1; i>=0; i--) {
if (i == 0) {
if (l[i] > L || w[i] > W) {
v[i] = v[i+1];
} else {
v[i] = v[i+1]+p[i];
}
continue;
}
int[] l1 = Arrays.copyOfRange(l, 0, i-1);
int[] w1 = Arrays.copyOfRange(w, 0, i-1);
int[] p1 = Arrays.copyOfRange(p, 0, i-1);
int opt1 = v[i+1]+ maxValue(l1, w1, p1, L, W); // not us... 阅读全帖 |
|
b*******n
发帖数: 8 | 3 用讨论里的方法写了java 代码，不用字符串操作。
public class NumsWith5 {
public static void numsWith5(int maxvalue, int partial, int pos, boolean
hasFive) {
if (pos == 0) {
if (partial <= maxvalue && hasFive)
System.out.printf(partial + " ");
return;
}
int num = (int)Math.pow(10, pos - 1);
for (int i = 0; i < 10; i++) {
numsWith5(maxvalue, partial + num * i,
pos - 1, hasFive || i == 5);
}
}
publ... 阅读全帖 |
|
b*******n
发帖数: 8 | 4 用讨论里的方法写了java 代码，不用字符串操作。
public class NumsWith5 {
public static void numsWith5(int maxvalue, int partial, int pos, boolean
hasFive) {
if (pos == 0) {
if (partial <= maxvalue && hasFive)
System.out.printf(partial + " ");
return;
}
int num = (int)Math.pow(10, pos - 1);
for (int i = 0; i < 10; i++) {
numsWith5(maxvalue, partial + num * i,
pos - 1, hasFive || i == 5);
}
}
publ... 阅读全帖 |
|
w*****3
发帖数: 101 | 5 value 全正
/*
* find the maximum pair
*/
public int F( bn root){
return maxValue(root.left) +maxValue(root.right);;
}
/*
* find the bigest value path from root to the node
*/
public int maxValue( bn root){
if( root == null) return 0;
return root.value + Math.max(maxValue(root.left), maxValue(root.right));
} |
|
w*****3
发帖数: 101 | 6 有负值
HashMap map = new HashMap();
/*
* find the maximum pair
*/
public int solve( btn root){
if(root == null) return 0;
int res = maxValue(root.left) +maxValue(root.right);
res = Math.max(res, solve(root.left));
res = Math.max(res, solve(root.right));
return res;
}
/*
* find the bigest value path from root to the node
*/
public int maxValue( btn root){
if( root == null) return 0;... 阅读全帖 |
|
l********t
发帖数: 878 | 7 Judge small 全对
Judge large, 一共92个test case,有90个是对滴，
其中一个错误的是这个test case
{9,6,-3,#,#,-6,2,#,#,2,#,-6,-6,-6}
还有一个太长，不写了。
我自己编译运行结果是16，也是正确答案。上OJ非说我的结果是15...
leetcode，或者哪位大牛给看看？谢谢啊！
/**
* Definition for binary tree */
#include
#include
#include
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxValue;
int maxPathSum(TreeNode... 阅读全帖 |
|
l********t
发帖数: 878 | 8 另外谢谢 longway2008，确实是算单线最长的时候没考虑周到。贴个改过后work的
class Solution {
public:
int maxValue;
int maxPathSum(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int singleDown;
maxValue = -9999;
return maxPathOverload(root, singleDown);
}
int maxPathOverload(TreeNode* root, int& singleLine){
if (!root){
singleLine = 0;
return 0;
}
int leftSingleLine = 0;
... 阅读全帖 |
|
l*****s
发帖数: 279 | 9 2nd question
public static int maxValue(int[] l, int[] w, int[] p, int L, int W) {
assert(l.length == w.length && l.length == p.length);
if (l.length == 0) return Integer.MIN_VALUE;
return maxValueRecur(l, w, p, L, W, 0);
}
public static int maxValueRecur(int[] l, int[] w, int[] p, int L, int W,
int value) {
int len = l.length;
assert(l.length == w.length && l.length == p.length);
if (len == 1) {
if (l[0] > L || w[0]... 阅读全帖 |
|
l*****s
发帖数: 279 | 10 2nd question
public static int maxValue(int[] l, int[] w, int[] p, int L, int W) {
assert(l.length == w.length && l.length == p.length);
if (l.length == 0) return Integer.MIN_VALUE;
return maxValueRecur(l, w, p, L, W, 0);
}
public static int maxValueRecur(int[] l, int[] w, int[] p, int L, int W,
int value) {
int len = l.length;
assert(l.length == w.length && l.length == p.length);
if (len == 1) {
if (l[0] > L || w[0]... 阅读全帖 |
|
d*******l
发帖数: 338 | 11 对于每个非叶节点，算出对应的maxValue，这个可以O(n)做到。
对于每个非叶节点，用maxValue(leftChild)+maxValue(rightChild)去更新当前最大值
。也可以O(n)做到。
其实本质上就是wwwwar3的方法，保存每个节点的maxValue用到hashmap，如果是完全二
叉树也可以考虑用数组，那这个问题就非常像DP了。
wwwwar3的方法中对于null返回0感觉值得商榷，如果认为X和Y可以是同一个节点那可以
这么做，否则返回负无穷比较合适。 |
|
w*****3
发帖数: 101 | 12 我开始理解错了，
这个思路基本上是darksteel 说的一样，
java返回多个参数还真不方便，
HashMap map = new HashMap();
btn ln = null, rn = null;
int max = 0;
/*
* find the maximum pair
*/
public void solve(btn root) {
if (root == null)
return;
maxValue(root);
go(root, 0);
print(ln.value);
print(rn.value);
}
/*
* for each node, find the maximum pair
*/
private void go(btn root, int sumhere) {
if ... 阅读全帖 |
|
t*****9
发帖数: 569 | 13 用动态规划如何?
class FindMinWindow
{
private static readonly int[] A = { 1,1,1,1,2,1,1,1,1,3 };
private static readonly int[] Q = { 1,1,1,1,3 };
public static Point FindWindow(int startA, int startQ, bool
firstCall)
{
if (Q.Length <= startQ) return new Point(startA, 0);
if (A.Length <= startA) return new Point(startA, Int32.MaxValue);
List valueList = FindValue(startA, Q[startQ]);
i... 阅读全帖 |
|
S**I
发帖数: 15689 | 14 ☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Tue Jun 21 01:52:31 2011, 美东) 提到:
Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is
maximum where F(X,Y) = sum of nodes in the path from root to X + sum of
nodes in the path from root to Y - sum of nodes in the common path from root
to first common ancestor of the Nodes X and Y
☆─────────────────────────────────────☆
SecretVest (Secret Vest) 于 (Tue Jun 21 04:01:30 2011, 美东) 提到:
not hard if someone is used... 阅读全帖 |
|
w****w
发帖数: 521 | 15 Memory够的话，hash一下就出来了。不够的话得分批。
#!/usr/bin/env python
smallfile = file("small.txt","r")
largefile = file("large.txt","r")
outfile=file("out.txt","w")
HASHSIZE=10*1024*1024
maxvalue=0
hash={}
while 1:
line=largefile.readline()
if not line:
break
v=int(line.strip())
if v>maxvalue:
hash={}
while 1:
r=smallfile.readline()
if not r:
break
maxvalue=int(r.strip())
hash[maxvalue]=1
if le... 阅读全帖 |
|
H***e
发帖数: 476 | 16 第二题，
用往上面反值的方法， 左右子树传值给parent node. 总复杂度为O(n).
inside a class:
BSTNode maxsumNode = null;
int maxValue = Integer.MIN_VALUE;
public void findMaxSumSubtree(BSTNode node, MutableInt sum) {
// base cases:
if (node == null) {
sum.setValue(0);
return;
}
// normal cases:
MutableInt leftSum = new MutableInt();
MutableInt rightSum = new MutableInt();
findMaxSumSubtree(node.left, leftSum);
findMaxSumSubtree... 阅读全帖 |
|
y****n
发帖数: 743 | 17 思路：
1. 逆序遍历，凡是比后面最小值min大的元素，都需要swap。
并且记录其中最小值swapMin。
2. 再次逆序遍历，把第一次没数过的并且比swapMin大的都需要swap。
假设输入参数不为空：
public static int MinSwap(int[] arr)
{
int swapCount = 0;
int swapMin = int.MaxValue;
int min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
if (arr[i] > min)
{
swapCount++;
if (arr[i] < swapMin)
swapMin = arr[i];
}
else if (arr[i] < min)
min = arr[i];
min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
{
if ((arr[i] <= min) && (arr[i] > swapMin))
swapCount++;
if (arr[i] ... 阅读全帖 |
|
y****n
发帖数: 743 | 18 思路：
1. 逆序遍历，凡是比后面最小值min大的元素，都需要swap。
并且记录其中最小值swapMin。
2. 再次逆序遍历，把第一次没数过的并且比swapMin大的都需要swap。
假设输入参数不为空：
public static int MinSwap(int[] arr)
{
int swapCount = 0;
int swapMin = int.MaxValue;
int min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
if (arr[i] > min)
{
swapCount++;
if (arr[i] < swapMin)
swapMin = arr[i];
}
else if (arr[i] < min)
min = arr[i];
min = int.MaxValue;
for (int i = arr.Length - 1; i >= 0; i--)
{
if ((arr[i] <= min) && (arr[i] > swapMin))
swapCount++;
if (arr[i] ... 阅读全帖 |
|
r*c
发帖数: 167 | 19 之前写了个C#的。思路都一样， use tree matching algorithm to determine the
candidate window.
//using System;
using System.Collections.Generic;
using System.Linq;
using System.Collections;
class MinWindowSolution
{
class TreeNode
{
public TreeNode parent;
public int val;
public List children;
public TreeNode(int i, TreeNode p) { val = i; parent = p; children =
new List(); }
};
public void FindMinWindow_Tree(int[] input, int[] query, out int nS... 阅读全帖 |
|
m***2
发帖数: 595 | 20 ac的一个，不知道是不是最优
public class Solution {
/**
* @param nums: A list of integers
* @param k: As described
* @return: The majority number
*/
public int majorityNumber(ArrayList nums, int k) {
if (nums == null || nums.size() == 0 || k > nums.size() || k <= 0) {
return Integer.MAX_VALUE;
}
int[] value = new int[k];
int[] count = new int[k];
for (int i = 0; i < k; i++) {
count[i] = 0;
}
... 阅读全帖 |
|
f*******h
发帖数: 53 | 21 isBst(Node node, int maxValue, int minValue)
用这个做递归，刚开始maxValue=Integer.MAX_VALUE minValue=Integer.MIN_VALUE
从root做起：
isBst(root.left,root.value,Integer.MIN_VALUE) && isBst(root.right,Integer.
MAX_VALUE, root.value)
明白了么？ |
|
s*******f
发帖数: 1114 | 22 using System;
using System.Collections.Generic;
using System.Text;
namespace MSC
{
class Program
{
//“bool F(string s, char ch1, char
ch2, int n)”
//The function determines whether
or not there exists an occurrence of
//ch1 and ch2 separated by a
distance of no more than n in the given
//string s, where s is ascii and
user entered (your function needs
//to work on any input.) The
function must be efficient and
//**optimized** for both space... 阅读全帖 |
|
E*******0
发帖数: 465 | 23 我有一个假设：
Min(sum)>=Max[2*average, MaxValu];
int goal=Max[2*average, MaxValu];
同样排序，用greedy algorithm找到尽可能多的组合which sum equals goal. |
|
r*****n
发帖数: 35 | 24 来自主题: JobHunting版 - f家店面题 A method combine DP and greedy
object RiverJump {
def main(args: Array[String]) {
//val a = Array(1,1,1,0,1,1,0,0)
val a = Array(1,1,1,0,1,1,1,1, 0, 0)
val m = jump(a, 0, 1)
println(s"""$m""")
}
val set = new mutable.HashSet[(Int, Int)]()
def jump(r: Array[Int], start: Int, speed: Int): (Int, Boolean) = {
var ret: (Int, Boolean) = (Int.MaxValue, false)
if (start >= r.length) {
ret = (0, true)
} else if (set.contains(start, speed) || r(start) == 0) {
... 阅读全帖 |
|
u***n
发帖数: 21026 | 25 人家要找三个连在一起的，你这个不连在一起
最后找map最大的应该这么写，平时工作不怎么会iterator map，一般都是iterator
array,list所以抓瞎了
应该是 maxvalue= Math.Max(map.getValues())
for(ppp:map.getKeys()){
if(map.get(ppp) = maxvalue)
return ppp
}
唉，唉，唉 |
|
c******a
发帖数: 198 | 26 1. Given a method (public int Rand()) that returns any random integer in the
int range, write a wrapper method that returns a random number within a
specific range [min, max], assuming int.MinValue <= min <= max <= int.
MaxValue.
my solution was: min + (Rand() - int.MinValue) * (max - min + 1) / (int.
MaxValue - int.MinValue + 1), and use long type to account for overflow
issue. is this solution correct?
2. Given a M*N matrix where some cells are blocked and there may or may not
be a cell which ... 阅读全帖 |
|
l******s
发帖数: 3045 | 27 谢谢分享。不过会有time O(n)的可能么？
写了一个O(nln(n))的对付一下。
private static int jumpTimes(int[] leaves, int distance, int maxStep){
SortedDictionary dict = new SortedDictionary();
int i = 0;
for(i = 0; i < leaves.Length; i++)
if(!dict.ContainsKey(leaves[i])) dict[leaves[i]] = i;
int[,] lt = new int[dict.Count, 2];
i = 0;
foreach(var d in dict)
{ lt[i, 0] = d.Key; lt[i++, 1] = d.Value; }
for(i = 0; i < lt.Length; i++){
if(lt[i, 0] - (i == 0 ? 0 :... 阅读全帖 |
|
b****o
发帖数: 403 | 28 用 imshow(a, 'DisplayRange', [minvalue maxvalue]) 可以把一个grayscale图像显
示出来，像素值在minvalue和maxvalue的被线性转换为0-255的数值，超出范围的像素
值在两头分别被转换为0和255.
我的问题是，不自己编程，有没有现成的函数得到这个转换过后的图像内容？
先谢谢了 |
|
c******o
发帖数: 1277 | 29 看看kafka的source code, 哪儿像scala?
https://github.com/apache/kafka/blob/0.8.2/core/src/main/scala/kafka/api/
ApiUtils.scala
def readShortString(buffer: ByteBuffer): String = {
val size: Int = buffer.getShort()
if(size < 0)
return null
val bytes = new Array[Byte](size)
buffer.get(bytes)
new String(bytes, ProtocolEncoding)
}
def writeShortString(buffer: ByteBuffer, string: String) {
if(string == null) {
buffer.putShort(-1)
} else {
val encodedString ... 阅读全帖 |
|
H*******r
发帖数: 98 | 30 one is...
data select;
set original;
where var1 in (value1 value2 value3 value4 value5 value6 value7 value8)
or
var1 between minvalue and maxvalue or
var2 in (number1 number2 number3) or
var3 in (number1 number2 number3) or
var4 in (number1 number2 number3) or
var5 in (number1 number2 number3) or
var6 in (number1 number2 number3) or
var7 in (number1 number2 number3) or
var8 in (number1 number2 number3) or
... 阅读全帖 |
|
h********0
发帖数: 440 | 31 前面看到有一个贴子是判断isBinaryTree的问题
http://www.mitbbs.com/article_t/JobHunting/31521831.html
讨论结果主要有两个方向
(1) inOrderScan, 看看是不是结果排序了
(2) 对每一个节点判断是不是
node->val >＝ minValue(right tree)
node->val < maxValue(left tree)
对于第一种思路，我有一个问题，如果BST有重复值
BST assumes
left child <= current node < right child
但是如果我们只是看结果是不是排序，这个“＝”就不知道在什么地方了
有可能是 for some node: left child < current node <=right child.
那即使结果是排序的，其实也是有问题。
我自己想可以用一些方法来检查，但是都很ugly. 所以不知道有没有什么更好的想法。
对于第二种思路，在上一个贴子里有提供一个链接
http://cslibrary.stanford |
|
d****n
发帖数: 233 | 32 Here is the code in C#, please do let me know if you find any bug
// This program returns the shortest substring is src
// which contains all charactors in dest
// INT_MAX returned if no coverage found
static int MinimumCover(string src, string dst)
{
int minDist = int.MaxValue;
Hashtable ht = new Hashtable();
ArrayList al = new ArrayList();
foreach (char c in dst)
{
ht.Add(c,1);
|
|
I**A
发帖数: 2345 | 33 这个我大致看过
int minValue(struct node* node) {
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return(current->data);
}
int maxValue(struct node* node) {
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->right != NULL) {
current = current->left;
}
return(current->data);
}
这俩function，肯定有一个有问题。。。
再说了，这样求max and min也不make sense，因为只要在保证left or right是BST的
情况下才能 |
|
i**9
发帖数: 351 | 34 很多人给出的答案
int isBST(struct node* node) {
if (node==NULL) return(true);
// false if the max of the left is > than us
// (bug -- an earlier version had min/max backwards here)
if (node->left!=NULL && maxValue(node->left) > node->data)
return(false);
// false if the min of the right is <= than us
if (node->right!=NULL && minValue(node->right) <= node->data)
return(false);
// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
... 阅读全帖 |
|
j*****u
发帖数: 1133 | 35 bool F(string s, char ch1, char ch2, int n)
{
if (string.IsNullOrEmpty(s) || n <= 0 || ch1 == ch2)
throw new ArgumentException();
var index1 = new List();
var index2 = new List();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == ch1)
index1.Add(i);
else if (s[i] == ch2)
index2.Add(i);
}
int minDist = int.MaxValue;
int i1 = 0, i2 = 0;
while (i1 < index1.Count && i2 < index2.Count)
{
int diff ... 阅读全帖 |
|
j*****u
发帖数: 1133 | 36 bool F(string s, char ch1, char ch2, int n)
{
if (string.IsNullOrEmpty(s) || n <= 0 || ch1 == ch2)
throw new ArgumentException();
var index1 = new List();
var index2 = new List();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == ch1)
index1.Add(i);
else if (s[i] == ch2)
index2.Add(i);
}
int minDist = int.MaxValue;
int i1 = 0, i2 = 0;
while (i1 < index1.Count && i2 < index2.Count)
{
int diff ... 阅读全帖 |
|
c*********n
发帖数: 1371 | 37 我觉得这个题的本质是在第一个数组A中，对第二个数组B中的每个
元素找最接近的两个数：
假设对space没有要求.
create arrays:
BLower[B.length]{int.minValue, ........},
BUpper[B.length]{int.maxValue, ........}
for each( a in A){
for( i from 0 to B.length-1)
{
if(a
BLower[i]=a;
}
if(a>B[i] && BUpper[i]>a){
BUpper[i]=a;
}
}
}
return string[]{"[BLower[0], BUpper[0]", "[BLower[1], BUpper[1]",....."[
BLower[n-1], BUpper[n-1]"}
22]
string |
|
p*****2
发帖数: 21240 | 38
这样的话。上边那个答案也有问题吧？上来把root.value给了maxvalue。 |
|
s******n
发帖数: 3946 | 39 第二题，就是搞2个Heap来实现。
Heap1：MaxHeap, Heap2：MinHeap，保持Heap1.size==Heap2.size或者Heap1.size==
Heap2.size+1
void addNum(int num) {
if (Heap1.size==Heap2.size+1) {
if (num<=Heap1.maxValue()) {
int heap1MaxValue = Heap1.pop();
Heap2.add(heap1MaxValue);
Heap1.add(num);
} else Heap2.add(num);
} else {
if (num>=Heap2.MinValue()) {
int heap2MinValue = Heap2.pop();
Heap1.add(heap2MinValue);
Heap2.add(num);
} else Heap1.add(num);
}
}
多个机器的问题：从每个机器读一个block过来，效率比较好 |
|
e***s
发帖数: 799 | 40 public static int JumpGameII(int[] A)
{
if (A.Length <= 1)
return 0;
int[] MinJumps = new int[A.Length];
MinJumps[0] = 0;
for (int i = 1; i < A.Length; i++)
{
int Min = Int16.MaxValue;
for (int j = 0; j < i; j++)
{
if (MinJumps[j] >= Min)
continue;
if (A[j] >= i - j)
Min = Math.M... 阅读全帖 |
|
e***s
发帖数: 799 | 41 public static int JumpGameII(int[] A)
{
if (A.Length <= 1)
return 0;
int[] MinJumps = new int[A.Length];
MinJumps[0] = 0;
for (int i = 1; i < A.Length; i++)
{
int Min = Int16.MaxValue;
for (int j = 0; j < i; j++)
{
if (MinJumps[j] >= Min)
continue;
if (A[j] >= i - j)
Min = Math.M... 阅读全帖 |
|
y****n
发帖数: 743 | 42 牛顿迭代的算法要远好于Binary Search的O(lgn)。
贴个Sqrt(double)的算法。
static double Sqrt(double num)
{
double root = 1;
double diff = num - root * root;
double oldDiff = double.MaxValue;
int loop = 0;
while ((loop < 2) || (Math.Abs(diff) < Math.Abs(oldDiff)))
{
root = root + diff / root / 2;
oldDiff = diff;
diff = num - root * root;
loop++;
}
return root;
} |
|
y****n
发帖数: 743 | 43 改编成整数开方。算法复杂度说不清楚，远好于O(lgN)。
我只假设是O(lg(lgN))。
static Int64 SqrtInt(Int64 num)
{
Int64 maxRoot = (Int64)1 << 31;
Int64 root = 1;
Int64 oldDiff = Int64.MaxValue;
Int64 diff = num - root * root;
int loop = 0;
while ((loop < 2) || (Math.Abs((double)diff) < Math.Abs((double)oldDiff)
))
{
root = Math.Min(maxRoot, root + diff / root / 2);
oldDiff = diff;
diff = num - root * root;
loop++;
}
return (diff < 0) ? root - 1 : root;
} |
|
b******7
发帖数: 92 | 44 在[0,n-1]间查找，再减去多余的部分
int adjust(int A[],int n, int b)
{
if(n <= 0 || b < 0) return -1;
sort(A,A+n);
int index = -1;
int cursum = -1;
int low = 0, high = n-1;
while(low <= high)
{
int mid = low + (high - low)/2;
int sum = 0;
for(int i = 0; i < n; i++)
{
sum += min(A[i],A[mid]);
}
if(sum == b) return A[mid];
else if(sum > b)
{
index = mid;
cursum = sum;
high =... 阅读全帖 |
|
b******7
发帖数: 92 | 45 在[0,n-1]间查找，再减去多余的部分
int adjust(int A[],int n, int b)
{
if(n <= 0 || b < 0) return -1;
sort(A,A+n);
int index = -1;
int cursum = -1;
int low = 0, high = n-1;
while(low <= high)
{
int mid = low + (high - low)/2;
int sum = 0;
for(int i = 0; i < n; i++)
{
sum += min(A[i],A[mid]);
}
if(sum == b) return A[mid];
else if(sum > b)
{
index = mid;
cursum = sum;
high =... 阅读全帖 |
|
d***n
发帖数: 832 | 46 第一题可运行C# code，题目给出的test cases都过
不过我觉得我理解有误，因为b是2的整数倍这条信息没有用到
public static Int64 GetNumber(Int64 a, Int64 b)
{
if (a <= b) return b;
Int64 rem = b-a%b;
if((Int64.MaxValue - rem) < a)
{
throw new ArgumentOutOfRangeException();
}
return a + rem;
}
第三题在windows叫access violation。segmentation fault应该是unix的概念而且很
老了。 |
|
b******7
发帖数: 92 | 47 “perfect hash function”和该问题是两个不同的问题
前者是静态hash，即key的hash（key）已知，求hash函数。
而对于你贴中提到的hash排序，即要求key1< key2等价于hash（key1）
具体hash（key）的值未知，理想中是hash（key)为key排序时的相对序数。
所以基本上总绕不开要排序（包括非比较的排序）
非要用hash表排序的话，可能是用hash表替换数组实现基数排序
比如abc gf
用hash表hash 存储 <'a'*128*128+'b'*128+'c', "abc"> <'g'*128+'f'
, "gf">
然后查询key从0~maxvalue，检测是否key在hash表中 |
|
d****n
发帖数: 233 | 48 void MinimumWindowCoverInOrder(int[] A, int[] B, out int start, out int min)
{
Dictionary> bPosInAMap = new Dictionary>(
);
Queue[] bPosInA = new Queue[B.Length];
start = -1;
min = Int32.MaxValue;
for (int i = 0; i < B.Length; ++i) {
if (!bPosInAMap.ContainsKey(B[i]))
bPosInAMap.Add(B[i], new Queue());
}
for (int i = 0; i < A.Length; ++i) {
if (bPosInAMap.ContainsKey(A[i]))
bPosInAMa... 阅读全帖 |
|
z*********8
发帖数: 2070 | 49 输入double.MaxValue 陷入死循环了。。。 |
|
