Scribd Logo
Upload

Welcome to Scribd!

  • 10 views

    Suba

    Uploaded by

    subashini udayakumar
    The document discusses methods for determining if a path of line segments crosses itself. It defines three cases where the path could cross: 1) if a line crosses the one three steps before it, 2) if a line crosses the one four steps before when their y-values are equal, and 3) if a line crosses the one five steps before under certain conditions.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Suba

    Uploaded by

    subashini udayakumar
    10 views7 pages
    The document discusses methods for determining if a path of line segments crosses itself. It defines three cases where the path could cross: 1) if a line crosses the one three steps before it, 2) if a line crosses the one four steps before when their y-values are equal, and 3) if a line crosses the one five steps before under certain conditions.

    Original Title

    suba

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses methods for determining if a path of line segments crosses itself. It defines three cases where the path could cross: 1) if a line crosses the one three steps before it, 2) if a line crosses the one four steps before when their y-values are equal, and 3) if a line crosses the one five steps before under certain conditions.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    10 views7 pages

    Suba

    Uploaded by

    subashini udayakumar
    The document discusses methods for determining if a path of line segments crosses itself. It defines three cases where the path could cross: 1) if a line crosses the one three steps before it, 2) if a line crosses the one four steps before when their y-values are equal, and 3) if a line crosses the one five steps before under certain conditions.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 7

    1.

    class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    int ac = 0;
    int bc = 0;
    ListNode a = headA;
    ListNode b = headB;
    while(a != null){
    ac++;
    a = a.next;
    }
    while(b != null){
    bc++;
    b = b.next;
    }
    while(ac > bc){
    ac--;
    headA = headA.next;
    }
    while(bc > ac){
    bc--;
    headB = headB.next;
    }

    while(headA != headB){
    headA = headA.next;
    headB = headB.next;
    }
    return headA;
    }
    }
    2. class Solution {
    public:
    string convertToTitle(int columnNumber) {
    string res = "";

    while (columnNumber > 0) {


    columnNumber--;
    res = char((columnNumber % 26) + 'A') + res;
    columnNumber /= 26;
    }

    return res;
    }
    };

    3. class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
    ans, pos = 0, 0
    for letter in reversed(columnTitle):
    digit = ord(letter)-64
    ans += digit * 26**pos
    pos += 1

    return ans

    4. class Solution {
    public:
    int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
    for (int j = 1; j * j <= i; ++j){
    dp[i] = min(dp[i], dp[i - j * j] + 1);
    }
    }
    return dp[n];
    }
    };

    5. class Solution:

    def __init__(self):
    self.x = None

    def price(self, num):


    res = 0
    for i in range(self.x - 1, 64, self.x):
    numModTwoTimesI = num % (1 << (i + 1))
    res += ((num - numModTwoTimesI) >> 1) + max(numModTwoTimesI - (1 <<
    i), 0)
    return res

    def findMaximumNumber(self, k: int, x: int) -> int:


    self.x = x
    return bisect_right(range((1 << 63) - 1), k, key=self.price) - 2

    6. class Solution {

    public int numberOfPairs(int[][] points) {


    int maxi = 0;
    for(int i=0;i<points.length;i++)
    {
    for(int j=0;j<points.length;j++)
    {
    if(i==j || points[i][0]>points[j][0] || points[i][1]<points[j][1])
    {
    continue;
    }
    int k = 0;
    for(;k<points.length;k++)
    {
    if(k==i || k==j)
    {
    continue;
    }
    if(points[k][1] <= points[i][1] && points[k][1] >= points[j]
    [1] && points[k][0] <= points[j][0] && points[k][0] >= points[i][0]) {
    break;
    }
    }
    if(k==points.length)
    {
    maxi++;
    }
    }
    }
    return maxi;
    }
    }

    7. class Solution:

    def minimumArrayLength(self, nums: List[int]) -> int:


    nums.sort()

    cnt = 1
    for num in nums[1:]:
    if num == nums[0]: cnt += 1
    else:
    if num % nums[0] != 0: return 1
    return (cnt+1)//2

    8. class Solution {
    public:
    vector<string> ans;

    string space(int c) {
    return string(c, ' ');
    }

    vector<string> print_wIdx(vector<string>& words, vector<pair<vector<int>,


    int>>& wIdx, int maxWidth) {
    for (int i = 0; i < wIdx.size(); i++) {
    int numWords = wIdx[i].first.size();
    int totalLen = wIdx[i].second;
    int totalSpaces = maxWidth - totalLen;
    int numGaps = numWords - 1;
    int numSpaces = 1;
    int remainingSpaces = 0;

    if (numGaps > 0) {
    numSpaces = totalSpaces / numGaps;
    remainingSpaces = totalSpaces % numGaps;
    }

    string line = words[wIdx[i].first[0]]; // Start with the first word


    for (int j = 1; j < numWords; j++) {
    if (i == wIdx.size() - 1) {
    // Last line, left justify
    line += space(1);
    }
    else {
    line+= space(numSpaces+(remainingSpaces>0?1:0));
    remainingSpaces--;
    }
    line+= words[wIdx[i].first[j]];
    }

    if (line.size() < maxWidth)


    line+= space(maxWidth-line.size());

    ans.push_back(line);
    }

    return ans;
    }

    vector<string> fullJustify(vector<string>& words, int maxWidth) {


    int n = words.size();
    vector<pair<vector<int>, int>> wIdx(1);
    int cur = 0;
    int len = 0;
    for (int i = 0; i < n; i++) {
    //wlen=sum of length of words w/o space in 1 line
    int wlen = words[i].size();
    len += wlen;
    if (len > maxWidth) {
    wIdx.push_back({{i}, wlen});
    cur++;
    len = wlen;
    }
    else {
    wIdx[cur].first.push_back(i);
    wIdx[cur].second += wlen;
    }
    len++; //at least 1 whitespace between words
    }

    return print_wIdx(words, wIdx, maxWidth);


    }
    };

    9. #include <vector>
    #include <climits>

    class Solution {
    public:
    int calculateMinimumHP(vector<vector<int>>& d) {
    int n = d.size();
    int m = d[0].size();

    vector<vector<int>> dp(n, vector<int>(m, 0));

    return helper(d, n, m, 0, 0, dp);


    }
    int helper(vector<vector<int>>& d, int n, int m, int row, int col,
    vector<vector<int>>& dp) {
    // base condition 1
    if (row == n - 1 && col == m - 1) {
    return max(1, 1 - d[row][col]);
    }

    // base condition 2
    if (row >= n || col >= m) {
    return INT_MAX;
    }

    if (dp[row][col] != 0) {
    return dp[row][col];
    }

    int right = helper(d, n, m, row, col + 1, dp);


    int down = helper(d, n, m, row + 1, col, dp);

    // Calculate the minimum health needed at the current position


    dp[row][col] = min(right, down) - d[row][col];

    // Ensure the minimum health is at least 1


    dp[row][col] = max(1, dp[row][col]);

    return dp[row][col];
    }
    };

    10. class Solution:


    def isSelfCrossing(self, x: List[int]) -> bool:
    # If there are less than 4 values in the array, the path can't cross itself
    if len(x) <= 3:
    return False

    # Loop through the array starting from the 3rd index


    for i in range(3, len(x)):
    # Case 1: current line crosses the line 3 steps before it
    # _______
    # | |
    # | |
    # _______|_| <-- current line
    # | |
    # | |
    # || <-- line 3 steps before
    if x[i - 2] <= x[i] and x[i - 1] <= x[i - 3]:
    return True

    # Case 2: current line crosses the line 4 steps before it


    # _____
    # | |
    # | |
    # | |________
    # | |
    # | |
    # |_| <-- current line
    # line 4 steps before
    if i >= 4 and x[i - 1] == x[i - 3] and x[i - 2] <= x[i] + x[i - 4]:
    return True

    # Case 3: current line crosses the line 5 steps before it


    # ______
    # | |
    # | |
    # || <-- line 5 steps before
    # |
    # |
    # _____|______
    # | |
    # | |
    # || <-- current line
    if i >= 5 and x[i - 4] <= x[i - 2] and x[i - 2] <= x[i] + x[i - 4] and x[i -
    1] <= x[i - 3] and x[i - 3] <= x[i - 1] + x[i - 5]:
    return True

    # If no crossing has been found, the path does not cross itself
    return False

    You might also like