G家电面悲剧总结

可以用这个方法，在stackflow上面看到。http://stackoverflow.com/questions/275944/how-do-i-count-the-number-of-occurrences-of-a-char-in-a-string/275979#275979
String s = "11222333";
int charCount = s.length() - s.replaceAll("2", "").length();

public class FindHowManyDuplicates {

        public static void main(String[] args) {
               
                String ss = "11222333";
                char cc = '1';
               
                binarySearch(ss, cc, 0, ss.length() - 1);
                System.out.println(count);
        }
       
        private static int count = 0;
       
        private static void binarySearch(String ss, char cc, int low, int high){
               
                if (low > high){
                        return;
                }
                else{
                        int mid = (low + high) / 2;
                        char c = ss.charAt(mid);
                       
                        if (c == cc)
                                count++;
                       
                        if (c >= cc)
                                binarySearch(ss, cc, low, mid - 1);
                       
                        if (c <= cc)
                                binarySearch(ss, cc, mid + 1, high);
                }
        }
       
}

testestest2008 发表于 2014-2-22 14:24
public class FindHowManyDuplicates {

        public static void main(String[] args) {

你这个复杂度是cc出现的频率， 不好。

北美农民 发表于 2014-2-23 03:49
你这个复杂度是cc出现的频率， 不好。

谢谢提醒，我换了一种实现方法。

public class FindHowManyDuplicates {

        public static void main(String[] args) {
               
                String ss = "112223334";
                char cc = '4';
                binarySearch2a(ss, cc);
        }
       
        private static void binarySearch2a(String ss, char cc){
               
                if (ss==null)
                        return;
               
                first = ss.length() + 1;
                last = -1;
               
                binarySearch2b(ss, cc, 0, ss.length() - 1);
               
                if (last == -1)
                        first = last = -1;
               
                System.out.println("count=" + (last - first + 1));
        }
       
        private static int first = -1, last = -1;
        private static void binarySearch2b(String ss, char cc, int low, int high){
               
                if (low > high){
                        return;
                }
                else{
                        int mid = (low + high) / 2;
                        char c = ss.charAt(mid);
                       
                        if (c == cc){
                                first = mid < first ? mid : first;
                                last = mid > last ? mid : last;
                                binarySearch2b(ss, cc, mid + 1, high);
                                binarySearch2b(ss, cc, low, mid -1);
                        }
                       
                        if (c < cc){
                                binarySearch2b(ss, cc, mid + 1, high);
                        }
                        else if (c > cc){
                                binarySearch2b(ss, cc, low, mid -1);
                        }
                       
                }
               
        }
       
}

北美农民 发表于 2014-2-23 03:49
你这个复杂度是cc出现的频率， 不好。

中午没吃饭。。。感觉自己实现得越来越复杂。。。不知道对不对，请指点。。。谢谢

testestest2008 发表于 2014-2-23 04:12
中午没吃饭。。。感觉自己实现得越来越复杂。。。不知道对不对，请指点。。。谢谢

感觉你还是没掌握好binary search，这题就是LeetCode Search for a Range，这类binary search类似binary insertion sort时找一个elem插入位置的折半

testestest2008 发表于 2014-2-22 15:12
中午没吃饭。。。感觉自己实现得越来越复杂。。。不知道对不对，请指点。。。谢谢

指点倒谈不上。 思想很简单，但要一遍也对也不容易。 我刚一遍也没写对。

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int result[] = new int[2];
        result[0] = binarySearch(A, target, true);
        result[1] = binarySearch(A, target, false);
        return result;
    }
   
    private int binarySearch(int[] a, int target, boolean mostLeft) {
        if (a == null) return -1;
        int start = 0;
        int end = a.length - 1;
        int mid;
        int result = -1;
        
        while (start <= end) {
            mid = start + (end - start) / 2;
            if (a[mid] > target) end = mid - 1;
            else if (a[mid] < target) start = mid + 1;
            else {
                result = mid;
                if (mostLeft) end = mid - 1;
                else start = mid + 1;
            }
        }
        
        return result;
    }
}

北美农民 发表于 2014-2-23 07:20
指点倒谈不上。 思想很简单，但要一遍也对也不容易。 我刚一遍也没写对。

public class Solution {

谢谢。理解了！我之前没能灵活运用binarySearch。
刚开始刷leetcode。。。慢慢向大家学习！

北美农民 发表于 2014-2-23 07:20
指点倒谈不上。 思想很简单，但要一遍也对也不容易。 我刚一遍也没写对。

public class Solution {

赞 “mid = start + (end - start) / 2;”

北美农民 发表于 2014-2-23 07:20
指点倒谈不上。 思想很简单，但要一遍也对也不容易。 我刚一遍也没写对。

public class Solution {

最后最好再根据返回的index范围判断下target是否存在