2018-03-28

LeetCode/LintCode 刷题

3 minutes read (About 408 words)

Leetcode 215 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，它是数组有序排列后的第 k 个最大元素，而不是第 k 个不同元素。

例如，
给出 [3,2,1,5,6,4] 和 k = 2，返回 5。

注意事项:

你可以假设 k 总是有效的，1 ≤ k ≤ 数组的长度。

思路 1 堆

可以先取k个元素，放到一个数组中，然后把数组转换成最小堆。之后遍历剩下的全部元素，和最小堆的根进行比较。如果比根要大，则替换根，之后把数组重新转换成最小堆。遍历完成后，最小堆堆根即为第 k 大的元素。

class Solution {

   public static int findKthLargest(int[] nums, int k) {
    int[] heap = new int[k];
    //首先取k个元素
    System.arraycopy(nums, 0, heap, 0, k);
    //从倒数k个节点开始 调整数组成为最小堆
    for (int i = k / 2 - 1; i >= 0; i--) {
      adjest(heap, i);
    }
    //如果元素小于最小堆 跳过。
    //如果元素大于最小堆 把元素放在堆顶 然后调整堆
    for (int i = k; i < nums.length; i++) {
      if (heap[0] < nums[i]) {
        heap[0] = nums[i];
        adjest(heap, 0);
      }
    }
    //返回堆顶堆元素
    return heap[0];
  }


  /**
   * 调整最小堆
   * @param heap 堆
   * @param i 从哪个 index 开始
   */
  private static void adjest(int[] heap, int i) {
    int temp = heap[i];
    int length = heap.length;
    for (int k = i * 2 + 1; k < length; k = 2 * k + 1) {
      if (k + 1 < length && heap[k + 1] < heap[k]) {
        k++;
      }
      if (temp <= heap[k]) {
        break;
      } else {
        heap[i] = heap[k];
        i = k;
      }
    }
    heap[i] = temp;
  }
}

题目链接

Leetcode-cn
Leetcode

2017-03-06

LeetCode/LintCode 刷题

2 minutes read (About 239 words)

[medium] linked list cycle

难度: 中等标题：带环链表

给定一个链表，判断它是否有环。

思路

一开始想到的思路是放到hashmap里，每次前进一格就查询在hashmap中是否存在。存在则返回true，遇到null就返回false。但是这样需要额外空间。

后来的思路是两个指针first和second。second每次前进两格，first前进一格。若有环，second必定追上first。

思路想到后调试了很久，总是超出内存范围。

代码

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null){
            return false;
        }
        ListNode first = head;
        ListNode second = head;
        while (first != null && second != null && second.next != null){
            second = second.next.next;
            first = first.next;
            if (first == second){
                return true;
            }
        }
        return false;
    }
}

链接

https://www.lintcode.com/zh-cn/problem/linked-list-cycle/

2016-07-12

LeetCode/LintCode 刷题

2 minutes read (About 237 words)

[easy]Two Sum

难度: 简单标题：Two Sum 求和

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路

方法1 :两层循环，先选定一个数，然后遍历它之后的数，假如符合条件则返回坐标。

方法2:把traget - nums[i]放入hashmap。然后查询 nums[i] 在不在hashmap里，假如在的话就说明他和之前的某个数字加起来等于traget;

代码

//代码 1
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int a[] = new int[2];
        for(int i = 0;i < nums.length -1;i++){
            a[0] = i;
            for(int j = i + 1;j < nums.length;j++){
                a[1] = j;
                if((nums[a[0]] + nums[a[1]]) == target){
                    return a;
                }
            }
        }
        return a;
    }
}

//代码2
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) != null) {
                int[] result = {map.get(nums[i]), i};
                return result;
            }
            map.put(target - nums[i], i);
        }
        int[] result = {};
        return result;
    }
}

链接

https://leetcode.com/problems/two-sum/

2016-07-12

LeetCode/LintCode 刷题

a minute read (About 168 words)

[easy] Delete Node in a Linked List

难度: 简单标题：Delete Node in a Linked List 删除链表的节点

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

思路

A->B->C->D

原本要删除B，知道A，只需要A.next= B.next;

现在只提供B，无法提供 A 时只能把 C 复制到 B，然后删除 C 即可。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

链接

https://leetcode.com/problems/delete-node-in-a-linked-list/

2016-07-12

LeetCode/LintCode 刷题

2 minutes read (About 258 words)

[medium]Integer Break

难度: 中等标题：整数拆分

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

Hint:

There is a simple O(n) solution to this problem.
You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

把一个整数拆分成几个数字，使得他们的积最大。

思路

可以把1-10的拆分结果都列出来，发现当 n > 6 以后，(n - 3) = 3 * n。所以可以吧n = 2 - 6的结果先列出来，然后把6以上的数拆掉若干个3，直到能在表中查到。

开始用的是switch，发现语句太繁琐了，就使用一维数组。

代码

//递归
public class Solution {
    public int integerBreak(int n) {
        int a[] = {1,2,4,6,9};
        if(n < 7){
            return a[n-2];
        }
        else return 3 * integerBreak(n-3);
    }
}

//非递归
public class Solution {
    public int integerBreak(int n) {
        int a[] = {1,2,4,6,9};
        if(n < 7){
            return a[n-2];
        }
        int val = 1;
        while(n >= 7){
            val = 3 * val;
            n = n-3;
        }
        return a[n-2] * val;
    }
}

链接

https://leetcode.com/problems/integer-break/

2016-07-11

LeetCode/LintCode 刷题

a minute read (About 218 words)

[easy] First Bad Version

难度: 简单标题：第一个坏版本

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

找出最先坏的版本。

思路

二分法查询。主要要注意的是mid = head + (tail - head)/2。假如使用head + tail 会越界。

代码

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int head = 1;int tail = n;
        while(!isBadVersion(head) && head <= tail){
            int mid = head + (tail - head)/2;
            if(isBadVersion(mid)){
                tail = mid -1;
                
            }else{
                head = mid + 1;
            }
        }
        return head;
    }
}

链接

https://leetcode.com/problems/first-bad-version/

2016-07-11

LeetCode/LintCode 刷题

a minute read (About 182 words)

[easy] Same Tree

难度: 简单标题：相同二叉树

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

判断两颗二叉树是否相同。

思路

递归，当左子树相同，右子树相同，值相同时两棵树相同。

取子树之前判断一下是否为 null。否则null.left,null.right,null.val会报错。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null || q == null){
            if(p== null && q == null){
                return true;
            }else return false;
        }
        return p.val == q.val &&isSameTree(p.left,q.left)&&isSameTree(q.right,p.right);
    }
}

链接

https://leetcode.com/problems/same-tree/

2016-07-10

LeetCode/LintCode 刷题

a minute read (About 131 words)

[easy]Power of Two

难度: 简单标题：2的冥

Given an integer, write a function to determine if it is a power of two.

判断一个是否是2的幂。

思路

一个数转换成二进制后，假如此数为2的冥，则它的形式一定是100…000。

所以只要不断右移，计算1出现的次数。n & 1 ,假如 n 末尾为1，则结果为1.末尾为 0，结果为 0；

代码

public class Solution {
    public boolean isPowerOfTwo(int n) {
        int ctz = 0;
        while(n > 0){
            ctz += (n & 1);
            n = n >> 1;
        }
        return ctz == 1;
    }
}

链接

https://leetcode.com/problems/power-of-two/

2016-07-09

LeetCode/LintCode 刷题

a minute read (About 209 words)

[easy]Move Zeroes

难度：简单标题：移动零

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

把数组的零移动到末尾，不改变原有非零数字顺序。

思路

双指针，flag指向下一个非零数字存放的位置。i遍历整个数组，当遇到非零数字则复制到num[flag]的位置且flag++。遇到0则跳过。最后把num[flag]以后的所有数字都赋值为0;

代码

public class Solution {
    public void moveZeroes(int[] nums) {
        int flag = 0;
        for(int i = 0;i<nums.length;i++){
            if(nums[i] != 0){
                nums[flag] = nums[i];
                flag++;
            }
        }
        for (int i = flag;i<nums.length;i++){
            nums[i] = 0;
        }
        return;
    }
}

链接

https://leetcode.com/problems/move-zeroes/

2016-07-09

LeetCode/LintCode 刷题

a minute read (About 133 words)

[easy] Maximum Depth of Binary Tree

难度: 简单标题：二叉树最大深度

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

思路

root == null时深度为0;最大深度为左/右的最大深度+1;

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        int DL = maxDepth(root.left);
        int DR = maxDepth(root.right);
        return (DL>DR?DL:DR)+1;
        
    }
}

链接

https://leetcode.com/problems/maximum-depth-of-binary-tree/