面经-算法

查找文本中出现最多的字符，和位置

map记录字符和数量

#pyhon版本
def wordcount(str):
    h =[]
    dict = {}
    max = 0
    maxkey = ""
    chars = str.split()
    for c in chars:
        if c not in dict:
            dict[c] = 1
            continue
        dict[c] = dict[c] + 1
        if max < dict[c]:
            max = dict[c]
            maxkey = c
    for index, c in enumerate(chars):
        if c == maxkey:
            h.append(index)
    print(h)
    print(dict)
    print(maxkey)

private static void findMostStr(String s) {
    HashMap<String, Integer> map = new HashMap<>();
    ArrayList<Integer> localList = new ArrayList<>();
    String[] ss = s.split(" ");
    int max = 0;
    String maxKey = null;
    for (String str : ss) {
        if (!map.containsKey(str)){
            map.put(str, 0);
            continue;
        }
        map.put(str, map.get(str)+1);
        if (max < map.get(str)) {
            max = map.get(str);
            maxKey = str;
        }
    }
    for(int i = 0; i < ss.length; i++) {
        if (ss[i].equals(maxKey)) {
            localList.add(i);
        }
    }
    System.out.println(localList);
}

快速排序

【全网最清晰快速排序，看完快排思想和代码全部通透，不通透你打我！】https://www.bilibili.com/video/BV1vP411g7J3?vd_source=b5b6b7b62043766d7076c5c42dfe4aef

找到基准，把比基准小的数放入基准前方，比基准大的数放入基准后面，然后分而治之

private static void quickSort(int[] a, int low, int high) {
 if (low < high) {
        //        找到当前基准位置
        int p = partition(a,low,high);
        quickSort(a,low, p - 1);
        quickSort(a, p + 1, high);
    }
        
 }

private static int partition(int[] a, int low, int high) {
    int j = a[low];
    while(low < high) {
        while (low < high && a[high] >= j) {
            high --;
        }
        a[low] = a[high];
        while (low < high && a[low] <= j) {
            low ++;
        }
        a[high] = a[low];
    }
    a[low] = j;
    return low;
}

#pyhon版
def partiton(a, low, high):
    point = a[low]
    while (low < high) :
        while (low < high and a[high] >= point):
            high = high - 1
        a[low] = a[high]
        while(low < high and a[low] <= point):
            low = low + 1
        a[high] = a[low]
    a[low] = point
    return low


def quicksort(a, low, high):
    if (low < high):
        p = partiton(a,low, high)
        quicksort(a, low, p - 1)
        quicksort(a, p + 1, high)

最大不重复字符串字串