精华内容
下载资源
问答
  • 面试常见算法

    千次阅读 2019-01-22 11:58:14
    面试常见算法 /** * 快速排序 * 选择一个基准值,将比基准值小的放在左侧,大的放在右侧 * 再将两侧的数组进行递归调用即可 */ public void quickSort(int[] numbers, int start, int end){ if (start &lt...

    面试常见算法

    /**
         * 快速排序
         * 选择一个基准值,将比基准值小的放在左侧,大的放在右侧
         * 再将两侧的数组进行递归调用即可
         */
        public void quickSort(int[] numbers, int start, int end){
            if (start < end) {
                int base = numbers[start]; // 选定的基准值(第一个数值作为基准值)
                int temp; // 记录临时中间值
                int i = start, j = end;
                do {
                    while ((numbers[i] < base) && (i < end)) {
                        i++;
                    }
                    while ((numbers[j] > base) && (j > start)){
                        j--;
                    }
                    if (i <= j) {
                        temp = numbers[i];
                        numbers[i] = numbers[j];
                        numbers[j] = temp;
                        i++;
                        j--;
                    }
                    for (int x : numbers){
                        System.out.print(x + ",");
                    }
                    System.out.println("--------------------------");
                } while (i <= j);
                if (start < j) {
                    quickSort(numbers, start, j);
                }
                if (end > i) {
                    quickSort(numbers, i, end);
                }
            }
        }
    
         /**
         * 选择排序
         * 在未排序序列中找到最小元素,存放到排序序列的起始位置
         * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾
         * 以此类推,直到所有元素均排序完毕。
         */
        public void selectSort(int[] arr) {
            int temp, k, j;
            for (int i = 0; i < arr.length; i++) {
                k = i;
                for (j = arr.length - 1; j > i; j--) {
                    if (arr[j] < arr[k]) {
                        k = j;    //k为当前这一趟最小的元素下标值
                    }
                }
                temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }
        }
    
    /**
         * 插入排序
         * 从第一个元素开始,该元素可以认为已经被排序
         * 取出下一个元素,在已经排序的元素序列中从后向前扫描
         * 如果该元素(已排序)大于新元素,将该元素移到下一位置
         * 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
         * 将新元素插入到该位置中
         * 重复步骤2
         */
        public void insertSort(int[] arr) {
            int temp, j;
            for (int i = 1; i < arr.length; i++) {
                temp = arr[i];
                for (j = i; j > 0 && temp < arr[j - 1]; j--) {
                    arr[j] = arr[j - 1];
                }
                arr[j] = temp;
            }
        }
    
     /**
         * Atoi函数实现
         * atoi() 函数会扫描 str 字符串,跳过前面的空白字符(例如空格,tab缩进等),直到遇上数字或正负符号才开始做转换,而再遇到非数字或字符串结束时('\0')才结束转换,并将结果返回。
         * 返回转换后的整型数;如果 str 不能转换成 int 或者 str 为空字符串,那么将返回 0。如果超出Integer的范围,将会返回Integer最大值或者最小值
         */
        public int myAtoi(String str) {
            if (str == null || str.length() < 0) {
                return 0;
            }
            str = str.replaceAll(" ", "");
            char flag = '+';
            int i = 0;
            if (str.charAt(0) == '-') {
                flag = '-';
                i++;
            } else if (str.charAt(0) == '+') {
                i++;
            }
            double res = 0;
            while (i < str.length() && str.charAt(i) > '0' && str.charAt(i) < '9') {
                res = res * 10 + str.charAt(i) - '0';
                i++;
            }
            if (flag == '-') {
                res = -1 * res;
            }
            if (res > Integer.MAX_VALUE) {
                return Integer.MAX_VALUE;
            } else if (res < Integer.MIN_VALUE) {
                return Integer.MIN_VALUE;
            }
            return (int) res;
        }
    
     /**
         * 二分查找
         * 要求待查找的序列有序。
         * 每次取中间位置的值与待查关键字比较,如果中间位置的值比待查关键字大,则在前半部分循环这个查找的过程,如果中间位置的值比待查关键字小,则在后半部分循环这个查找的过程。直到查找到了为止,否则序列中没有待查的关键字。
         * 返回key所在数组位置
         */
        public int binSearch(int[] arr, int key) {
            int mid = arr.length / 2;
            if (key == arr[mid]) {
                return mid;
            }
            int start = 0;
            int end = arr.length - 1;
            while (start < end) {
                mid = (end - start) / 2 + start;
                if (key < arr[mid]) {
                    end = mid - 1;
                } else if (key > arr[mid]) {
                    start = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
    
    展开全文
  • 面试常见算法总结

    千次阅读 2017-04-01 21:36:30
    这里是我在网上搜索的一些面试常见算法,总结一下,利人利己。top k 问题:选取第k大(前k大)的数可以采用类似于快速排序的方法, 利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中...

    这里是我在网上搜索的一些面试常见算法,总结一下,利人利己。

    top k 问题:

    选取第k大(前k大)的数可以采用类似于快速排序的方法, 利用快速排序的思想,从数组S中随机找出一个元素X,把数组分为两部分Sa和Sb。Sa中的元素大于等于X,Sb中元素小于X。这时有两种情况:
    1. Sa中元素的个数小于k,则Sb中的第k-|Sa|个元素即为第k大数;
    2. Sa中元素的个数大于等于k,则返回Sa中的第k大数。时间复杂度近似为O(n)

    也可以用最大堆的方法,pop k次即可。

    海量数据的top k 问题:

    比如在一亿(N)个数中选取最大的10000(m)个,这时候要分情况讨论,如果说内存不足的话,那么可以采用建立一个m最小堆,然后遍历N个数,如果大于堆顶则插入。

    如果内存足够的情况,可以直接采用快速排序方法,可以借助分治法,比如把N个数分为100份数,分别找出100个最大的10000,然后最后在100万中找10000个最大的。

    选取频率最高问题

    海量数据的top k 问题,如果有1g大小的文件,需要统计其中出现频率最高的100个词,有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

    方案:顺序读文件中,对于每个词x,取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,…x4999)中。这样每个文件大概是200k左右。

    如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
    对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100个词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。

    海量数据处理http://blog.csdn.net/yangquanhui1991/article/details/52172768

    通常就是先hash映射到不同的小文件中,然后通过hash map求频率,最后归并

    两个有序数列的中位数http://blog.csdn.net/zcsylj/article/details/6802062 采取二分法的思路

    有一个数组,设其为N1,如何取出前N2大个数,数字都是0-10000之间的 。 可以用基数排序,时间复杂度为o(n)

    1.数组中逆序对计算。(剑指offer)
    2.判读一个树是不是另一个树的子树(剑指offer)
    3.数据流要求o(1)求得中位数,o(lgn)插入(剑指offer)
    4.顺时针打印矩阵(剑指offer)
    5.复杂链表复制(剑指offer)
    6.二叉排序树中第k小的数(剑指offer)
    7.反转链表递归 、非递归(剑指offer)
    8.链表中倒数第k个结点(剑指offer)
    9.数组中超过一半的数字(剑指offer)
    10.左旋转字符串(剑指offer)
    11.把二叉树打印成多行(剑指offer)
    12.旋转数组查找(剑指offer)
    13.链表归并排序
    14.Trapping Rain Water https://leetcode.com/problems/trapping-rain-water/
    15.Longest Palindromic Substring https://leetcode.com/problems/longest-palindromic-substring/
    16.Gray Code https://leetcode.com/problems/gray-code/
    17.Binary Tree Maximum Path Sum https://leetcode.com/problems/binary-tree-maximum-path-sum/
    18.Search for a Range https://leetcode.com/problems/search-for-a-range/
    19.算术表达式转逆波兰表达式(后缀表达)
    20.k-means
    21.字符串由大小写字母组成,要求去重,只允许使用几个int临时变量,要求时间复杂度尽可能少
    22.青蛙每次跳台阶,每次一步或者二步,青蛙总共可以跳n次,台阶共m阶(n<=m),每个台阶有若干害虫,使得青蛙吃的害虫最多。
    23.左右括号组成的字符串,去除最少使得剩余的字符串是合法的(符合左右括号规则)
    24.实现5选3 组合
    25.数组中后面的数减前面的数差的最大值,要求时间、空间复杂度尽可能低
    26.多个有序数组的归并
    27.多个有序数组求交集
    28.二个有序数组求差集
    29.字符串中最长不重复子串
    30.小于10万的回文数的个数

    给定两个正整数x,y,x有两中状态转移方式:一个是f(x) = 2*x + 1,另一个是g(x) = 3*x+1,问x最少能够几次转移到y,转移不到输出-1。

    int func(int x, int y){
    if(x < 0) return -1;
    if(x > y) return -1;
    if(x == y) return 0;
    int l = func(2*x+1,y);
    int r = func(3*x+1,y);
    if(l == -1 && r == -1) return -1;
    if(l == -1) return r + 1;
    return l + 1;
    }

    展开全文
  • java面试常见算法总结

    千次阅读 2019-03-05 18:23:27
    java面试常见算法总结 一个int[]数组 如何打印出重复次数前5的元素及重复次数 /** * 排序 * @author v_liuwen * @date 2019/3/5 */ public class SortDemo { public static void main(String[] args) { int[]...

    java面试常见算法总结

    1、 一个int[]数组 如何打印出重复次数前5的元素及重复次数

    /**
     * 排序
     * @author v_liuwen
     * @date 2019/3/5
     */
    public class SortDemo {
    
        public static void main(String[] args) {
            int[] nums = new int[]{1,3,7,4,9,2,3,4,3,4,5,3,6,3,7,5,4,5,6,7,9,4};
            sort(nums);
        }
    
    
        public static void sort(int[] nums){
            Map<Integer,Integer> map = new HashMap<>();
            Arrays.stream(nums).forEach(num ->{
                if(map.get(num)==null){
                    map.put(num,1);
                }else {
                    map.put(num,map.get(num)+1);
                }
            });
    
            map.forEach((k,v) ->{
                System.out.println("key:"+k+"  value:"+v);
            });
    
    
            //按键排序
    //        System.out.println("---------------按键排序--------------------");
    //        Map<Integer,Integer> resultKey = map.entrySet()
    //                .stream().sorted(Map.Entry.comparingByKey())
    //                .collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue,(oldValue,newValue) ->oldValue,LinkedHashMap::new));
    //        System.out.println(resultKey);
            //按值排序
            System.out.println("---------------按值排序--------------------");
            Map<Integer,Integer> resultValue = map.entrySet()
                    .stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
                    .collect(Collectors.toMap(Map.Entry::getKey,Map.Entry::getValue,(oldValue,newValue) ->oldValue,LinkedHashMap::new));
            Integer count = 5;
            for(Integer key:resultValue.keySet()){
                if(count<1){
                    break;
                }
                System.out.println("key:"+key+"   value:"+resultValue.get(key));
                count--;
            }
        }
    }
    
    

    打印结果

    key:1  value:1
    key:2  value:1
    key:3  value:5
    key:4  value:5
    key:5  value:3
    key:6  value:2
    key:7  value:3
    key:9  value:2
    ---------------按值排序--------------------
    key:3   value:5
    key:4   value:5
    key:5   value:3
    key:7   value:3
    key:6   value:2
    

    持续更新中。。。

    展开全文
  • 面试常见算法-排序查找算法

    千次阅读 2015-06-22 07:37:26
    算法是程序员必被的一个技能,在面试中常常出现,下面总结了面试中出现的常见算法,这些算法程序员应该牢记在心中,要非常熟练。

    【常见面试问题总结目录>>>


    算法是程序员必被的一个技能,在面试中常常出现,下面总结了面试中出现的常见算法,这些算法程序员应该牢记在心中,要非常熟练。

    插入排序算法

    原理:将数组分为无序区和有序区两个区,然后不断将无序区的第一个元素按大小顺序插入到有序区中去,最终将所有无序区元素都移动到有序区完成排序。

    要点:设立哨兵,作为临时存储和判断数组边界之用。

    public class InsertSort {
       private static void insertSort(int[] a) {
           int j;
           int tmp;
           for (int i = 1; i < a.length; i++) {
               tmp = a[i];
               for (j = i; j > 0 && tmp < a[j - 1]; j--) {
                    a[j] = a[j - 1];
               }
               a[j] = tmp;
           }
        }
    }

    希尔排序算法

    原理:又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组,使用直接插入排序法进行排序,然后不断缩小增量直至为1,最后使用直接插入排序完成排序。

    要点:增量的选择以及排序最终以1为增量进行排序结束。

    public class ShellSort {
        private static void shellSort(int[] a) {
            int j;
            int tmp;
            for (int gap = a.length / 2; gap >0; gap /= 2) {
                for (int i = gap; i < a.length;i++) {
                    tmp = a[i];
                    for (j = i; j >= gap && tmp< a[j - gap]; j -= gap) {
                        a[j] = a[j - gap];
                    }
                    a[j] = tmp;
                }
            }
        }
    }

    冒泡排序算法

    原理:将序列划分为无序和有序区,不断通过交换较大元素至无序区尾完成排序。

    要点:设计交换判断条件,提前结束以排好序的序列循环。

    public class BubbleSort {
       private static void bubbleSort(int[] a) {
            for (int i = 0; i < a.length - 1;i++) {
               for (int j = 0; j < a.length - 1 - i; j++) {
                    if (a[j] > a[j + 1]) {
                        swap(a, j, j + 1);
                    }
               }
           }
        }
       private static void swap(int[] a, int x, int y) {
           int tmp = a[x];
           a[x] = a[y];
           a[y] = tmp;
        }
    }

    快速排序算法

    原理:不断寻找一个序列的中点,然后对中点左右的序列递归的进行排序,直至全部序列排序完成,使用了分治的思想。

    要点:递归、分治

    public class QuickSort {
       private static void quickSort(int[] a) {
           quickSort(a, 0, a.length - 1);
        }
       private static void quickSort(int[] a, int left, int right) {
           if (left < right) {
               int pivot = a[left];
               int lo = left;
               int hi = right;
               while (lo < hi) {
                    while (lo < hi &&a[hi] >= pivot) {
                        hi--;
                    }
                    a[lo] = a[hi];
                    while (lo < hi &&a[lo] <= pivot) {
                        lo++;
                    }
                    a[hi] = a[lo];
               }
               a[lo] = pivot;
               quickSort(a, left, lo - 1);
               quickSort(a, lo + 1, right);
           }
        }
    }

    简单选择排序算法

    原理:将序列划分为无序和有序区,寻找无序区中的最小值和无序区的首元素交换,有序区扩大一个,循环最终完成全部排序

    public class SelectSort {
       private static void selectSort(int[] a) {
           int idx;
           for (int i = 0; i < a.length; i++) {
               idx = i;
               for (int j = i + 1; j < a.length; j++) {
                    if (a[idx] > a[j]) {
                        idx = j;
                    }
               }
               swap(a, idx, i);
           }
        }
       private static void swap(int[] a, int x, int y) {
           int tmp = a[x];
           a[x] = a[y];
           a[y] = tmp;
        }
    }

    堆排序算法

    原理:利用大根堆或小根堆思想,首先建立堆,然后将堆首与堆尾交换,堆尾之后为有序区。

    要点:建堆、交换、调整堆

    public class HeapSort {
       private static void heapSort(int[] a) {
           // 先创建大堆,从第一个非叶子结点开始调整,然后调整第二个非叶子结点...
           for (int i = a.length / 2; i >= 0 ; i--) {
               shiftDown(a, i, a.length);
           }
           // 调整大堆,将最大的元素调整到未排好序的部分的末尾
           for (int i = a.length - 1; i > 0 ; i--) {
               swap(a, 0, i);
               shiftDown(a, 0, i);
           }
        }
       private static void shiftDown(int[] a, int i, int n) {
           int child;
           int tmp;
           for (tmp = a[i]; i * 2 + 1 < n; i = child) {
               child = i * 2 + 1;
               if (child != n - 1 && a[child] < a[child + 1]) {
                    child++;
               }
               if (tmp < a[child]) {
                    a[i] = a[child];
                } else {
                    break;
               }
           }
           a[i] = tmp;
        }
       private static void swap(int[] a, int x, int y) {
           int tmp = a[x];
           a[x] = a[y];
           a[y] = tmp;
        }
    }

    归并排序算法

    原理:将原序列划分为有序的两个序列,然后利用归并算法进行合并,合并之后即为有序序列。

    要点:归并、分治

    public class MergeSort {
       private static void mergeSort(int[] a) {
           int[] b = new int[a.length];
           mergeSort(a, b, 0, a.length - 1);
        }
       private static void mergeSort(int[] a, int[] b, int left, int right) {
           if (left < right) {
               int center = left + (right - left) / 2;
               mergeSort(a, b, left, center);
               mergeSort(a, b, center + 1, right);
               merge(a, b, left, center + 1, right);
           }
        }
       private static void merge(int[] a, int[] b, int leftPos, int rightPos, intrightEnd) {
           int leftEnd = rightPos - 1;
           int tempPos = leftPos;
           int numElements = rightEnd - leftPos + 1;
     
           while (leftPos <= leftEnd && rightPos <= rightEnd) {
               if (a[leftPos] <= a[rightPos]) {
                    b[tempPos] = a[leftPos];
                    tempPos++;
                    leftPos++;
               } else {
                    b[tempPos] = a[rightPos];
                    tempPos++;
                    rightPos++;
               }
           }
           while (leftPos <= leftEnd) {
               b[tempPos] = a[leftPos];
               tempPos++;
               leftPos++;
           }
           while (rightPos <= rightEnd) {
               b[tempPos] = a[rightPos];
               tempPos++;
               rightPos++;
           }
           for (int i = 0; i < numElements; i++, rightEnd--) {
               a[rightEnd] = b[rightEnd];
           }
        }
    }

    二分查找算法

    public class BinarySearch {
       public static int binarySearch(int[] a, int v) {
           int mid;
           int lo = 0;
           int hi = a.length - 1;
           while (lo <= hi) {
               mid = lo + ((hi - lo) >>> 1); // 移位运算的优先级比较低,要用括号
               if (a[mid] == v) { // 已经找到
                    return mid;
               } else if (a[mid] < v) { // 可能在右边
                    lo = mid + 1;
               } else { // 可能在左边
                    hi = mid - 1;
               }
           }
           return -1; // 未找到
        }
    }

    展开全文
  • 1 三线程打印ABC 7 如何实现一个lru 8 如何定位链表尾部前面的第k个节点,写一下
  • JS面试常见算法

    千次阅读 2017-09-10 15:45:07
    学习数据结构与算法对于工程师去理解和分析问题都是有帮助的。如果将来当我们面对较为复杂的问题,这些基础知识的积累可以帮助我们更好的优化解决思路。下面罗列在前端面试中经常撞见的几个问题吧。 1.统计一个字符...
  • [算法] 面试常见算法题 (不断更新)

    千次阅读 2019-07-16 20:37:35
    Leetcode画解算法 class Solution { public: int reverse(int x) { int ans = 0; int pop = 0; while (x) { pop = x % 10; if(ans > INT_MAX / 10 || (ans == INT_MAX / 10 && pop > 7)) return 0; if...
  • )的朋友可能知道,我来上海一个多星期,面试了大概十几家公司,收到了一些 offer,其实截止到昨天下午我依然还是在面试的路上。我是自学 Python,因为之前不知道自己未来要从事什么样的岗位,所以学的时候爬虫和后端...
  • O(n)的那个算法,如果只操作一次还是可以接受的,但是如果需要大量的求和操作,比如第一次求下标(1,1234)的和第二次求下标(2,1024)的和,很容易发现在第一次计算的过程中(2,1024)的和是计算过的,只是...
  • 算法工程师面试常见问题

    万次阅读 多人点赞 2018-03-11 11:45:53
    八九月份就要开始找工作了,一直期待能够成为一名算法工程师,所以在...面试常见问题 深度学习 常见问题 编程语言 C++、python 基本算法 剑指offer+Leetcode基本就能解决 剑指offer算法实现 ...
  • 面试常见排序算法(上)

    千次阅读 2017-05-12 18:58:43
    查找和排序是算法的的入门知识,其思想可用于很多算法当中,应用性比较常见。所以在面试中经常会问到排序算法及相关的问题。下来是我对这些简单排序算法的思想及其特点的整理。 冒泡排序  冒泡排序是最原始的排序...
  • 算法面试常见问题大集合

    万次阅读 多人点赞 2019-06-17 17:23:56
    1.参考博客 算法面试常见问题大集合
  • C#常见算法面试

    万次阅读 2016-06-16 18:50:51
    转载于:C#常见算法面试 一、求以下表达式的值,写出您想到的一种或几种实现方法: 1-2+3-4+……+m  //方法一,通过顺序规律写程序,同时也知道flag标志位的重要性。  static int F1(int m) { int ...
  • 前端常见算法面试

    千次阅读 2018-09-14 23:24:02
    显然,学习算法对于任何工程师提高编程能力和提高理解分析问题的能力都是有帮助的,接下来放几道常见的前端面试中出现的算法题供大家学习,当然,这些题目的解法未必是最优的,仅供大家学习参考。 // 判断是否...
  • 常见面试手写算法

    千次阅读 2017-09-05 14:49:02
    import java.time.chrono.JapaneseChronology; import java.util.Arrays; public class Main { public static int binarySort(int[] number, int n) { int start = 0; int end = number.length - 1;
  • iOS面试题系列之常见算法

    万次阅读 2016-05-02 00:27:34
    iOS面试中熟悉常见算法1、 对以下一组数据进行降序排序(冒泡排序)。“24,17,85,13,9,54,76,45,5,63” int main(int argc, char *argv[]) { int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63}; int...
  • 数据结构算法常见面试考题

    万次阅读 多人点赞 2018-11-08 09:29:44
    类似森林 (4) 贪心算法和动态规划的区别 贪心算法:局部最优,划分的每个子问题都最优,得到全局最优,但是不能保证是全局最优解,所以对于贪心算法来说,解是从上到下的,一步一步最优,直到最后。 动态规划:将...
  • 计算机面试常见题目-算法

    千次阅读 2020-05-11 22:48:47
    面试问题之软件工程题 1.软件重用? 同一个函数重复用。 2.软件测试类型? 单元,集成,黑盒,白盒。 3.软件工程步骤 需求,设计,开发,测试。 4.UML 系统流程建模工具 5软件工程的认识? 运用工程化的方法管理软件...
  • 常见算法面试题一

    千次阅读 2018-09-29 08:33:40
    1 、 介绍一下平衡二叉树查看答案&gt;&gt; 2 、 什么是二叉查找树?性能怎么样?什么情况下达到最差性能?...6 、 介绍一下LRU算法查看答案&gt;&gt; 7 、 介绍一下红黑树及其应用场景查看...
  • class Solution { private: vector<vector<int>> memo; public: int knapsack01(const vector<int> &w, const vector<int> &v, int C) { int n = (int) w.size();...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 102,288
精华内容 40,915
关键字:

面试常见算法