Showing posts with label Cracking Coding Interview. Show all posts
Showing posts with label Cracking Coding Interview. Show all posts

猫狗收容所


https://www.nowcoder.com/questionTerminal/6235a76b1e404f748f7c820583125c50
        有家动物收容所只收留猫和狗，但有特殊的收养规则，收养人有两种收养方式，第一种为直接收养所有动物中最早进入收容所的，第二种为选择收养的动物类型（猫或狗），并收养该种动物中最早进入收容所的。
       给定一个操作序列int[][2] ope(C++中为vector<vector<int>>)代表所有事件。若第一个元素为1，则代表有动物进入收容所，第二个元素为动物的编号，正数代表狗，负数代表猫；若第一个元素为2，则代表有人收养动物，第二个元素若为0，则采取第一种收养方式，若为1，则指定收养狗，若为-1则指定收养猫。请按顺序返回收养的序列。若出现不合法的操作，即没有可以符合领养要求的动物，则将这次领养操作忽略。
测试样例： 
[[1,1],[1,-1],[2,0],[2,-1]]
返回：[1,-1]


https://blog.csdn.net/qq_39445165/article/details/84796849
2. 思路分析：① 从题目中我们可以知道需要按照时间顺序求解出收养动物编号的序列，而且控制台输入的情况不同，对应的收养情况也会不同，其实这里蕴含着某种数据结构的特点，为“先进先出”，先进来的动物是最早可能被收养的，所以我们可以使用队列这种数据结构来存储其中的数据

② 我们可以使用两个队列，一个是猫的队列，一个是狗的队列这样可以方便我们入队和出队，当操作序列的第一个元素为1的时候我们就入队，根据操作序列的第二个元素我们可以知道入的是猫队还是狗队

当操作序列的第一个元素为2的时候我们需要出队，根据操作序列的第二个元素假如元素为1而且狗队里面的元素不为空的话我们就从狗队里面出一个元素，元素为-1而且猫队里面的元素不为空的话我们就从猫队里面出一个元素

元素为0的时候这个时候就要比较猫的队首元素和狗的队首元素入收容所的时间，怎么样知道这个时间呢？我们知道进入队列肯定时间有先有后那么我们可以在入队的时候就记录这个时间，等到查看队首元素的时候我们就知道这个时间了然后进行比较就可以了

③ 我们可以在一开始创建队列的时候就可以把队列里面的数据类型设置为一个对象，利用对象可以封装对应的属性的特点，往对象中增加时间这个属性这样我们就可以在一创建这个对象的时候就把入队的时间进行记录下来，这里可以使用设置一个全局变量来进行时间的记录，然后再创建对象的时候这个全局变量的值加一然后赋值给这个对象中的时间属性，注意这里的类是私有的内部类，而且必须声明成static
  private static int timeCur = 1;

  private static class Animal {
    private int typeNumber;
    private int time;

    public Animal(int typeNumber) {
      super();
      this.typeNumber = typeNumber;
      this.time = timeCur++;
    }

    @Override
    public String toString() {
      return "Animal [typeNumber=" + typeNumber + ", time=" + time + "]";
    }
  }

  private static ArrayList<Integer> catAndDogAsyLum(int opValue[][]) {
    Queue<Animal> cats = new LinkedList<Animal>();
    Queue<Animal> dogs = new LinkedList<Animal>();
    ArrayList<Integer> res = new ArrayList<Integer>();
    for (int opVal[] : opValue) {
      int opCode = opVal[0];
      int value = opVal[1];
      if (opCode == 1) {
        if (value > 0) {
          Animal dog = new Animal(value);
          dogs.add(dog);
        }
        if (value < 0) {
          Animal cat = new Animal(value);
          cats.add(cat);
        }
      } else if (opCode == 2) {
        if (!dogs.isEmpty() && value == 1) {
          res.add(dogs.poll().typeNumber);
        }
        if (!cats.isEmpty() && value == -1) {
          res.add(cats.poll().typeNumber);
        }
        if (value == 0) {
          if (dogs.isEmpty() && !cats.isEmpty()) {
            res.add(cats.poll().typeNumber);
          } else if (!dogs.isEmpty() && cats.isEmpty()) {
            res.add(dogs.poll().typeNumber);
          } else if (!dogs.isEmpty() && !cats.isEmpty()) {
            int type = dogs.peek().time > cats.peek().time ? cats.poll().typeNumber : dogs.poll().typeNumber;
            res.add(type);
          }
        }
      } else {
        break;
      }
    }
    return res;
  }

https://blog.csdn.net/hj605635529/article/details/70876254
因为先进先出，用两个队列来表示收养所，猫队列的头部就是最早进入收留所的猫，狗队列的头部就是最早进入收留所的狗，
但是这种形式我们不能确定第一个进入的猫和第一个进入的狗谁最早进入，所以我们想到当入队列的时候，把动物的时间也压入。用一个额外的int变量来表示时序。
vector<int> Asylum(vector<vector<int> > ope)
{
queue<int> cat;
queue<int> dog;
vector<int> ret;
int idx = 0;  //表示时间。
for(int i = 0; i < ope.size(); ++i)
{
if(ope[i][0] == 1) //有动物要进收养所了。
{
if(ope[i][1] > 0) //编号大于0，表示狗进入
{
dog.push(idx++); //把动物的时序也一并压入。
dog.push(ope[i][1]);
}
else
{
cat.push(idx++);
cat.push(ope[i][1]);
}
}
if(ope[i][0] == 2) //表示有人要收养动物了。
{
if(ope[i][1] == 0) //第一种方式收养，收养最早的动物。
{
int catidx = cat.empty() ? 10000000 :cat.front(); 
int dogidx = dog.empty() ? 10000000 :dog.front();
if(catidx < dogidx)
{
cat.pop(); //把时序弹出。
ret.push_back(cat.front() );
cat.pop();
}
else
{
dog.pop(); //把时序弹出。
ret.push_back(dog.front() );
dog.pop();
}
}
else if(ope[i][1] == 1) //第二种方式收养，收养狗
{
if(!dog.empty())
{
dog.pop(); //把时序弹出。
ret.push_back(dog.front() );
dog.pop();
}
}
else
{
if(!cat.empty() )
{
cat.pop(); //把时序弹出。
ret.push_back(cat.front() );
cat.pop();
}
}
}
}
return ret;
}


at
Labels: ,

Set of Stacks - nowcoder


https://blog.csdn.net/HelloZEX/article/details/81126850
请实现一种数据结构SetOfStacks，由多个栈组成，其中每个栈的大小为size，当前一个栈填满时，新建一个栈。该数据结构应支持与普通栈相同的push和pop操作。

给定一个操作序列int[][2] ope(C++为vector<vector<int>>)，每个操作的第一个数代表操作类型，若为1，则为push操作，后一个数为应push的数字；若为2，则为pop操作，后一个数无意义。请返回一个int[][](C++为vector<vector<int>>)，为完成所有操作后的SetOfStacks，顺序应为从下到上，默认初始的SetOfStacks为空。保证数据合法。

思路：首先建立一个栈组A（定义为vector<vector<int>> A），存放长度达到size的栈。定义vector<int> vect

操作如下：

从i = 0 ~ ope.size() - 1遍历

1、对于压栈指令(即ope[i][0] = 1)，首先判断A是否为空

    1）如果A为空，那么考虑将数据压入vect

            1.如果vect长度已经达到size，那么先将vect压入A，然后清空vect里的元素，再将数据ope[i][1]压入vect;

            2.如果vect长度小于size，直接将vect压入A（此时不可以判断vect的长度是否到达size，即使到达size，也要确定下一个指令不是pop，才可以将vect压入A，以免压入之后，再从A[A.size() - 1]中弹出数据）。

    2）如果A不为空，先判断A的顶栈是否是满的，即判断A[A.size() - 1]长度是不是达到size，如果没有达到size，则将数据压入A[A.size() -1];如果达到size，则对vect进行判断，如果vect长度小于size，直接压入vect，否则执行上一步的第一条。

2、对于出栈指令，首先判断vect是否为空

    1）如果vect为空，则从A的顶栈中弹出顶元素，即执行A[a.size() - 1].pop_back()，弹出之后如果A[a.size() - 1]为空，则从A中弹出A[a.size() - 1],即执行A.pop_back;

    2）如果vect不为空，则直接从vect中弹出元素，即执行vect.pop_back().

遍历结束之后，如果vect不为空，则将vect压入A，即A.push_back(vect)。

返回A。

    vector<vector<int> > setOfStacks(vector<vector<int> > ope, int size) {
        // write code here
        vector<int> vect;
        vector<vector<int>> A;
        int len = vect.size();
        for(int i = 0; i < ope.size(); i ++)
            {
            //压入操作时
            if(ope[i][0] == 1)
                {
                //判断A是否为空
                if(A.size() == 0)
                    {
                    //判断vect是否已满
                    if(vect.size() == size)
                        {
                        A.push_back(vect);
                        vect.clear();
                        vect.push_back(ope[i][1]);
                    }
                    else
                        vect.push_back(ope[i][1]);
                }
                else  //A不为空
                    {
                    //判断A的顶栈是否已满
                    if(A[A.size() - 1].size() < size)
                        A[A.size() - 1].push_back(ope[i][1]);
                    else
                        {
                        if(vect.size() == size)
                            {
                            A.push_back(vect);
                            vect.clear();
                            vect.push_back(ope[i][1]);
                        }
                        else
                            vect.push_back(ope[i][1]);
                    }
                }
            }
            else   //弹出操作
                {
                //判断vect是否为空
                if(vect.empty())   //为空
                    {
                    //弹出A顶栈的元素
                    A[A.size() - 1].pop_back();
                    //判断顶栈是否为空
                    if(A[A.size() - 1].empty())  //为空则弹出顶栈
                        A.pop_back();
                }
                else    //vect不为空
                    vect.pop_back();
            }
        }
        if(!vect.empty())
            A.push_back(vect);
        return A;
    }
https://blog.csdn.net/qq_17034717/article/details/51364533
https://www.nowcoder.com/questionTerminal/69f0ffed01c741c5ae5594a23f7cd739
  public ArrayList<ArrayList<Integer>> setOfStacks(int[][] ope, int size) {
    // write code here
    ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> curArray = new ArrayList<Integer>(size);
    list.add(curArray);
    for (int i = 0; i < ope.length; i++) {
      switch (ope[i][0]) {
      // 1:push
      case 1:
        // 当前数组未满
        if (curArray.size() != size) {
          curArray.add(ope[i][1]);
        } else {
          curArray = new ArrayList<Integer>(size);
          list.add(curArray);
          curArray.add(ope[i][1]);
        }
        break;
      // 2:pop
      case 2:
        // 当前数组不为空
        if (curArray.size() != 0) {
          curArray.remove(curArray.size() - 1);
        } else {
          list.remove(list.size() - 1);
          curArray = list.get(list.size() - 1);
          curArray.remove(curArray.size() - 1);
        }
        break;
      }
    }
    return list;

  }

https://www.bbsmax.com/A/D854p0w5Eg/
at
Labels: , ,

Set of Stacks


https://www.cnblogs.com/grandyang/p/4677072.html
3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOf Stacks that mimics this. SetOf Stacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOf Stacks. push() and SetOf Stacks. pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

这道题让我们实现一个多个栈的数据结构，这个多个栈顾名思义是由许多子栈组成的，每个子栈都有相同的大小，在压入栈的过程中，如果当前子栈满了，则新建一个栈，压入新值。在移除栈顶元素时，若最上面的子栈移除后为空时，移除该子栈。还是返回栈顶元素和判断栈是否为空，这些基本的栈操作都不是很难，只要注意需要的时候新建和销毁子栈就行了。难点在于Follow Up，让我们来实现一个popAt函数，这个函数是要对于任意一个子函数来移除栈顶元素，找到并移除子栈的站定元素并不难，难点在于如果我们默认子栈必须都存满的话，那么如果中间的子栈栈顶被移除了，上面紧挨的子栈的栈底元素就要移到下面，成为下面的子栈的栈顶元素，然后以此类推，每个中间的子栈都要装满，这个实现起来就比较复杂，我们需要用递归来做，我们需要实现一个leftShift的辅助函数，这个函数可以移除子栈的栈顶元素或者栈底元素，具体实现参见代码如下：
    SetOfStacks(int capacity) : _capacity(capacity) {}
    
    void push(int x) {
        stack<int> last;
        if (!_stacks.empty() && _stacks.back().size() < _capacity) {
            last = _stacks.back();
            _stacks.pop_back();
        }
        last.push(x);
        _stacks.push_back(last);
    }
    
    void pop() {
        if (!_stacks.empty()) {
            stack<int> last = _stacks.back();
            last.pop();
            if (last.empty()) _stacks.pop_back();
        }
    }
    
    int top() {
        if (!_stacks.empty()) {
            stack<int> last = _stacks.back();
            return last.top();
        }
        return 0;
    }
    
    bool empty() {
        return _stacks.empty();
    }
    
    void popAt(int index) {
        leftShift(index, true);
    }
    
    int leftShift(int index, bool removeTop) {
        stack<int> *cur = &_stacks[index];
        int removed_item;
        if (removeTop) {
            removed_item = cur->top();
            cur->pop();
        } else {
            stack<int> tmp;
            while (!cur->empty() && cur->size() != 1) {
                tmp.push(cur->top());
                cur->pop();
            }
            removed_item = cur->top();
            cur->pop();
            while (!tmp.empty()) {
                cur->push(tmp.top());
                tmp.pop();
            }
        }
        if (cur->empty()) _stacks.erase(_stacks.begin() + index);
        else if (_stacks.size() > index + 1) {
            int val = leftShift(index + 1, false);
            cur->push(val);
        }
        return removed_item;
    }
    
private:
    vector<stack<int> > _stacks;
    int _capacity;


at
Labels: ,

打印出二叉树中结点值的和为输入整数的所有路径


https://blog.csdn.net/derrantcm/article/details/46705853
输入一棵二叉树和一个整数， 打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径
https://www.nowcoder.com/questionTerminal/b736e784e3e34731af99065031301bca
  private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
  private ArrayList<Integer> list = new ArrayList<Integer>();

  public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
    if (root == null)
      return listAll;
    list.add(root.val);
    target -= root.val;
    if (target == 0 && root.left == null && root.right == null)
      listAll.add(new ArrayList<Integer>(list));
    FindPath(root.left, target);
    FindPath(root.right, target);
    list.remove(list.size() - 1);
    return listAll;

  }


由于路径是从根结点出发到叶结点， 也就是说路径总是以根结点为起始点，因此我们首先需要遍历根结点。在树的前序、中序、后序三种遍历方式中，只有前序遍历是首先访问根结点的。

当用前序遍历的方式访问到某一结点时， 我们把该结点添加到路径上，并累加该结点的值。如果该结点为叶结点并且路径中结点值的和刚好等于输入的整数， 则当前的路径符合要求，我们把它打印出来。如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保返回父结点时路径刚好是从根结点到父结点的路径。

不难看出保存路径的数据结构实际上是一个枝， 因为路径要与递归调用状态一致， 而递归调用的本质就是一个压栈和出栈的过程。

    public static void findPath(BinaryTreeNode root, int expectedSum) {
        // 创建一个链表，用于存放根结点到当前处理结点的所经过的结点
        List<Integer> list = new ArrayList<>();

        // 如果根结点不为空，就调用辅助处理方法
        if (root != null) {
            findPath(root, 0, expectedSum, list);
        }
    }

    /**
     * @param root        当前要处理的结点
     * @param curSum      当前记录的和（还未加上当前结点的值）
     * @param expectedSum 要求的路径和
     * @param result      根结点到当前处理结点的所经过的结点，（还未包括当前结点）
     */
    public static void findPath(BinaryTreeNode root, int curSum, int expectedSum, List<Integer> result) {

        // 如果结点不为空就进行处理
        if (root != null) {
            // 加上当前结点的值
            curSum += root.value;
            // 将当前结点入队
            result.add(root.value);
            // 如果当前结点的值小于期望的和
            if (curSum < expectedSum) {
                // 递归处理左子树
                findPath(root.left, curSum, expectedSum, result);
                // 递归处理右子树
                findPath(root.right, curSum, expectedSum, result);
            }
            // 如果当前和与期望的和相等
            else if (curSum == expectedSum) {
                // 当前结点是叶结点，则输出结果
                if (root.left == null && root.right == null) {
                    System.out.println(result);
                }
            }
            // 移除当前结点
            result.remove(result.size() - 1);
        }
    }



at
Labels: ,

字符串的排列


https://blog.csdn.net/zjkC050818/article/details/71116168
编写一个方法，确定某字符串的所有排列组合。

给定一个string A和一个int n,代表字符串和其长度，请返回所有该字符串字符的排列，保证字符串长度小于等于11且字符串中字符均为大写英文字符，排列中的字符串按字典序从大到小排序。(不合并重复字符串)

测试样例：
"ABC"
返回：["CBA","CAB","BCA","BAC","ACB","ABC"]

ArrayList<String> list = new ArrayList<String>();

public ArrayList<String> getPermutation(String A) {
char[] chars = A.toCharArray();
getString(chars, 0, A.length()-1);

//Collections.sort()默认从小到大排序，所以需要重写Comparator
Collections.sort(list, new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
});

return list;
}

private void getString(char[] chars, int left, int right) {
if (left > right)
return;
//当到达字符数组最后一位时，添加到list中
if (left == right) {
list.add(String.valueOf(chars));
return;
}
for (int i = left; i <= right; i++) {
change(chars, left, i);
getString(chars, left + 1, right);
//因为只有一个char[]数组，所以每一次返回需要把数组change回去
change(chars, left, i);
}
}

private void change(char[] chars, int left, int i) {
char tmp = chars[left];
chars[left] = chars[i];
chars[i] = tmp;
}

https://blog.csdn.net/sinat_24048051/article/details/71506713
https://www.bbsmax.com/A/D854p0w5Eg/
    public static ArrayList<String> getPermutation(String A) {
        // write code here
        ArrayList<StringBuffer> res = new ArrayList();
        ArrayList<String> finalRes = new ArrayList();
        char[] c = A.toCharArray();
        Arrays.sort(c);
        StringBuffer start = new StringBuffer();
        start.append(c[c.length - 1]);
        res.add(start);
        System.out.println(res);
        for (int i = c.length - 2; i >= 0; --i) {
            ArrayList<StringBuffer> temp = new ArrayList();
            for (StringBuffer sb : res) {
                for (int j = 0; j <= sb.length(); ++j) {
                    StringBuffer tempSb = new StringBuffer(sb);
                    tempSb.insert(j, c[i]);
                    temp.add(tempSb);
                }
            }
            res = new ArrayList(temp);
        }
        for (int i = 0; i < res.size(); ++i) {
            finalRes.add(new String(res.get(i)));
        }
        Collections.sort(finalRes, new Comparator<String>() {
            public int compare(String a, String b) {
                for (int i = 0; i < a.length() && i < b.length(); ++i) {
                    if (a.charAt(i) < b.charAt(i)) {
                        return 1;
                    } else if (a.charAt(i) > b.charAt(i)) {
                        return -1;
                    }
                }
                if (a.length() > b.length()) {
                    return -1;
                } else {
                    return 1;
                }
            }
        });
        System.out.println(finalRes);
        return finalRes;
    }


at
Labels:

Magic Index


https://www.cnblogs.com/wuchanming/p/4149788.html
http://www.voidcn.com/article/p-ofbkvbvl-bkw.html
在数组A[0..n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个升序数组，元素值各不相同，编写一个方法，判断在数组A中是否存在魔术索引。请思考一种复杂度优于o(n)的方法。
给定一个int数组A和int n代表数组大小，请返回一个bool，代表是否存在魔术索引。
测试样例：
[1,2,3,4,5]
返回：false

解答

暴力法

class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        // write code here
        for(int i = 0;i<n;++i)
            if(A[i] == i)
                return true;

        return false;
    }
};

根据数据特点，利用二分查找的思想

　　给定的数组是有序的。
　　这个问题域经典的二分查找非常相似。在二分查找中，要找出元素k，我们会先拿它跟数组中间的元素x比较，确定k是位于x的左边还是右边。
　　以此为基础，是否可以通过检查中间元素来确定魔术索引的位置？
　　这里写图片描述
　　以上面的数组为例，看到中间元素A[5] = 3，由于A[mid]
    bool findMagicIndex(vector<int> A, int n) {
        // write code here
        return findMagicIndexCore(A,0,A.size()-1) == -1?false:true;

    }

    int findMagicIndexCore(vector<int> A,int start,int end)
    {
        if(end<start || start < 0 || end>=A.size())
            return -1;
        int mid = (start+mid)/2;
        if(A[mid] == mid)
            return mid;
        else if(A[mid] < mid)
            return findMagicIndexCore(A,mid+1,end);
        else
            return findMagicIndexCore(A,start,mid-1);
    }
X. https://www.cnblogs.com/wuchanming/p/4149788.html
如果存在重复元素，前面的算法就会失效。以下面的数组为例：
-10 -5 2 2 2 3 4 7 9 12 13
  0   1  2 3 4 5 6 7 8 9 10 11
看到A[mid]<mid时，我们无法判定魔术索引位于数组哪一边。它可能在数组右侧，跟前面一样。或者，也可能在左侧（在本例中的确在左侧）。
它有没有可能在左侧的任意位置呢？不可能。由A[5]=3可知，A[4]不可能是魔术索引。A[4]必须等于4,其索引才能成为魔术索引，但数组是有序的，故A[4]必定小于A[5]。
事实上，看到A[5]=3时按照前面的做法，我们需要递归搜索右半部分。不过，如搜索左半部分，我们可以跳过一些元素，值递归搜索A[0]到A[3]的元素。A[3]是第一个可能成为魔术索引的元素。

综上：我们得到一种搜索模式，先比较midIndex和midValue是否相同。然后，若两者不同，则按如下方式递归搜索左半部分和右半部分。
左半部分：搜索索引从start到min(midIndex-1,midValue)的元素。
右半部分：搜索索引从max(midIndex+1,minValue)到end的元素。
可以看做前面的基础上求左右两边的交集，例如A[mid]<mid，需要搜索mid左边的部分元素，即区间从start到min(midIndex-1,midValue)的元素和mid右边的全部元素。
A[mid]>mid，需要搜索mid左边的全部元素和右边的部分元素，即区间从max(midIndex+1,minValue)到end，然后两者求交集，就得到上面的区间了。
int magicHelper(int arr[],int n,int l,int r)
{
    if(l>r||l<0||r>=n)
        return -1;
    int mid=(l+r)/2;
    if(mid==arr[mid])
        return mid;
    int rightindex=min(mid-1,arr[mid]);
    int left=magicHelper(arr,n,l,rightindex);
    if(left>=0)
        return left;
    int leftindex=max(mid+1,arr[mid]);
    int right=magicHelper(arr,n,leftindex,r);
    return right;
}
//有重复元素
int magicFast(int arr[],int n)
{
    if(n==0)
        return -1;
    return magicHelper(arr,n,0,n-1);
}

http://www.voidcn.com/article/p-rkooanvq-bkw.html
在数组A[0..n-1]中，有所谓的魔术索引，满足条件A[i]=i。给定一个不下降序列，元素值可能相同，编写一个方法，判断在数组A中是否存在魔术索引。请思考一种复杂度优于o(n)的方法。
给定一个int数组A和int n代表数组大小，请返回一个bool，代表是否存在魔术索引。
测试样例：
[1,1,3,4,5]
返回：true

解答

　　如果数组的元素有重复，魔术索引1中的方法就会失效。以下面的数组为例
　　这里写图片描述
　　可以看到A[mid] < mid时，我们无法判定魔术索引位于数组的哪一边。
　　它是否可能在左侧的任意位置？不是。由A[5]=3，可以知道，A[4]不可能是魔术索引。A[4]=4，它才能是魔术索引，但数组是有序的，索引A[4]必定小于等于A[5]。
　　所以，我们可以将算法分为两步
　　
  1. 比较midIndex与midValue，若二者相同，直接返回。
  2. 否按照如下的方式，递归搜索数组的左半部分和右半部分：
    左半部分：搜索从start到min（midIndex-1,midValue）的元素；
    右半部分：搜索从max（midIndex+1,midValue）到end的元素。
    bool findMagicIndex(vector<int> A, int n) {
        // write code here
        return findMagicIndexCore(A,0,A.size()-1) == -1?false:true;
    }

    int findMagicIndexCore(vector<int> A,int start,int end)
    {
        if(end<start || start <0 || end>=A.size())
            return -1;
        int midIndex = (start+end)/2;
        int midValue = A[midIndex];
        if( midValue == midIndex)
            return midIndex;

        int leftEnd = min(midIndex-1,midValue);
        int left = findMagicIndexCore(A,start,leftEnd);
        if(left>=0)
            return left;

        int rightStart = max(midIndex+1,midValue);
        int right = findMagicIndexCore(A,rightStart,end);

        return right;

    }



at
Labels: , , ,

找出字符串


https://blog.csdn.net/LK274857347/article/details/71123086

有一个排过序的字符串数组，但是其中有插入了一些空字符串，请设计一个算法，找出给定字符串的位置。算法的查找部分的复杂度应该为log级别。
给定一个string数组str,同时给定数组大小n和需要查找的string x，请返回该串的位置(位置从零开始)。
测试样例：
["a","b","","c","","d"],6,"c"
返回：3

https://blog.csdn.net/LK274857347/article/details/71123086
  public int find(String[] str, int n, String toFindString) {
    if (str == null || n == 0)
      return -1;
    int low = 0, high = n - 1;

    while (low <= high) {
      int mid = (high - low) / 2 + low;
      if (str[mid] == "") {
        int index = mid;
        while (index >= low && str[index] == "") {
          index--;
        }
        if (index < low)
          low = mid + 1;
        else if (str[index].compareTo(toFindString) > 0)
          high = index - 1;
        else if (str[index] == toFindString)
          return index;
        else
          low = mid + 1;
      }
      if (str[mid].compareTo(toFindString) > 0)
        high = mid - 1;
      else if (str[mid].compareTo(toFindString) < 0)
        low = mid + 1;
      else if (str[mid] == toFindString)
        return mid;
    }
    return -1;
  }

  public int find2(String[] str, int n, String x) {
    // write code here
    if (str == null || n == 0)
      return -1;
//int length = str.length;
    int left = 0, right = n - 1;
    while (left <= right) {
      int mid = (right - left) / 2 + left;
      if (str[mid] == x)
        return mid;
      if (str[mid] == "") {
        int index = mid;
        while (index >= left && str[index] == "")
          index--;
        if (index < left)
          left = mid + 1;
        if (str[index] == x)
          return index;
        else if (str[index].compareTo(x) > 0)
          right = index - 1;
        else
          left = mid + 1;
      } // if(str[mid]=="")
      if (str[mid].compareTo(x) > 0)
        right = mid - 1;
      else if (str[mid].compareTo(x) < 0)
        left = mid + 1;
    } // while(left<=right){
    return -1;
  }

//该方法更加简洁，简单。
  public int find3(String[] str, int n, String x) {
    // write code here
    if (str == null || n == 0)
      return -1;
//int length = str.length;
    int left = 0;
    int right = n - 1;
    int mid;
    while (left <= right) {
      mid = (right + left) / 2;

      if (str[mid].equals("")) {
        mid--;
      } // if(str[mid]=="")
      if (str[mid].equals(x)) {// 牛客编译器使用==无法得到结果，显示时间超时。
        return mid;
      } else if (str[mid].compareTo(x) > 0) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } // while(left<=right){
    return -1;

  }
http://www.voidcn.com/article/p-pbkpujpb-bdv.html
    public int findString(String[] str, int n, String x) {
        // write code here
        int i =0,j=n-1;
        while(i<=j)
        {
            int mid = (i+j)/2;
            if(str[mid].equals(" "))
            {
                int index = mid;
                while(str[index].equals(" ")&&index>i)
                {
                    index--;
                }
                if(index==i)
                {
                    index = mid+1;
                    while(str[index].equals(" ")&&index<j)
                    {
                        index++;
                    }
                    
                }
                mid = index;
            }
            if(str[mid].equals(x))  return mid;
            else if(str[mid].compareTo(x)>0)    j = mid-1;
            else i = mid+1;


        }
        return -1;
    }


http://www.voidcn.com/article/p-welkqjqq-nx.html
这是一道二分查找 的变形题目。唯一的关注点就是当str[mid] == ""时的处理，此时仅通过str[mid]=""是无法判断目标是在mid的左边还是右边。所以，我们遍历mid左边的元素找到第一个不是空字符串的元素。
如果mid左边的所有元素都是空字符串，则去掉令s=mid+1；
否则
    找到第一个不是空字符串的元素下标为s1
    （1）如果str[s1]等于目标正好返回。
    （2）如果str[s1]大于目标，则说明目标在str[s1]左边，令e= s1- 1。
    （3）如果str[s1]小于目标，则说明目标在str[mid]右边，令s= mid + 1

class Finder {
public:
 int find(vector<string>& str, int s, int e, string& x)
 {
  if (s > e)return -1;
  int mid = (s + e) / 2;
  int index = -1;
  int s1 = mid;
  if (str[mid].empty())
  {
   while (s1 >s&& str[--s1].empty());
   
  }
  if (str[s1].compare(x)>0){
   index = find(str, s, s1 - 1, x);
  }
  else if (str[s1].compare(x) == 0){
   return s1;
  }
  else if (str[s1].compare(x) < 0) //mid左侧全部是空字符串或者左边第一个非空字符串比x小
  {
   index = find(str, mid+1, e, x);
  }
  
  return index;
 }

 int findString(vector<string> str, int n, string x) {
  // write code here
  int index = find(str, 0, n - 1, x);
  return index;
 }


答案和思路：因为含有“”，那么在到了mid的时候找一个和他最近的部位“”来代替他。这次是往左找到头了才开始往右找。优化的话两边都开始同时找。


    public int findString(String[] str, int n, String x) {
        // write code here
        if (null == str || n == 0) {
            return 0;
        }
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int keep = mid;
            while (mid >= left && str[mid].equals("")) {
                mid--;
            }
            if (mid < left) {
                mid = keep;
                while (mid <= right && str[mid].equals("")) {
                    mid++;
                    if (mid > right) {
                        return -1;
                    }
                }
            }
            if (str[mid].equals(x)) {
                return mid;
            }
            if (str[mid].compareTo(x) > 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
at
Labels: , ,
Subscribe to: Posts (Atom)

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts