思路
(KMP) $O(n+m)$

具体过程如下：

1. next[i]记录子串ha[1, 2, , , i - 1, i]的最长相等前后缀的前缀最后一位下标，或者说是子串的最长相等前后缀的长度。
2. 预处理出next数组。
3. 遍历字符串ha：
   ● 当ha字符串和ne字符串发生失配时，根据next数组回退到其他位置。
   ● 当匹配ne字符串的终点时，用匹配终点i减去字符串ne的长度m即是答案。

KMP核心思路如下图所示：

时间复杂度分析： KMP 算法的时间复杂度为 $O(n+m)$。

C++代码

class Solution {
public:
    int strStr(string ha, string ne) {
        int n = ha.size(), m = ne.size();
        if(m == 0) return 0;
        vector<int> next(m + 1);
        ha = ' ' + ha ,ne = ' ' + ne;
        for(int i = 2, j = 0; i <= m; i++){
            while(j && ne[i] != ne[j + 1]) j = next[j];
            if(ne[i] == ne[j + 1]) j++;
            next[i] = j;
        }
        for(int i = 1, j = 0; i <= n; i++){
            while(j && ha[i] != ne[j + 1]) j = next[j];
            if(ha[i] == ne[j + 1]) j++;
            if(j == m){
                return i - m;
            }
        }
        return -1;
    }
};

Java代码

class Solution {
    public int strStr(String ha, String ne) {
        if (ha.isEmpty()) return 0;
        int n = ha.length(), m = ne.length();
        ha = " " + ha;
        ne = " " + ne;
        int[] next = new int[m + 1];
        for (int i = 2, j = 0; i <= m; ++i) {
            while (j > 0 && ne.charAt(i) != ne.charAt(j + 1)) j = next[j];
            if (ne.charAt(i) == ne.charAt(j + 1)) j++;
            next[i] = j;
        }
        for (int i = 1, j = 0; i <= n; ++i) {
            while (j > 0 && ha.charAt(i) != ne.charAt(j + 1)) j = next[j];
            if (ha.charAt(i) == ne.charAt(j + 1)) j++;
            if (j == m) {
                return i - m;
            }
        }
        return -1;
    }
}

Go代码

func strStr(ha string, ne string) int {
    if len(ne) == 0 {
        return 0
    }
    n, m := len(ha), len(ne)
    ha, ne = " " + ha, " " + ne
    next := make([]int, m + 1)
    for i, j := 2, 0; i <= m; i++ {
        for j > 0 && ne[i] != ne[j + 1] {
            j = next[j]
        }
        if ne[i] == ne[j+1] {
            j++
        }
        next[i] = j
    }
    for i, j := 1, 0; i <= n; i++ {
        for j > 0 && ha[i] != ne[j + 1] {
            j = next[j]
        }
        if ha[i] == ne[j + 1] {
            j++
        }
        if j == m {
            return i - m
        }
    }
    return -1
}

思路
(数组) $O(n)$

取第一个数或者只要当前数和前一个数不相等时，我们就取当前数（相当于重复元素取最后一个）。

C++代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 0;
        for(int i = 0; i < nums.size(); i++){
            if(!i || nums[i] != nums[i - 1])
                nums[k++] = nums[i];
        }
        return k;
    }
};

Java代码

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 0;
        for(int i = 0; i < nums.length; i++){
            if(i == 0 || nums[i] != nums[i - 1])
                nums[k++] = nums[i];
        }
        return k;
    }
}

Go代码

func removeDuplicates(nums []int) int {
    k := 0
    for i := 0; i < len(nums); i++ {
        if i == 0 || nums[i] != nums[i - 1] {
            nums[k] = nums[i]
            k++
        }
    }
    return k
}

欢迎加入力扣算法交流群，一起组队刷题！！！

思路
(链表) $O(n)$

具体操作，如图所示，黑色表示当前原始状况，红色表示操作状况

1. 将后k个元素进行倒序操作，共操作k - 1次，详细操作看代码（注意：需要确保有k个元素才操作）
2. 将后k个元素倒序后的序列的尾部指向后k + 1的元素
3. 将p->next指向倒序后的序列的头部
4. 更新p指针的位置，即指向倒序后的序列的尾部

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto dummy =  new ListNode(-1);
        dummy->next = head;
        for(auto p = dummy; ;)
        {
            auto q = p;
            for(int i = 0;  i < k && q; i++) q = q->next;
            if(!q) break;
            auto a = p->next,b = a->next;
            for(int i = 0; i < k - 1; i++)
            {
                auto next = b->next;
                b->next = a;
                a = b, b = next;
            }
            auto c = p->next;
            c->next = b,p->next = a;
            p = c;
        }
        return dummy->next;
    }
};

Java代码

/**
 * 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 reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next= head;
        for(ListNode p = dummy;;)
        {
            ListNode q = p;
            for(int i = 0;i < k && q != null; i++) q = q.next;
            if(q == null)  break;
            ListNode a = p.next, b = a.next;
            for(int i = 0; i < k - 1; i++)
            {
                ListNode next = b.next;
                b.next = a;
                a = b;
                b = next;
            }
            ListNode c = p.next;
            c.next = b;
            p.next = a;
            p = c;
        }
        return dummy.next;
    }
}

Go代码

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Val : -1, Next : nil}
    dummy.Next = head
    p := dummy
    for p.Next != nil {
        q := p
        for i := 0; i < k && q != nil; i++ {
            q = q.Next
        }
        if q == nil {
            break
        }
        a := p.Next
        b := a.Next
        for i := 0; i < k - 1; i++ {
            next := b.Next
            b.Next = a
            a = b
            b = next
        } 
        c := p.Next
        c.Next = b
        p.Next = a
        p = c
    }
    return dummy.Next
}

欢迎加入力扣算法交流群，一起组队刷题！！！

思路
(模拟) $O(n)$
题目给定一个链表，要求我们两两交换其中相邻的节点，并返回交换后的链表。由于可能会对头节点进行改变，因此需要建立一个虚拟头结点dummy，指向原来的头节点。

根据题意进行模拟迭代，两两交换相邻两个结点，如下图所示：

具体过程详解：
1、首先定义p = dummy，a = p->next，b = a->next。
2、遍历整个链表，第一步先将p的next指针指向b，即p->next = b。
3、然后将a的next指向b->next，即a->next = b->next。
4、最后将b的next指向a，即b->next = a。
经过上述操作以后，我们就成功交换了a，b节点，然后让p指向a节点，重复上述操作即可。

5、最后返回虚拟头节点的下一个节点

时间复杂度分析： $O(n)$，其中 $n$是链表的节点数量。

C++代码

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode*  dummy = new ListNode(-1);  //虚拟头节点
        dummy->next = head;
        for(auto p = dummy; p->next && p->next->next; )
        {
            auto a = p->next, b = a->next;
            p->next = b;
            a->next = b->next;
            b->next = a;
            p = a;
        }
        return dummy->next;
    }
};

Java代码

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        for(ListNode p = dummy; p.next != null && p.next.next != null;)
        {
            ListNode a = p.next;    //虚拟头节点
            ListNode b = a.next;
            p.next = b;
            a.next = b.next;
            b.next = a;
            p = a;
        }
        return dummy.next;
    }
}

Go代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Val : -1, Next : nil}
    dummy.Next = head
    p := dummy
    for p.Next != nil && p.Next.Next != nil {
        a := p.Next
        b := a.Next
        p.Next = b
        a.Next = b.Next
        b.Next = a
        p = a
    }
    return dummy.Next
}

欢迎加入力扣算法交流群，一起组队刷题！！！

思路

(优先队列） $O(nlogk)$

我们可以通过双路归并合并两个有序链表，但是这题要求对多个链表进行并操作。 其实和双路归并思路类似，我们分别用指针指向该链表的头节点，每次找到这些指针中值最小的节点，然后依次连接起来，并不断向后移动指针。

如何找到一堆数中的最小值？

用小根堆维护指向k个链表当前元素最小的指针，因此这里我们需要用到优先队列，并且自定义排序规则，如下：

struct cmp{ //自定义排序规则
    bool operator() (ListNode* a, ListNode* b){
        return a->val > b->val;  // val值小的在队列前
    }
};

具体过程如下：

1、定义一个优先队列，并让val值小的元素排在队列前。
2、新建虚拟头节点dummy，定义 cur指针并使其指向 dummy。
3、首先将k个链表的头节点都加入优先队列中。
4、当队列不为空时：

• 取出队头元素t（队头即为k个指针中元素值最小的指针）;
• 令cur 的 next 指针指向t，并让cur后移一位；
• 如果t的next指针不为空，我们将t->next加入优先队列中；

5、最后返回dummy->next。

时间复杂度分析： $O(nlogk)$，$n$表示的是所有链表的总长度，$k$表示$k$个排序链表。

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    struct cmp{   //自定义排序规则
        bool operator()(ListNode* a, ListNode * b){
            return a->val > b->val;  //元素值小的在前面
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        for(auto l : lists) if(l) heap.push(l);
        ListNode* dummmy = new ListNode(-1);
        ListNode* cur = dummmy;
        while(heap.size()){
            auto t = heap.top();
            heap.pop();
            cur = cur->next = t;
            if(t->next) heap.push(t->next);
        }
        return dummmy->next;
    }
};

Java代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>((x,y) -> (x.val - y.val));
        for(ListNode l : lists) if(l != null) heap.add(l);
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(!heap.isEmpty()){
            ListNode t = heap.poll();
            cur = cur.next = t;
            if(t.next != null) heap.add(t.next);
        }
        return dummy.next;
    }
}

Go代码

type minHeap []*ListNode

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) {
    *h = append(*h, x.(*ListNode))
}
func (h *minHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func mergeKLists(lists []*ListNode) *ListNode {
    h := new(minHeap)
    for i := 0; i < len(lists); i++ {
        if lists[i] != nil {
            heap.Push(h, lists[i])
        }
    }
    dummy := new(ListNode)
    cur := dummy
    for h.Len() > 0 {
        t := heap.Pop(h).(*ListNode)
        cur.Next = t
        cur = cur.Next
        if t.Next != nil {
            heap.Push(h, t.Next)
        }
    }
    return dummy.Next
}

欢迎加入力扣算法交流群，一起组队刷题！！！

分享题解，分享喜欢，点击右上角【+关注TA】，给个关注呗！

思路
(dfs) $O(C_{2n}^{n})$
首先我们需要知道一个结论，一个合法的括号序列需要满足两个条件：
● 1、左右括号数量相等
● 2、任意前缀中左括号数量 >= 右括号数量 （也就是说每一个右括号总能找到相匹配的左括号）

题目要求我们生成n对的合法括号序列组合，可以考虑使用深度优先搜索，将搜索顺序定义为枚举序列的每一位填什么，那么最终的答案一定是有n个左括号和n个右括号组成。

如何设计dfs搜索函数？

最关键的问题在于搜索序列的当前位时，是选择填写左括号，还是选择填写右括号 ？因为我们已经知道合法的括号序列任意前缀中左括号数量一定 >= 右括号数量，因此，如果左括号数量不大于 n，我们可以放一个左括号，等待一个右括号来匹配 。如果右括号数量小于左括号的数量，我们可以放一个右括号，来使一个右括号和一个左括号相匹配。

递归树如下：

递归函数设计

void dfs(int n ,int lc, int rc ,string str)

n是括号对数，lc是左括号数量，rc是右括号数量，str是当前维护的合法括号序列。
搜索过程如下：
● 1、初始时定义序列的左括号数量lc 和右括号数量rc都为0。
● 2、如果 lc < n，左括号的个数小于n，则在当前序列str后拼接左括号。
● 3、如果 rc < n && lc > rc , 右括号的个数小于左括号的个数，则在当前序列str后拼接右括号。
● 4、当lc == n && rc == n 时，将当前合法序列str加入答案数组res中。

时间复杂度分析：经典的卡特兰数问题，因此时间复杂度为 $O(\frac{1}{n+1}C_{2n}^{n}) = O(C_{2n}^n)$ 。

C++代码

class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0, "");
        return res;
    }

    void dfs(int n, int lc, int rc, string str){
        if(lc == n && rc == n){
            res.push_back(str);
            return ;
        }
        if(lc < n) dfs(n, lc + 1, rc, str + '(');
        if(rc < n && lc > rc) dfs(n, lc, rc + 1, str + ')');
    }
};

Java代码

class Solution {
    static List<String> res = new ArrayList<String>();  //记录答案 

    public List<String> generateParenthesis(int n) {
        res.clear();
        dfs(n, 0, 0, "");
        return res;
    }
    public void dfs(int n ,int lc, int rc ,String str) {
        if( lc == n && rc == n) res.add(str);   //递归边界
        else {
            if(lc < n) dfs(n, lc + 1, rc, str + "(");            //拼接左括号
            if(rc < n && lc > rc) dfs(n, lc, rc + 1, str + ")"); //拼接右括号
        }
    }
}

Go代码

var res []string

func generateParenthesis(n int) []string {
    res = make([]string, 0)
    dfs(n, 0, 0, "")
    return res
}

func dfs(n int, lc int, rc int, path string) {
    if lc == n && rc == n {
        res = append(res, path)
        return 
    } else {
        if lc < n {
            dfs(n, lc + 1, rc, path + "(")
        } 
        if rc < lc {
            dfs(n, lc, rc + 1, path + ")")
        }
    }

}

欢迎加入力扣算法交流群，一起组队刷题！！！

思路
(线性合并) $O(n)$
解题过程如下：
1、新建虚拟头节点 dummy，定义 cur指针并使其指向 dummy。
2、当l1 或 l2都不为为空时：
○ 若l1->val < l2->val，则令 cur 的 next 指针指向l1且l1后移；
○ 若l1->val >=l2->val，则令 cur 的 next 指针指向l2且 l2后移；
○ cur后移一步；
3、将剩余的 l1 或 l2 接到 cur 指针后边。
4、最后返回dummy->next。

时间复杂度分析： $O(n)$
C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if(l1) cur->next = l1;
        if(l2) cur->next = l2;
        return dummy->next;
    }
};

Java代码

/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            } 
            else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1 != null) cur.next = l1;
        if(l2 != null) cur.next = l2;
        return dummy.next;
    }
}

Go代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val : -1, Next : nil}
    cur := dummy
    for l1 != nil && l2 != nil {
        if(l1.Val < l2.Val){
            cur.Next = l1;
            l1 = l1.Next
        } else {
            cur.Next = l2;
            l2 = l2.Next
        }
        cur = cur.Next
    }
    if(l1 != nil) {
        cur.Next = l1
    }
    if(l2 != nil) {
        cur.Next = l2
    }
    return dummy.Next
}

思路
(排序 + 双指针） $O(n^2)$

1. 将整个nums数组按从小到大排好序
2. 枚举每个数，表示该数nums[i]已被确定，在排序后的情况下，通过双指针l，r分别从左边l = i + 1和右边r = n - 1往中间靠拢，找到nums[i] + nums[l] + nums[r] == 0的所有符合条件的搭配
3. 在找符合条件搭配的过程中，假设sum = nums[i] + nums[l] + nums[r]
   若sum > 0，则r往左走，使sum变小
   若sum < 0，则l往右走，使sum变大
   若sum == 0，则表示找到了与nums[i]搭配的组合nums[l]和nums[r]，存到res中
4. 判重处理
   确定好nums[i]时，l需要从i + 1开始
   当nums[i] == nums[i - 1]，表示当前确定好的数与上一个一样，需要直接跳过
   当找符合条件搭配时，即sum == 0,需要对相同的nums[l]和nums[r]进行判重处理

时间复杂度分析： $O(n^2)$。

C++代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n; i++){
            if(i && nums[i] == nums[i - 1]) continue;  //跳过相同的i，保证每次都是新开始
            int l = i + 1, r = n - 1;
            while(l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if(sum > 0) r--;
                else if(sum < 0) l++;
                else if(sum == 0){
                    res.push_back({nums[i], nums[l], nums[r]});
                    do l++; while(l < r && nums[l] == nums[l - 1]);  //跳过相同的l
                    do r--; while(l < r && nums[r] == nums[r + 1]);  //跳过相同的r
                }
            }
        }
        return res;
    }
};

Java代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for(int i = 0;i < n ;i ++){
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1,r = n - 1;
            while(l < r){
                int sum = nums[i] + nums[l] + nums[r];
                if(sum > 0) r--;
                else if(sum < 0) l++;
                else if(sum == 0){
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    do l ++; while(l < r && nums[l] == nums[l - 1]);
                    do r --; while(l < r && nums[r] == nums[r + 1]);
                }
            }
        }
        return res;
    }
}

Go代码

func threeSum(nums []int) [][]int {
    res := [][]int{}
    sort.Ints(nums)
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == nums[i - 1] {
            continue
        }
        l, r := i + 1, len(nums) - 1
        for l < r {
            sum := nums[i] + nums[l] + nums[r]
            if sum > 0 {
                r--
            }else if sum < 0 {
                l++
            }else if sum == 0 {
                res = append(res, []int{nums[i], nums[l], nums[r]})
                for l < r && nums[l] == nums[l + 1] {
                    l++
                }
                for l < r && nums[r] == nums[r - 1] {
                    r--
                }
                l++; r--
            }
        }
    }
    return res
}

欢迎加入力扣算法交流群，一起组队刷题！！！

思路
(字符串)

1、我们以第一个字符串为基准，枚举第一个字符串的每一位。
2、遍历整个字符串数组，让其他字符串的每一位同第一个字符串做比较，如果不相等或者到达了其他字符串终点，则直接返回结果。
3、否则说明最长公共前缀可以扩展，结果加上第一个字符串的当前位。

C++代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        if(strs.empty()) return res;
        string str1 = strs[0];
        for(int i = 0; i < str1.size(); i++){
            for(string str : strs){
                if(i >= str.size() || str[i] != str1[i]) return res;
            }
            res += str1[i];
        }
        return res;
    }
};

Java代码

class Solution {
    public String longestCommonPrefix(String[] strs) {

        StringBuilder res = new StringBuilder();
        for (int i = 0; i < strs[0].length(); ++i) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; ++j) {
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    return res.toString();
                }
            }
            res.append(c);
        }
        return res.toString();
    }
}

Go代码

func longestCommonPrefix(strs []string) string {
    res := ""
    if len(strs) == 0 {
        return res
    }
    str1 := strs[0]
    for i := 0;  i < len(str1); i++ {
        for j := 1; j < len(strs); j++ {
            if i >= len(strs[j]) || str1[i] != strs[j][i] {
                return res
            }
        }
        res += string(str1[i])
    }
    return res
}

欢迎加入力扣算法交流群，一起组队刷题！！！

C++代码

class Solution {
public:
    string intToRoman(int num) {
    int  valus[]={
        1000,
        900,500,400,100,
        90, 50, 40, 10,
        9,  5,  4,  1 
    };
    string luoma[]{
        "M",
        "CM","D","CD","C",
        "XC","L","XL","X",
        "IX","V","IV","I"
    };
    string res;
    for(int i = 0; i < 13; i++)
    {
        while(num >= valus[i])
        {
            num -= valus[i];
            res += luoma[i];
        }
    }
    return res;
  }
};

Java代码

class Solution {
    static String[] luoma = new String[]{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    static int[] values = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    public String intToRoman(int num) {
        String res = "";
        for(int i = 0;i < 13; i++)
        {
            while(num >= values[i])
            {
                num -= values[i];
                res += luoma[i];
            }
        }
        return res;
    }
}

Go代码

func intToRoman(num int) string {
    values := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    luoma := []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
    res := ""
    for i := 0; i < 13; i++ {
        for num >= values[i] {
            num -= values[i]
            res += luoma[i]
        }
    }
    return res
}

欢迎加入力扣算法交流群，一起组队刷题！！！