头像

木木灬

山东大学


访客:29135

离线:4个月前



木木灬
2019-05-10 08:20

算法1

(递归)
  1. 递归结束条件,如果两个字符串都到了最后,返回true
  2. 如果其中一个结束,则匹配不成功,返回false
  3. 如果当前两个位置的值相同或p的值为’.’,则递归下一位置
  4. 如果下一位置为‘*’,当前位置两个字符创相同或者p的字符串为‘.’,则分类讨论,因为‘※’可以代表0,1,多次,所以可以s不动,p向后移动两位;或者s向后一位;或者同时移动,s一位,p两位
  5. 如果前面的都没成功,则匹配失败,返回false;

Java 代码

class Solution {
    public boolean isMatch(String s, String p) {
        if(s==null||p==null)
            return false;
        if((s.length()!=0&&p.length()==0))
            return false;        
        char[] str = s.toCharArray();
        char[] pat = p.toCharArray();

        return matchCore(str,0,pat,0);
    }

    private boolean matchCore(char[] str, int indexOfStr, char[] pattern, int indexOfPattern) {
        if (indexOfStr == str.length && indexOfPattern == pattern.length){
            return true;}
        if (indexOfStr < str.length && indexOfPattern == pattern.length)
            return false;
        if (indexOfPattern + 1 < pattern.length && pattern[indexOfPattern + 1] == '*') {
            if ((indexOfStr < str.length && pattern[indexOfPattern] == '.')
                    || (indexOfStr < str.length && pattern[indexOfPattern] == str[indexOfStr])) {
                return matchCore(str, indexOfStr, pattern, indexOfPattern + 2)
                        || matchCore(str, indexOfStr + 1, pattern, indexOfPattern)
                        || matchCore(str, indexOfStr + 1, pattern, indexOfPattern + 2);
            } else {
                return matchCore(str, indexOfStr, pattern, indexOfPattern + 2);
            }
        }
        if (indexOfStr < str.length && (pattern[indexOfPattern] == str[indexOfStr] || (pattern[indexOfPattern] == '.'))){
            return matchCore(str, indexOfStr + 1, pattern, indexOfPattern + 1);

        }
        return false;
    }
}



木木灬
2019-05-10 07:37

算法1

(递归)

见注释

Java 代码

class Solution {
    private static final int g_maxValue = 6;
    //基于递归求骰子点数,时间效率不高
    public int[] numberOfDice(int number) {
        int[] nums = new int[5*number+1];
        if(number<1) return null;
        int maxSum = number*g_maxValue;
        int[] pProbabilities = new int[maxSum-number+1];
        //初始化,开始统计之前都为0次
        for(int i=number;i<=maxSum;i++){
            pProbabilities[i-number] = 0;
        }
        //probability(number,pProbabilities);这个函数计算n~6n每种情况出现的次数
        probability(number,pProbabilities);
        for(int i=number;i<=maxSum;i++){
            int ratio = pProbabilities[i-number];
            // System.out.println("i: "+i+" ratio: "+ratio);
            nums[i-number] = ratio;
        }
        return nums;
    }
    public static void probability(int number,int[] pProbabilities){
        for(int i=1;i<=g_maxValue;i++){//从第一个骰子开始
            probability(number,number,i,pProbabilities);
        }
    }
    //总共original个骰子,当前第 current个骰子,当前的和,贯穿始终的数组
    public static void probability(int original,int current,int sum,int[] pProbabilities){
        if(current==1){
            pProbabilities[sum-original]++;
        }else{
            for(int i=1;i<=g_maxValue;i++){
                probability(original,current-1,sum+i,pProbabilities);
            }
        }
    }
}



木木灬
2019-05-10 07:27

算法1

  1. 先对数组排序
  2. 然后求出0的数量
  3. 然后求出空位的数量
  4. 根据0的数量和空位的数量,判断是否是顺子
  5. 若是对子,直接返回false;

Java 代码

class Solution {
    public boolean isContinuous(int [] nums) {
        int len = nums.length;
        if(nums==null||nums.length<1)
        return false;
        Arrays.sort(nums);

        int zero = 0;
        for(int i = 0;i<len&&nums[i]==0;i++){
            zero++;
        }

        int small = zero;
        int big = zero+1;
        int gap = 0;

        while(big<len){
            if(nums[small]==nums[big])
                return false;

            gap+=nums[big]-nums[small]-1;
            small = big;
            big++;
        }
        return zero>=gap?true:false;
    }
}



木木灬
2019-05-09 12:18

算法1

用一个数组记录A数组中每个位置前面值的乘积
用第二个数组记录A数组中每个位置后面的乘积
然后把每个位置前后乘积相乘即可

Java 代码

class Solution {
    public int[] multiply(int[] A) {
        if(A.length<=0)
            return A;
        int len = A.length;
        int[] B = new int[len];
        B[0]=1;
        for(int i =1;i<len;i++){
            B[i] = B[i-1]*A[i-1];
        }

        int tmp = 1;
        for(int j=len-2;j>=0;j--){
            tmp *= A[j+1];
            B[j] *= tmp;
        }

        return B;
    }
}



木木灬
2019-05-09 07:30

算法1

(后续遍历,递归) $O(n)$

后序遍历二叉树,如果遍历到的当前节点为cur。因为是后序遍历,所以先处理cur的两棵子树。假设cur左子树时返回left,右子树返回right
1. 如果cur为null或p,q,返回cur
2. 如果left和right都为空,说明cur左右子树都没有p,q,返回null
3. 如果都不为空,说明左子树上发现过p或q,右子树同理,并在cur相遇,则返回cur
4. 如果left和right其中一个是null,另一个不为空,直接返回不为空的那个节点即是公共祖先。

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left!=null&&right!=null){
            return root;
        }

        return left!=null?left:right;
    }
}



木木灬
2019-05-09 06:57

算法1

(环形链表) $O(n)$

经典的解法, 用环形链表模拟圆圈。

创建一个总共有 n 个结点的环形链表,然后每次在这个链表中删除第 m 个结点。

Java 代码

class Solution {
    public int lastRemaining(int n, int m) {
    if (n < 1 || m < 1) {
        return -1;
    }
    List<Integer> list = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        list.add(i);
    }
    // 要删除元素的位置
    int idx = 0;
    // 开始计数的位置
    int start = 0;
    while (list.size() > 1) {
        // 只要移动m-1次就可以移动到下一个要删除的元素上
        for (int i = 1; i < m; i++) {
            idx = (idx + 1) % list.size(); // 【A】
        }
        list.remove(idx);
        // 确保idx指向每一轮的第一个位置
    }
    return list.get(0);


    }
}

算法2

剑指offer的分析法

Java 代码

public static int lastRemaining2(int n, int m) {
    if (n < 1 || m < 1) {
        return -1;
    }
    int last = 0;
    for (int i = 2; i <=n ; i++) {
        last = (last + m)%i;
    }
    return last;
}



木木灬
2019-05-07 08:56

算法1

各种情况的检查 $O(n)$
  1. 首先去除空格
  2. 然后判断非法字符串,如空或长度为0
  3. 然后判断是否有符号位
  4. 然后判断是否是在‘0’-‘9’
  5. 然后求的当前的值为多少,正的直接加,负的应该加标志位去减掉
  6. 然后判断是否溢出,如果当前的得到的值比之前的值小,说明正的变成负的,溢出了,反之亦然
  7. 最后输出

Java 代码

class Solution {
    public int strToInt(String str) {

        str = str.trim();
        int result = 0;
        int symbol = 1;
        boolean isValid = false;
        char[] array = str.toCharArray();
        if (array == null || array.length <= 0) {
            return 0;
        } 
        if (array[0] == '-' ) {
            symbol = -1;
        }
        for(int i =  (array[0] == '+' || array[0] == '-') ? 1 : 0; i < array.length; i++){
            if (!('0' <= array[i] && array[i] <= '9') ){
                isValid = true;
                return result * symbol;
            }
             int result1 = result * 10 + symbol * (array[i] - '0');
             if(symbol==1){
                 if(result1>result){
                     result = result1;
                 }else{
                    return Integer.MAX_VALUE;
                 }
             }else if(symbol==-1){
                 if(result1<result){
                     result = result1;
                 }else{
                    return Integer.MIN_VALUE;
                 }
             }
        }
        return result ;
    }
}


算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析:blablabla

C++ 代码

blablabla



木木灬
2019-05-07 08:10

算法1

$O(n)$

用两个值来记录当前最小的买入金额和最大的利润即可
1. 如果当前的值小于最小值,将其设为最小值
2. 求出当前值与最小值的差值
3. 如果利润大于最大利润,更新最大利润

Java 代码

class Solution {
    public int maxDiff(int[] nums) {
        if(nums==null||nums.length==0)
            return 0;
        int maxdiff = 0;
        int min = nums[0];
        for(int i = 1;i<nums.length;i++){
            if(nums[i]<min) min = nums[i];
            int diff = nums[i]-min;
            if(diff>maxdiff)maxdiff = diff;
        }
        return maxdiff;
    }
}



木木灬
2019-05-07 07:56

算法1

(队列) $O(n)$
  1. 先判断队列是否为空,如果为空,将当前的下标放进队列作为最大值;
  2. start用来检测当前队列中的最大值是否已经离开滑动窗口,所以一开始start=i-k+1,如果start大于队列中最大值的下标,则弹出最大值
  3. 然后判断队列是否为空,并且从队列尾与当前值比较,来更新队列中的最大值;
  4. 当start。=0时,说明滑动窗口已经完全进入数组,可以开始记录最大值了

Java 代码

class Solution {
    public int[] maxInWindows(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];
        if(k==0)return res;
        int start;
        int index = 0;
        ArrayDeque<Integer> max = new ArrayDeque<>();
        for(int i=0;i<nums.length;i++){
            start = i-k+1;
            if(max.isEmpty())
                max.add(i);
            else if(start>max.peekFirst())
                max.pollFirst();

            while((!max.isEmpty())&&nums[max.peekLast()]<=nums[i])
                max.pollLast();
            max.add(i);
            if(start>=0)
                res[index++] = nums[max.peekFirst()];
        }
        return res;
    }
}



木木灬
2019-05-06 11:10

算法1

(异或) $O(n)$
  1. 因为1+0和0+1都是1,1+1和0+0都是0,和异或一样

  2. 不同的是1+1有进位,所以,用&操作,来求进位

  3. 得到是否有进位之后,将进位向左边移1位与之前异或求的的值进行异或

  4. 循环直至没有进位

Java 代码

class Solution {
    public int add(int num1, int num2) {
        int sum = 0,carry = 0;

        do{
            sum = num1^num2;
            carry = (num1 & num2)<<1;
            num1 = sum;
            num2 = carry;
        }while(num2!=0);

        return num1;
    }
}