剑指Offer_45

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

题目

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

解题思路

抽取五张牌，构成顺子的的条件

a. 不包含大小鬼其中ABCDE，E-A == 4

b. 包含大小鬼，其中ABCXE，E-A <= 4

c. 一旦抽取重复的牌，就不可能是顺子

也就是，抽取的五张牌能够构成顺子，必须max-min <= 4

public class Solution {
    public boolean isContinuous(int [] numbers) {
		if(numbers == null || numbers.length != 5){
            return false;
        }
        
        //检测1-13号扑克牌是否重复
        //鬼牌可以重复
        boolean []dupCard = new boolean[14];
        int max = -1;
        int min = 14;
        for(int i = 0; i < numbers.length; ++i){
            //鬼牌直接跳过
            if(numbers[i] == 0){
                continue;
            }
            
            if(dupCard[numbers[i]]){
                return false;
            }
            
            if(numbers[i] < min){
                min = numbers[i];
            }
            if(numbers[i] > max){
                max = numbers[i];
            }
            //标记号码已被抽过
            dupCard[numbers[i]] = true;
        }
        if(max - min <= 4){
            return true;
        }
        return false;
    }
}

剑指Offer_44

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

题目

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

解题思路

解法一：

一个一个单词进行处理

public class Solution {
    public String ReverseSentence(String str) {
        if(str == null){
            return null;
        } 
        if(str.trim().equals("")){
            return str;
        }
        
        StringBuffer sb = new StringBuffer();
        String []strings = str.split(" ");
        for(int i = strings.length-1; i > 0; --i){
            sb.append(strings[i]);
            sb.append(" ");
        }
        //最后一个不加空格的string
        sb.append(strings[0]);
        return sb.toString();
    }
}

解法二：

一个一个字符处理

public class Solution {
    private void reverseCharArray(char []chars, int lo, int hi){
        while(lo < hi){
            char t = chars[lo];
            chars[lo] = chars[hi];
            chars[hi] = t;
            ++lo;
            --hi;
        }
    }
    
    public String ReverseSentence(String str) {
        char []chars = str.toCharArray();
        reverseCharArray(chars, 0, chars.length-1);
        int lo = 0, hi = 0;
        for(int i = 0; i < chars.length; ++i){
            if(chars[i] == ' '){
                hi = i-1;
                reverseCharArray(chars, lo, hi);
                lo = i+1;
            }
        }
        //收尾
        reverseCharArray(chars, lo, chars.length-1);
        
        return new String(chars);
    }
}

剑指Offer_43

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

题目

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

解题思路

解法一：

Java String API

public class Solution {
    public String LeftRotateString(String str,int n) {
        if(str == null || str.length() < n){
            return "";
        }
        
        int len = str.length();
        
        str += str;
        return str.substring(n, len + n);
    }
}

解法二：

举个例子：

利用 YX = （X的转置乘以Y的转置）的转置

a. abc 的转置为 cba
b. defg 的转置为 gfed
c. cbagfed的转置为 defgabc

输入

1	"abcdefg" 3

输出

"defgabc"

public class Solution {
    private void swapCharArray(char []chars, int lo, int hi){
        while(lo < hi){
            char t = chars[lo];
            chars[lo] = chars[hi];
            chars[hi] = t;
            ++lo;
            --hi;
        }
    }
    
    public String LeftRotateString(String str,int n) {
        if(str == null || str.length() < n){
            return "";
        }
        
        char []chars = str.toCharArray();
        swapCharArray(chars, 0, n-1);
        swapCharArray(chars, n, chars.length-1);
        swapCharArray(chars, 0, chars.length-1);
        
        return new String(chars);
    }
}

剑指Offer_42

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

题目

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

输入描述：

1	对应每个测试案例，输出两个数，小的先输出。

解题思路

二分搜索

输入两个数的乘积最小的，array递增数组中，两数距离越远，乘积越小

数组头尾两指针遍历，往中间逼近

a. 当 array[lo] + array[hi] < sum，值不够大，往中间逼近，++lo
b. 当 array[lo] + array[hi] > sum，值太大了，往中间逼近，- -hi

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        
        if(array == null || array.length < 2){
            return list;
        }
        int lo = 0;
        int hi = array.length - 1;
        while(lo < hi){
            if(array[lo] + array[hi] == sum){
                break;
            }
            else if(array[lo] + array[hi] < sum){
                ++lo;
            }
            else{
                --hi;
            }
        }
        if(lo == hi){
            return list;
        }
        
        list.add(array[lo]);
        list.add(array[hi]);
        
        return list;
    }
}

剑指Offer_41

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

题目

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述：

1	输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

解题思路

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> AA = new ArrayList<>();
        
        //序列至少2个数
        int lo = 1;
        int hi = 2;
        while(lo < hi){
            int curSum = ((lo + hi) * (hi - lo + 1)) / 2;
            if(curSum == sum){
                ArrayList<Integer> A = new ArrayList<>();
                for(int i = lo; i <= hi; ++i){
                    A.add(i);
                }
                AA.add(A);
                ++hi;
            }
            else if(curSum < sum){
              	//curSum太小，扩大范围
                ++hi;
            }
            else{
            	//curSum太大，缩小范围
                ++lo;
            }
        }
        return AA;
    }
}

剑指Offer_40

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

题目

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

解题思路

a. array数组中的全部元素进行异或得到 x
b. 因为两个不同的数，异或结果一定不为0，这里假设x为6(0000 0110)
c. findLastBit在x二进制中从右往左找到第一个为1的位，右移1次(posBit)可以得到
d. 再次遍历数组，当array[i]右移posBit并和1进行与运算，可以将两个不同的数分在不同的组
e. 与此同时，num1[0]和num2[0]的它同组的元素进行异或操作，得到最终结果

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    private int findLastBit(int x){
        int cnt = 0;
        while(x != 0){
            if((x & 1) == 1){
                break;
            }
            x >>= 1;
            ++cnt;
        }
        return cnt;
    }
    
    private boolean hasBit(int target, int posBit){
        return ((target >> posBit) & 1) == 1;
    }
    
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if(array == null || array.length < 2){
            return;
        }
        int x = 0;
        for(int i = 0; i < array.length; ++i){
            x ^= array[i];
        }
        
        int posBit = findLastBit(x);
        num1[0] = 0;
        num2[0] = 0;
        for(int i = 0; i < array.length; ++i){
            if(hasBit(array[i], posBit)){
                num1[0] ^= array[i];
            }
            else{
                num2[0] ^= array[i];
            }
        }
    }
}

剑指Offer_39

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

题目

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

解题思路

二叉树的后序遍历

public class Solution {
    private boolean isBalance = true;
    
    private int depth(TreeNode node){
        if(node == null){
            return 0;
        }
        int left = depth(node.left);
        int right = depth(node.right);
        if(Math.abs(left - right) > 1){
            isBalance = false;
        }
        
        //返回左右子树的父节点的深度
        return left > right ? left + 1 : right + 1;
    }
    
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null){
            return true;
        }
        depth(root);
        
        return isBalance;
    }
    
}

剑指Offer_38

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

题目

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

解题思路

解法一：

递归

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
    }
}

解法二：

非递归

import java.util.LinkedList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        int depth = 0;
        while(!list.isEmpty()){
            ++depth;
            
            //计算深度的时候，每次都要把队列里的节点（一层）全部抛出
            for(int i = 0; i < list.size(); ++i){
                TreeNode node = list.pollFirst();
                if(node.left != null){
                    list.add(node.left);
                }
                if(node.right != null){
                    list.add(node.right);
                }
            }
            
        }
        return depth;
    }
}

剑指Offer_37

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

题目

统计一个数字在排序数组中出现的次数。

解题思路

二分搜索法

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0){
            return 0;
        }
       
        int lo = 0;
        int hi = array.length-1;
        int mid = 0;
        int cnt = 0;
        
        while(lo <= hi){
            mid = (hi + lo) >> 1;
            if(array[mid] < k){
                lo = mid + 1;
            }
            else if(array[mid] > k){
                hi = mid - 1;
            }
            else{
                cnt = 1;
                break;
            }
        }
        
        if(cnt == 0){
            return 0;
        }
        
        int i = mid - 1;
        int j = mid + 1;
        while(i >= 0 && array[i--] == k) { ++cnt; }
        while(j < array.length && array[j++] == k) { ++cnt; }
        
        return cnt;
    }
}

剑指Offer_36

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

题目

输入两个链表，找出它们的第一个公共结点。

解题思路

一个简单的方法是：首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第二次遍历的时候，先在较长的节点上走若干步，接着同时在两个链表上遍历，找到的第一个相同的节点就是它们的公共的节点。该算法的时间复杂度为：O(m+n)。

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    private ListNode skipKNode(ListNode list, int k){
        while(k-- != 0){
            list = list.next;
        }
        return list;
    }
    
    private int length(ListNode pHead){
        int cnt = 0;
        while(pHead != null){
            ++cnt;
            pHead = pHead.next;
        }
        return cnt;
    }
    
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    	if(pHead1 == null || pHead2 == null){
            return null;
        }
        int len1 = length(pHead1);
        int len2 = length(pHead2);
        int k = Math.abs(len1-len2);
        
        if(len1 > len2){
        //java参数传值，当参数为对象时，传递是对象引用的拷贝
        //传递给skipKNode的参数是pHead1引用的一个拷贝
        //如果pHead1在skipKNode中发生改变，那么两个形参和实参会引用不同的地址值
            pHead1 = skipKNode(pHead1, k);
        }
        else{
            pHead2 = skipKNode(pHead2, k);
        }
        
        while(pHead1 != null && pHead2 != null){
            if(pHead1 == pHead2){
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }
}