Tag: LeetCode OJ

题目：

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south,x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.
Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
Example 1:

Given x = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
    │
Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>
Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
┌───┐
│   │
└───┼>
Return true (self crossing)

思路：

https://leetcode.com/discuss/88054/java-oms-with-explanation
本人愚钝，想不到O(1)空间复杂度的方法，只能看Discussion啦，看完以后发现，遇到问题能够分析出各种情况真是不容易。
把大神的代码总结一下，可以变成下面这张图，图中给出了可能发生self-crossing的所有情况（其他情况都是这些情况的”旋转”版本）：

所以就是遍历所有移动步x[i]，判断之前的情况是否在这三种情况之内，如果有的话，那肯定就有crossing了。其中情况2的意思是，当前的步进x[i]覆盖到了x[i-4]了，其他情况看图应该都好理解的。

代码：

class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        int numSz = x.size();
        if(numSz <= 3)
            return false;
        for(int i=3; i<numSz; i++){
            if(x[i]>=x[i-2] && x[i-1]<=x[i-3]) //Cond 1
                return true;
            else if(i>=4 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2])//Cond 2
                return true;
            else if(i>=5 && x[i-1]<=x[i-3] && x[i-4]<=x[i-2] && x[i]+x[i-4]>=x[i-2] && x[i-1]+x[i-5]>=x[i-3]) //Cond 3
                return true;
        }
        return false;
    }
};

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?

思路

其实还有更简单的方法，在《Cracking the Coding Interview》上有提到。通过数学计算可以推导出来，用快行指针的方法判断出环后，可以不用计算环大小，把快指针变慢然后放到链头上，两个指针继续走到相碰就剩入口了。
分为三步：判断环，计算环的大小，找到入口
判断环就是老一套，用2倍速指针就行，这个之前的题目里头有；
计算环的大小k，环的大小么，刚才相碰的地方找个指针绕圈圈走。记个数，再碰到相遇地点就是环大小了；
找到入口后，我们有两个普通速度的指针pA,pB，让其中一个pA先往前走k步，然后两个一起开始挪动，可以知道，如果pA与pB又相遇了，那相遇点就是环的入口了。此时pA比pB刚好多走了一整圈。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* meetingNode(ListNode* head){
        //Find the meeting node
        if(head == NULL)
            return NULL;
        ListNode* slow = head->next;
        if(slow == NULL)
            return NULL;
        ListNode* fast = slow->next;
        while(fast != NULL && slow != NULL){
            if (slow == fast)
                return slow;
            slow = slow->next;
            fast = fast->next;
            if(fast != NULL)
                fast = fast->next;
        }
        return NULL;
    }
    ListNode *detectCycle(ListNode *head) {
        ListNode* meet = meetingNode(head);
        if(meet == NULL)
            return NULL;
        //Get loop size
        ListNode* temp = meet->next;
        int count = 1;
        while(temp != meet){
            count++;
            temp = temp->next;
        }
        //Pick one pointer at start, move `count` steps forward
        temp = head;
        meet = head;
        while(count > 0){
            count--;
            meet = meet->next;
        }
        //Find the cycle start
        while(temp != meet){
            temp = temp->next;
            meet = meet->next;
        }
        return meet;
    }
};

Determine if a Sudoku is valid, according to: Sudoku Puzzles – The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

思路

行搜索、列搜索、sub-box搜索，根据规则来就行了

代码

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        set<char> workingSet;
        // Row
        char c;
        for(int row = 0; row<9; row++){
            workingSet.clear();
            for(int col=0; col<9; col++){
                c = board[row][col];
                if(c == '.')
                    continue;
                if(workingSet.count(c) > 0)
                    return false;
                workingSet.insert(c);
            }
        }
        // Col
        for(int col = 0; col<9; col++){
            workingSet.clear();
            for(int row=0; row<9; row++){
                c = board[row][col];
                if(c == '.')
                    continue;
                if(workingSet.count(c) > 0)
                    return false;
                workingSet.insert(c);
            }
        }
        // Sub-box
        for(int lPos=0; lPos < 9; lPos+=3){
            for(int tPos=0; tPos<9; tPos+=3){
                workingSet.clear();
                for(int i=0; i<3; i++){
                    for(int j=0; j<3; j++){
                        c = board[lPos+i][tPos+j];
                        if(c == '.')
                            continue;
                        if(workingSet.count(c) > 0)
                            return false;
                        workingSet.insert(c);
                    }
                }
            }
        }
        return true;
    }
};

Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number.

思路

《剑指Offer》上的原题34，所以就说个大概吧。
下一个丑数是之前的丑数（最初是1）乘以2、3或者5得到的，所以下一个丑数就是之前的某个数乘出来的。这样的找法比从1到n一个个判断是不是丑数高效很多，不然每个数都要去除个2、3、5判断一下。
由于要管次序问题，所以安排三个指针，分别记录乘以2、3、5后不超过当前最大丑数的位置，假设是p2, p3, p5，下一次找下个丑数的时候，从(p2)2、(p3)3、(p5)5里头找到个最小的，加在数组最后面，然后更新三个指针的值，如此往复……

代码

class Solution {
public:
    int nthUglyNumber(int n) {
        if(n <= 0)
            return 0;
        int* uglyAry = new int[n];
        uglyAry[0] = 1;
        int nextPos = 1;
        int *pNextUgly2 = uglyAry;
        int *pNextUgly3 = uglyAry;
        int *pNextUgly5 = uglyAry;
        while(nextPos < n){
            int nextUgly = min3(*pNextUgly2 * 2, *pNextUgly3 * 3, *pNextUgly5 * 5);
            uglyAry[nextPos] = nextUgly;
            //Move forward to find next possible candidates
            while(*pNextUgly2 * 2 <= nextUgly)
                pNextUgly2++;
            while(*pNextUgly3 * 3 <= nextUgly)
                pNextUgly3++;
            while(*pNextUgly5 * 5 <= nextUgly)
                pNextUgly5++;
            nextPos++;
        }
        int ugly = uglyAry[n-1];
        delete []uglyAry;
        return ugly;
    }
    int min3(int n1, int n2, int n3){
        int min = n1<n2?n1:n2;
        min = min<n3?min:n3;
        return min;
    }
};

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> results;
        vector<int> path;
        binaryTreePaths(root, path, results);
        return results;
    }
    void binaryTreePaths(TreeNode* root, vector<int> path, vector<string>& results){
        if(root == NULL){
            //Error
            return;
        }
        path.push_back(root->val);
        if(root->left == NULL && root->right == NULL) {
            //Leaf
            string result;
            int pSize = path.size();
            for(int i=0; i<pSize; i++){
                result += to_string(path[i]);
                if(i != pSize - 1)
                    result += "->";
            }
            results.push_back(result);
        } else {
            if(root->left != NULL)
                binaryTreePaths(root->left, path, results);
            if(root->right != NULL)
                binaryTreePaths(root->right, path, results);
        }
    }
};