算法题

算法题网址：https://leetcode-cn.com/problemset/all/

头条：https://leetcode-cn.com/explore/featured/card/bytedance/245/data-structure/1049/

newCoder：https://www.nowcoder.com/contestRoom

1、两数之和

题解

一遍哈希表

在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

复杂度分析：

• 时间复杂度：O(n)O(n)， 我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)O(1) 的时间。

• 空间复杂度：O(n)O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 nn 个元素。

2、三数之和

题解：

* a.我们可以先将原数组从小到大排序，固定其中两个元素 i 和 j，i从前往后走，j从后往前走，i 每往后一个，将 j 重置为数组末尾的下标，在 i 和 j

* 之间找使nums[i] +nums[j] +nums[k] == 0成立的k。

*<p>

* b.如何去重:每次得出nums[i] +nums[j] +nums[k] == 0成立的i、j、k之后，令 i 往后走，直到nums[i] !=

*nums[i + 1],并令 j 向前走，直到nums[j] !=nums[j-1]。这样就能保证得到的三个数字不会有重复

    /**
     * 三数之和
     * 
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {

        // result
        List<List<Integer>> result = new ArrayList<>();

        // sort
        Arrays.sort(nums);

        //
        for (int i = 0; i < nums.length; i++) {

            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // i 每往后一个，将 j 重置为数组末尾的下标
            int j = nums.length - 1;

            // target
            int target = 0 - nums[i];

            int k = i + 1;

            // 固定其中两个元素 i 和 j,在 i 和 j 之间找使nums[i] + nums[j] + nums[k] == 0成立的k。
            while (k < j) {

                if (nums[k] + nums[j] == target) {

                    // set result
                    result.add(Arrays.asList(nums[i], nums[k], nums[j]));

                    // 去重
                    while (k < j && nums[k] == nums[k + 1]) {
                        k++;
                    }
                    while (k < j && nums[j] == nums[j - 1]) {
                        j--;
                    }

                    // j-- k++
                    k++;
                    j--;

                } else if (nums[k] + nums[j] < target) {
                    k++;
                } else {
                    j--;
                }

            }
        }
        return result;
    }

3、数组中的第K个最大元素

a、排序 ：时间复杂度 O(NlogN)，空间复杂度 O(1)

public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

b、使用优先队列（priorityQueue）维持一个小顶堆（min heap）

java中的优先队列，priorityQueue的作用是保证每次取出的元素都是队列中权值最小的。其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）

堆排序 ：时间复杂度 O(NlogK)，空间复杂度 O(K)。

    public int findKthLargestMy(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
        for (int val : nums) {
            pq.add(val);
            if (pq.size() > k) // 维护堆的大小为 K
                pq.poll();
        }
        return pq.peek();
    }

c、快速选择 ：时间复杂度 O(N)，空间复杂度 O(1)

    public int findKthLargest(int[] nums, int k) {

        int begin=0;

        int end=nums.length-1;

         k=nums.length+1-k;

         while(begin<end){

            int pos=partition(nums,begin,end);

            if(pos==k-1) break;

            else if(pos<k-1) begin=pos+1;

            else end=pos-1;

        }

        return nums[k-1];

    }

    public int partition(int[]nums,int l,int r){

          int less=l-1;//小于区的下标

          int  more=r;//大于区的下标，默认以最后一个下标的数作为划分值

          while(l<more){

              if(nums[l]<nums[r])

                 swap(nums,++less,l++);

              else if  (nums[l]>nums[r]) 

                 swap(nums,--more,l);

              else l++;

          }

          swap(nums,more,r);

          return less+1;//小于区位置+1可以得到划分的这个数的下标

      }

    private void swap(int[] a, int i, int j) {

          int t = a[i];

          a[i] = a[j];

          a[j] = t;

    }

4、搜索旋转排序数组

分析

看到这个O(logN)的复杂度要求，一瞬间就想到二分法。

这题说的旋转，实际上就是左右整体互换，也就导致出现了两个递增序列。也就是说当我们二分查找时，有两种可能，一种是选择的部分一个递增序列，而另一种可能选择的部分横跨两个递增序列。

        public int search(int[] nums, int target) {
            //实际上就是两个递增序列，依旧是二分法
            //只不过只在递增序列中二分
            if(nums.length==0){
                return -1;
            }
            int st = 0,end = nums.length-1;
            while(st <= end){
                int mid = st+(end-st)/2;
                if(nums[mid]==target){
                    return mid;
                }
                if(nums[mid]>=nums[st]){
                    if(nums[st]<=target&&target<nums[mid]){
                        end = mid-1;
                    }else{
                        st = mid+1;
                    }
                }else{
                    if(nums[mid]<target&&target<=nums[end]){
                        st = mid+1;
                    }else{

                        end = mid==0?mid:mid-1;
                    }
                }
            }
            return -1;
        }

5、反转字符串

@Test
    public void reverseString() {

        StringBuffer sBuffer = new StringBuffer("hello");

        System.out.println(sBuffer.reverse().toString());

    }

    @Test
    public void reverseString1() {

        String string = "hello";

        char[] chars = string.toCharArray();
        for (int i = 0; i < chars.length / 2; i++) {
            char tmp = chars[i];
            chars[i] = chars[chars.length - 1 - i];
            chars[chars.length - 1 - i] = tmp;
        }

        System.out.println(new String(chars));

    }