剑指Offer_55

发表于 2017-12-05 | 分类于剑指Offer

题目

一个链表中包含环，请找出该链表的环的入口结点。

解题思路

参考博客： 点击跳转

解法一：

快慢指针 fast 走2步和 slow 走1步

情况一： 快指针比慢指针只多走了一个环，如下图所示

点击加载

a. 首先找到快慢指针在环中的相遇点

b. 设慢指针走了x步，且环中有n个节点，那么快指针多走一圈的情况下：
2x = n + x，即 n = x

c. 可以看出slow实际走了一个环的步数，再让fast指向链表头部，slow位置不变。

假设链表开头到环接口的距离是y，如下图所示，那么x-y表示slow指针走过的除链表开头y在环中走过的距离，那么slow再走y步，此时fast结点与slow结点相遇，fast == slow ，x-y+y=x = n，即此时slow指向环的入口。

最后，slow在走y步就到环的入口了 x -> n

点击加载

情况二： 当 fast 比 slow 多走n个环

fast比slow多走r圈有2x=rn+x; x=rn

同情况一可得： fast == slow时，x-y+y=x = rn，即此时slow指向环的入口。

点击加载

/*
 public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode fast = pHead;
        ListNode slow = pHead;
        
        // while循环条件 有环
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            
            if(fast == slow){
                fast = pHead;
                while(fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}

解法二：

使用HashSet来判断重复值

import java.util.HashSet;
/*
 public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        HashSet<ListNode> hashSet = new HashSet<>();
        while(pHead != null){
            if(hashSet.contains(pHead)){
                return pHead;
            }
            hashSet.add(pHead);
            pHead = pHead.next;
        }
        return pHead;
    }
}

剑指Offer_54

发表于 2017-12-05 | 分类于剑指Offer

题目

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

输入描述

1	如果当前字符流没有存在出现一次的字符，返回#字符。

解题思路

a. 构造一个int数组，记录每个出现的次数

b. 构造一个StringBuffer，记录每个字符的出现顺序

c. 在StringBuffer提取字符在int数组找出现一次的字符

public class Solution {
    //Insert one char from stringstream
    int []table = new int[256];
    StringBuffer sb = new StringBuffer();
    
    public void Insert(char ch)
    {
        table[ch]++;
        sb.append(ch);
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
    	char []chars = sb.toString().toCharArray();
        for(char c: chars){
            if(table[c] == 1){
                return c;
            }
        }
        return '#';
    }
}

剑指Offer_53

发表于 2017-12-05 | 分类于剑指Offer

题目

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。
但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

解题思路

这道题的数值标准和下图有点不同，但判断的思路是一样的。

点击加载

public class Solution {
    private boolean isDigit(char c){
        return c <= '9' && c >= '0';
    }
    private boolean isFrom1To9(char c){
        return c <= '9' && c >= '1';
    }
    
    public boolean isNumeric(char[] str) {
        if(str == null || str.length == 0){
            return false;
        }
        int length = str.length;
        int i = 0;
        
        if(i < length && (str[i] == '+' || str[i] == '-')){
            ++i;
        }
        
        if(i < length && str[i] == '0'){
            ++i;
        }
        else{
            //在测例中，-.123 是合法的...
            if(i < length && !isFrom1To9(str[i]) && str[i] != '.'){
                return false;
            }
            for(++i; i < length && isDigit(str[i]); ++i){}
        }
        
        // . 点之后必须有数字 
        if(i < length && str[i] == '.'){
            ++i;
            if(i < length && !isDigit(str[i])){
                return false;
            }
            for(++i; i < length && isDigit(str[i]); ++i){}
        }
        
        // e 或 E 之后必须有数字
        if(i < length && (str[i] == 'e' || str[i] == 'E')){
            ++i;
            if(i < length && (str[i] == '+' || str[i] == '-')){
                ++i;
            }
            if(i < length && !isDigit(str[i])){
                return false;
            }
            //12e 会导致 i = length+1
            for(++i; i < length && isDigit(str[i]); ++i){}
        }
        if(i == length){
            return true;
        }
        return false;
    }
}

剑指Offer_52

发表于 2017-12-05 | 分类于剑指Offer

题目

请实现一个函数用来匹配包括 ‘ .’ 和‘ ’的正则表达式。模式中的字符 ‘ . ’表示任意一个字符，而 ‘ ’ 表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab ac a”匹配，但是与”aa.a”和”ab * a”均不匹配。

解题思路


public class Solution {
    public boolean match(char[] str, char[] pattern) {
    if (str == null || pattern == null) {
        return false;
    }
    int strIndex = 0;
    int patternIndex = 0;
    return matchCore(str, strIndex, pattern, patternIndex);
}
  
public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
    //有效性检验：str到尾，pattern到尾，匹配成功
    if (strIndex == str.length && patternIndex == pattern.length) {
        return true;
    }
    //pattern先到尾，匹配失败
    if (strIndex != str.length && patternIndex == pattern.length) {
        return false;
    }
    //模式第2个是*，且字符串第1个跟模式第1个匹配,分3种匹配模式；如不匹配，模式后移2位
    if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
            return matchCore(str, strIndex, pattern, patternIndex + 2)//模式后移2，视为x*匹配0个字符
                    || matchCore(str, strIndex + 1, pattern, patternIndex + 2)//视为模式匹配1个字符
                    || matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个，再匹配str中的下一个
        } else {
            return matchCore(str, strIndex, pattern, patternIndex + 2);
        }
    }
    //模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
    if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) {
        return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
    }
    return false;
    }
}

剑指Offer_51

发表于 2017-12-05 | 分类于剑指Offer

题目

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0] x A[1]x … x A[i-1] x A[i+1] x … x A[n-1]。不能使用除法。

解题思路

举个例子

B0：X A1 A2 A3 A4
B1：A0 X A2 A3 A4
B2：A0 A1 X A3 A4
B3：A0 A1 A2 X A4
B4：A0 A1 A2 A3 X

两趟循环，第一趟处理对角线的左下角，第二趟处理对角线的右上角。

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
    	int []B = new int[A.length];
        
        B[0] = 1;
        for(int i = 1; i < A.length; ++i){
            B[i] = A[i-1] * B[i-1];
        }
        
        int temp = 1;
        for(int i = A.length-1; i >= 0; --i){
            B[i] *= temp;
            temp *= A[i];
        }
        
        return B;
    }
}

剑指Offer_50

发表于 2017-12-05

题目

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

解题思路

numbers数组中的元素为0到length，建立boolean数组对应其元素

一旦检测到dup[numbers[i]] == true，便是第一个重复的元素

public class Solution {
    public boolean duplicate(int numbers[],int length,int [] duplication) {
    	boolean []dup = new boolean[length];
        for(int i = 0; i < length; ++i){
            if(dup[numbers[i]]){
                duplication[0] = numbers[i];
                return true;
            }
            dup[numbers[i]] = true;
        }
        return false;
    }
}

剑指Offer_49

发表于 2017-12-05 | 分类于剑指Offer

题目

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0

输入描述
输入一个字符串,包括数字字母符号,可以为空

输出描述
如果是合法的数值表达则返回该数字，否则返回0

示例输入

1 2	+2147483647 1a33

示例输出

1 2	2147483647 0

解题思路

public class Solution {
    public int StrToInt(String str) {
        int ans = 0;
        boolean flag = false;
        char []chars = str.toCharArray();
        
        for(int i = 0; i < chars.length; ++i){
            if(i == 0 && (chars[i] == '+' || chars[i] == '-')){
                if(chars[i] == '-'){
                    flag = true;
                }
                continue;
            }
            if(chars[i] <= '9' && chars[i] >= '0'){
                ans = ans * 10 + (chars[i] - '0');
            }
            else{
                return 0;
            }
        }
        return flag ? -ans : ans;
    }
}

剑指Offer_48

发表于 2017-12-05 | 分类于剑指Offer

题目

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

解题思路

来自牛客网，点击跳转到链接

a. 按位与是查看两个数哪些二进制位都为1，这些都是进位位，结果需左移一位，表示进位后的结果
b. 异或是查看两个数哪些二进制位只有一个为1，这些是非进位位，可以直接加、减，结果表示非进位位进行加操作后的结果
c. n1&n2是查看有没有进位位了，如果有，需要重复a、b；如果没有，保留n1、n2上二进制为1的部分，用或将之合为一个数，即为最后结果

public class Solution {
    public int Add(int num1,int num2) {
        while(num2 != 0){
            int temp = num1 ^ num2;
            num2 = (num1 & num2) << 1;
            num1 = temp;
        }
        return num1;
    }
}

剑指Offer_47

发表于 2017-12-05 | 分类于剑指Offer

题目

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

解题思路

不能循环就递归实现

不能if就条件判断使用 && 实现

public class Solution {
    public int Sum_Solution(int n) {
        int res = n;
        //这里需要返回个boolean值，不然编译不通过
        //当res == 0时，就会退出递归循环了
        boolean x = (res > 0) && ((res += Sum_Solution(n - 1)) > 0);
        return res;
    }
}

剑指Offer_46

发表于 2017-12-05 | 分类于剑指Offer

题目

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

解题思路

两个指针：

kidNumber：指向孩子号码

step：指向round，每过一个人加1

a. 当kidNumber = = n 时，kidNumber赋予0，重头开始

b. 当isOut[kidNumber]为true时，孩子已经出局，指向下个孩子

c. 当step = = round 时，从0开始数下一个孩子

d. 循环退出条件，孩子全数完了，并且kidNumber保存着最后一个孩子的号码

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        int kids = n;
        int kidNumber = -1;
        int round = m;
        int step = 0;
        boolean []isOut = new boolean[n];
        
        while(kids > 0){
            kidNumber++;
            if(kidNumber == n){
                kidNumber = 0;
            }
            if(isOut[kidNumber]){
                continue;
            }
            ++step;
            if(step == round){
                isOut[kidNumber] = true;
                step = 0;
                kids--;
            }
        }
        return kidNumber;
    }
}