[LeetCode] Insert Interval

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].

思路：

遍历input list。如果当前interval < newInterval, add当前；如果当前interval > newInterval, add new Interval; 若重叠，则合并成新的new interval.

Java:

/**

 * 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) {

        Interval temp = newInterval;

        ArrayList<Interval> lst = new ArrayList<Interval>();

        

        for(Interval i : intervals){

            if(i.end < temp.start){

                lst.add(i);

            }

            else if(i.start > temp.end){

                lst.add(temp);

                temp = i;

            }

            else{

                temp = new Interval(Math.min(temp.start, i.start), Math.max(temp.end, i.end));

            }

        }

        

        lst.add(temp);

        

        return lst;

    }

}

C++:

/**

 * Definition for an interval.

 * struct Interval {

 *     int start;

 *     int end;

 *     Interval() : start(0), end(0) {}

 *     Interval(int s, int e) : start(s), end(e) {}

 * };

 */

class Solution {

public:

    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {

        // Start typing your C/C++ solution below

        // DO NOT write int main() function

        Interval temp = newInterval;
        vector<Interval> v;

        

        for(int i = 0; i < intervals.size(); i++){
            if(intervals[i].start > temp.end){
                v.push_back(temp);
                temp = intervals[i];
            }
            else if(intervals[i].end < temp.start){
                v.push_back(intervals[i]);
            }
            else{
                temp.start = min(temp.start, intervals[i].start);
                temp.end = max(temp.end, intervals[i].end);
            }
        }
        v.push_back(temp);
        return v;
    }
};

[LeetCode] Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

递归

Java:

public class Solution {

    public boolean exist(char[][] board, String word) {

        // Start typing your Java solution below

        // DO NOT write main() function

        if(word.length() == 0)   return true;

        int h = board.length;

        if(h == 0)    return false;

        int w = board[0].length;

        boolean[][] flag = new boolean[h][w];

        

        for(int i = 0; i < h; i++){

            for(int j = 0; j < w; j++){

                if(word.charAt(0) == board[i][j]){

                    if(func(board, word, 0, w, h, j, i, flag)) return true;

                }

            }

        }

        

        return false;

    }

    

    public boolean func(char[][] board, String word, int spos, int w, int h, int x, int y, boolean[][] flag){

        if(spos == word.length())  return true;

        if(x < 0 || x >= w || y < 0 || y >= h)   return false;

        if(flag[y][x] || board[y][x] != word.charAt(spos))   return false;

        

        flag[y][x] = true;

        

        // up

        if(func(board, word, spos + 1, w, h, x, y-1, flag)){

            return true;

        }

        // down

        if(func(board, word, spos + 1, w, h, x, y+1, flag)){

            return true;

        }

        // left

        if(func(board, word, spos + 1, w, h, x-1, y, flag)){

            return true;

        }

        // right

        if(func(board, word, spos + 1, w, h, x+1, y, flag)){

            return true;

        }

        

        flag[y][x] = false;

        

        return false;

    }

}

c++