链表

206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {};
};

class Solution {
public:
    //头插法 92题的特例(需要反转len(链表)-1次)
    ListNode *reverseList(ListNode *head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *cnt = head;
        int len = 0;
        while (cnt != nullptr) {
            len++;
            cnt = cnt->next;
        }
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy;
        for (int i = 1; i < len; i++) {
            ListNode *temp = head->next;
            head->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        return dummy->next;
    }

    // 递归
    ListNode *reverseList2(ListNode *head) {
        return reverse(head, nullptr);
    }

    ListNode *reverse(ListNode *cur, ListNode *pre) {
        if (cur == nullptr)
            return pre;
        ListNode *temp = cur->next;
        cur->next = pre;
        return reverse(temp, cur);
    }
};

92. 反转链表 II 重点

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
    /**
     * 思路:(头插法)head表示需要反转的当前节点头,pre表示反转的当前节点的前驱节点
     * 反转n-m次,每一次我们将head的next节点移动到需要反转链表部分的首部,需要反转链表部分剩余节点依旧保持相对顺序即可
     * 比如1->2->3->4->5,m=1,n=5
     * 第一次反转:1(head) 2(next) 3 4 5 反转为 2 1 3 4 5
     * 第二次反转:2 1(head) 3(next) 4 5 反转为 3 2 1 4 5
     * 第三次发转:3 2 1(head) 4(next) 5 反转为 4 3 2 1 5
     * 第四次反转:4 3 2 1(head) 5(next) 反转为 5 4 3 2 1
     * */
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy;
        for (int i = 1; i < m; i++)
            pre = pre->next;
        head = pre->next;
        for (int i = m; i < n; i++) {
            //下面两步相当于删除head->next(temp)
            ListNode *temp = head->next;
            head->next = temp->next;
            //下面两步相当于在pre后面插入head->next(temp)
            temp->next = pre->next;
            pre->next = temp;
        }
        //此时head为最开始的第一个节点,即反转后的尾节点
        return dummy->next;
    }
};

25. K 个一组翻转链表

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例 :

给定这个链表:1->2->3->4->5

当 k = 2 时,应当返回: 2->1->4->3->5

当 k = 3 时,应当返回: 3->2->1->4->5

说明 :

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
    /**依然是92题的思路*/
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if (k <= 0 || head == nullptr)
            return head;
        ListNode *dummy = new ListNode(0);
        ListNode *pre = dummy;
        dummy->next = head;
        int len = 0;
        while (head != nullptr) {
            len++;
            head = head->next;
        }
        head = dummy->next;
        for (int i = 0; i < len / k; i++) {
            for (int j = 1; j < k; j++) {//只反转k-1次
                ListNode *temp = head->next;
                head->next = temp->next;
                temp->next = pre->next;
                pre->next = temp;
            }
            pre = head;//head指向
            head = pre->next;
        }
        return dummy->next;
    }
};

23. 合并K个排序链表

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {};
};

struct cmp {
    bool operator()(ListNode *a, ListNode *b) {
        return a->val > b->val;//小根堆
    }
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode *, vector<ListNode *>, cmp> pq;
        for (auto list:lists) {
            if (list != nullptr)
                pq.push(list);
        }
        ListNode *ans = new ListNode(0);
        ListNode *temp = ans;
        while (!pq.empty()) {
            auto cur = pq.top();
            pq.pop();
            temp->next = cur;
            temp = temp->next;
            if (cur->next != nullptr)
                pq.push(cur->next);
        }
        return ans->next;
    }
};
编写一个程序,找到两个单链表相交的起始节点。
class Solution {
    /**法一:走的长度一样*/
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr)
            return nullptr;
        ListNode *p = headA;
        ListNode *q = headB;
        while (q != p) {
            if (q == nullptr)
                q = headA;
            else
                q = q->next;

            if (p == nullptr)
                p = headB;
            else
                p = p->next;
        }
        return p;
    }

    /**方法二:转化为142.将headA或者headB变为环,就变成了环形链表找相交点。但是会改变其中一个链表的结构*/
    ListNode *getIntersectionNode2(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr)
            return nullptr;
        ListNode *p = headA;
        while (p->next != nullptr) {
            p = p->next;
        }
        p->next = headA;
        //现在headA就是环形链表了
        ListNode *slow = headB;
        ListNode *fast = headB;
        bool flag = false;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                flag = true;
                break;
            }
        }
        if (!flag)
            return nullptr;
        //相交点为slow==fast
        ListNode *q = headB;
        while (q != slow) {
            q = q->next;
            slow = slow->next;
        }
        return q;
    }
};

138. 复制带随机指针的链表

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。 

 

示例:



输入:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释:
节点 1 的值是 1,它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2,它的下一个指针指向 null,随机指针指向它自己。
 

提示:

你必须返回给定头的拷贝作为对克隆列表的引用。
package gongel_first;

import java.util.HashMap;
import java.util.Map;

class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {
    }

    public Node(int _val, Node _next, Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
}

public class Onehundred_thirtyEight {
    /**
     * 第一步,将原链表从头遍历,然后将每个节点深拷贝一份(这里的深拷贝意思:创建一个新的节点,里面的值用原节点的值一样),然后将这个新的节点放入哈希表中,其中key为原节点,value为新的节点;
     * 第二步,从头再遍历原链表,每次遍历从哈希表中取以当前节点为key的新节点,获得新的节点之后,新的节点的next为当前节点的next为key的新节点,新的节点的random也是如此
     */
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node p = head;
        while (p != null) {
            Node newListNode = new Node(p.val);
            //以当前的原节点为key,新节点为value
            map.put(p, newListNode);
            p = p.next;
        }
        p = head;
        while (p != null) {
            //获取以当前的原节点为key的新节点
            Node q = map.get(p);
            //新节点的next
            q.next = map.get(p.next);
            //新节点的random
            q.random = map.get(p.random);
            p = p.next;
        }
        return map.get(head);
    }
}
class Solution {
public:
    Node *copyRandomList(Node *head) {
        if (head == nullptr)
            return nullptr;
        map<Node *, Node *> copy;
        Node *p = head;
        while (p != nullptr) {
            Node *node = new Node(p->val);
            copy[p] = node;
            p = p->next;
        }
        p = head;
        while (p != nullptr) {
            auto node = copy[p];
            node->next = copy[p->next];
            node->random = copy[p->random];
            p = p->next;
        }
        return copy[head];
    }
};

148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5
//归并排序版本
class Solution {
    /**吸收21和109题二者之精华*/
public:
    ListNode *sortList(ListNode *head) {
        return merge_sort(head);
    }

    ListNode *merge_sort(ListNode *head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *slow = head;
        ListNode *mid = head->next;
        ListNode *fast = head->next->next;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            mid = mid->next;
            fast = fast->next->next;
        }
        //中间节点为mid
        slow->next = nullptr;
        ListNode *left = merge_sort(head);
        ListNode *right = merge_sort(mid);
        return merge(left, right);

    }

    ListNode *merge(ListNode *p, ListNode *q) {
        if (p == nullptr)
            return q;
        if (q == nullptr)
            return p;
        if (p->val <= q->val) {
            p->next = merge(p->next, q);
            return p;
        } else {
            q->next = merge(p, q->next);
            return q;
        }
    }

};
//快排版本
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        return quick_sort(dummy, nullptr);
    }

    ListNode *quick_sort(ListNode *head, ListNode *end) {
        if (head == nullptr || head->next == end || head->next->next == end)
            return head;
        ListNode *temp_head = new ListNode(-1);
        //将小于pivot的值放在临时链表中
        ListNode *temp = temp_head;
        //current为当前指针
        ListNode *current = head->next;
        //pivot为枢轴值
        ListNode *pivot = head->next;

        while (current->next != end) {
            if (current->next->val < pivot->val) {
                temp->next = current->next;
                temp = temp->next;
                current->next = current->next->next;
            } else {
                current = current->next;
            }
        }
        //temp已经走到临时表的末尾,由于临时表都比pivot小,那么剩下的原始链表中的值都比临时表的值大,所以应该在其后
        temp->next = head->next;
        //接回来,让head重新代表第一轮sort后的新链表
        head->next = temp_head->next;
        quick_sort(head, pivot);//不会处理到pivot
        quick_sort(pivot, end);//不会处理到pivot
        return head->next;
    }
};

234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?。
class Solution {
    /**
     * 模板题
     * 三指针法:中间指针停留在奇数中间或者偶数中间的第二个节点(类似于109,148)
     * 反转需要带着中间节点一起反转,且前半段链表必须断链
     * 1 2 2 1----(slow=2,mid=2)--->1 2 1 2---->1 2 (断链) 1 2
     * 1 2 1---(slow=1,mid=2)--->1 1 2----->1 (断链) 1 2
     * */
public:
    bool isPalindrome(ListNode *head) {
        if (head == nullptr || head->next == nullptr)
            return true;
        ListNode *slow = head;
        ListNode *mid = head->next;
        ListNode *fast = head->next->next;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            mid = mid->next;
            fast = fast->next->next;
        }
        int len = 0;
        ListNode *temp = mid;
        while (temp != nullptr) {
            len++;
            temp = temp->next;
        }
        //将mid及其后面的链表反转,slow->next=mid
        ListNode *pre = slow;
        for (int i = 1; i < len; i++) {
            temp = mid->next;
            mid->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        mid = pre->next;
        //前半段链表断链
        slow->next = nullptr;
        while (head != nullptr && mid != nullptr) {
            if (head->val != mid->val)
                return false;
            head = head->next;
            mid = mid->next;
        }
        return true;
    }
};

环形链表

删除排序链表中的相同元素

return home

组合

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
package gongel_first;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Thirty_nine {
    /**
     * 递归+回溯
     * 增加了一个start变量。下轮递归还是从当前元素开始,表示元素可被重复使用,但是不会使用当前元素之前的元素
     */
    public void dfs(int[] candicates, int target, int start, List<Integer> temp, List<List<Integer>> ans) {
        if (target < 0)
            return;
        if (target == 0) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i < candicates.length && candicates[i] <= target; i++) {
            temp.add(candicates[i]);
            dfs(candicates, target - candicates[i], i, temp, ans);//还从i开始是因为可以重复使用
            temp.remove(temp.size() - 1);
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        if (candidates == null || candidates.length == 0)
            return ans;
        Arrays.sort(candidates);
        dfs(candidates, target, 0, temp, ans);
        return ans;
    }
}
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        if (candidates.empty())
            return vector<vector<int>>();
        vector<int> temp;
        vector<vector<int>> ans;
        sort(candidates.begin(), candidates.end());
        helper(candidates, temp, ans, target, 0);
        return ans;
    }

    void helper(vector<int> &candidates, vector<int> &temp, vector<vector<int>> &ans, int target, int start) {
        if (target < 0)
            return;
        if (target == 0) {
            ans.push_back(temp);
            return;
        }
        for (int i = start; i < candidates.size() && candidates[i] <= target; i++) {
            temp.push_back(candidates[i]);
            helper(candidates, temp, ans, target - candidates[i], i);
            temp.pop_back();
        }
    }
};

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]
package gongel_first;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Forty {
    /**
     * 递归+回溯
     * 增加了一个start变量,下轮递归还是从start+1开始,表示元素只可以被使用一次
     */
    public void dfs(int[] candicates, int target, int start, List<Integer> temp, List<List<Integer>> ans) {
        if (target < 0)
            return;
        if (target == 0) {
            List<Integer> tem = new ArrayList<>(temp);
            if (!ans.contains(tem))//去重
                ans.add(tem);
            return;
        }
        for (int i = start; i < candicates.length && candicates[i] <= target; i++) {
            temp.add(candicates[i]);
            dfs(candicates, target - candicates[i], i + 1, temp, ans);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        if (candidates == null || candidates.length == 0)
            return ans;
        dfs(candidates, target, 0, temp, ans);
        return ans;
    }
}
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
        if (candidates.empty())
            return vector<vector<int>>();
        vector<int> temp;
        set<vector<int>> ans;
        sort(candidates.begin(), candidates.end());
        helper(candidates, temp, ans, target, 0);
        return vector<vector<int>>(ans.begin(), ans.end());
    }

    void helper(vector<int> &candidates, vector<int> &temp, set<vector<int>> &ans, int target, int start) {
        if (target < 0)
            return;
        if (target == 0) {
            ans.insert(temp);
            return;
        }
        for (int i = start; i < candidates.size() && candidates[i] <= target; i++) {
            temp.push_back(candidates[i]);
            helper(candidates, temp, ans, target - candidates[i], i + 1);
            temp.pop_back();
        }
    }
};

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

说明:

所有数字都是正整数。
解集不能包含重复的组合。 
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
package gongel_first;

import java.util.ArrayList;
import java.util.List;

public class Twohundred_sixteen {
    /**
     * 递归+回溯
     */
    public void dfs(List<List<Integer>> ans, List<Integer> temp, int k, int n, int start) {
        if (n < 0)
            return;
        if (n == 0 && temp.size() == k) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i <= 9; i++) {
            temp.add(i);
            dfs(ans, temp, k, n - i, i + 1);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        if (k <= 0 || n <= 0)
            return ans;
        dfs(ans, temp, k, n, 1);
        return ans;
    }
}
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        if (k < 0)
            return vector<vector<int>>();
        vector<int> temp;
        vector<vector<int>> ans;
        helper(temp, ans, 1, k, n);
        return ans;
    }

    void helper(vector<int> &temp, vector<vector<int>> &ans, int start, int k, int n) {
        if (temp.size() > k || n < 0)
            return;
        if (temp.size() == k && n == 0) {
            ans.push_back(temp);
            return;
        }
        for (int i = start; i <= 9 && i <= n; i++) {
            temp.push_back(i);
            helper(temp, ans, i + 1, k, n - i);
            temp.pop_back();
        }
    }
};

377. 组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意,顺序不同的序列被视作不同的组合。

因此输出为 7。
进阶:
如果给定的数组中含有负数会怎么样?
问题会产生什么变化?
我们需要在题目中添加什么限制来允许负数的出现?
public class Threehundred_seventySeven {
    /**
     * 和518找零钱差不多,但这里的组合中元素顺序不同都算一种:(1,2,1)和(1,1,2)不同
     * 涉及顺序的完全背包问题
     */
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || target < 0)
            return 0;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}
class Solution {
public:
    /**
     * 会超时*/
    int combinationSum4(vector<int> &nums, int target) {
        if (nums.empty())
            return 0;
        int ans = 0;
        sort(nums.begin(), nums.end());
        helper(nums, target, ans);
        return ans;
    }

    void helper(vector<int> &nums, int target, int &ans) {
        if (target < 0)
            return;
        if (target == 0) {
            ans++;
            return;
        }
        for (int i = 0; i < nums.size() && nums[i] <= target; i++)
            helper(nums, target - nums[i], ans);
    }

    int combinationSum4_two(vector<int> &nums, int target) {
        if (nums.empty())
            return 0;
        vector<LL> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num:nums) {
                if (i >= num)
                    dp[i] += dp[i - num];
            }
        }
        return dp.back();
    }
};

77. 组合

给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
public class Solution {
    private void dfs(List<List<Integer>> ans, List<Integer> temp, int start, int k, int n) {
        if (temp.size() == k) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i < n + 1; i++) {
            temp.add(i);
            dfs(ans, temp, i + 1, k, n);
            temp.remove(temp.size() - 1);
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        if (k <= 0 || n <= 0)
            return new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        dfs(ans, temp, 1, k, n);
        return ans;
    }
}
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        if (k < 0)
            return vector<vector<int>>();
        vector<int> temp;
        vector<vector<int>> ans;
        helper(ans, temp, n, k, 1);
        return ans;
    }

    void helper(vector<vector<int>> &ans, vector<int> &temp, int n, int k, int start) {
        if (temp.size() > k)
            return;
        if (temp.size() == k) {
            ans.push_back(temp);
            return;
        }
        for (int i = start; i <= n; i++) {
            temp.push_back(i);
            helper(ans, temp, n, k, i + 1);
            temp.pop_back();
        }
    }
};

杨辉三角

118. 杨辉三角

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。



在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
package gongel_first;

import java.util.ArrayList;
import java.util.List;

public class Onehundred_eighteen {
    /**
     * 法一比较傻,硬怼
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        if (numRows <= 0)
            return ans;
        List<Integer> temp = new ArrayList<>();
        temp.add(1);
        ans.add(temp);
        if (numRows == 1) {
            return ans;
        }
        temp = new ArrayList<>();
        temp.add(1);
        temp.add(1);
        ans.add(temp);
        if (numRows == 2) {
            return ans;
        }

        for (int i = 3; i <= numRows; i++) {
            List<Integer> te = new ArrayList<>();
            te.add(1);
            te.add(1);
            int k = 1;
            List<Integer> mid = ans.get(i - 2);
            for (int j = 0; j < mid.size() - 1; j++) {
                te.add(k, mid.get(j) + mid.get(j + 1));
            }
            ans.add(te);
        }
        return ans;
    }

    /**
     * 法二:二维数组
     */
    public List<List<Integer>> generate2(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        int[][] dp = new int[numRows][numRows];
        for (int i = 0; i < numRows; i++) {
            List<Integer> temp = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i)
                    dp[i][j] = 1;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                temp.add(dp[i][j]);
            }
            ans.add(temp);
        }
        return ans;
    }
}

119. 杨辉三角 II

给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。



在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

输入: 3
输出: [1,3,3,1]
进阶:

你可以优化你的算法到 O(k) 空间复杂度吗?
package gongel_first;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Onehundred_nineteen {
    /**
     * */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> ans = new ArrayList<>(Collections.nCopies(rowIndex + 1, 1));
        for (int line = 0; line <= rowIndex; line++) {
            for (int j = line - 1; j > 0; j--) {
                ans.set(j, ans.get(j - 1) + ans.get(j));
            }
        }
        return ans;
    }
}

 

Java List部分操作

1.List修改值

E set(int index, E element)

2.Collections.fill(List<T>,T element)

替换list中所有元素

3.提前声明长度并填充指定值

List<Integer> ans = new ArrayList<>(Collections.nCopies(rowIndex + 1, 1));
   public List<Integer> getRow(int rowIndex) {
        List<Integer> ans = new ArrayList<>(Collections.nCopies(rowIndex + 1, 1));
        for (int line = 0; line <= rowIndex; line++) {
            for (int j = line - 1; j > 0; j--) {
                ans.set(j, ans.get(j - 1) + ans.get(j));
            }
        }
        System.out.println(ans);
        //[1, 3, 3, 1]
        Collections.fill(ans, 888);
        System.out.println(ans);
        //[888, 888, 888, 888]
        return ans;
    }

ref:Collections常用方法总结