q165 比较版本号

/**
 * Compare two version numbers version1 and version2.
 * If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.
 *
 * You may assume that the version strings are non-empty and contain only digits and the . character.
 *
 * The . character does not represent a decimal point and is used to separate number sequences.
 *
 * For instance, 2.5 is not "two and a half" or "half way to version three",
 * it is the fifth second-level revision of the second first-level revision.
 *
 * You may assume the default revision number for each level of a version number to be 0.
 * For example, version number 3.4 has a revision number of 3 and 4
 * for its first and second level revision number.
 * Its third and fourth level revision number are both 0.
 */
public class CompareVersionNum {

    public static void main(String[] args) {
        String test = "0001";
        //System.out.println(Integer.valueOf(test));
        String v1 = "0.1";
        String v2 = "1.1";
        System.out.println(compareVersion(v1, v2));
    }


    /**
     * 自己思路:
     * 两个字符串都使用'.'分开形成两个String字符串数组
     * 然后一组一组数字进行比较，如果其中一个长度不够长的话就用0进行比较
     * @param version1
     * @param version2
     * @return
     */
    public static int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int len = Math.max(v1.length, v2.length);
        System.out.println(len);
        for (int i=0; i<len;i++){
            int v1Curr = v1.length>i ? Integer.valueOf(v1[i]):0;
            int v2Curr = v2.length>i ? Integer.valueOf(v2[i]):0;
            System.out.println("v1Curr: "+ v1Curr +" v2Curr: "+v2Curr);
            if (v1Curr<v2Curr){
                return -1;
            }else if (v1Curr>v2Curr){
                return 1;
            }

        }

        return 0;

    }
}

q315计算右侧比当前元素小的元素个数

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * You are given an integer array nums and you have to return a new counts array.
 * The counts array has the property where counts[i] is the number of smaller elements
 * to the right of nums[i].
 *
 * Example 1:
 * Input: nums = [5,2,6,1]
 * Output: [2,1,1,0]
 * Explanation:
 * To the right of 5 there are 2 smaller elements (2 and 1).
 * To the right of 2 there is only 1 smaller element (1).
 * To the right of 6 there is 1 smaller element (1).
 * To the right of 1 there is 0 smaller element.
 */
public class CountOfSmallerNumAfterSelf {

    /**
     * 最简单的做法: 暴力求解 时间复杂度 O(n^2)
     * @param nums
     * @return
     */
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i=0;i<nums.length-1;i++){
            int count = 0;
            int label = nums[i];
            for (int j=i+1;j<nums.length;j++){
                if (nums[j]<label){
                    count++;
                }
            }
            res.add(count);
        }
        res.add(0);
        return res;
    }

    /**
     * 使用binarySearch方式
     * 从后往前遍历 找到在有序的list之中新元素的位置 从而推导出来有多少个元素比它小
     * @param nums
     * @return
     */
    public List<Integer> countSmallerTwo(int[] nums){
        List<Integer> res = new ArrayList<>();
        List<Integer> sortedList = new ArrayList<>();

        if (nums == null || nums.length == 0){
            return res;
        }

        res.add(0);
        sortedList.add(nums[nums.length-1]);

        for (int i=nums.length-2; i>=0; i--){
            int index = Collections.binarySearch(sortedList, nums[i]);

            if (index >= 0){
                while (index>0 && sortedList.get(index-1) == nums[i]){
                    index--;
                }
            }else {
                index = -1-index;
            }

            res.add(0,index);
            sortedList.add(index, nums[i]);
        }

        return res;


    }
}

q341 扁平化嵌套列表迭代器

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

/**
 * Given a nested list of integers, implement an iterator to flatten it.
 *
 * Each element is either an integer, or a list -- whose elements may also be integers or other lists.
 */
public class NestedIterator implements Iterator<Integer> {

    Stack<Integer> res;

    public NestedIterator(List<NestedInteger> nestedList){
        Stack<NestedInteger> stack = new Stack<>();
        add(nestedList,stack);
        res = new Stack<>();
        while (!stack.isEmpty()){
            res.add(stack.pop().getInteger());
        }
    }

    public void add(List<NestedInteger> nestedList, Stack<NestedInteger> stack){
        for (NestedInteger i:nestedList){
            if (i.isInteger()){
                stack.add(i);
            }else {
                add(i.getList(),stack);
            }
        }
    }


    @Override
    public boolean hasNext() {
        return !res.isEmpty();
    }

    @Override
    public Integer next() {
        if (hasNext()){
            return res.pop();
        }
        return null;
    }

    public class NestedInteger {

        // @return true if this NestedInteger holds a single integer, rather than a nested list.
        public boolean isInteger(){
            return false;
        }

        // @return the single integer that this NestedInteger holds, if it holds a single integer
        // Return null if this NestedInteger holds a nested list
        public Integer getInteger(){
            return 0;
        }

        // @return the nested list that this NestedInteger holds, if it holds a nested list
        // Return null if this NestedInteger holds a single integer
        public List<NestedInteger> getList(){
            return new ArrayList<>();
        }
    }
}

q394 字符串解码

import java.util.Stack;

/**
 * Given an encoded string, return its decoded string.
 *
 * The encoding rule is: k[encoded_string], 
 * where the encoded_string inside the square brackets is being repeated exactly k times. 
 * Note that k is guaranteed to be a positive integer.
 *
 * You may assume that the input string is always valid; 
 * No extra white spaces, square brackets are well-formed, etc.
 *
 * Furthermore, you may assume that the original data does not 
 * contain any digits and that digits are only for those repeat numbers, 
 * k. For example, there won't be input like 3a or 2[4].
 */
public class DecodeString {

    public static void main(String[] args) {
        String test = "3[a2[c]]";
        String test2 = "3[ab2[cd]]";
        String test3 = "100[leetcode]";
        System.out.println(decodeString(test3));
    }

    /**
     * 使用两个栈，一个存储频率，一个存储括号和字符，每个左括号对应一个频率
     * @param s
     * @return
     */
    public static String decodeString(String s) {
        Stack<Integer> frequency = new Stack<>();
        Stack<String> alphabet = new Stack<>();


        //temp存储的在遇到上一个括号之内遍历需要形成的String
        StringBuilder temp = new StringBuilder();
        StringBuilder currentStr = new StringBuilder();

        for (int i=0;i<s.length();i++){
            if (Character.isDigit(s.charAt(i))){
                int currNum = 0;
                while (Character.isDigit(s.charAt(i))){
                    currNum = currNum*10 + s.charAt(i)-'0';
                    i++;
                }
                i--;
                frequency.add(currNum);
            } else if (s.charAt(i)==']'){
                while (!alphabet.peek().equals("[")){
                    temp.append(alphabet.pop());
                }

                alphabet.pop();
                int currFrenquency = frequency.pop();

                for (int j=0;j<currFrenquency;j++){
                    currentStr.append(temp.toString());
                }

                alphabet.push(currentStr.toString());
                currentStr.setLength(0);
                temp.setLength(0);
            }else {
                alphabet.add(String.valueOf(s.charAt(i)));
            }
        }

        StringBuilder res = new StringBuilder();
        while (!alphabet.isEmpty()){
            res.append(alphabet.pop());
        }

        return res.reverse().toString();
    }

}