Rotate List, Leetcode 解题笔记

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

一开始以为k必须小于list的长度,于是想用two pointer做。后来发现题目本意是k可以超过list的长度。于是用下面的方法:
首先从head开始跑,直到最后一个节点,这时可以得出链表长度len。然后将尾指针指向头指针,将整个圈连起来,接着往前跑len – k%len,从这里断开,就是要求的结果了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode rotateRight(ListNode head, int n) 
    {
        if (head == null || n == 0) { return head; }
        
        ListNode lastEle = head;
        int length = 1;
        while (lastEle.next != null) {
            lastEle = lastEle.next;
            length ++;
        }
        
        n = n % length;
        lastEle.next = head;
        ListNode cur = head;
        for (int i=0; i<length-n-1; i++) {
            cur = cur.next;
        }
        head = cur.next;
        cur.next = null;
        return head;
    }
}
Advertisements

Permutation Sequence, Leetcode 解题笔记

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

第一思路肯定是DFS枚举,跟之前的Permutation I && II 类似。只是这次不用枚举所有的结果,而是只到第k个就行了。但是这种方法时间复杂度太高了,过不了OJ。

第二思路是数学方法,算出第k个时每个数字的位置。这种方法只适用于这一道题,没有什么可移植性,了解一下就好。

DFS枚举:

public class Solution {

    int count = 0;
    String ret = "";
    char [] dic = {'1','2','3','4','5','6','7','8','9'};
    public String getPermutation(int n, int k) {
        StringBuilder s = new StringBuilder();
        int[] visited = new int[n];
        dfs(n, k, s, 0, visited);
        return ret;
    }

    public void dfs(int n, int k, StringBuilder s, int deep, int[] visited){
        if(deep == n){
            count++;
            if(count == k){
                ret = s.toString();
                return;
            }
        }
        for(int i = 0; i < n; i++){
            if(visited[i] == 0){
                s.append(dic[i]);
                visited[i] = 1;
                dfs(n, k, s, deep+1, visited);
                s.deleteCharAt(s.length()-1);
                visited[i] = 0;
            }

        }
    }
}

数学:

public class Solution {
	public String getPermutation(int n, int k) {
 
		// initialize all numbers
		ArrayList<Integer> numberList = new ArrayList<Integer>();
		for (int i = 1; i <= n; i++) {
			numberList.add(i);
		}
 
		// change k to be index
		k--;
 
		// set factorial of n
		int mod = 1;
		for (int i = 1; i <= n; i++) {
			mod = mod * i;
		}
 
		String result = "";
 
		// find sequence
		for (int i = 0; i < n; i++) {
			mod = mod / (n - i);
			// find the right number(curIndex) of
			int curIndex = k / mod;
			// update k
			k = k % mod;
 
			// get number according to curIndex
			result += numberList.get(curIndex);
			// remove from list
			numberList.remove(curIndex);
		}
 
		return result.toString();
	}
}

Spiral Matrix II, Leetcode 解题笔记

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

数组实现题,注意边界情况。

public class Solution {
    public int[][] generateMatrix(int n) {
        
        int[][] matrix = new int[n][n];
        if(n == 0) return (new int[n][n]);
        //if(n == 1) return ;
        int row = 0;
        int col = 0;
        int row_end = n-1;
        int col_end = n-1;
        int cur = 1;
        
        int num = n*n;
        
        while(true){
            for(int i = col; i <= col_end; i++){
                matrix[row][i] = cur;
                cur++;
            }
            row++;
            if(cur > num) break;
            for(int j = row; j <= row_end; j++){
                matrix[j][col_end] = cur;
                cur++;
            }
            col_end--;
            if(cur > num) break;
            for(int i = col_end; i >= col; i--){
                matrix[row_end][i] = cur;
                cur++;
            }
            row_end--;
            if(cur > num) break;
            for(int j = row_end; j >= row; j--){
                matrix[j][col] = cur;
                cur++;
            }
            col++;
            if(cur > num) break;
        }
        return matrix;
    }
}

Length of Last Word, Leetcode 解题笔记

Given a string s consists of upper/lower-case alphabets and empty space characters ‘ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = “Hello World”,
return 5.

这题思路很简单,就是从后往前找空格,但是要注意考虑到所有的情况。比如我一开始就没想到“a ”这种以空格为结尾的情况。

public class Solution {
    public int lengthOfLastWord(String s) {
        if(s.length() == 0) return 0;
        int count = 0;
        int i = s.length()-1;
        while(i >= 0 && s.charAt(i) == ' '){
            i--;
        }
        while(i >= 0 && s.charAt(i) != ' '){
            i--;
            count++;
        }
        if(i < -1) return 0;
        else return count;
    }
}

Insert Interval, Leetcode 解题笔记

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

其实就是三种情况,一次遍历就解决了。

insert-interval--650x351
图片来自:http://www.programcreek.com/2012/12/leetcode-insert-interval/

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        ArrayList<Interval> ret = new ArrayList<Interval>();
        boolean flag = false;
        if(intervals.size() == 0){
            ret.add(newInterval);
            return ret;
        }
        
        for(int i = 0; i < intervals.size(); i++){
            Interval cur = intervals.get(i);
            if(newInterval.start > cur.end){
                ret.add(cur);
            }
            else if(newInterval.end < cur.start){
                ret.add(newInterval);
                for(int j = i; j < intervals.size(); j++){
                    ret.add(intervals.get(j));
                }
                flag = true;
                break;
            }
            else{
                newInterval = new Interval(Math.min(newInterval.start, cur.start), Math.max(newInterval.end, cur.end));
            }
        }
        if(!flag)
            ret.add(newInterval);
        return ret;
    }
}

同样的思路,人家写的实在是太简洁了:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
 
        ArrayList<Interval> result = new ArrayList<Interval>();
 
        for(Interval interval: intervals){
            if(interval.end < newInterval.start){
                result.add(interval);
            }else if(interval.start > newInterval.end){
                result.add(newInterval);
                newInterval = interval;        
            }else if(interval.end >= newInterval.start || interval.start <= newInterval.end){
                newInterval = new Interval(Math.min(interval.start, newInterval.start), Math.max(newInterval.end, interval.end));
            }
        }
 
        result.add(newInterval); 
 
        return result;
    }
}

Merge Intervals, Leetcode 解题笔记

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

这道题思路不难,很容易想到先将intervals排序,然后再合并。这题关键考察的是Comparator的override的知识点。与此题类似的可以复习之前做过的Merge k sorted lists那道题。

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if(intervals == null || intervals.size() <= 1) return intervals;
        
        //注意学习此处sort list的用法
        Collections.sort(intervals, new IntervalComparator());
        ArrayList<Interval> ret = new ArrayList<Interval>();

        Interval pre = intervals.get(0);
        for(int i = 1; i < intervals.size(); i++){
            Interval cur = intervals.get(i);
            if(cur.start <= pre.end){
                Interval temp = new Interval(pre.start, Math.max(cur.end, pre.end));
                pre = temp;
            }
            else{
                ret.add(pre);
                pre = cur;
            }
        }
        ret.add(pre);
        return ret;
    }
}

//构建自定义的Comparator
class IntervalComparator implements Comparator<Interval>{
    public int compare(Interval i1, Interval i2){
        return i1.start - i2.start;
    }
}

Jump Game, Leetcode 解题笔记

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

一维DP,记录当前能达到的最远值。

public class Solution {
    public boolean canJump(int[] A) {
        int maxCover = 0;
        for(int i = 0; i < A.length && i <= maxCover; i++){
            if(A[i] + i > maxCover)
                maxCover = i+A[i];
            if(maxCover >= A.length-1)
                return true;
        }
        return false;
    }
}