This is the 8th day of my participation in the August More Text Challenge

17. Print n digits from 1 to maximum

The title

Enter the number n to print out the largest n decimal digits in sequence. For example, if you type 3, you print 1, 2, 3 up to 999.

Example 1:

Input: n = 1 Output: [1,2,3,4,5,6,7,8,9]Copy the code

Description:

  • Return a list of integers instead of printing
  • N is a positive integer

Methods a

Simulation: The first time I did it, I didn’t think too much about it, and I really fit the simple label. After all, it refers to the Offer. After looking at the solution of the problem, sure enough, LeetCode has simplified the original problem, including large numbers.

class Solution { public int[] printNumbers(int n) { n = (int)Math.pow(10, n); int res[] = new int[n - 1]; for (int i = 0; i < n - 1; i ++ ) res[i] = i + 1; return res; }}Copy the code

Time complexity: O(10^n)

Space complexity: O(10^n)

Method 2

When n ==cur, return the string with the leading 0 removed instead of parsing back to Int

class Solution { int[] res; int index = 0; char[] num; public int[] printNumbers(int n) { res = new int[(int)Math.pow(10, n) - 1]; num = new char[n]; dfs(0, n); return res; } public void dfs(int cur, int n) { if (cur == n) { String tmp = String.valueOf(num); int i = 0; while(i < n && tmp.charAt(i) == '0') i ++; if (i == n) return ; tmp = tmp.substring(i); int curNum = Integer.parseInt(tmp); res[index ++] = curNum; return ; } for (char i = '0'; i <= '9'; i ++ ) { num[cur] = i; dfs(cur + 1, n); }}}Copy the code

Time complexity: O(10^n)

Space complexity: O(10^n)

18. Remove nodes from the list

The title

Given a head pointer to a one-way linked list and the value of a node to delete, define a function to delete that node.

Returns the head node of the deleted list.

Note: this question has been changed from the original question

Example 1:

Input: head = [4,5,1,9], val = 5 Output: [4,1,9]Copy the code

Example 2:

Input: head = [4,5,1,9], val = 1 Output: [4,5,9]Copy the code

Description:

  • They make sure that the values of the nodes in the list are different
  • If you’re using C or C++, you don’tfree 或 deleteThe node is deleted

Methods a

Naive method: two variables are introduced to point to the current node and the precursor node of the current node respectively. When the current node is equal to the target value, the successor of the precursor node points to the successor of the current node

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode p = dummy, q = head;
        while (q.val != val) {
            p = p.next;
            q = q.next;
        }
        p.next = q.next;
        return dummy.next;
    }
}
Copy the code

Time complexity: O(n)

Space complexity: O(1)

Note: Virtual headers are introduced to simplify judgment