526互联

11.20打卡

发布时间 2023-11-20 10:27:01作者: forever_fate

1. 格雷编码（89）

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

class Solution {
    public List<Integer> grayCode(int n) {
            List<Integer> res = new ArrayList<>(){{add(0);}};

            int head = 1;
            for(int i =0;i<n;i++){
                for(int k = res.size()-1;k>=0;k--){
                    res.add(head+res.get(k));
                   
                }
                 head <<=1;
            }
            return res;    }
}

2. 子集（90）

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
      List<Integer> cur = new ArrayList<>();
        dfssubsetsWithDup(nums,0,cur,res);
        return res;
    }

    private void dfssubsetsWithDup(int[] nums, int i, List<Integer> cur, List<List<Integer>> res) {
        res.add(new ArrayList<>(cur));
        for (int j = i; j <nums.length ; j++) {
            if(j>i && nums[j]==nums[j-1])
                continue;
            cur.add(nums[j]);
            dfssubsetsWithDup(nums,j+1,cur,res);
            cur.remove(cur.size()-1);
        }
    
    }
}

3. 解码方法（91）

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

  • "AAJF" ，将消息分组为 (1 1 10 6)
  • "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数

class Solution {
    public int numDecodings(String s) {
  int n = s.length();
        s=" "+s;
        char[] cs = s.toCharArray();
        int[] f = new int[3];
        f[0]=1;
        for (int i = 1; i <cs.length ; i++) {
            f[i%3] = 0;
            int a = cs[i]-'0';
            int b = (cs[i-1]-'0')*10+(cs[i]-'0');
            if(1<=a && a<=9) f[i%3]=f[(i-1)%3];
            if(10<=b&& b<=26) f[i%3] += f[(i-2)%3];
        }
        return f[n%3];
    }
}

4. 反转链表（92）

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
  ListNode  dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i <left-1 ; i++) {
            pre=pre.next;
        }
        ListNode cur = pre.next;
        ListNode next=cur.next;
        for (int i = 0; i <right-left ; i++) {
            ListNode tmp = next.next;
            next.next = cur;
            cur = next;
            next =tmp;
            
        }
        pre.next.next =next;
        pre.next =cur;
       
        return dummy.next;
    }
}