LintCode(12-22)




(12) – Min Stack

一个栈维护最小值,另一个栈存数据

为什么最小值同步插入可行,因为栈的pop只能从栈顶开始,所以:

1.栈顶元素最小,minValue栈顶也是该元素
2.栈顶元素不是最小,minValue中没有该元素

public class MinStack {

    private Stack<Integer> data;
    private Stack<Integer> minValue;

    public MinStack() {
        // do intialization if necessary
        data=new Stack<>();
        minValue=new Stack<>();
        minValue.push(0x3f3f3f3f);
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    public void push(int number) {
        // write your code here
        data.push(number);
        if(number<=minValue.peek()) minValue.push(number);
    }

    /*
     * @return: An integer
     */
    public int pop() {
        // write your code here
        if(data.peek().equals(minValue.peek())) minValue.pop();
        return data.pop();
    }

    /*
     * @return: An integer
     */
    public int min() {
        // write your code here
        return minValue.peek();
    }
}

(13) – Implement strStr()

KMP模板,但是实际面试的时候不需要使用KMP,暴力O(N^2)即可

public class Solution {

    private final int maxn=10000+7;
    private int Next[];

    private void getNext(String S,String T){
        int k=-1,len=T.length();
        int j=0;
        Next[0]=-1;
        while(j<len){
            if(k==-1 || T.charAt(j)==T.charAt(k)) Next[++j]=++k;
            else k=Next[k];
        }
    }

    private int KMP_index(String S,String T){
        int i=0,j=0,slen=S.length(),tlen=T.length();
        getNext(S,T);
        while(i<slen && j<tlen){
            if(j==-1 || S.charAt(i)==T.charAt(j)){
                i++;
                j++;
            }else j=Next[j];
        }
        if(j==tlen) return i-tlen;
        else return -1;
    }

    /**
     * @param source: 
     * @param target: 
     * @return: return the index
     */
    public int strStr(String source, String target) {
        // Write your code here
        Next=new int[maxn];
        return KMP_index(source,target);

    }
}

(14) – First Position of Target

C++偷懒用二分

class Solution {
public:
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    int binarySearch(vector<int> &nums, int target) {
        // write your code here
        int index=lower_bound(nums.begin(),nums.end(),target)-nums.begin();
        if(nums[index]!=target)
            return -1;
        return index;
    }
};

Java 实现二分

public class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        // write your code here

        int mid=0,l=0,r=nums.length;
        while(l<=r){
            mid=((l+r)>>1);
            if(nums[mid]<target)
                l=mid+1;
            else r=mid-1;
        }
        if(nums[l]==target) return l;
        else return -1;
    }
}

(15) – Permutations

dfs即可

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        helper(nums, used, new LinkedList<>(), res);
        return res;
    }
  private void helper(int[] nums, boolean[] used, List<Integer> tmp, List<List<Integer>> res) {
    if (tmp.size() == nums.length) {
      res.add(new LinkedList<>(tmp));
      return;
    }
    for (int i = 0; i < nums.length; i++) {
      if (used[i]) {
        continue;
      }
      used[i] = true;
      tmp.add(nums[i]);
      helper(nums, used, tmp, res);
      used[i] = false;
      tmp.remove(tmp.size()-1);
    }
    return;
  }
}

(16) – Permutations II

用set集直接映射即可

public class Solution {

    private Set<String> reg;

    private void helper(int[] nums, boolean[] used, List<Integer> tmp, List<List<Integer>> res,StringBuilder str){
        if (tmp.size() == nums.length) {
            String ts=str.toString();
            if(reg.contains(ts)){
                return;
            }
            reg.add(ts);
            res.add(new LinkedList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            tmp.add(nums[i]);
            String nw=String.valueOf(nums[i]);
            str.append(nw);
            helper(nums, used, tmp, res,str);
            used[i] = false;
            tmp.remove(tmp.size()-1);
            str.delete(str.length()-nw.length(),str.length());
        }
        return;
    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        reg=new HashSet<String>();
        helper(nums, used, new LinkedList<>(), res,new StringBuilder());
        return res;
    }
};

(17) – Subsets

方法:

[[]]]
[[1]]
[[2],[1,2]]
[[3],[1,3],[2,3],[1,2,3]]
合起来就好了

一个小语法

java中的List是引用传递,List套List给出来的是引用对象,所以必须new一个新的ArrayList才行.

public class Solution {
    /**
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        int len=nums.length;
        Arrays.sort(nums);
        List<Integer> init=new ArrayList();
        List<List<Integer>> ans = new LinkedList<>();
        ans.add(init);
        for(int i=0;i<len;++i){
            int size=ans.size();
            for(int j=0;j<size;++j){
                List<Integer> reg=new ArrayList<Integer>(ans.get(j));
                reg.add(nums[i]);
                ans.add(reg);
            }
        }
        return ans;
    }
}

(18) – Subsets II

还是用set映射

import java.util.*;

public class Topic_18 {
    private static Set<String> dict;

    /**
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        // write your code here
        dict=new HashSet<String>();
        int len=nums.length;
        Arrays.sort(nums);
        List<Integer> init=new ArrayList();
        List<List<Integer>> ans = new LinkedList<>();
        ans.add(init);
        for(int i=0;i<len;++i){
            int size=ans.size();
            for(int j=0;j<size;++j){
                StringBuilder str=new StringBuilder();
                List<Integer> reg=new ArrayList<Integer>(ans.get(j));
                reg.add(nums[i]);
                for(int k=0;k<reg.size();++k){
                    str.append(String.valueOf(reg.get(k)));
                }
                String n=str.toString();
                if(!dict.contains(n)){
                    ans.add(reg);
                    dict.add(n);
                }
            }
        }
        return ans;
    }
    public static void main(String[] args){
        int[] nums={1,2};
        List<List<Integer>> ans=subsetsWithDup(nums);
        System.out.println(ans.size());
    }

}

发表评论